blob: 73231b1ebdbe0d2121f586c7d0500bb6393cd82c [file] [log] [blame]
Linus Torvalds1da177e2005-04-16 15:20:36 -07001/*
2 * Copyright 2000 by Hans Reiser, licensing governed by reiserfs/README
3 */
4
Linus Torvalds1da177e2005-04-16 15:20:36 -07005#include <asm/uaccess.h>
6#include <linux/string.h>
7#include <linux/time.h>
Al Virof466c6f2012-03-17 01:16:43 -04008#include "reiserfs.h"
Linus Torvalds1da177e2005-04-16 15:20:36 -07009#include <linux/buffer_head.h>
10
11/* this is one and only function that is used outside (do_balance.c) */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -070012int balance_internal(struct tree_balance *,
13 int, int, struct item_head *, struct buffer_head **);
Linus Torvalds1da177e2005-04-16 15:20:36 -070014
Jeff Mahoney098297b2014-04-23 10:00:36 -040015/*
16 * modes of internal_shift_left, internal_shift_right and
17 * internal_insert_childs
18 */
Linus Torvalds1da177e2005-04-16 15:20:36 -070019#define INTERNAL_SHIFT_FROM_S_TO_L 0
20#define INTERNAL_SHIFT_FROM_R_TO_S 1
21#define INTERNAL_SHIFT_FROM_L_TO_S 2
22#define INTERNAL_SHIFT_FROM_S_TO_R 3
23#define INTERNAL_INSERT_TO_S 4
24#define INTERNAL_INSERT_TO_L 5
25#define INTERNAL_INSERT_TO_R 6
26
Linus Torvaldsbd4c6252005-07-12 20:21:28 -070027static void internal_define_dest_src_infos(int shift_mode,
28 struct tree_balance *tb,
29 int h,
30 struct buffer_info *dest_bi,
31 struct buffer_info *src_bi,
32 int *d_key, struct buffer_head **cf)
Linus Torvalds1da177e2005-04-16 15:20:36 -070033{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -070034 memset(dest_bi, 0, sizeof(struct buffer_info));
35 memset(src_bi, 0, sizeof(struct buffer_info));
36 /* define dest, src, dest parent, dest position */
37 switch (shift_mode) {
Jeff Mahoney098297b2014-04-23 10:00:36 -040038
39 /* used in internal_shift_left */
40 case INTERNAL_SHIFT_FROM_S_TO_L:
Linus Torvaldsbd4c6252005-07-12 20:21:28 -070041 src_bi->tb = tb;
42 src_bi->bi_bh = PATH_H_PBUFFER(tb->tb_path, h);
43 src_bi->bi_parent = PATH_H_PPARENT(tb->tb_path, h);
44 src_bi->bi_position = PATH_H_POSITION(tb->tb_path, h + 1);
45 dest_bi->tb = tb;
46 dest_bi->bi_bh = tb->L[h];
47 dest_bi->bi_parent = tb->FL[h];
48 dest_bi->bi_position = get_left_neighbor_position(tb, h);
49 *d_key = tb->lkey[h];
50 *cf = tb->CFL[h];
51 break;
52 case INTERNAL_SHIFT_FROM_L_TO_S:
53 src_bi->tb = tb;
54 src_bi->bi_bh = tb->L[h];
55 src_bi->bi_parent = tb->FL[h];
56 src_bi->bi_position = get_left_neighbor_position(tb, h);
57 dest_bi->tb = tb;
58 dest_bi->bi_bh = PATH_H_PBUFFER(tb->tb_path, h);
59 dest_bi->bi_parent = PATH_H_PPARENT(tb->tb_path, h);
Jeff Mahoney098297b2014-04-23 10:00:36 -040060 /* dest position is analog of dest->b_item_order */
61 dest_bi->bi_position = PATH_H_POSITION(tb->tb_path, h + 1);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -070062 *d_key = tb->lkey[h];
63 *cf = tb->CFL[h];
64 break;
Linus Torvalds1da177e2005-04-16 15:20:36 -070065
Jeff Mahoney098297b2014-04-23 10:00:36 -040066 /* used in internal_shift_left */
67 case INTERNAL_SHIFT_FROM_R_TO_S:
Linus Torvaldsbd4c6252005-07-12 20:21:28 -070068 src_bi->tb = tb;
69 src_bi->bi_bh = tb->R[h];
70 src_bi->bi_parent = tb->FR[h];
71 src_bi->bi_position = get_right_neighbor_position(tb, h);
72 dest_bi->tb = tb;
73 dest_bi->bi_bh = PATH_H_PBUFFER(tb->tb_path, h);
74 dest_bi->bi_parent = PATH_H_PPARENT(tb->tb_path, h);
75 dest_bi->bi_position = PATH_H_POSITION(tb->tb_path, h + 1);
76 *d_key = tb->rkey[h];
77 *cf = tb->CFR[h];
78 break;
Linus Torvalds1da177e2005-04-16 15:20:36 -070079
Linus Torvaldsbd4c6252005-07-12 20:21:28 -070080 case INTERNAL_SHIFT_FROM_S_TO_R:
81 src_bi->tb = tb;
82 src_bi->bi_bh = PATH_H_PBUFFER(tb->tb_path, h);
83 src_bi->bi_parent = PATH_H_PPARENT(tb->tb_path, h);
84 src_bi->bi_position = PATH_H_POSITION(tb->tb_path, h + 1);
85 dest_bi->tb = tb;
86 dest_bi->bi_bh = tb->R[h];
87 dest_bi->bi_parent = tb->FR[h];
88 dest_bi->bi_position = get_right_neighbor_position(tb, h);
89 *d_key = tb->rkey[h];
90 *cf = tb->CFR[h];
91 break;
Linus Torvalds1da177e2005-04-16 15:20:36 -070092
Linus Torvaldsbd4c6252005-07-12 20:21:28 -070093 case INTERNAL_INSERT_TO_L:
94 dest_bi->tb = tb;
95 dest_bi->bi_bh = tb->L[h];
96 dest_bi->bi_parent = tb->FL[h];
97 dest_bi->bi_position = get_left_neighbor_position(tb, h);
98 break;
Linus Torvalds1da177e2005-04-16 15:20:36 -070099
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700100 case INTERNAL_INSERT_TO_S:
101 dest_bi->tb = tb;
102 dest_bi->bi_bh = PATH_H_PBUFFER(tb->tb_path, h);
103 dest_bi->bi_parent = PATH_H_PPARENT(tb->tb_path, h);
104 dest_bi->bi_position = PATH_H_POSITION(tb->tb_path, h + 1);
105 break;
106
107 case INTERNAL_INSERT_TO_R:
108 dest_bi->tb = tb;
109 dest_bi->bi_bh = tb->R[h];
110 dest_bi->bi_parent = tb->FR[h];
111 dest_bi->bi_position = get_right_neighbor_position(tb, h);
112 break;
113
114 default:
Jeff Mahoneyc3a9c212009-03-30 14:02:25 -0400115 reiserfs_panic(tb->tb_sb, "ibalance-1",
116 "shift type is unknown (%d)",
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700117 shift_mode);
118 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700119}
120
Jeff Mahoney098297b2014-04-23 10:00:36 -0400121/*
122 * Insert count node pointers into buffer cur before position to + 1.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700123 * Insert count items into buffer cur before position to.
124 * Items and node pointers are specified by inserted and bh respectively.
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700125 */
126static void internal_insert_childs(struct buffer_info *cur_bi,
127 int to, int count,
128 struct item_head *inserted,
129 struct buffer_head **bh)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700130{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700131 struct buffer_head *cur = cur_bi->bi_bh;
132 struct block_head *blkh;
133 int nr;
134 struct reiserfs_key *ih;
135 struct disk_child new_dc[2];
136 struct disk_child *dc;
137 int i;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700138
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700139 if (count <= 0)
140 return;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700141
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700142 blkh = B_BLK_HEAD(cur);
143 nr = blkh_nr_item(blkh);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700144
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700145 RFALSE(count > 2, "too many children (%d) are to be inserted", count);
146 RFALSE(B_FREE_SPACE(cur) < count * (KEY_SIZE + DC_SIZE),
147 "no enough free space (%d), needed %d bytes",
148 B_FREE_SPACE(cur), count * (KEY_SIZE + DC_SIZE));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700149
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700150 /* prepare space for count disk_child */
151 dc = B_N_CHILD(cur, to + 1);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700152
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700153 memmove(dc + count, dc, (nr + 1 - (to + 1)) * DC_SIZE);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700154
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700155 /* copy to_be_insert disk children */
156 for (i = 0; i < count; i++) {
Jeff Mahoneya228bf82014-04-23 10:00:42 -0400157 put_dc_size(&new_dc[i],
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700158 MAX_CHILD_SIZE(bh[i]) - B_FREE_SPACE(bh[i]));
Jeff Mahoneya228bf82014-04-23 10:00:42 -0400159 put_dc_block_number(&new_dc[i], bh[i]->b_blocknr);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700160 }
161 memcpy(dc, new_dc, DC_SIZE * count);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700162
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700163 /* prepare space for count items */
Jeff Mahoney4cf5f7a2014-04-23 10:00:35 -0400164 ih = internal_key(cur, ((to == -1) ? 0 : to));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700165
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700166 memmove(ih + count, ih,
167 (nr - to) * KEY_SIZE + (nr + 1 + count) * DC_SIZE);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700168
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700169 /* copy item headers (keys) */
170 memcpy(ih, inserted, KEY_SIZE);
171 if (count > 1)
172 memcpy(ih + 1, inserted + 1, KEY_SIZE);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700173
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700174 /* sizes, item number */
175 set_blkh_nr_item(blkh, blkh_nr_item(blkh) + count);
176 set_blkh_free_space(blkh,
177 blkh_free_space(blkh) - count * (DC_SIZE +
178 KEY_SIZE));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700179
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700180 do_balance_mark_internal_dirty(cur_bi->tb, cur, 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700181
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700182 /*&&&&&&&&&&&&&&&&&&&&&&&& */
183 check_internal(cur);
184 /*&&&&&&&&&&&&&&&&&&&&&&&& */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700185
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700186 if (cur_bi->bi_parent) {
187 struct disk_child *t_dc =
188 B_N_CHILD(cur_bi->bi_parent, cur_bi->bi_position);
189 put_dc_size(t_dc,
190 dc_size(t_dc) + (count * (DC_SIZE + KEY_SIZE)));
191 do_balance_mark_internal_dirty(cur_bi->tb, cur_bi->bi_parent,
192 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700193
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700194 /*&&&&&&&&&&&&&&&&&&&&&&&& */
195 check_internal(cur_bi->bi_parent);
196 /*&&&&&&&&&&&&&&&&&&&&&&&& */
197 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700198
199}
200
Jeff Mahoney098297b2014-04-23 10:00:36 -0400201/*
202 * Delete del_num items and node pointers from buffer cur starting from
203 * the first_i'th item and first_p'th pointers respectively.
204 */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700205static void internal_delete_pointers_items(struct buffer_info *cur_bi,
206 int first_p,
207 int first_i, int del_num)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700208{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700209 struct buffer_head *cur = cur_bi->bi_bh;
210 int nr;
211 struct block_head *blkh;
212 struct reiserfs_key *key;
213 struct disk_child *dc;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700214
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700215 RFALSE(cur == NULL, "buffer is 0");
216 RFALSE(del_num < 0,
217 "negative number of items (%d) can not be deleted", del_num);
218 RFALSE(first_p < 0 || first_p + del_num > B_NR_ITEMS(cur) + 1
219 || first_i < 0,
220 "first pointer order (%d) < 0 or "
221 "no so many pointers (%d), only (%d) or "
222 "first key order %d < 0", first_p, first_p + del_num,
223 B_NR_ITEMS(cur) + 1, first_i);
224 if (del_num == 0)
225 return;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700226
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700227 blkh = B_BLK_HEAD(cur);
228 nr = blkh_nr_item(blkh);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700229
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700230 if (first_p == 0 && del_num == nr + 1) {
231 RFALSE(first_i != 0,
232 "1st deleted key must have order 0, not %d", first_i);
233 make_empty_node(cur_bi);
234 return;
235 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700236
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700237 RFALSE(first_i + del_num > B_NR_ITEMS(cur),
238 "first_i = %d del_num = %d "
239 "no so many keys (%d) in the node (%b)(%z)",
240 first_i, del_num, first_i + del_num, cur, cur);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700241
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700242 /* deleting */
243 dc = B_N_CHILD(cur, first_p);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700244
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700245 memmove(dc, dc + del_num, (nr + 1 - first_p - del_num) * DC_SIZE);
Jeff Mahoney4cf5f7a2014-04-23 10:00:35 -0400246 key = internal_key(cur, first_i);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700247 memmove(key, key + del_num,
248 (nr - first_i - del_num) * KEY_SIZE + (nr + 1 -
249 del_num) * DC_SIZE);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700250
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700251 /* sizes, item number */
252 set_blkh_nr_item(blkh, blkh_nr_item(blkh) - del_num);
253 set_blkh_free_space(blkh,
254 blkh_free_space(blkh) +
255 (del_num * (KEY_SIZE + DC_SIZE)));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700256
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700257 do_balance_mark_internal_dirty(cur_bi->tb, cur, 0);
258 /*&&&&&&&&&&&&&&&&&&&&&&& */
259 check_internal(cur);
260 /*&&&&&&&&&&&&&&&&&&&&&&& */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700261
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700262 if (cur_bi->bi_parent) {
263 struct disk_child *t_dc;
264 t_dc = B_N_CHILD(cur_bi->bi_parent, cur_bi->bi_position);
265 put_dc_size(t_dc,
266 dc_size(t_dc) - (del_num * (KEY_SIZE + DC_SIZE)));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700267
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700268 do_balance_mark_internal_dirty(cur_bi->tb, cur_bi->bi_parent,
269 0);
270 /*&&&&&&&&&&&&&&&&&&&&&&&& */
271 check_internal(cur_bi->bi_parent);
272 /*&&&&&&&&&&&&&&&&&&&&&&&& */
273 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700274}
275
Linus Torvalds1da177e2005-04-16 15:20:36 -0700276/* delete n node pointers and items starting from given position */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700277static void internal_delete_childs(struct buffer_info *cur_bi, int from, int n)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700278{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700279 int i_from;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700280
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700281 i_from = (from == 0) ? from : from - 1;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700282
Jeff Mahoney098297b2014-04-23 10:00:36 -0400283 /*
284 * delete n pointers starting from `from' position in CUR;
285 * delete n keys starting from 'i_from' position in CUR;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700286 */
287 internal_delete_pointers_items(cur_bi, from, i_from, n);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700288}
289
Jeff Mahoney098297b2014-04-23 10:00:36 -0400290/*
291 * copy cpy_num node pointers and cpy_num - 1 items from buffer src to buffer
292 * dest
293 * last_first == FIRST_TO_LAST means that we copy first items
294 * from src to tail of dest
295 * last_first == LAST_TO_FIRST means that we copy last items
296 * from src to head of dest
Linus Torvalds1da177e2005-04-16 15:20:36 -0700297 */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700298static void internal_copy_pointers_items(struct buffer_info *dest_bi,
299 struct buffer_head *src,
300 int last_first, int cpy_num)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700301{
Jeff Mahoney098297b2014-04-23 10:00:36 -0400302 /*
303 * ATTENTION! Number of node pointers in DEST is equal to number
304 * of items in DEST as delimiting key have already inserted to
305 * buffer dest.
306 */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700307 struct buffer_head *dest = dest_bi->bi_bh;
308 int nr_dest, nr_src;
309 int dest_order, src_order;
310 struct block_head *blkh;
311 struct reiserfs_key *key;
312 struct disk_child *dc;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700313
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700314 nr_src = B_NR_ITEMS(src);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700315
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700316 RFALSE(dest == NULL || src == NULL,
317 "src (%p) or dest (%p) buffer is 0", src, dest);
318 RFALSE(last_first != FIRST_TO_LAST && last_first != LAST_TO_FIRST,
319 "invalid last_first parameter (%d)", last_first);
320 RFALSE(nr_src < cpy_num - 1,
321 "no so many items (%d) in src (%d)", cpy_num, nr_src);
322 RFALSE(cpy_num < 0, "cpy_num less than 0 (%d)", cpy_num);
323 RFALSE(cpy_num - 1 + B_NR_ITEMS(dest) > (int)MAX_NR_KEY(dest),
324 "cpy_num (%d) + item number in dest (%d) can not be > MAX_NR_KEY(%d)",
325 cpy_num, B_NR_ITEMS(dest), MAX_NR_KEY(dest));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700326
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700327 if (cpy_num == 0)
328 return;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700329
330 /* coping */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700331 blkh = B_BLK_HEAD(dest);
332 nr_dest = blkh_nr_item(blkh);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700333
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700334 /*dest_order = (last_first == LAST_TO_FIRST) ? 0 : nr_dest; */
335 /*src_order = (last_first == LAST_TO_FIRST) ? (nr_src - cpy_num + 1) : 0; */
336 (last_first == LAST_TO_FIRST) ? (dest_order = 0, src_order =
337 nr_src - cpy_num + 1) : (dest_order =
338 nr_dest,
339 src_order =
340 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700341
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700342 /* prepare space for cpy_num pointers */
343 dc = B_N_CHILD(dest, dest_order);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700344
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700345 memmove(dc + cpy_num, dc, (nr_dest - dest_order) * DC_SIZE);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700346
347 /* insert pointers */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700348 memcpy(dc, B_N_CHILD(src, src_order), DC_SIZE * cpy_num);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700349
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700350 /* prepare space for cpy_num - 1 item headers */
Jeff Mahoney4cf5f7a2014-04-23 10:00:35 -0400351 key = internal_key(dest, dest_order);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700352 memmove(key + cpy_num - 1, key,
353 KEY_SIZE * (nr_dest - dest_order) + DC_SIZE * (nr_dest +
354 cpy_num));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700355
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700356 /* insert headers */
Jeff Mahoney4cf5f7a2014-04-23 10:00:35 -0400357 memcpy(key, internal_key(src, src_order), KEY_SIZE * (cpy_num - 1));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700358
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700359 /* sizes, item number */
360 set_blkh_nr_item(blkh, blkh_nr_item(blkh) + (cpy_num - 1));
361 set_blkh_free_space(blkh,
362 blkh_free_space(blkh) - (KEY_SIZE * (cpy_num - 1) +
363 DC_SIZE * cpy_num));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700364
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700365 do_balance_mark_internal_dirty(dest_bi->tb, dest, 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700366
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700367 /*&&&&&&&&&&&&&&&&&&&&&&&& */
368 check_internal(dest);
369 /*&&&&&&&&&&&&&&&&&&&&&&&& */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700370
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700371 if (dest_bi->bi_parent) {
372 struct disk_child *t_dc;
373 t_dc = B_N_CHILD(dest_bi->bi_parent, dest_bi->bi_position);
374 put_dc_size(t_dc,
375 dc_size(t_dc) + (KEY_SIZE * (cpy_num - 1) +
376 DC_SIZE * cpy_num));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700377
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700378 do_balance_mark_internal_dirty(dest_bi->tb, dest_bi->bi_parent,
379 0);
380 /*&&&&&&&&&&&&&&&&&&&&&&&& */
381 check_internal(dest_bi->bi_parent);
382 /*&&&&&&&&&&&&&&&&&&&&&&&& */
383 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700384
385}
386
Jeff Mahoney098297b2014-04-23 10:00:36 -0400387/*
388 * Copy cpy_num node pointers and cpy_num - 1 items from buffer src to
389 * buffer dest.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700390 * Delete cpy_num - del_par items and node pointers from buffer src.
391 * last_first == FIRST_TO_LAST means, that we copy/delete first items from src.
392 * last_first == LAST_TO_FIRST means, that we copy/delete last items from src.
393 */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700394static void internal_move_pointers_items(struct buffer_info *dest_bi,
395 struct buffer_info *src_bi,
396 int last_first, int cpy_num,
397 int del_par)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700398{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700399 int first_pointer;
400 int first_item;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700401
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700402 internal_copy_pointers_items(dest_bi, src_bi->bi_bh, last_first,
403 cpy_num);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700404
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700405 if (last_first == FIRST_TO_LAST) { /* shift_left occurs */
406 first_pointer = 0;
407 first_item = 0;
Jeff Mahoney098297b2014-04-23 10:00:36 -0400408 /*
409 * delete cpy_num - del_par pointers and keys starting for
410 * pointers with first_pointer, for key - with first_item
411 */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700412 internal_delete_pointers_items(src_bi, first_pointer,
413 first_item, cpy_num - del_par);
414 } else { /* shift_right occurs */
415 int i, j;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700416
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700417 i = (cpy_num - del_par ==
418 (j =
419 B_NR_ITEMS(src_bi->bi_bh)) + 1) ? 0 : j - cpy_num +
420 del_par;
421
422 internal_delete_pointers_items(src_bi,
423 j + 1 - cpy_num + del_par, i,
424 cpy_num - del_par);
425 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700426}
427
428/* Insert n_src'th key of buffer src before n_dest'th key of buffer dest. */
Jeff Mahoney098297b2014-04-23 10:00:36 -0400429static void internal_insert_key(struct buffer_info *dest_bi,
430 /* insert key before key with n_dest number */
431 int dest_position_before,
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700432 struct buffer_head *src, int src_position)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700433{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700434 struct buffer_head *dest = dest_bi->bi_bh;
435 int nr;
436 struct block_head *blkh;
437 struct reiserfs_key *key;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700438
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700439 RFALSE(dest == NULL || src == NULL,
440 "source(%p) or dest(%p) buffer is 0", src, dest);
441 RFALSE(dest_position_before < 0 || src_position < 0,
442 "source(%d) or dest(%d) key number less than 0",
443 src_position, dest_position_before);
444 RFALSE(dest_position_before > B_NR_ITEMS(dest) ||
445 src_position >= B_NR_ITEMS(src),
446 "invalid position in dest (%d (key number %d)) or in src (%d (key number %d))",
447 dest_position_before, B_NR_ITEMS(dest),
448 src_position, B_NR_ITEMS(src));
449 RFALSE(B_FREE_SPACE(dest) < KEY_SIZE,
450 "no enough free space (%d) in dest buffer", B_FREE_SPACE(dest));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700451
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700452 blkh = B_BLK_HEAD(dest);
453 nr = blkh_nr_item(blkh);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700454
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700455 /* prepare space for inserting key */
Jeff Mahoney4cf5f7a2014-04-23 10:00:35 -0400456 key = internal_key(dest, dest_position_before);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700457 memmove(key + 1, key,
458 (nr - dest_position_before) * KEY_SIZE + (nr + 1) * DC_SIZE);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700459
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700460 /* insert key */
Jeff Mahoney4cf5f7a2014-04-23 10:00:35 -0400461 memcpy(key, internal_key(src, src_position), KEY_SIZE);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700462
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700463 /* Change dirt, free space, item number fields. */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700464
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700465 set_blkh_nr_item(blkh, blkh_nr_item(blkh) + 1);
466 set_blkh_free_space(blkh, blkh_free_space(blkh) - KEY_SIZE);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700467
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700468 do_balance_mark_internal_dirty(dest_bi->tb, dest, 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700469
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700470 if (dest_bi->bi_parent) {
471 struct disk_child *t_dc;
472 t_dc = B_N_CHILD(dest_bi->bi_parent, dest_bi->bi_position);
473 put_dc_size(t_dc, dc_size(t_dc) + KEY_SIZE);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700474
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700475 do_balance_mark_internal_dirty(dest_bi->tb, dest_bi->bi_parent,
476 0);
477 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700478}
479
Jeff Mahoney098297b2014-04-23 10:00:36 -0400480/*
481 * Insert d_key'th (delimiting) key from buffer cfl to tail of dest.
482 * Copy pointer_amount node pointers and pointer_amount - 1 items from
483 * buffer src to buffer dest.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700484 * Replace d_key'th key in buffer cfl.
485 * Delete pointer_amount items and node pointers from buffer src.
486 */
487/* this can be invoked both to shift from S to L and from R to S */
Jeff Mahoney098297b2014-04-23 10:00:36 -0400488static void internal_shift_left(
489 /*
490 * INTERNAL_FROM_S_TO_L | INTERNAL_FROM_R_TO_S
491 */
492 int mode,
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700493 struct tree_balance *tb,
494 int h, int pointer_amount)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700495{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700496 struct buffer_info dest_bi, src_bi;
497 struct buffer_head *cf;
498 int d_key_position;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700499
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700500 internal_define_dest_src_infos(mode, tb, h, &dest_bi, &src_bi,
501 &d_key_position, &cf);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700502
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700503 /*printk("pointer_amount = %d\n",pointer_amount); */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700504
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700505 if (pointer_amount) {
Jeff Mahoney098297b2014-04-23 10:00:36 -0400506 /*
507 * insert delimiting key from common father of dest and
508 * src to node dest into position B_NR_ITEM(dest)
509 */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700510 internal_insert_key(&dest_bi, B_NR_ITEMS(dest_bi.bi_bh), cf,
511 d_key_position);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700512
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700513 if (B_NR_ITEMS(src_bi.bi_bh) == pointer_amount - 1) {
514 if (src_bi.bi_position /*src->b_item_order */ == 0)
515 replace_key(tb, cf, d_key_position,
516 src_bi.
517 bi_parent /*src->b_parent */ , 0);
518 } else
519 replace_key(tb, cf, d_key_position, src_bi.bi_bh,
520 pointer_amount - 1);
521 }
522 /* last parameter is del_parameter */
523 internal_move_pointers_items(&dest_bi, &src_bi, FIRST_TO_LAST,
524 pointer_amount, 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700525
526}
527
Jeff Mahoney098297b2014-04-23 10:00:36 -0400528/*
529 * Insert delimiting key to L[h].
Linus Torvalds1da177e2005-04-16 15:20:36 -0700530 * Copy n node pointers and n - 1 items from buffer S[h] to L[h].
531 * Delete n - 1 items and node pointers from buffer S[h].
532 */
533/* it always shifts from S[h] to L[h] */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700534static void internal_shift1_left(struct tree_balance *tb,
535 int h, int pointer_amount)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700536{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700537 struct buffer_info dest_bi, src_bi;
538 struct buffer_head *cf;
539 int d_key_position;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700540
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700541 internal_define_dest_src_infos(INTERNAL_SHIFT_FROM_S_TO_L, tb, h,
542 &dest_bi, &src_bi, &d_key_position, &cf);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700543
Jeff Mahoney098297b2014-04-23 10:00:36 -0400544 /* insert lkey[h]-th key from CFL[h] to left neighbor L[h] */
545 if (pointer_amount > 0)
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700546 internal_insert_key(&dest_bi, B_NR_ITEMS(dest_bi.bi_bh), cf,
547 d_key_position);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700548
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700549 /* last parameter is del_parameter */
550 internal_move_pointers_items(&dest_bi, &src_bi, FIRST_TO_LAST,
551 pointer_amount, 1);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700552}
553
Jeff Mahoney098297b2014-04-23 10:00:36 -0400554/*
555 * Insert d_key'th (delimiting) key from buffer cfr to head of dest.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700556 * Copy n node pointers and n - 1 items from buffer src to buffer dest.
557 * Replace d_key'th key in buffer cfr.
558 * Delete n items and node pointers from buffer src.
559 */
Jeff Mahoney098297b2014-04-23 10:00:36 -0400560static void internal_shift_right(
561 /*
562 * INTERNAL_FROM_S_TO_R | INTERNAL_FROM_L_TO_S
563 */
564 int mode,
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700565 struct tree_balance *tb,
566 int h, int pointer_amount)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700567{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700568 struct buffer_info dest_bi, src_bi;
569 struct buffer_head *cf;
570 int d_key_position;
571 int nr;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700572
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700573 internal_define_dest_src_infos(mode, tb, h, &dest_bi, &src_bi,
574 &d_key_position, &cf);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700575
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700576 nr = B_NR_ITEMS(src_bi.bi_bh);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700577
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700578 if (pointer_amount > 0) {
Jeff Mahoney098297b2014-04-23 10:00:36 -0400579 /*
580 * insert delimiting key from common father of dest
581 * and src to dest node into position 0
582 */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700583 internal_insert_key(&dest_bi, 0, cf, d_key_position);
584 if (nr == pointer_amount - 1) {
585 RFALSE(src_bi.bi_bh != PATH_H_PBUFFER(tb->tb_path, h) /*tb->S[h] */ ||
586 dest_bi.bi_bh != tb->R[h],
587 "src (%p) must be == tb->S[h](%p) when it disappears",
588 src_bi.bi_bh, PATH_H_PBUFFER(tb->tb_path, h));
589 /* when S[h] disappers replace left delemiting key as well */
590 if (tb->CFL[h])
591 replace_key(tb, cf, d_key_position, tb->CFL[h],
592 tb->lkey[h]);
593 } else
594 replace_key(tb, cf, d_key_position, src_bi.bi_bh,
595 nr - pointer_amount);
596 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700597
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700598 /* last parameter is del_parameter */
599 internal_move_pointers_items(&dest_bi, &src_bi, LAST_TO_FIRST,
600 pointer_amount, 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700601}
602
Jeff Mahoney098297b2014-04-23 10:00:36 -0400603/*
604 * Insert delimiting key to R[h].
Linus Torvalds1da177e2005-04-16 15:20:36 -0700605 * Copy n node pointers and n - 1 items from buffer S[h] to R[h].
606 * Delete n - 1 items and node pointers from buffer S[h].
607 */
608/* it always shift from S[h] to R[h] */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700609static void internal_shift1_right(struct tree_balance *tb,
610 int h, int pointer_amount)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700611{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700612 struct buffer_info dest_bi, src_bi;
613 struct buffer_head *cf;
614 int d_key_position;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700615
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700616 internal_define_dest_src_infos(INTERNAL_SHIFT_FROM_S_TO_R, tb, h,
617 &dest_bi, &src_bi, &d_key_position, &cf);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700618
Jeff Mahoney098297b2014-04-23 10:00:36 -0400619 /* insert rkey from CFR[h] to right neighbor R[h] */
620 if (pointer_amount > 0)
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700621 internal_insert_key(&dest_bi, 0, cf, d_key_position);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700622
623 /* last parameter is del_parameter */
624 internal_move_pointers_items(&dest_bi, &src_bi, LAST_TO_FIRST,
625 pointer_amount, 1);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700626}
627
Jeff Mahoney098297b2014-04-23 10:00:36 -0400628/*
629 * Delete insert_num node pointers together with their left items
630 * and balance current node.
631 */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700632static void balance_internal_when_delete(struct tree_balance *tb,
633 int h, int child_pos)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700634{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700635 int insert_num;
636 int n;
637 struct buffer_head *tbSh = PATH_H_PBUFFER(tb->tb_path, h);
638 struct buffer_info bi;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700639
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700640 insert_num = tb->insert_size[h] / ((int)(DC_SIZE + KEY_SIZE));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700641
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700642 /* delete child-node-pointer(s) together with their left item(s) */
643 bi.tb = tb;
644 bi.bi_bh = tbSh;
645 bi.bi_parent = PATH_H_PPARENT(tb->tb_path, h);
646 bi.bi_position = PATH_H_POSITION(tb->tb_path, h + 1);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700647
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700648 internal_delete_childs(&bi, child_pos, -insert_num);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700649
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700650 RFALSE(tb->blknum[h] > 1,
651 "tb->blknum[%d]=%d when insert_size < 0", h, tb->blknum[h]);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700652
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700653 n = B_NR_ITEMS(tbSh);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700654
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700655 if (tb->lnum[h] == 0 && tb->rnum[h] == 0) {
656 if (tb->blknum[h] == 0) {
657 /* node S[h] (root of the tree) is empty now */
658 struct buffer_head *new_root;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700659
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700660 RFALSE(n
661 || B_FREE_SPACE(tbSh) !=
662 MAX_CHILD_SIZE(tbSh) - DC_SIZE,
663 "buffer must have only 0 keys (%d)", n);
664 RFALSE(bi.bi_parent, "root has parent (%p)",
665 bi.bi_parent);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700666
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700667 /* choose a new root */
668 if (!tb->L[h - 1] || !B_NR_ITEMS(tb->L[h - 1]))
669 new_root = tb->R[h - 1];
670 else
671 new_root = tb->L[h - 1];
Jeff Mahoney098297b2014-04-23 10:00:36 -0400672 /*
673 * switch super block's tree root block
674 * number to the new value */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700675 PUT_SB_ROOT_BLOCK(tb->tb_sb, new_root->b_blocknr);
Jeff Mahoney098297b2014-04-23 10:00:36 -0400676 /*REISERFS_SB(tb->tb_sb)->s_rs->s_tree_height --; */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700677 PUT_SB_TREE_HEIGHT(tb->tb_sb,
678 SB_TREE_HEIGHT(tb->tb_sb) - 1);
679
680 do_balance_mark_sb_dirty(tb,
681 REISERFS_SB(tb->tb_sb)->s_sbh,
682 1);
683 /*&&&&&&&&&&&&&&&&&&&&&& */
Jeff Mahoney098297b2014-04-23 10:00:36 -0400684 /* use check_internal if new root is an internal node */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700685 if (h > 1)
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700686 check_internal(new_root);
687 /*&&&&&&&&&&&&&&&&&&&&&& */
688
689 /* do what is needed for buffer thrown from tree */
690 reiserfs_invalidate_buffer(tb, tbSh);
691 return;
692 }
693 return;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700694 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700695
Jeff Mahoney098297b2014-04-23 10:00:36 -0400696 /* join S[h] with L[h] */
697 if (tb->L[h] && tb->lnum[h] == -B_NR_ITEMS(tb->L[h]) - 1) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700698
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700699 RFALSE(tb->rnum[h] != 0,
700 "invalid tb->rnum[%d]==%d when joining S[h] with L[h]",
701 h, tb->rnum[h]);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700702
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700703 internal_shift_left(INTERNAL_SHIFT_FROM_S_TO_L, tb, h, n + 1);
704 reiserfs_invalidate_buffer(tb, tbSh);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700705
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700706 return;
707 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700708
Jeff Mahoney098297b2014-04-23 10:00:36 -0400709 /* join S[h] with R[h] */
710 if (tb->R[h] && tb->rnum[h] == -B_NR_ITEMS(tb->R[h]) - 1) {
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700711 RFALSE(tb->lnum[h] != 0,
712 "invalid tb->lnum[%d]==%d when joining S[h] with R[h]",
713 h, tb->lnum[h]);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700714
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700715 internal_shift_right(INTERNAL_SHIFT_FROM_S_TO_R, tb, h, n + 1);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700716
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700717 reiserfs_invalidate_buffer(tb, tbSh);
718 return;
719 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700720
Jeff Mahoney098297b2014-04-23 10:00:36 -0400721 /* borrow from left neighbor L[h] */
722 if (tb->lnum[h] < 0) {
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700723 RFALSE(tb->rnum[h] != 0,
724 "wrong tb->rnum[%d]==%d when borrow from L[h]", h,
725 tb->rnum[h]);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700726 internal_shift_right(INTERNAL_SHIFT_FROM_L_TO_S, tb, h,
727 -tb->lnum[h]);
728 return;
729 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700730
Jeff Mahoney098297b2014-04-23 10:00:36 -0400731 /* borrow from right neighbor R[h] */
732 if (tb->rnum[h] < 0) {
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700733 RFALSE(tb->lnum[h] != 0,
734 "invalid tb->lnum[%d]==%d when borrow from R[h]",
735 h, tb->lnum[h]);
736 internal_shift_left(INTERNAL_SHIFT_FROM_R_TO_S, tb, h, -tb->rnum[h]); /*tb->S[h], tb->CFR[h], tb->rkey[h], tb->R[h], -tb->rnum[h]); */
737 return;
738 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700739
Jeff Mahoney098297b2014-04-23 10:00:36 -0400740 /* split S[h] into two parts and put them into neighbors */
741 if (tb->lnum[h] > 0) {
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700742 RFALSE(tb->rnum[h] == 0 || tb->lnum[h] + tb->rnum[h] != n + 1,
743 "invalid tb->lnum[%d]==%d or tb->rnum[%d]==%d when S[h](item number == %d) is split between them",
744 h, tb->lnum[h], h, tb->rnum[h], n);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700745
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700746 internal_shift_left(INTERNAL_SHIFT_FROM_S_TO_L, tb, h, tb->lnum[h]); /*tb->L[h], tb->CFL[h], tb->lkey[h], tb->S[h], tb->lnum[h]); */
747 internal_shift_right(INTERNAL_SHIFT_FROM_S_TO_R, tb, h,
748 tb->rnum[h]);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700749
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700750 reiserfs_invalidate_buffer(tb, tbSh);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700751
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700752 return;
753 }
Jeff Mahoneyc3a9c212009-03-30 14:02:25 -0400754 reiserfs_panic(tb->tb_sb, "ibalance-2",
755 "unexpected tb->lnum[%d]==%d or tb->rnum[%d]==%d",
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700756 h, tb->lnum[h], h, tb->rnum[h]);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700757}
758
Linus Torvalds1da177e2005-04-16 15:20:36 -0700759/* Replace delimiting key of buffers L[h] and S[h] by the given key.*/
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700760static void replace_lkey(struct tree_balance *tb, int h, struct item_head *key)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700761{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700762 RFALSE(tb->L[h] == NULL || tb->CFL[h] == NULL,
763 "L[h](%p) and CFL[h](%p) must exist in replace_lkey",
764 tb->L[h], tb->CFL[h]);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700765
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700766 if (B_NR_ITEMS(PATH_H_PBUFFER(tb->tb_path, h)) == 0)
767 return;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700768
Jeff Mahoney4cf5f7a2014-04-23 10:00:35 -0400769 memcpy(internal_key(tb->CFL[h], tb->lkey[h]), key, KEY_SIZE);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700770
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700771 do_balance_mark_internal_dirty(tb, tb->CFL[h], 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700772}
773
Linus Torvalds1da177e2005-04-16 15:20:36 -0700774/* Replace delimiting key of buffers S[h] and R[h] by the given key.*/
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700775static void replace_rkey(struct tree_balance *tb, int h, struct item_head *key)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700776{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700777 RFALSE(tb->R[h] == NULL || tb->CFR[h] == NULL,
778 "R[h](%p) and CFR[h](%p) must exist in replace_rkey",
779 tb->R[h], tb->CFR[h]);
780 RFALSE(B_NR_ITEMS(tb->R[h]) == 0,
781 "R[h] can not be empty if it exists (item number=%d)",
782 B_NR_ITEMS(tb->R[h]));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700783
Jeff Mahoney4cf5f7a2014-04-23 10:00:35 -0400784 memcpy(internal_key(tb->CFR[h], tb->rkey[h]), key, KEY_SIZE);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700785
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700786 do_balance_mark_internal_dirty(tb, tb->CFR[h], 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700787}
788
Jeff Mahoney098297b2014-04-23 10:00:36 -0400789
790/*
791 * if inserting/pasting {
792 * child_pos is the position of the node-pointer in S[h] that
793 * pointed to S[h-1] before balancing of the h-1 level;
794 * this means that new pointers and items must be inserted AFTER
795 * child_pos
796 * } else {
797 * it is the position of the leftmost pointer that must be deleted
798 * (together with its corresponding key to the left of the pointer)
799 * as a result of the previous level's balancing.
800 * }
801 */
802
803int balance_internal(struct tree_balance *tb,
804 int h, /* level of the tree */
805 int child_pos,
806 /* key for insertion on higher level */
807 struct item_head *insert_key,
808 /* node for insertion on higher level */
809 struct buffer_head **insert_ptr)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700810{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700811 struct buffer_head *tbSh = PATH_H_PBUFFER(tb->tb_path, h);
812 struct buffer_info bi;
Jeff Mahoney098297b2014-04-23 10:00:36 -0400813
814 /*
815 * we return this: it is 0 if there is no S[h],
816 * else it is tb->S[h]->b_item_order
817 */
818 int order;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700819 int insert_num, n, k;
820 struct buffer_head *S_new;
821 struct item_head new_insert_key;
822 struct buffer_head *new_insert_ptr = NULL;
823 struct item_head *new_insert_key_addr = insert_key;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700824
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700825 RFALSE(h < 1, "h (%d) can not be < 1 on internal level", h);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700826
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700827 PROC_INFO_INC(tb->tb_sb, balance_at[h]);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700828
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700829 order =
830 (tbSh) ? PATH_H_POSITION(tb->tb_path,
831 h + 1) /*tb->S[h]->b_item_order */ : 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700832
Jeff Mahoney098297b2014-04-23 10:00:36 -0400833 /*
834 * Using insert_size[h] calculate the number insert_num of items
835 * that must be inserted to or deleted from S[h].
836 */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700837 insert_num = tb->insert_size[h] / ((int)(KEY_SIZE + DC_SIZE));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700838
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700839 /* Check whether insert_num is proper * */
840 RFALSE(insert_num < -2 || insert_num > 2,
841 "incorrect number of items inserted to the internal node (%d)",
842 insert_num);
843 RFALSE(h > 1 && (insert_num > 1 || insert_num < -1),
844 "incorrect number of items (%d) inserted to the internal node on a level (h=%d) higher than last internal level",
845 insert_num, h);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700846
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700847 /* Make balance in case insert_num < 0 */
848 if (insert_num < 0) {
849 balance_internal_when_delete(tb, h, child_pos);
850 return order;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700851 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700852
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700853 k = 0;
854 if (tb->lnum[h] > 0) {
Jeff Mahoney098297b2014-04-23 10:00:36 -0400855 /*
856 * shift lnum[h] items from S[h] to the left neighbor L[h].
857 * check how many of new items fall into L[h] or CFL[h] after
858 * shifting
859 */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700860 n = B_NR_ITEMS(tb->L[h]); /* number of items in L[h] */
861 if (tb->lnum[h] <= child_pos) {
862 /* new items don't fall into L[h] or CFL[h] */
863 internal_shift_left(INTERNAL_SHIFT_FROM_S_TO_L, tb, h,
864 tb->lnum[h]);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700865 child_pos -= tb->lnum[h];
866 } else if (tb->lnum[h] > child_pos + insert_num) {
867 /* all new items fall into L[h] */
868 internal_shift_left(INTERNAL_SHIFT_FROM_S_TO_L, tb, h,
869 tb->lnum[h] - insert_num);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700870 /* insert insert_num keys and node-pointers into L[h] */
871 bi.tb = tb;
872 bi.bi_bh = tb->L[h];
873 bi.bi_parent = tb->FL[h];
874 bi.bi_position = get_left_neighbor_position(tb, h);
875 internal_insert_childs(&bi,
876 /*tb->L[h], tb->S[h-1]->b_next */
877 n + child_pos + 1,
878 insert_num, insert_key,
879 insert_ptr);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700880
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700881 insert_num = 0;
882 } else {
883 struct disk_child *dc;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700884
Jeff Mahoney098297b2014-04-23 10:00:36 -0400885 /*
886 * some items fall into L[h] or CFL[h],
887 * but some don't fall
888 */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700889 internal_shift1_left(tb, h, child_pos + 1);
890 /* calculate number of new items that fall into L[h] */
891 k = tb->lnum[h] - child_pos - 1;
892 bi.tb = tb;
893 bi.bi_bh = tb->L[h];
894 bi.bi_parent = tb->FL[h];
895 bi.bi_position = get_left_neighbor_position(tb, h);
896 internal_insert_childs(&bi,
897 /*tb->L[h], tb->S[h-1]->b_next, */
898 n + child_pos + 1, k,
899 insert_key, insert_ptr);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700900
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700901 replace_lkey(tb, h, insert_key + k);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700902
Jeff Mahoney098297b2014-04-23 10:00:36 -0400903 /*
904 * replace the first node-ptr in S[h] by
905 * node-ptr to insert_ptr[k]
906 */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700907 dc = B_N_CHILD(tbSh, 0);
908 put_dc_size(dc,
909 MAX_CHILD_SIZE(insert_ptr[k]) -
910 B_FREE_SPACE(insert_ptr[k]));
911 put_dc_block_number(dc, insert_ptr[k]->b_blocknr);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700912
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700913 do_balance_mark_internal_dirty(tb, tbSh, 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700914
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700915 k++;
916 insert_key += k;
917 insert_ptr += k;
918 insert_num -= k;
919 child_pos = 0;
920 }
921 }
922 /* tb->lnum[h] > 0 */
923 if (tb->rnum[h] > 0) {
924 /*shift rnum[h] items from S[h] to the right neighbor R[h] */
Jeff Mahoney098297b2014-04-23 10:00:36 -0400925 /*
926 * check how many of new items fall into R or CFR
927 * after shifting
928 */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700929 n = B_NR_ITEMS(tbSh); /* number of items in S[h] */
930 if (n - tb->rnum[h] >= child_pos)
931 /* new items fall into S[h] */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700932 internal_shift_right(INTERNAL_SHIFT_FROM_S_TO_R, tb, h,
933 tb->rnum[h]);
934 else if (n + insert_num - tb->rnum[h] < child_pos) {
935 /* all new items fall into R[h] */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700936 internal_shift_right(INTERNAL_SHIFT_FROM_S_TO_R, tb, h,
937 tb->rnum[h] - insert_num);
938
939 /* insert insert_num keys and node-pointers into R[h] */
940 bi.tb = tb;
941 bi.bi_bh = tb->R[h];
942 bi.bi_parent = tb->FR[h];
943 bi.bi_position = get_right_neighbor_position(tb, h);
944 internal_insert_childs(&bi,
945 /*tb->R[h],tb->S[h-1]->b_next */
946 child_pos - n - insert_num +
947 tb->rnum[h] - 1,
948 insert_num, insert_key,
949 insert_ptr);
950 insert_num = 0;
951 } else {
952 struct disk_child *dc;
953
954 /* one of the items falls into CFR[h] */
955 internal_shift1_right(tb, h, n - child_pos + 1);
956 /* calculate number of new items that fall into R[h] */
957 k = tb->rnum[h] - n + child_pos - 1;
958 bi.tb = tb;
959 bi.bi_bh = tb->R[h];
960 bi.bi_parent = tb->FR[h];
961 bi.bi_position = get_right_neighbor_position(tb, h);
962 internal_insert_childs(&bi,
963 /*tb->R[h], tb->R[h]->b_child, */
964 0, k, insert_key + 1,
965 insert_ptr + 1);
966
967 replace_rkey(tb, h, insert_key + insert_num - k - 1);
968
Jeff Mahoney098297b2014-04-23 10:00:36 -0400969 /*
970 * replace the first node-ptr in R[h] by
971 * node-ptr insert_ptr[insert_num-k-1]
972 */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700973 dc = B_N_CHILD(tb->R[h], 0);
974 put_dc_size(dc,
975 MAX_CHILD_SIZE(insert_ptr
976 [insert_num - k - 1]) -
977 B_FREE_SPACE(insert_ptr
978 [insert_num - k - 1]));
979 put_dc_block_number(dc,
980 insert_ptr[insert_num - k -
981 1]->b_blocknr);
982
983 do_balance_mark_internal_dirty(tb, tb->R[h], 0);
984
985 insert_num -= (k + 1);
986 }
987 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700988
Jeff Mahoney098297b2014-04-23 10:00:36 -0400989 /** Fill new node that appears instead of S[h] **/
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700990 RFALSE(tb->blknum[h] > 2, "blknum can not be > 2 for internal level");
991 RFALSE(tb->blknum[h] < 0, "blknum can not be < 0");
Linus Torvalds1da177e2005-04-16 15:20:36 -0700992
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700993 if (!tb->blknum[h]) { /* node S[h] is empty now */
994 RFALSE(!tbSh, "S[h] is equal NULL");
Linus Torvalds1da177e2005-04-16 15:20:36 -0700995
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700996 /* do what is needed for buffer thrown from tree */
997 reiserfs_invalidate_buffer(tb, tbSh);
998 return order;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700999 }
1000
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001001 if (!tbSh) {
1002 /* create new root */
1003 struct disk_child *dc;
1004 struct buffer_head *tbSh_1 = PATH_H_PBUFFER(tb->tb_path, h - 1);
1005 struct block_head *blkh;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001006
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001007 if (tb->blknum[h] != 1)
Jeff Mahoneyc3a9c212009-03-30 14:02:25 -04001008 reiserfs_panic(NULL, "ibalance-3", "One new node "
1009 "required for creating the new root");
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001010 /* S[h] = empty buffer from the list FEB. */
1011 tbSh = get_FEB(tb);
1012 blkh = B_BLK_HEAD(tbSh);
1013 set_blkh_level(blkh, h + 1);
1014
1015 /* Put the unique node-pointer to S[h] that points to S[h-1]. */
1016
1017 dc = B_N_CHILD(tbSh, 0);
1018 put_dc_block_number(dc, tbSh_1->b_blocknr);
1019 put_dc_size(dc,
1020 (MAX_CHILD_SIZE(tbSh_1) - B_FREE_SPACE(tbSh_1)));
1021
1022 tb->insert_size[h] -= DC_SIZE;
1023 set_blkh_free_space(blkh, blkh_free_space(blkh) - DC_SIZE);
1024
1025 do_balance_mark_internal_dirty(tb, tbSh, 0);
1026
1027 /*&&&&&&&&&&&&&&&&&&&&&&&& */
1028 check_internal(tbSh);
1029 /*&&&&&&&&&&&&&&&&&&&&&&&& */
1030
1031 /* put new root into path structure */
1032 PATH_OFFSET_PBUFFER(tb->tb_path, ILLEGAL_PATH_ELEMENT_OFFSET) =
1033 tbSh;
1034
1035 /* Change root in structure super block. */
1036 PUT_SB_ROOT_BLOCK(tb->tb_sb, tbSh->b_blocknr);
1037 PUT_SB_TREE_HEIGHT(tb->tb_sb, SB_TREE_HEIGHT(tb->tb_sb) + 1);
1038 do_balance_mark_sb_dirty(tb, REISERFS_SB(tb->tb_sb)->s_sbh, 1);
1039 }
1040
1041 if (tb->blknum[h] == 2) {
1042 int snum;
1043 struct buffer_info dest_bi, src_bi;
1044
1045 /* S_new = free buffer from list FEB */
1046 S_new = get_FEB(tb);
1047
1048 set_blkh_level(B_BLK_HEAD(S_new), h + 1);
1049
1050 dest_bi.tb = tb;
1051 dest_bi.bi_bh = S_new;
1052 dest_bi.bi_parent = NULL;
1053 dest_bi.bi_position = 0;
1054 src_bi.tb = tb;
1055 src_bi.bi_bh = tbSh;
1056 src_bi.bi_parent = PATH_H_PPARENT(tb->tb_path, h);
1057 src_bi.bi_position = PATH_H_POSITION(tb->tb_path, h + 1);
1058
1059 n = B_NR_ITEMS(tbSh); /* number of items in S[h] */
1060 snum = (insert_num + n + 1) / 2;
1061 if (n - snum >= child_pos) {
1062 /* new items don't fall into S_new */
1063 /* store the delimiting key for the next level */
1064 /* new_insert_key = (n - snum)'th key in S[h] */
Jeff Mahoney4cf5f7a2014-04-23 10:00:35 -04001065 memcpy(&new_insert_key, internal_key(tbSh, n - snum),
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001066 KEY_SIZE);
1067 /* last parameter is del_par */
1068 internal_move_pointers_items(&dest_bi, &src_bi,
1069 LAST_TO_FIRST, snum, 0);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001070 } else if (n + insert_num - snum < child_pos) {
1071 /* all new items fall into S_new */
1072 /* store the delimiting key for the next level */
Jeff Mahoney098297b2014-04-23 10:00:36 -04001073 /*
1074 * new_insert_key = (n + insert_item - snum)'th
1075 * key in S[h]
1076 */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001077 memcpy(&new_insert_key,
Jeff Mahoney4cf5f7a2014-04-23 10:00:35 -04001078 internal_key(tbSh, n + insert_num - snum),
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001079 KEY_SIZE);
1080 /* last parameter is del_par */
1081 internal_move_pointers_items(&dest_bi, &src_bi,
1082 LAST_TO_FIRST,
1083 snum - insert_num, 0);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001084
Jeff Mahoney098297b2014-04-23 10:00:36 -04001085 /*
1086 * insert insert_num keys and node-pointers
1087 * into S_new
1088 */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001089 internal_insert_childs(&dest_bi,
1090 /*S_new,tb->S[h-1]->b_next, */
1091 child_pos - n - insert_num +
1092 snum - 1,
1093 insert_num, insert_key,
1094 insert_ptr);
1095
1096 insert_num = 0;
1097 } else {
1098 struct disk_child *dc;
1099
1100 /* some items fall into S_new, but some don't fall */
1101 /* last parameter is del_par */
1102 internal_move_pointers_items(&dest_bi, &src_bi,
1103 LAST_TO_FIRST,
1104 n - child_pos + 1, 1);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001105 /* calculate number of new items that fall into S_new */
1106 k = snum - n + child_pos - 1;
1107
1108 internal_insert_childs(&dest_bi, /*S_new, */ 0, k,
1109 insert_key + 1, insert_ptr + 1);
1110
1111 /* new_insert_key = insert_key[insert_num - k - 1] */
1112 memcpy(&new_insert_key, insert_key + insert_num - k - 1,
1113 KEY_SIZE);
Jeff Mahoney098297b2014-04-23 10:00:36 -04001114 /*
1115 * replace first node-ptr in S_new by node-ptr
1116 * to insert_ptr[insert_num-k-1]
1117 */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001118
1119 dc = B_N_CHILD(S_new, 0);
1120 put_dc_size(dc,
1121 (MAX_CHILD_SIZE
1122 (insert_ptr[insert_num - k - 1]) -
1123 B_FREE_SPACE(insert_ptr
1124 [insert_num - k - 1])));
1125 put_dc_block_number(dc,
1126 insert_ptr[insert_num - k -
1127 1]->b_blocknr);
1128
1129 do_balance_mark_internal_dirty(tb, S_new, 0);
1130
1131 insert_num -= (k + 1);
1132 }
1133 /* new_insert_ptr = node_pointer to S_new */
1134 new_insert_ptr = S_new;
1135
1136 RFALSE(!buffer_journaled(S_new) || buffer_journal_dirty(S_new)
1137 || buffer_dirty(S_new), "cm-00001: bad S_new (%b)",
1138 S_new);
1139
Jeff Mahoney098297b2014-04-23 10:00:36 -04001140 /* S_new is released in unfix_nodes */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001141 }
1142
1143 n = B_NR_ITEMS(tbSh); /*number of items in S[h] */
1144
1145 if (0 <= child_pos && child_pos <= n && insert_num > 0) {
1146 bi.tb = tb;
1147 bi.bi_bh = tbSh;
1148 bi.bi_parent = PATH_H_PPARENT(tb->tb_path, h);
1149 bi.bi_position = PATH_H_POSITION(tb->tb_path, h + 1);
1150 internal_insert_childs(&bi, /*tbSh, */
1151 /* ( tb->S[h-1]->b_parent == tb->S[h] ) ? tb->S[h-1]->b_next : tb->S[h]->b_child->b_next, */
1152 child_pos, insert_num, insert_key,
1153 insert_ptr);
1154 }
1155
1156 memcpy(new_insert_key_addr, &new_insert_key, KEY_SIZE);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001157 insert_ptr[0] = new_insert_ptr;
1158
1159 return order;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001160}