Commit | Line | Data |
---|---|---|
1da177e4 LT |
1 | /* |
2 | * Copyright 2000 by Hans Reiser, licensing governed by reiserfs/README | |
3 | */ | |
4 | ||
17093991 | 5 | #include <linux/uaccess.h> |
1da177e4 LT |
6 | #include <linux/string.h> |
7 | #include <linux/time.h> | |
f466c6fd | 8 | #include "reiserfs.h" |
1da177e4 LT |
9 | #include <linux/buffer_head.h> |
10 | ||
11 | /* this is one and only function that is used outside (do_balance.c) */ | |
bd4c625c LT |
12 | int balance_internal(struct tree_balance *, |
13 | int, int, struct item_head *, struct buffer_head **); | |
1da177e4 | 14 | |
098297b2 JM |
15 | /* |
16 | * modes of internal_shift_left, internal_shift_right and | |
17 | * internal_insert_childs | |
18 | */ | |
1da177e4 LT |
19 | #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 | ||
bd4c625c LT |
27 | static 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) | |
1da177e4 | 33 | { |
bd4c625c LT |
34 | 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) { | |
098297b2 JM |
38 | |
39 | /* used in internal_shift_left */ | |
40 | case INTERNAL_SHIFT_FROM_S_TO_L: | |
bd4c625c LT |
41 | 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); | |
098297b2 JM |
60 | /* dest position is analog of dest->b_item_order */ |
61 | dest_bi->bi_position = PATH_H_POSITION(tb->tb_path, h + 1); | |
bd4c625c LT |
62 | *d_key = tb->lkey[h]; |
63 | *cf = tb->CFL[h]; | |
64 | break; | |
65 | ||
098297b2 JM |
66 | /* used in internal_shift_left */ |
67 | case INTERNAL_SHIFT_FROM_R_TO_S: | |
bd4c625c LT |
68 | 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; | |
79 | ||
80 | 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; | |
92 | ||
93 | 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; | |
99 | ||
100 | 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: | |
c3a9c210 JM |
115 | reiserfs_panic(tb->tb_sb, "ibalance-1", |
116 | "shift type is unknown (%d)", | |
bd4c625c LT |
117 | shift_mode); |
118 | } | |
1da177e4 LT |
119 | } |
120 | ||
098297b2 JM |
121 | /* |
122 | * Insert count node pointers into buffer cur before position to + 1. | |
1da177e4 LT |
123 | * Insert count items into buffer cur before position to. |
124 | * Items and node pointers are specified by inserted and bh respectively. | |
bd4c625c LT |
125 | */ |
126 | static void internal_insert_childs(struct buffer_info *cur_bi, | |
127 | int to, int count, | |
128 | struct item_head *inserted, | |
129 | struct buffer_head **bh) | |
1da177e4 | 130 | { |
bd4c625c LT |
131 | 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; | |
138 | ||
139 | if (count <= 0) | |
140 | return; | |
141 | ||
142 | blkh = B_BLK_HEAD(cur); | |
143 | nr = blkh_nr_item(blkh); | |
144 | ||
145 | 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)); | |
149 | ||
150 | /* prepare space for count disk_child */ | |
151 | dc = B_N_CHILD(cur, to + 1); | |
152 | ||
153 | memmove(dc + count, dc, (nr + 1 - (to + 1)) * DC_SIZE); | |
154 | ||
155 | /* copy to_be_insert disk children */ | |
156 | for (i = 0; i < count; i++) { | |
a228bf8f | 157 | put_dc_size(&new_dc[i], |
bd4c625c | 158 | MAX_CHILD_SIZE(bh[i]) - B_FREE_SPACE(bh[i])); |
a228bf8f | 159 | put_dc_block_number(&new_dc[i], bh[i]->b_blocknr); |
bd4c625c LT |
160 | } |
161 | memcpy(dc, new_dc, DC_SIZE * count); | |
162 | ||
163 | /* prepare space for count items */ | |
4cf5f7ad | 164 | ih = internal_key(cur, ((to == -1) ? 0 : to)); |
bd4c625c LT |
165 | |
166 | memmove(ih + count, ih, | |
167 | (nr - to) * KEY_SIZE + (nr + 1 + count) * DC_SIZE); | |
168 | ||
169 | /* copy item headers (keys) */ | |
170 | memcpy(ih, inserted, KEY_SIZE); | |
171 | if (count > 1) | |
172 | memcpy(ih + 1, inserted + 1, KEY_SIZE); | |
173 | ||
174 | /* 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)); | |
179 | ||
180 | do_balance_mark_internal_dirty(cur_bi->tb, cur, 0); | |
181 | ||
182 | /*&&&&&&&&&&&&&&&&&&&&&&&& */ | |
183 | check_internal(cur); | |
184 | /*&&&&&&&&&&&&&&&&&&&&&&&& */ | |
185 | ||
186 | 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); | |
193 | ||
194 | /*&&&&&&&&&&&&&&&&&&&&&&&& */ | |
195 | check_internal(cur_bi->bi_parent); | |
196 | /*&&&&&&&&&&&&&&&&&&&&&&&& */ | |
197 | } | |
1da177e4 LT |
198 | |
199 | } | |
200 | ||
098297b2 JM |
201 | /* |
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 | */ | |
bd4c625c LT |
205 | static void internal_delete_pointers_items(struct buffer_info *cur_bi, |
206 | int first_p, | |
207 | int first_i, int del_num) | |
1da177e4 | 208 | { |
bd4c625c LT |
209 | 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; | |
214 | ||
215 | 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; | |
226 | ||
227 | blkh = B_BLK_HEAD(cur); | |
228 | nr = blkh_nr_item(blkh); | |
229 | ||
230 | 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 | } | |
1da177e4 | 236 | |
bd4c625c LT |
237 | 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); | |
241 | ||
242 | /* deleting */ | |
243 | dc = B_N_CHILD(cur, first_p); | |
244 | ||
245 | memmove(dc, dc + del_num, (nr + 1 - first_p - del_num) * DC_SIZE); | |
4cf5f7ad | 246 | key = internal_key(cur, first_i); |
bd4c625c LT |
247 | memmove(key, key + del_num, |
248 | (nr - first_i - del_num) * KEY_SIZE + (nr + 1 - | |
249 | del_num) * DC_SIZE); | |
250 | ||
251 | /* 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))); | |
256 | ||
257 | do_balance_mark_internal_dirty(cur_bi->tb, cur, 0); | |
258 | /*&&&&&&&&&&&&&&&&&&&&&&& */ | |
259 | check_internal(cur); | |
260 | /*&&&&&&&&&&&&&&&&&&&&&&& */ | |
261 | ||
262 | 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))); | |
267 | ||
268 | do_balance_mark_internal_dirty(cur_bi->tb, cur_bi->bi_parent, | |
269 | 0); | |
270 | /*&&&&&&&&&&&&&&&&&&&&&&&& */ | |
271 | check_internal(cur_bi->bi_parent); | |
272 | /*&&&&&&&&&&&&&&&&&&&&&&&& */ | |
273 | } | |
274 | } | |
1da177e4 LT |
275 | |
276 | /* delete n node pointers and items starting from given position */ | |
bd4c625c | 277 | static void internal_delete_childs(struct buffer_info *cur_bi, int from, int n) |
1da177e4 | 278 | { |
bd4c625c | 279 | int i_from; |
1da177e4 | 280 | |
bd4c625c | 281 | i_from = (from == 0) ? from : from - 1; |
1da177e4 | 282 | |
098297b2 JM |
283 | /* |
284 | * delete n pointers starting from `from' position in CUR; | |
285 | * delete n keys starting from 'i_from' position in CUR; | |
bd4c625c LT |
286 | */ |
287 | internal_delete_pointers_items(cur_bi, from, i_from, n); | |
1da177e4 LT |
288 | } |
289 | ||
098297b2 JM |
290 | /* |
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 | |
1da177e4 | 297 | */ |
bd4c625c LT |
298 | static void internal_copy_pointers_items(struct buffer_info *dest_bi, |
299 | struct buffer_head *src, | |
300 | int last_first, int cpy_num) | |
1da177e4 | 301 | { |
098297b2 JM |
302 | /* |
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 | */ | |
bd4c625c LT |
307 | 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; | |
313 | ||
314 | nr_src = B_NR_ITEMS(src); | |
315 | ||
316 | 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)); | |
326 | ||
327 | if (cpy_num == 0) | |
328 | return; | |
1da177e4 LT |
329 | |
330 | /* coping */ | |
bd4c625c LT |
331 | blkh = B_BLK_HEAD(dest); |
332 | nr_dest = blkh_nr_item(blkh); | |
1da177e4 | 333 | |
bd4c625c LT |
334 | /*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); | |
1da177e4 | 341 | |
bd4c625c LT |
342 | /* prepare space for cpy_num pointers */ |
343 | dc = B_N_CHILD(dest, dest_order); | |
1da177e4 | 344 | |
bd4c625c | 345 | memmove(dc + cpy_num, dc, (nr_dest - dest_order) * DC_SIZE); |
1da177e4 LT |
346 | |
347 | /* insert pointers */ | |
bd4c625c LT |
348 | memcpy(dc, B_N_CHILD(src, src_order), DC_SIZE * cpy_num); |
349 | ||
350 | /* prepare space for cpy_num - 1 item headers */ | |
4cf5f7ad | 351 | key = internal_key(dest, dest_order); |
bd4c625c LT |
352 | memmove(key + cpy_num - 1, key, |
353 | KEY_SIZE * (nr_dest - dest_order) + DC_SIZE * (nr_dest + | |
354 | cpy_num)); | |
355 | ||
356 | /* insert headers */ | |
4cf5f7ad | 357 | memcpy(key, internal_key(src, src_order), KEY_SIZE * (cpy_num - 1)); |
bd4c625c LT |
358 | |
359 | /* 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)); | |
364 | ||
365 | do_balance_mark_internal_dirty(dest_bi->tb, dest, 0); | |
366 | ||
367 | /*&&&&&&&&&&&&&&&&&&&&&&&& */ | |
368 | check_internal(dest); | |
369 | /*&&&&&&&&&&&&&&&&&&&&&&&& */ | |
370 | ||
371 | 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)); | |
377 | ||
378 | do_balance_mark_internal_dirty(dest_bi->tb, dest_bi->bi_parent, | |
379 | 0); | |
380 | /*&&&&&&&&&&&&&&&&&&&&&&&& */ | |
381 | check_internal(dest_bi->bi_parent); | |
382 | /*&&&&&&&&&&&&&&&&&&&&&&&& */ | |
383 | } | |
1da177e4 LT |
384 | |
385 | } | |
386 | ||
098297b2 JM |
387 | /* |
388 | * Copy cpy_num node pointers and cpy_num - 1 items from buffer src to | |
389 | * buffer dest. | |
1da177e4 LT |
390 | * 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 | */ | |
bd4c625c LT |
394 | static 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) | |
1da177e4 | 398 | { |
bd4c625c LT |
399 | int first_pointer; |
400 | int first_item; | |
401 | ||
402 | internal_copy_pointers_items(dest_bi, src_bi->bi_bh, last_first, | |
403 | cpy_num); | |
404 | ||
405 | if (last_first == FIRST_TO_LAST) { /* shift_left occurs */ | |
406 | first_pointer = 0; | |
407 | first_item = 0; | |
098297b2 JM |
408 | /* |
409 | * delete cpy_num - del_par pointers and keys starting for | |
410 | * pointers with first_pointer, for key - with first_item | |
411 | */ | |
bd4c625c LT |
412 | internal_delete_pointers_items(src_bi, first_pointer, |
413 | first_item, cpy_num - del_par); | |
414 | } else { /* shift_right occurs */ | |
415 | int i, j; | |
416 | ||
417 | 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 | } | |
1da177e4 LT |
426 | } |
427 | ||
428 | /* Insert n_src'th key of buffer src before n_dest'th key of buffer dest. */ | |
098297b2 JM |
429 | static void internal_insert_key(struct buffer_info *dest_bi, |
430 | /* insert key before key with n_dest number */ | |
431 | int dest_position_before, | |
bd4c625c | 432 | struct buffer_head *src, int src_position) |
1da177e4 | 433 | { |
bd4c625c LT |
434 | struct buffer_head *dest = dest_bi->bi_bh; |
435 | int nr; | |
436 | struct block_head *blkh; | |
437 | struct reiserfs_key *key; | |
438 | ||
439 | 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)); | |
451 | ||
452 | blkh = B_BLK_HEAD(dest); | |
453 | nr = blkh_nr_item(blkh); | |
454 | ||
455 | /* prepare space for inserting key */ | |
4cf5f7ad | 456 | key = internal_key(dest, dest_position_before); |
bd4c625c LT |
457 | memmove(key + 1, key, |
458 | (nr - dest_position_before) * KEY_SIZE + (nr + 1) * DC_SIZE); | |
459 | ||
460 | /* insert key */ | |
4cf5f7ad | 461 | memcpy(key, internal_key(src, src_position), KEY_SIZE); |
bd4c625c LT |
462 | |
463 | /* Change dirt, free space, item number fields. */ | |
464 | ||
465 | set_blkh_nr_item(blkh, blkh_nr_item(blkh) + 1); | |
466 | set_blkh_free_space(blkh, blkh_free_space(blkh) - KEY_SIZE); | |
467 | ||
468 | do_balance_mark_internal_dirty(dest_bi->tb, dest, 0); | |
469 | ||
470 | 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); | |
474 | ||
475 | do_balance_mark_internal_dirty(dest_bi->tb, dest_bi->bi_parent, | |
476 | 0); | |
477 | } | |
1da177e4 LT |
478 | } |
479 | ||
098297b2 JM |
480 | /* |
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. | |
1da177e4 LT |
484 | * 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 */ | |
098297b2 JM |
488 | static void internal_shift_left( |
489 | /* | |
490 | * INTERNAL_FROM_S_TO_L | INTERNAL_FROM_R_TO_S | |
491 | */ | |
492 | int mode, | |
bd4c625c LT |
493 | struct tree_balance *tb, |
494 | int h, int pointer_amount) | |
1da177e4 | 495 | { |
bd4c625c LT |
496 | struct buffer_info dest_bi, src_bi; |
497 | struct buffer_head *cf; | |
498 | int d_key_position; | |
499 | ||
500 | internal_define_dest_src_infos(mode, tb, h, &dest_bi, &src_bi, | |
501 | &d_key_position, &cf); | |
502 | ||
503 | /*printk("pointer_amount = %d\n",pointer_amount); */ | |
504 | ||
505 | if (pointer_amount) { | |
098297b2 JM |
506 | /* |
507 | * insert delimiting key from common father of dest and | |
508 | * src to node dest into position B_NR_ITEM(dest) | |
509 | */ | |
bd4c625c LT |
510 | internal_insert_key(&dest_bi, B_NR_ITEMS(dest_bi.bi_bh), cf, |
511 | d_key_position); | |
512 | ||
513 | 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); | |
1da177e4 LT |
525 | |
526 | } | |
527 | ||
098297b2 JM |
528 | /* |
529 | * Insert delimiting key to L[h]. | |
1da177e4 LT |
530 | * 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] */ | |
bd4c625c LT |
534 | static void internal_shift1_left(struct tree_balance *tb, |
535 | int h, int pointer_amount) | |
1da177e4 | 536 | { |
bd4c625c LT |
537 | struct buffer_info dest_bi, src_bi; |
538 | struct buffer_head *cf; | |
539 | int d_key_position; | |
1da177e4 | 540 | |
bd4c625c LT |
541 | internal_define_dest_src_infos(INTERNAL_SHIFT_FROM_S_TO_L, tb, h, |
542 | &dest_bi, &src_bi, &d_key_position, &cf); | |
1da177e4 | 543 | |
098297b2 JM |
544 | /* insert lkey[h]-th key from CFL[h] to left neighbor L[h] */ |
545 | if (pointer_amount > 0) | |
bd4c625c LT |
546 | internal_insert_key(&dest_bi, B_NR_ITEMS(dest_bi.bi_bh), cf, |
547 | d_key_position); | |
1da177e4 | 548 | |
bd4c625c LT |
549 | /* last parameter is del_parameter */ |
550 | internal_move_pointers_items(&dest_bi, &src_bi, FIRST_TO_LAST, | |
551 | pointer_amount, 1); | |
1da177e4 LT |
552 | } |
553 | ||
098297b2 JM |
554 | /* |
555 | * Insert d_key'th (delimiting) key from buffer cfr to head of dest. | |
1da177e4 LT |
556 | * 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 | */ | |
098297b2 JM |
560 | static void internal_shift_right( |
561 | /* | |
562 | * INTERNAL_FROM_S_TO_R | INTERNAL_FROM_L_TO_S | |
563 | */ | |
564 | int mode, | |
bd4c625c LT |
565 | struct tree_balance *tb, |
566 | int h, int pointer_amount) | |
1da177e4 | 567 | { |
bd4c625c LT |
568 | struct buffer_info dest_bi, src_bi; |
569 | struct buffer_head *cf; | |
570 | int d_key_position; | |
571 | int nr; | |
572 | ||
573 | internal_define_dest_src_infos(mode, tb, h, &dest_bi, &src_bi, | |
574 | &d_key_position, &cf); | |
575 | ||
576 | nr = B_NR_ITEMS(src_bi.bi_bh); | |
577 | ||
578 | if (pointer_amount > 0) { | |
098297b2 JM |
579 | /* |
580 | * insert delimiting key from common father of dest | |
581 | * and src to dest node into position 0 | |
582 | */ | |
bd4c625c LT |
583 | 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 | } | |
597 | ||
598 | /* last parameter is del_parameter */ | |
599 | internal_move_pointers_items(&dest_bi, &src_bi, LAST_TO_FIRST, | |
600 | pointer_amount, 0); | |
1da177e4 LT |
601 | } |
602 | ||
098297b2 JM |
603 | /* |
604 | * Insert delimiting key to R[h]. | |
1da177e4 LT |
605 | * 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] */ | |
bd4c625c LT |
609 | static void internal_shift1_right(struct tree_balance *tb, |
610 | int h, int pointer_amount) | |
1da177e4 | 611 | { |
bd4c625c LT |
612 | struct buffer_info dest_bi, src_bi; |
613 | struct buffer_head *cf; | |
614 | int d_key_position; | |
615 | ||
616 | internal_define_dest_src_infos(INTERNAL_SHIFT_FROM_S_TO_R, tb, h, | |
617 | &dest_bi, &src_bi, &d_key_position, &cf); | |
618 | ||
098297b2 JM |
619 | /* insert rkey from CFR[h] to right neighbor R[h] */ |
620 | if (pointer_amount > 0) | |
bd4c625c | 621 | internal_insert_key(&dest_bi, 0, cf, d_key_position); |
1da177e4 | 622 | |
bd4c625c LT |
623 | /* last parameter is del_parameter */ |
624 | internal_move_pointers_items(&dest_bi, &src_bi, LAST_TO_FIRST, | |
625 | pointer_amount, 1); | |
bd4c625c | 626 | } |
1da177e4 | 627 | |
098297b2 JM |
628 | /* |
629 | * Delete insert_num node pointers together with their left items | |
630 | * and balance current node. | |
631 | */ | |
bd4c625c LT |
632 | static void balance_internal_when_delete(struct tree_balance *tb, |
633 | int h, int child_pos) | |
1da177e4 | 634 | { |
bd4c625c LT |
635 | int insert_num; |
636 | int n; | |
637 | struct buffer_head *tbSh = PATH_H_PBUFFER(tb->tb_path, h); | |
638 | struct buffer_info bi; | |
639 | ||
640 | insert_num = tb->insert_size[h] / ((int)(DC_SIZE + KEY_SIZE)); | |
641 | ||
642 | /* 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); | |
647 | ||
648 | internal_delete_childs(&bi, child_pos, -insert_num); | |
649 | ||
650 | RFALSE(tb->blknum[h] > 1, | |
651 | "tb->blknum[%d]=%d when insert_size < 0", h, tb->blknum[h]); | |
652 | ||
653 | n = B_NR_ITEMS(tbSh); | |
654 | ||
655 | 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; | |
659 | ||
660 | 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); | |
666 | ||
667 | /* 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]; | |
098297b2 JM |
672 | /* |
673 | * switch super block's tree root block | |
674 | * number to the new value */ | |
bd4c625c | 675 | PUT_SB_ROOT_BLOCK(tb->tb_sb, new_root->b_blocknr); |
098297b2 | 676 | /*REISERFS_SB(tb->tb_sb)->s_rs->s_tree_height --; */ |
bd4c625c LT |
677 | 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 | /*&&&&&&&&&&&&&&&&&&&&&& */ | |
098297b2 | 684 | /* use check_internal if new root is an internal node */ |
bd4c625c | 685 | if (h > 1) |
bd4c625c LT |
686 | 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; | |
694 | } | |
695 | ||
098297b2 JM |
696 | /* join S[h] with L[h] */ |
697 | if (tb->L[h] && tb->lnum[h] == -B_NR_ITEMS(tb->L[h]) - 1) { | |
bd4c625c LT |
698 | |
699 | RFALSE(tb->rnum[h] != 0, | |
700 | "invalid tb->rnum[%d]==%d when joining S[h] with L[h]", | |
701 | h, tb->rnum[h]); | |
702 | ||
703 | internal_shift_left(INTERNAL_SHIFT_FROM_S_TO_L, tb, h, n + 1); | |
704 | reiserfs_invalidate_buffer(tb, tbSh); | |
705 | ||
706 | return; | |
707 | } | |
708 | ||
098297b2 JM |
709 | /* join S[h] with R[h] */ |
710 | if (tb->R[h] && tb->rnum[h] == -B_NR_ITEMS(tb->R[h]) - 1) { | |
bd4c625c LT |
711 | RFALSE(tb->lnum[h] != 0, |
712 | "invalid tb->lnum[%d]==%d when joining S[h] with R[h]", | |
713 | h, tb->lnum[h]); | |
714 | ||
715 | internal_shift_right(INTERNAL_SHIFT_FROM_S_TO_R, tb, h, n + 1); | |
716 | ||
717 | reiserfs_invalidate_buffer(tb, tbSh); | |
718 | return; | |
1da177e4 | 719 | } |
1da177e4 | 720 | |
098297b2 JM |
721 | /* borrow from left neighbor L[h] */ |
722 | if (tb->lnum[h] < 0) { | |
bd4c625c LT |
723 | RFALSE(tb->rnum[h] != 0, |
724 | "wrong tb->rnum[%d]==%d when borrow from L[h]", h, | |
725 | tb->rnum[h]); | |
bd4c625c LT |
726 | internal_shift_right(INTERNAL_SHIFT_FROM_L_TO_S, tb, h, |
727 | -tb->lnum[h]); | |
728 | return; | |
729 | } | |
730 | ||
098297b2 JM |
731 | /* borrow from right neighbor R[h] */ |
732 | if (tb->rnum[h] < 0) { | |
bd4c625c LT |
733 | 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 | } | |
739 | ||
098297b2 JM |
740 | /* split S[h] into two parts and put them into neighbors */ |
741 | if (tb->lnum[h] > 0) { | |
bd4c625c LT |
742 | 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); | |
745 | ||
746 | 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]); | |
749 | ||
750 | reiserfs_invalidate_buffer(tb, tbSh); | |
751 | ||
752 | return; | |
753 | } | |
c3a9c210 JM |
754 | reiserfs_panic(tb->tb_sb, "ibalance-2", |
755 | "unexpected tb->lnum[%d]==%d or tb->rnum[%d]==%d", | |
bd4c625c LT |
756 | h, tb->lnum[h], h, tb->rnum[h]); |
757 | } | |
1da177e4 LT |
758 | |
759 | /* Replace delimiting key of buffers L[h] and S[h] by the given key.*/ | |
bd4c625c | 760 | static void replace_lkey(struct tree_balance *tb, int h, struct item_head *key) |
1da177e4 | 761 | { |
bd4c625c LT |
762 | 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]); | |
1da177e4 | 765 | |
bd4c625c LT |
766 | if (B_NR_ITEMS(PATH_H_PBUFFER(tb->tb_path, h)) == 0) |
767 | return; | |
1da177e4 | 768 | |
4cf5f7ad | 769 | memcpy(internal_key(tb->CFL[h], tb->lkey[h]), key, KEY_SIZE); |
1da177e4 | 770 | |
bd4c625c | 771 | do_balance_mark_internal_dirty(tb, tb->CFL[h], 0); |
1da177e4 LT |
772 | } |
773 | ||
1da177e4 | 774 | /* Replace delimiting key of buffers S[h] and R[h] by the given key.*/ |
bd4c625c | 775 | static void replace_rkey(struct tree_balance *tb, int h, struct item_head *key) |
1da177e4 | 776 | { |
bd4c625c LT |
777 | 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])); | |
1da177e4 | 783 | |
4cf5f7ad | 784 | memcpy(internal_key(tb->CFR[h], tb->rkey[h]), key, KEY_SIZE); |
1da177e4 | 785 | |
bd4c625c | 786 | do_balance_mark_internal_dirty(tb, tb->CFR[h], 0); |
1da177e4 LT |
787 | } |
788 | ||
098297b2 JM |
789 | |
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 | ||
803 | int 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) | |
1da177e4 | 810 | { |
bd4c625c LT |
811 | struct buffer_head *tbSh = PATH_H_PBUFFER(tb->tb_path, h); |
812 | struct buffer_info bi; | |
098297b2 JM |
813 | |
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; | |
bd4c625c LT |
819 | 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; | |
824 | ||
825 | RFALSE(h < 1, "h (%d) can not be < 1 on internal level", h); | |
826 | ||
827 | PROC_INFO_INC(tb->tb_sb, balance_at[h]); | |
828 | ||
829 | order = | |
830 | (tbSh) ? PATH_H_POSITION(tb->tb_path, | |
831 | h + 1) /*tb->S[h]->b_item_order */ : 0; | |
832 | ||
098297b2 JM |
833 | /* |
834 | * Using insert_size[h] calculate the number insert_num of items | |
835 | * that must be inserted to or deleted from S[h]. | |
836 | */ | |
bd4c625c LT |
837 | insert_num = tb->insert_size[h] / ((int)(KEY_SIZE + DC_SIZE)); |
838 | ||
839 | /* 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); | |
846 | ||
847 | /* Make balance in case insert_num < 0 */ | |
848 | if (insert_num < 0) { | |
849 | balance_internal_when_delete(tb, h, child_pos); | |
850 | return order; | |
1da177e4 | 851 | } |
1da177e4 | 852 | |
bd4c625c LT |
853 | k = 0; |
854 | if (tb->lnum[h] > 0) { | |
098297b2 JM |
855 | /* |
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 | */ | |
bd4c625c LT |
860 | 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]); | |
bd4c625c LT |
865 | 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); | |
bd4c625c LT |
870 | /* 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); | |
880 | ||
881 | insert_num = 0; | |
882 | } else { | |
883 | struct disk_child *dc; | |
884 | ||
098297b2 JM |
885 | /* |
886 | * some items fall into L[h] or CFL[h], | |
887 | * but some don't fall | |
888 | */ | |
bd4c625c LT |
889 | 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); | |
900 | ||
901 | replace_lkey(tb, h, insert_key + k); | |
902 | ||
098297b2 JM |
903 | /* |
904 | * replace the first node-ptr in S[h] by | |
905 | * node-ptr to insert_ptr[k] | |
906 | */ | |
bd4c625c LT |
907 | 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); | |
912 | ||
913 | do_balance_mark_internal_dirty(tb, tbSh, 0); | |
914 | ||
915 | 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] */ | |
098297b2 JM |
925 | /* |
926 | * check how many of new items fall into R or CFR | |
927 | * after shifting | |
928 | */ | |
bd4c625c LT |
929 | 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] */ | |
bd4c625c LT |
932 | 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] */ | |
bd4c625c LT |
936 | 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 | ||
098297b2 JM |
969 | /* |
970 | * replace the first node-ptr in R[h] by | |
971 | * node-ptr insert_ptr[insert_num-k-1] | |
972 | */ | |
bd4c625c LT |
973 | 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 | } | |
1da177e4 | 988 | |
098297b2 | 989 | /** Fill new node that appears instead of S[h] **/ |
bd4c625c LT |
990 | RFALSE(tb->blknum[h] > 2, "blknum can not be > 2 for internal level"); |
991 | RFALSE(tb->blknum[h] < 0, "blknum can not be < 0"); | |
1da177e4 | 992 | |
bd4c625c LT |
993 | if (!tb->blknum[h]) { /* node S[h] is empty now */ |
994 | RFALSE(!tbSh, "S[h] is equal NULL"); | |
1da177e4 | 995 | |
bd4c625c LT |
996 | /* do what is needed for buffer thrown from tree */ |
997 | reiserfs_invalidate_buffer(tb, tbSh); | |
998 | return order; | |
999 | } | |
1da177e4 | 1000 | |
bd4c625c LT |
1001 | 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; | |
1da177e4 | 1006 | |
bd4c625c | 1007 | if (tb->blknum[h] != 1) |
c3a9c210 JM |
1008 | reiserfs_panic(NULL, "ibalance-3", "One new node " |
1009 | "required for creating the new root"); | |
bd4c625c LT |
1010 | /* 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); | |
1da177e4 | 1014 | |
bd4c625c LT |
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); | |
1da177e4 | 1024 | |
bd4c625c | 1025 | do_balance_mark_internal_dirty(tb, tbSh, 0); |
1da177e4 | 1026 | |
bd4c625c LT |
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); | |
1da177e4 | 1039 | } |
bd4c625c LT |
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] */ | |
4cf5f7ad | 1065 | memcpy(&new_insert_key, internal_key(tbSh, n - snum), |
bd4c625c LT |
1066 | KEY_SIZE); |
1067 | /* last parameter is del_par */ | |
1068 | internal_move_pointers_items(&dest_bi, &src_bi, | |
1069 | LAST_TO_FIRST, snum, 0); | |
bd4c625c LT |
1070 | } 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 */ | |
098297b2 JM |
1073 | /* |
1074 | * new_insert_key = (n + insert_item - snum)'th | |
1075 | * key in S[h] | |
1076 | */ | |
bd4c625c | 1077 | memcpy(&new_insert_key, |
4cf5f7ad | 1078 | internal_key(tbSh, n + insert_num - snum), |
bd4c625c LT |
1079 | 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); | |
bd4c625c | 1084 | |
098297b2 JM |
1085 | /* |
1086 | * insert insert_num keys and node-pointers | |
1087 | * into S_new | |
1088 | */ | |
bd4c625c LT |
1089 | 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); | |
bd4c625c LT |
1105 | /* 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); | |
098297b2 JM |
1114 | /* |
1115 | * replace first node-ptr in S_new by node-ptr | |
1116 | * to insert_ptr[insert_num-k-1] | |
1117 | */ | |
bd4c625c LT |
1118 | |
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 | ||
098297b2 | 1140 | /* S_new is released in unfix_nodes */ |
1da177e4 LT |
1141 | } |
1142 | ||
bd4c625c | 1143 | n = B_NR_ITEMS(tbSh); /*number of items in S[h] */ |
1da177e4 | 1144 | |
bd4c625c LT |
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 | ||
1da177e4 | 1156 | insert_ptr[0] = new_insert_ptr; |
0a11b9aa JM |
1157 | if (new_insert_ptr) |
1158 | memcpy(new_insert_key_addr, &new_insert_key, KEY_SIZE); | |
1da177e4 LT |
1159 | |
1160 | return order; | |
bd4c625c | 1161 | } |