File: /usr/src/linux/fs/reiserfs/lbalance.c
1 /*
2 * Copyright 2000 by Hans Reiser, licensing governed by reiserfs/README
3 */
4
5 #include <linux/config.h>
6 #include <asm/uaccess.h>
7 #include <linux/string.h>
8 #include <linux/sched.h>
9 #include <linux/reiserfs_fs.h>
10
11 /* these are used in do_balance.c */
12
13 /* leaf_move_items
14 leaf_shift_left
15 leaf_shift_right
16 leaf_delete_items
17 leaf_insert_into_buf
18 leaf_paste_in_buffer
19 leaf_cut_from_buffer
20 leaf_paste_entries
21 */
22
23
24 /* copy copy_count entries from source directory item to dest buffer (creating new item if needed) */
25 static void leaf_copy_dir_entries (struct buffer_info * dest_bi, struct buffer_head * source,
26 int last_first, int item_num, int from, int copy_count)
27 {
28 struct buffer_head * dest = dest_bi->bi_bh;
29 int item_num_in_dest; /* either the number of target item,
30 or if we must create a new item,
31 the number of the item we will
32 create it next to */
33 struct item_head * ih;
34 struct reiserfs_de_head * deh;
35 int copy_records_len; /* length of all records in item to be copied */
36 char * records;
37
38 ih = B_N_PITEM_HEAD (source, item_num);
39
40 #ifdef CONFIG_REISERFS_CHECK
41 if (!is_direntry_le_ih (ih))
42 reiserfs_panic(0, "vs-10000: leaf_copy_dir_entries: item must be directory item");
43 #endif
44
45 /* length of all record to be copied and first byte of the last of them */
46 deh = B_I_DEH (source, ih);
47 if (copy_count) {
48 copy_records_len = (from ? deh[from - 1].deh_location : ih->ih_item_len) -
49 deh[from + copy_count - 1].deh_location;
50 records = source->b_data + ih->ih_item_location + deh[from + copy_count - 1].deh_location;
51 } else {
52 copy_records_len = 0;
53 records = 0;
54 }
55
56 /* when copy last to first, dest buffer can contain 0 items */
57 item_num_in_dest = (last_first == LAST_TO_FIRST) ? (( B_NR_ITEMS(dest) ) ? 0 : -1) : (B_NR_ITEMS(dest) - 1);
58
59 /* if there are no items in dest or the first/last item in dest is not item of the same directory */
60 if ( (item_num_in_dest == - 1) ||
61 (last_first == FIRST_TO_LAST && le_key_k_offset (ih_version (ih), &(ih->ih_key)) == DOT_OFFSET) ||
62 (last_first == LAST_TO_FIRST && comp_short_le_keys/*COMP_SHORT_KEYS*/ (&ih->ih_key, B_N_PKEY (dest, item_num_in_dest)))) {
63 /* create new item in dest */
64 struct item_head new_ih;
65
66 /* form item header */
67 memcpy (&new_ih.ih_key, &ih->ih_key, KEY_SIZE);
68 new_ih.ih_version = cpu_to_le16 (ITEM_VERSION_1);
69 /* calculate item len */
70 new_ih.ih_item_len = cpu_to_le16 (DEH_SIZE * copy_count + copy_records_len);
71 I_ENTRY_COUNT(&new_ih) = 0;
72
73 if (last_first == LAST_TO_FIRST) {
74 /* form key by the following way */
75 if (from < I_ENTRY_COUNT(ih)) {
76 set_le_ih_k_offset (&new_ih, cpu_to_le32 (le32_to_cpu (deh[from].deh_offset)));
77 /*memcpy (&new_ih.ih_key.k_offset, &deh[from].deh_offset, SHORT_KEY_SIZE);*/
78 } else {
79 /* no entries will be copied to this item in this function */
80 set_le_ih_k_offset (&new_ih, cpu_to_le32 (U32_MAX));
81 /* this item is not yet valid, but we want I_IS_DIRECTORY_ITEM to return 1 for it, so we -1 */
82 }
83 set_le_key_k_type (ITEM_VERSION_1, &(new_ih.ih_key), TYPE_DIRENTRY);
84 }
85
86 /* insert item into dest buffer */
87 leaf_insert_into_buf (dest_bi, (last_first == LAST_TO_FIRST) ? 0 : B_NR_ITEMS(dest), &new_ih, NULL, 0);
88 } else {
89 /* prepare space for entries */
90 leaf_paste_in_buffer (dest_bi, (last_first==FIRST_TO_LAST) ? (B_NR_ITEMS(dest) - 1) : 0, MAX_US_INT,
91 DEH_SIZE * copy_count + copy_records_len, records, 0
92 );
93 }
94
95 item_num_in_dest = (last_first == FIRST_TO_LAST) ? (B_NR_ITEMS(dest)-1) : 0;
96
97 leaf_paste_entries (dest_bi->bi_bh, item_num_in_dest,
98 (last_first == FIRST_TO_LAST) ? I_ENTRY_COUNT(B_N_PITEM_HEAD (dest, item_num_in_dest)) : 0,
99 copy_count, deh + from, records,
100 DEH_SIZE * copy_count + copy_records_len
101 );
102 }
103
104
105 /* Copy the first (if last_first == FIRST_TO_LAST) or last (last_first == LAST_TO_FIRST) item or
106 part of it or nothing (see the return 0 below) from SOURCE to the end
107 (if last_first) or beginning (!last_first) of the DEST */
108 /* returns 1 if anything was copied, else 0 */
109 static int leaf_copy_boundary_item (struct buffer_info * dest_bi, struct buffer_head * src, int last_first,
110 int bytes_or_entries)
111 {
112 struct buffer_head * dest = dest_bi->bi_bh;
113 int dest_nr_item, src_nr_item; /* number of items in the source and destination buffers */
114 struct item_head * ih;
115 struct item_head * dih;
116
117 dest_nr_item = B_NR_ITEMS(dest);
118
119 if ( last_first == FIRST_TO_LAST ) {
120 /* if ( DEST is empty or first item of SOURCE and last item of DEST are the items of different objects
121 or of different types ) then there is no need to treat this item differently from the other items
122 that we copy, so we return */
123 ih = B_N_PITEM_HEAD (src, 0);
124 dih = B_N_PITEM_HEAD (dest, dest_nr_item - 1);
125 if (!dest_nr_item || (!op_is_left_mergeable (&(ih->ih_key), src->b_size)))
126 /* there is nothing to merge */
127 return 0;
128
129 #ifdef CONFIG_REISERFS_CHECK
130 if ( ! ih->ih_item_len )
131 reiserfs_panic (0, "vs-10010: leaf_copy_boundary_item: item can not have empty dynamic length");
132 #endif
133
134 if ( is_direntry_le_ih (ih) ) {
135 if ( bytes_or_entries == -1 )
136 /* copy all entries to dest */
137 bytes_or_entries = le16_to_cpu (ih->u.ih_entry_count);
138 leaf_copy_dir_entries (dest_bi, src, FIRST_TO_LAST, 0, 0, bytes_or_entries);
139 return 1;
140 }
141
142 /* copy part of the body of the first item of SOURCE to the end of the body of the last item of the DEST
143 part defined by 'bytes_or_entries'; if bytes_or_entries == -1 copy whole body; don't create new item header
144 */
145 if ( bytes_or_entries == -1 )
146 bytes_or_entries = le16_to_cpu (ih->ih_item_len);
147
148 #ifdef CONFIG_REISERFS_CHECK
149 else {
150 if (bytes_or_entries == le16_to_cpu (ih->ih_item_len) && is_indirect_le_ih(ih))
151 if (get_ih_free_space (ih))
152 reiserfs_panic (0, "vs-10020: leaf_copy_boundary_item: "
153 "last unformatted node must be filled entirely (%h)",
154 ih);
155 }
156 #endif
157
158 /* merge first item (or its part) of src buffer with the last
159 item of dest buffer. Both are of the same file */
160 leaf_paste_in_buffer (dest_bi,
161 dest_nr_item - 1, dih->ih_item_len, bytes_or_entries, B_I_PITEM(src,ih), 0
162 );
163
164 if (is_indirect_le_ih (dih)) {
165 #ifdef CONFIG_REISERFS_CHECK
166 if (get_ih_free_space (dih))
167 reiserfs_panic (0, "vs-10030: leaf_copy_boundary_item: "
168 "merge to left: last unformatted node of non-last indirect item %h must have zerto free space",
169 ih);
170 #endif
171 if (bytes_or_entries == le16_to_cpu (ih->ih_item_len))
172 set_ih_free_space (dih, get_ih_free_space (ih));
173 }
174
175 return 1;
176 }
177
178
179 /* copy boundary item to right (last_first == LAST_TO_FIRST) */
180
181 /* ( DEST is empty or last item of SOURCE and first item of DEST
182 are the items of different object or of different types )
183 */
184 src_nr_item = B_NR_ITEMS (src);
185 ih = B_N_PITEM_HEAD (src, src_nr_item - 1);
186 dih = B_N_PITEM_HEAD (dest, 0);
187
188 if (!dest_nr_item || !op_is_left_mergeable (&(dih->ih_key), src->b_size))
189 return 0;
190
191 if ( is_direntry_le_ih (ih)) {
192 if ( bytes_or_entries == -1 )
193 /* bytes_or_entries = entries number in last item body of SOURCE */
194 bytes_or_entries = le16_to_cpu (ih->u.ih_entry_count);
195
196 leaf_copy_dir_entries (dest_bi, src, LAST_TO_FIRST, src_nr_item - 1, le16_to_cpu (ih->u.ih_entry_count) - bytes_or_entries, bytes_or_entries);
197 return 1;
198 }
199
200 /* copy part of the body of the last item of SOURCE to the begin of the body of the first item of the DEST;
201 part defined by 'bytes_or_entries'; if byte_or_entriess == -1 copy whole body; change first item key of the DEST;
202 don't create new item header
203 */
204
205 #ifdef CONFIG_REISERFS_CHECK
206 if (is_indirect_le_ih(ih) && get_ih_free_space (ih))
207 reiserfs_panic (0, "vs-10040: leaf_copy_boundary_item: "
208 "merge to right: last unformatted node of non-last indirect item must be filled entirely (%h)",
209 ih);
210 #endif
211
212 if ( bytes_or_entries == -1 ) {
213 /* bytes_or_entries = length of last item body of SOURCE */
214 bytes_or_entries = ih->ih_item_len;
215
216 #ifdef CONFIG_REISERFS_CHECK
217 if (le_ih_k_offset (dih) != le_ih_k_offset (ih) + op_bytes_number (ih, src->b_size))
218 reiserfs_panic (0, "vs-10050: leaf_copy_boundary_item: items %h and %h do not match", ih, dih);
219 #endif
220
221 /* change first item key of the DEST */
222 set_le_ih_k_offset (dih, le_ih_k_offset (ih));
223
224 /* item becomes non-mergeable */
225 /* or mergeable if left item was */
226 set_le_ih_k_type (dih, le_ih_k_type (ih));
227 } else {
228 /* merge to right only part of item */
229 #ifdef CONFIG_REISERFS_CHECK
230 if ( le16_to_cpu (ih->ih_item_len) <= bytes_or_entries )
231 reiserfs_panic (0, "vs-10060: leaf_copy_boundary_item: no so much bytes %lu (needed %lu)",
232 ih->ih_item_len, bytes_or_entries);
233 #endif
234
235 /* change first item key of the DEST */
236 if ( is_direct_le_ih (dih) ) {
237 #ifdef CONFIG_REISERFS_CHECK
238 if (le_ih_k_offset (dih) <= (unsigned long)bytes_or_entries)
239 reiserfs_panic (0, "vs-10070: leaf_copy_boundary_item: dih %h, bytes_or_entries(%d)",
240 dih, bytes_or_entries);
241 #endif
242 set_le_ih_k_offset (dih, le_ih_k_offset (dih) - bytes_or_entries);
243 } else {
244 #ifdef CONFIG_REISERFS_CHECK
245 if (le_ih_k_offset (dih) <= (bytes_or_entries / UNFM_P_SIZE) * dest->b_size )
246 reiserfs_panic (0, "vs-10080: leaf_copy_boundary_item: dih %h, bytes_or_entries(%d)",
247 dih, (bytes_or_entries/UNFM_P_SIZE)*dest->b_size);
248 #endif
249 set_le_ih_k_offset (dih, le_ih_k_offset (dih) - ((bytes_or_entries / UNFM_P_SIZE) * dest->b_size));
250 }
251 }
252
253 leaf_paste_in_buffer (dest_bi, 0, 0, bytes_or_entries, B_I_PITEM(src,ih) + ih->ih_item_len - bytes_or_entries, 0);
254 return 1;
255 }
256
257
258 /* copy cpy_mun items from buffer src to buffer dest
259 * last_first == FIRST_TO_LAST means, that we copy cpy_num items beginning from first-th item in src to tail of dest
260 * last_first == LAST_TO_FIRST means, that we copy cpy_num items beginning from first-th item in src to head of dest
261 */
262 static void leaf_copy_items_entirely (struct buffer_info * dest_bi, struct buffer_head * src, int last_first,
263 int first, int cpy_num)
264 {
265 struct buffer_head * dest;
266 int nr;
267 int dest_before;
268 int last_loc, last_inserted_loc, location;
269 int i, j;
270 struct block_head * blkh;
271 struct item_head * ih;
272
273 #ifdef CONFIG_REISERFS_CHECK
274 if (last_first != LAST_TO_FIRST && last_first != FIRST_TO_LAST)
275 reiserfs_panic (0, "vs-10090: leaf_copy_items_entirely: bad last_first parameter %d", last_first);
276
277 if (B_NR_ITEMS (src) - first < cpy_num)
278 reiserfs_panic (0, "vs-10100: leaf_copy_items_entirely: too few items in source %d, required %d from %d",
279 B_NR_ITEMS(src), cpy_num, first);
280
281 if (cpy_num < 0)
282 reiserfs_panic (0, "vs-10110: leaf_copy_items_entirely: can not copy negative amount of items");
283
284 if ( ! dest_bi )
285 reiserfs_panic (0, "vs-10120: leaf_copy_items_entirely: can not copy negative amount of items");
286 #endif
287
288 dest = dest_bi->bi_bh;
289
290 #ifdef CONFIG_REISERFS_CHECK
291 if ( ! dest )
292 reiserfs_panic (0, "vs-10130: leaf_copy_items_entirely: can not copy negative amount of items");
293 #endif
294
295 if (cpy_num == 0)
296 return;
297
298 nr = le16_to_cpu ((blkh = B_BLK_HEAD(dest))->blk_nr_item);
299
300 /* we will insert items before 0-th or nr-th item in dest buffer. It depends of last_first parameter */
301 dest_before = (last_first == LAST_TO_FIRST) ? 0 : nr;
302
303 /* location of head of first new item */
304 ih = B_N_PITEM_HEAD (dest, dest_before);
305
306 #ifdef CONFIG_REISERFS_CHECK
307 if (le16_to_cpu (blkh->blk_free_space) < cpy_num * IH_SIZE) {
308 reiserfs_panic (0, "vs-10140: leaf_copy_items_entirely: "
309 "not enough free space for headers %d (needed %d)",
310 B_FREE_SPACE (dest), cpy_num * IH_SIZE);
311 }
312 #endif
313
314 /* prepare space for headers */
315 memmove (ih + cpy_num, ih, (nr-dest_before) * IH_SIZE);
316
317 /* copy item headers */
318 memcpy (ih, B_N_PITEM_HEAD (src, first), cpy_num * IH_SIZE);
319
320 blkh->blk_free_space = cpu_to_le16 (le16_to_cpu (blkh->blk_free_space) - IH_SIZE * cpy_num);
321
322 /* location of unmovable item */
323 j = location = (dest_before == 0) ? dest->b_size : (ih-1)->ih_item_location;
324 for (i = dest_before; i < nr + cpy_num; i ++)
325 ih[i-dest_before].ih_item_location =
326 (location -= ih[i-dest_before].ih_item_len);
327
328 /* prepare space for items */
329 last_loc = ih[nr+cpy_num-1-dest_before].ih_item_location;
330 last_inserted_loc = ih[cpy_num-1].ih_item_location;
331
332 /* check free space */
333 #ifdef CONFIG_REISERFS_CHECK
334 if (le16_to_cpu (blkh->blk_free_space) < j - last_inserted_loc) {
335 reiserfs_panic (0, "vs-10150: leaf_copy_items_entirely: not enough free space for items %d (needed %d)",
336 le16_to_cpu (blkh->blk_free_space), j - last_inserted_loc);
337 }
338 #endif
339
340 memmove (dest->b_data + last_loc,
341 dest->b_data + last_loc + j - last_inserted_loc,
342 last_inserted_loc - last_loc);
343
344 /* copy items */
345 memcpy (dest->b_data + last_inserted_loc, B_N_PITEM(src,(first + cpy_num - 1)),
346 j - last_inserted_loc);
347
348 /* sizes, item number */
349 blkh->blk_nr_item = cpu_to_le16 (le16_to_cpu (blkh->blk_nr_item) + cpy_num);
350 blkh->blk_free_space = cpu_to_le16 (le16_to_cpu (blkh->blk_free_space) - (j - last_inserted_loc));
351
352 do_balance_mark_leaf_dirty (dest_bi->tb, dest, 0);
353
354 if (dest_bi->bi_parent) {
355 #ifdef CONFIG_REISERFS_CHECK
356 if (B_N_CHILD (dest_bi->bi_parent, dest_bi->bi_position)->dc_block_number != dest->b_blocknr) {
357 reiserfs_panic (0, "vs-10160: leaf_copy_items_entirely: "
358 "block number in bh does not match to field in disk_child structure %lu and %lu",
359 dest->b_blocknr, B_N_CHILD (dest_bi->bi_parent, dest_bi->bi_position)->dc_block_number);
360 }
361 #endif
362 B_N_CHILD (dest_bi->bi_parent, dest_bi->bi_position)->dc_size +=
363 j - last_inserted_loc + IH_SIZE * cpy_num;
364
365 do_balance_mark_internal_dirty (dest_bi->tb, dest_bi->bi_parent, 0);
366 }
367 }
368
369
370 /* This function splits the (liquid) item into two items (useful when
371 shifting part of an item into another node.) */
372 static void leaf_item_bottle (struct buffer_info * dest_bi, struct buffer_head * src, int last_first,
373 int item_num, int cpy_bytes)
374 {
375 struct buffer_head * dest = dest_bi->bi_bh;
376 struct item_head * ih;
377
378 #ifdef CONFIG_REISERFS_CHECK
379 if ( cpy_bytes == -1 )
380 reiserfs_panic (0, "vs-10170: leaf_item_bottle: bytes == - 1 means: do not split item");
381 #endif
382
383 if ( last_first == FIRST_TO_LAST ) {
384 /* if ( if item in position item_num in buffer SOURCE is directory item ) */
385 if (is_direntry_le_ih (ih = B_N_PITEM_HEAD(src,item_num)))
386 leaf_copy_dir_entries (dest_bi, src, FIRST_TO_LAST, item_num, 0, cpy_bytes);
387 else {
388 struct item_head n_ih;
389
390 /* copy part of the body of the item number 'item_num' of SOURCE to the end of the DEST
391 part defined by 'cpy_bytes'; create new item header; change old item_header (????);
392 n_ih = new item_header;
393 */
394 memcpy (&n_ih, ih, IH_SIZE);
395 n_ih.ih_item_len = cpu_to_le16 (cpy_bytes);
396 if (is_indirect_le_ih (ih)) {
397 #ifdef CONFIG_REISERFS_CHECK
398 if (cpy_bytes == le16_to_cpu (ih->ih_item_len) && get_ih_free_space (ih))
399 reiserfs_panic (0, "vs-10180: leaf_item_bottle: "
400 "when whole indirect item is bottle to left neighbor, it must have free_space==0 (not %lu)",
401 get_ih_free_space (ih));
402 #endif
403 set_ih_free_space (&n_ih, 0);
404 }
405
406 #ifdef CONFIG_REISERFS_CHECK
407 if (op_is_left_mergeable (&(ih->ih_key), src->b_size))
408 reiserfs_panic (0, "vs-10190: leaf_item_bottle: bad mergeability of item %h", ih);
409 #endif
410 n_ih.ih_version = ih->ih_version;;
411 leaf_insert_into_buf (dest_bi, B_NR_ITEMS(dest), &n_ih, B_N_PITEM (src, item_num), 0);
412 }
413 } else {
414 /* if ( if item in position item_num in buffer SOURCE is directory item ) */
415 if (is_direntry_le_ih(ih = B_N_PITEM_HEAD (src, item_num)))
416 leaf_copy_dir_entries (dest_bi, src, LAST_TO_FIRST, item_num, I_ENTRY_COUNT(ih) - cpy_bytes, cpy_bytes);
417 else {
418 struct item_head n_ih;
419
420 /* copy part of the body of the item number 'item_num' of SOURCE to the begin of the DEST
421 part defined by 'cpy_bytes'; create new item header;
422 n_ih = new item_header;
423 */
424 memcpy (&n_ih, ih, SHORT_KEY_SIZE);
425 n_ih.ih_version = cpu_to_le16 (ih_version (ih));
426 if (is_direct_le_ih (ih)) {
427 set_le_ih_k_offset (&n_ih, le_ih_k_offset (ih) + le16_to_cpu (ih->ih_item_len) - cpy_bytes);
428 set_le_ih_k_type (&n_ih, TYPE_DIRECT);
429 set_ih_free_space (&n_ih, MAX_US_INT);
430 } else {
431 /* indirect item */
432 #ifdef CONFIG_REISERFS_CHECK
433 if (!cpy_bytes && get_ih_free_space (ih))
434 reiserfs_panic (0, "vs-10200: leaf_item_bottle: ih->ih_free_space must be 0 when indirect item will be appended");
435 #endif
436 set_le_ih_k_offset (&n_ih, le_ih_k_offset (ih) + (le16_to_cpu (ih->ih_item_len) - cpy_bytes) / UNFM_P_SIZE * dest->b_size);
437 set_le_ih_k_type (&n_ih, TYPE_INDIRECT);
438 set_ih_free_space (&n_ih, get_ih_free_space (ih));
439 }
440
441 /* set item length */
442 n_ih.ih_item_len = cpu_to_le16 (cpy_bytes);
443 n_ih.ih_version = cpu_to_le16 (le16_to_cpu (ih->ih_version));
444 leaf_insert_into_buf (dest_bi, 0, &n_ih, B_N_PITEM(src,item_num) + le16_to_cpu (ih->ih_item_len) - cpy_bytes, 0);
445 }
446 }
447 }
448
449
450 /* If cpy_bytes equals minus one than copy cpy_num whole items from SOURCE to DEST.
451 If cpy_bytes not equal to minus one than copy cpy_num-1 whole items from SOURCE to DEST.
452 From last item copy cpy_num bytes for regular item and cpy_num directory entries for
453 directory item. */
454 static int leaf_copy_items (struct buffer_info * dest_bi, struct buffer_head * src, int last_first, int cpy_num,
455 int cpy_bytes)
456 {
457 struct buffer_head * dest;
458 int pos, i, src_nr_item, bytes;
459
460 dest = dest_bi->bi_bh;
461 #ifdef CONFIG_REISERFS_CHECK
462 if (!dest || !src)
463 reiserfs_panic (0, "vs-10210: leaf_copy_items: !dest || !src");
464
465 if ( last_first != FIRST_TO_LAST && last_first != LAST_TO_FIRST )
466 reiserfs_panic (0, "vs-10220: leaf_copy_items: last_first != FIRST_TO_LAST && last_first != LAST_TO_FIRST");
467
468 if ( B_NR_ITEMS(src) < cpy_num )
469 reiserfs_panic (0, "vs-10230: leaf_copy_items: No enough items: %d, required %d", B_NR_ITEMS(src), cpy_num);
470
471 if ( cpy_num < 0 )
472 reiserfs_panic (0, "vs-10240: leaf_copy_items: cpy_num < 0 (%d)", cpy_num);
473 #endif
474
475 if ( cpy_num == 0 )
476 return 0;
477
478 if ( last_first == FIRST_TO_LAST ) {
479 /* copy items to left */
480 pos = 0;
481 if ( cpy_num == 1 )
482 bytes = cpy_bytes;
483 else
484 bytes = -1;
485
486 /* copy the first item or it part or nothing to the end of the DEST (i = leaf_copy_boundary_item(DEST,SOURCE,0,bytes)) */
487 i = leaf_copy_boundary_item (dest_bi, src, FIRST_TO_LAST, bytes);
488 cpy_num -= i;
489 if ( cpy_num == 0 )
490 return i;
491 pos += i;
492 if ( cpy_bytes == -1 )
493 /* copy first cpy_num items starting from position 'pos' of SOURCE to end of DEST */
494 leaf_copy_items_entirely (dest_bi, src, FIRST_TO_LAST, pos, cpy_num);
495 else {
496 /* copy first cpy_num-1 items starting from position 'pos-1' of the SOURCE to the end of the DEST */
497 leaf_copy_items_entirely (dest_bi, src, FIRST_TO_LAST, pos, cpy_num-1);
498
499 /* copy part of the item which number is cpy_num+pos-1 to the end of the DEST */
500 leaf_item_bottle (dest_bi, src, FIRST_TO_LAST, cpy_num+pos-1, cpy_bytes);
501 }
502 } else {
503 /* copy items to right */
504 src_nr_item = B_NR_ITEMS (src);
505 if ( cpy_num == 1 )
506 bytes = cpy_bytes;
507 else
508 bytes = -1;
509
510 /* copy the last item or it part or nothing to the begin of the DEST (i = leaf_copy_boundary_item(DEST,SOURCE,1,bytes)); */
511 i = leaf_copy_boundary_item (dest_bi, src, LAST_TO_FIRST, bytes);
512
513 cpy_num -= i;
514 if ( cpy_num == 0 )
515 return i;
516
517 pos = src_nr_item - cpy_num - i;
518 if ( cpy_bytes == -1 ) {
519 /* starting from position 'pos' copy last cpy_num items of SOURCE to begin of DEST */
520 leaf_copy_items_entirely (dest_bi, src, LAST_TO_FIRST, pos, cpy_num);
521 } else {
522 /* copy last cpy_num-1 items starting from position 'pos+1' of the SOURCE to the begin of the DEST; */
523 leaf_copy_items_entirely (dest_bi, src, LAST_TO_FIRST, pos+1, cpy_num-1);
524
525 /* copy part of the item which number is pos to the begin of the DEST */
526 leaf_item_bottle (dest_bi, src, LAST_TO_FIRST, pos, cpy_bytes);
527 }
528 }
529 return i;
530 }
531
532
533 /* there are types of coping: from S[0] to L[0], from S[0] to R[0],
534 from R[0] to L[0]. for each of these we have to define parent and
535 positions of destination and source buffers */
536 static void leaf_define_dest_src_infos (int shift_mode, struct tree_balance * tb, struct buffer_info * dest_bi,
537 struct buffer_info * src_bi, int * first_last,
538 struct buffer_head * Snew)
539 {
540 #ifdef CONFIG_REISERFS_CHECK
541 memset (dest_bi, 0, sizeof (struct buffer_info));
542 memset (src_bi, 0, sizeof (struct buffer_info));
543 #endif
544
545 /* define dest, src, dest parent, dest position */
546 switch (shift_mode) {
547 case LEAF_FROM_S_TO_L: /* it is used in leaf_shift_left */
548 src_bi->tb = tb;
549 src_bi->bi_bh = PATH_PLAST_BUFFER (tb->tb_path);
550 src_bi->bi_parent = PATH_H_PPARENT (tb->tb_path, 0);
551 src_bi->bi_position = PATH_H_B_ITEM_ORDER (tb->tb_path, 0); /* src->b_item_order */
552 dest_bi->tb = tb;
553 dest_bi->bi_bh = tb->L[0];
554 dest_bi->bi_parent = tb->FL[0];
555 dest_bi->bi_position = get_left_neighbor_position (tb, 0);
556 *first_last = FIRST_TO_LAST;
557 break;
558
559 case LEAF_FROM_S_TO_R: /* it is used in leaf_shift_right */
560 src_bi->tb = tb;
561 src_bi->bi_bh = PATH_PLAST_BUFFER (tb->tb_path);
562 src_bi->bi_parent = PATH_H_PPARENT (tb->tb_path, 0);
563 src_bi->bi_position = PATH_H_B_ITEM_ORDER (tb->tb_path, 0);
564 dest_bi->tb = tb;
565 dest_bi->bi_bh = tb->R[0];
566 dest_bi->bi_parent = tb->FR[0];
567 dest_bi->bi_position = get_right_neighbor_position (tb, 0);
568 *first_last = LAST_TO_FIRST;
569 break;
570
571 case LEAF_FROM_R_TO_L: /* it is used in balance_leaf_when_delete */
572 src_bi->tb = tb;
573 src_bi->bi_bh = tb->R[0];
574 src_bi->bi_parent = tb->FR[0];
575 src_bi->bi_position = get_right_neighbor_position (tb, 0);
576 dest_bi->tb = tb;
577 dest_bi->bi_bh = tb->L[0];
578 dest_bi->bi_parent = tb->FL[0];
579 dest_bi->bi_position = get_left_neighbor_position (tb, 0);
580 *first_last = FIRST_TO_LAST;
581 break;
582
583 case LEAF_FROM_L_TO_R: /* it is used in balance_leaf_when_delete */
584 src_bi->tb = tb;
585 src_bi->bi_bh = tb->L[0];
586 src_bi->bi_parent = tb->FL[0];
587 src_bi->bi_position = get_left_neighbor_position (tb, 0);
588 dest_bi->tb = tb;
589 dest_bi->bi_bh = tb->R[0];
590 dest_bi->bi_parent = tb->FR[0];
591 dest_bi->bi_position = get_right_neighbor_position (tb, 0);
592 *first_last = LAST_TO_FIRST;
593 break;
594
595 case LEAF_FROM_S_TO_SNEW:
596 src_bi->tb = tb;
597 src_bi->bi_bh = PATH_PLAST_BUFFER (tb->tb_path);
598 src_bi->bi_parent = PATH_H_PPARENT (tb->tb_path, 0);
599 src_bi->bi_position = PATH_H_B_ITEM_ORDER (tb->tb_path, 0);
600 dest_bi->tb = tb;
601 dest_bi->bi_bh = Snew;
602 dest_bi->bi_parent = 0;
603 dest_bi->bi_position = 0;
604 *first_last = LAST_TO_FIRST;
605 break;
606
607 default:
608 reiserfs_panic (0, "vs-10250: leaf_define_dest_src_infos: shift type is unknown (%d)", shift_mode);
609 }
610 #ifdef CONFIG_REISERFS_CHECK
611 if (src_bi->bi_bh == 0 || dest_bi->bi_bh == 0) {
612 reiserfs_panic (0, "vs-10260: leaf_define_dest_src_etc: mode==%d, source (%p) or dest (%p) buffer is initialized incorrectly",
613 shift_mode, src_bi->bi_bh, dest_bi->bi_bh);
614 }
615 #endif
616 }
617
618
619
620
621 /* copy mov_num items and mov_bytes of the (mov_num-1)th item to
622 neighbor. Delete them from source */
623 int leaf_move_items (int shift_mode, struct tree_balance * tb, int mov_num, int mov_bytes, struct buffer_head * Snew)
624 {
625 int ret_value;
626 struct buffer_info dest_bi, src_bi;
627 int first_last;
628
629 leaf_define_dest_src_infos (shift_mode, tb, &dest_bi, &src_bi, &first_last, Snew);
630
631 ret_value = leaf_copy_items (&dest_bi, src_bi.bi_bh, first_last, mov_num, mov_bytes);
632
633 leaf_delete_items (&src_bi, first_last, (first_last == FIRST_TO_LAST) ? 0 : (B_NR_ITEMS(src_bi.bi_bh) - mov_num), mov_num, mov_bytes);
634
635
636 return ret_value;
637 }
638
639
640 /* Shift shift_num items (and shift_bytes of last shifted item if shift_bytes != -1)
641 from S[0] to L[0] and replace the delimiting key */
642 int leaf_shift_left (struct tree_balance * tb, int shift_num, int shift_bytes)
643 {
644 struct buffer_head * S0 = PATH_PLAST_BUFFER (tb->tb_path);
645 int i;
646
647 /* move shift_num (and shift_bytes bytes) items from S[0] to left neighbor L[0] */
648 i = leaf_move_items (LEAF_FROM_S_TO_L, tb, shift_num, shift_bytes, 0);
649
650 if ( shift_num ) {
651 if (B_NR_ITEMS (S0) == 0) { /* number of items in S[0] == 0 */
652
653 #ifdef CONFIG_REISERFS_CHECK
654 if ( shift_bytes != -1 )
655 reiserfs_panic (tb->tb_sb, "vs-10270: leaf_shift_left: S0 is empty now, but shift_bytes != -1 (%d)", shift_bytes);
656
657 if (tb->tb_mode == M_PASTE || tb->tb_mode == M_INSERT) {
658 print_cur_tb ("vs-10275");
659 reiserfs_panic (tb->tb_sb, "vs-10275: leaf_shift_left: balance condition corrupted (%c)", tb->tb_mode);
660 }
661 #endif
662
663 if (PATH_H_POSITION (tb->tb_path, 1) == 0)
664 replace_key (tb, tb->CFL[0], tb->lkey[0], PATH_H_PPARENT (tb->tb_path, 0), 0);
665
666 #if 0
667 /* change right_delimiting_key field in L0's block header */
668 copy_key (B_PRIGHT_DELIM_KEY(tb->L[0]), B_PRIGHT_DELIM_KEY (S0));
669 #endif
670 } else {
671 /* replace lkey in CFL[0] by 0-th key from S[0]; */
672 replace_key (tb, tb->CFL[0], tb->lkey[0], S0, 0);
673
674 #if 0
675 /* change right_delimiting_key field in L0's block header */
676 copy_key (B_PRIGHT_DELIM_KEY(tb->L[0]), B_N_PKEY (S0, 0));
677 #endif
678 #ifdef CONFIG_REISERFS_CHECK
679 if (shift_bytes != -1 && !(is_direntry_le_ih (B_N_PITEM_HEAD (S0, 0))
680 && !I_ENTRY_COUNT (B_N_PITEM_HEAD (S0, 0)))) {
681 if (!op_is_left_mergeable (B_N_PKEY (S0, 0), S0->b_size)) {
682 reiserfs_panic (tb->tb_sb, "vs-10280: leaf_shift_left: item must be mergeable");
683 }
684 }
685 #endif
686 }
687 }
688
689 return i;
690 }
691
692
693
694
695
696 /* CLEANING STOPPED HERE */
697
698
699
700
701 /* Shift shift_num (shift_bytes) items from S[0] to the right neighbor, and replace the delimiting key */
702 int leaf_shift_right(
703 struct tree_balance * tb,
704 int shift_num,
705 int shift_bytes
706 )
707 {
708 // struct buffer_head * S0 = PATH_PLAST_BUFFER (tb->tb_path);
709 int ret_value;
710
711 /* move shift_num (and shift_bytes) items from S[0] to right neighbor R[0] */
712 ret_value = leaf_move_items (LEAF_FROM_S_TO_R, tb, shift_num, shift_bytes, 0);
713
714 /* replace rkey in CFR[0] by the 0-th key from R[0] */
715 if (shift_num) {
716 replace_key (tb, tb->CFR[0], tb->rkey[0], tb->R[0], 0);
717
718 #if 0
719 /* change right_delimiting_key field in S0's block header */
720 copy_key (B_PRIGHT_DELIM_KEY(S0), B_N_PKEY (tb->R[0], 0));
721 #endif
722 }
723
724 return ret_value;
725 }
726
727
728
729 static void leaf_delete_items_entirely (struct buffer_info * bi,
730 int first, int del_num);
731 /* If del_bytes == -1, starting from position 'first' delete del_num items in whole in buffer CUR.
732 If not.
733 If last_first == 0. Starting from position 'first' delete del_num-1 items in whole. Delete part of body of
734 the first item. Part defined by del_bytes. Don't delete first item header
735 If last_first == 1. Starting from position 'first+1' delete del_num-1 items in whole. Delete part of body of
736 the last item . Part defined by del_bytes. Don't delete last item header.
737 */
738 void leaf_delete_items (struct buffer_info * cur_bi, int last_first,
739 int first, int del_num, int del_bytes)
740 {
741 struct buffer_head * bh;
742 int item_amount = B_NR_ITEMS (bh = cur_bi->bi_bh);
743
744 #ifdef CONFIG_REISERFS_CHECK
745 if ( !bh )
746 reiserfs_panic (0, "leaf_delete_items: 10155: bh is not defined");
747
748 if ( del_num < 0 )
749 reiserfs_panic (0, "leaf_delete_items: 10160: del_num can not be < 0. del_num==%d", del_num);
750
751 if ( first < 0 || first + del_num > item_amount )
752 reiserfs_panic (0, "leaf_delete_items: 10165: invalid number of first item to be deleted (%d) or "
753 "no so much items (%d) to delete (only %d)", first, first + del_num, item_amount);
754 #endif
755
756 if ( del_num == 0 )
757 return;
758
759 if ( first == 0 && del_num == item_amount && del_bytes == -1 ) {
760 make_empty_node (cur_bi);
761 do_balance_mark_leaf_dirty (cur_bi->tb, bh, 0);
762 return;
763 }
764
765 if ( del_bytes == -1 )
766 /* delete del_num items beginning from item in position first */
767 leaf_delete_items_entirely (cur_bi, first, del_num);
768 else {
769 if ( last_first == FIRST_TO_LAST ) {
770 /* delete del_num-1 items beginning from item in position first */
771 leaf_delete_items_entirely (cur_bi, first, del_num-1);
772
773 /* delete the part of the first item of the bh
774 do not delete item header
775 */
776 leaf_cut_from_buffer (cur_bi, 0, 0, del_bytes);
777 } else {
778 struct item_head * ih;
779 int len;
780
781 /* delete del_num-1 items beginning from item in position first+1 */
782 leaf_delete_items_entirely (cur_bi, first+1, del_num-1);
783
784 if (is_direntry_le_ih (ih = B_N_PITEM_HEAD(bh, B_NR_ITEMS(bh)-1))) /* the last item is directory */
785 /* len = numbers of directory entries in this item */
786 len = le16_to_cpu (ih->u.ih_entry_count);
787 else
788 /* len = body len of item */
789 len = le16_to_cpu (ih->ih_item_len);
790
791 /* delete the part of the last item of the bh
792 do not delete item header
793 */
794 leaf_cut_from_buffer (cur_bi, B_NR_ITEMS(bh)-1, len - del_bytes, del_bytes);
795 }
796 }
797 }
798
799
800 /* insert item into the leaf node in position before */
801 void leaf_insert_into_buf (struct buffer_info * bi, int before,
802 struct item_head * inserted_item_ih,
803 const char * inserted_item_body,
804 int zeros_number)
805 {
806 struct buffer_head * bh = bi->bi_bh;
807 int nr;
808 struct block_head * blkh;
809 struct item_head * ih;
810 int i;
811 int last_loc, unmoved_loc;
812 char * to;
813
814
815 nr = le16_to_cpu ((blkh = B_BLK_HEAD (bh))->blk_nr_item);
816
817 #ifdef CONFIG_REISERFS_CHECK
818 /* check free space */
819 if (le16_to_cpu (blkh->blk_free_space) < le16_to_cpu (inserted_item_ih->ih_item_len) + IH_SIZE)
820 reiserfs_panic (0, "leaf_insert_into_buf: 10170: "
821 "not enough free space in block %z, new item %h",
822 bh, inserted_item_ih);
823 if (zeros_number > inserted_item_ih->ih_item_len)
824 reiserfs_panic (0, "vs-10172: leaf_insert_into_buf: "
825 "zero number == %d, item length == %d", zeros_number, inserted_item_ih->ih_item_len);
826 #endif /* CONFIG_REISERFS_CHECK */
827
828
829 /* get item new item must be inserted before */
830 ih = B_N_PITEM_HEAD (bh, before);
831
832 /* prepare space for the body of new item */
833 last_loc = nr ? ih[nr - before - 1].ih_item_location : bh->b_size;
834 unmoved_loc = before ? (ih-1)->ih_item_location : bh->b_size;
835
836 memmove (bh->b_data + last_loc - inserted_item_ih->ih_item_len,
837 bh->b_data + last_loc, unmoved_loc - last_loc);
838
839 to = bh->b_data + unmoved_loc - inserted_item_ih->ih_item_len;
840 memset (to, 0, zeros_number);
841 to += zeros_number;
842
843 /* copy body to prepared space */
844 if (inserted_item_body)
845 memmove (to, inserted_item_body, inserted_item_ih->ih_item_len - zeros_number);
846 else
847 memset(to, '\0', inserted_item_ih->ih_item_len - zeros_number);
848
849 /* insert item header */
850 memmove (ih + 1, ih, IH_SIZE * (nr - before));
851 memmove (ih, inserted_item_ih, IH_SIZE);
852
853 /* change locations */
854 for (i = before; i < nr + 1; i ++)
855 ih[i-before].ih_item_location =
856 (unmoved_loc -= ih[i-before].ih_item_len);
857
858 /* sizes, free space, item number */
859 blkh->blk_nr_item = cpu_to_le16 (le16_to_cpu (blkh->blk_nr_item) + 1);
860 blkh->blk_free_space = cpu_to_le16 (le16_to_cpu (blkh->blk_free_space) -
861 (IH_SIZE + inserted_item_ih->ih_item_len));
862
863 do_balance_mark_leaf_dirty (bi->tb, bh, 1);
864
865 if (bi->bi_parent) {
866 B_N_CHILD (bi->bi_parent, bi->bi_position)->dc_size += (IH_SIZE + inserted_item_ih->ih_item_len);
867 do_balance_mark_internal_dirty (bi->tb, bi->bi_parent, 0);
868 }
869 }
870
871
872 /* paste paste_size bytes to affected_item_num-th item.
873 When item is a directory, this only prepare space for new entries */
874 void leaf_paste_in_buffer (struct buffer_info * bi, int affected_item_num,
875 int pos_in_item, int paste_size,
876 const char * body,
877 int zeros_number)
878 {
879 struct buffer_head * bh = bi->bi_bh;
880 int nr;
881 struct block_head * blkh;
882 struct item_head * ih;
883 int i;
884 int last_loc, unmoved_loc;
885
886
887 nr = le16_to_cpu ((blkh = B_BLK_HEAD(bh))->blk_nr_item);
888
889 #ifdef CONFIG_REISERFS_CHECK
890 /* check free space */
891 if (le16_to_cpu (blkh->blk_free_space) < paste_size)
892 reiserfs_panic (0, "leaf_paste_in_buffer: 10175: not enough free space: needed %d, available %d",
893 paste_size, le16_to_cpu (blkh->blk_free_space));
894 if (zeros_number > paste_size) {
895 print_cur_tb ("10177");
896 reiserfs_panic (0, "vs-10177: leaf_paste_in_buffer: zero number == %d, paste_size == %d",
897 zeros_number, paste_size);
898 }
899 #endif /* CONFIG_REISERFS_CHECK */
900
901
902 /* item to be appended */
903 ih = B_N_PITEM_HEAD(bh, affected_item_num);
904
905 last_loc = ih[nr - affected_item_num - 1].ih_item_location;
906 unmoved_loc = affected_item_num ? (ih-1)->ih_item_location : bh->b_size;
907
908 /* prepare space */
909 memmove (bh->b_data + last_loc - paste_size, bh->b_data + last_loc,
910 unmoved_loc - last_loc);
911
912
913 /* change locations */
914 for (i = affected_item_num; i < nr; i ++)
915 ih[i-affected_item_num].ih_item_location -= paste_size;
916
917 if ( body ) {
918 if (!is_direntry_le_ih (ih)) {
919 if (!pos_in_item) {
920 /* shift data to right */
921 memmove (bh->b_data + ih->ih_item_location + paste_size,
922 bh->b_data + ih->ih_item_location, ih->ih_item_len);
923 /* paste data in the head of item */
924 memset (bh->b_data + ih->ih_item_location, 0, zeros_number);
925 memcpy (bh->b_data + ih->ih_item_location + zeros_number, body, paste_size - zeros_number);
926 } else {
927 memset (bh->b_data + unmoved_loc - paste_size, 0, zeros_number);
928 memcpy (bh->b_data + unmoved_loc - paste_size + zeros_number, body, paste_size - zeros_number);
929 }
930 }
931 }
932 else
933 memset(bh->b_data + unmoved_loc - paste_size,'\0',paste_size);
934
935 ih->ih_item_len += paste_size;
936
937 /* change free space */
938 blkh->blk_free_space = cpu_to_le16 (le16_to_cpu (blkh->blk_free_space) - paste_size);
939
940 do_balance_mark_leaf_dirty (bi->tb, bh, 0);
941
942 if (bi->bi_parent) {
943 B_N_CHILD (bi->bi_parent, bi->bi_position)->dc_size += paste_size;
944 do_balance_mark_internal_dirty (bi->tb, bi->bi_parent, 0);
945 }
946 }
947
948
949 /* cuts DEL_COUNT entries beginning from FROM-th entry. Directory item
950 does not have free space, so it moves DEHs and remaining records as
951 necessary. Return value is size of removed part of directory item
952 in bytes. */
953 static int leaf_cut_entries (
954 struct buffer_head * bh,
955 struct item_head * ih,
956 int from,
957 int del_count
958 )
959 {
960 char * item;
961 struct reiserfs_de_head * deh;
962 int prev_record_offset; /* offset of record, that is (from-1)th */
963 char * prev_record; /* */
964 int cut_records_len; /* length of all removed records */
965 int i;
966
967
968 #ifdef CONFIG_REISERFS_CHECK
969 /* make sure, that item is directory and there are enough entries to
970 remove */
971 if (!is_direntry_le_ih (ih))
972 reiserfs_panic (0, "leaf_cut_entries: 10180: item is not directory item");
973
974 if (I_ENTRY_COUNT(ih) < from + del_count)
975 reiserfs_panic (0, "leaf_cut_entries: 10185: item contains not enough entries: entry_cout = %d, from = %d, to delete = %d",
976 I_ENTRY_COUNT(ih), from, del_count);
977 #endif
978
979 if (del_count == 0)
980 return 0;
981
982 /* first byte of item */
983 item = bh->b_data + ih->ih_item_location;
984
985 /* entry head array */
986 deh = B_I_DEH (bh, ih);
987
988 /* first byte of remaining entries, those are BEFORE cut entries
989 (prev_record) and length of all removed records (cut_records_len) */
990 prev_record_offset = (from ? deh[from - 1].deh_location : ih->ih_item_len);
991 cut_records_len = prev_record_offset/*from_record*/ - deh[from + del_count - 1].deh_location;
992 prev_record = item + prev_record_offset;
993
994
995 /* adjust locations of remaining entries */
996 for (i = I_ENTRY_COUNT(ih) - 1; i > from + del_count - 1; i --)
997 deh[i].deh_location -= (DEH_SIZE * del_count);
998
999 for (i = 0; i < from; i ++)
1000 deh[i].deh_location -= DEH_SIZE * del_count + cut_records_len;
1001
1002 I_ENTRY_COUNT(ih) -= del_count;
1003
1004 /* shift entry head array and entries those are AFTER removed entries */
1005 memmove ((char *)(deh + from),
1006 deh + from + del_count,
1007 prev_record - cut_records_len - (char *)(deh + from + del_count));
1008
1009 /* shift records, those are BEFORE removed entries */
1010 memmove (prev_record - cut_records_len - DEH_SIZE * del_count,
1011 prev_record, item + ih->ih_item_len - prev_record);
1012
1013 return DEH_SIZE * del_count + cut_records_len;
1014 }
1015
1016
1017 /* when cut item is part of regular file
1018 pos_in_item - first byte that must be cut
1019 cut_size - number of bytes to be cut beginning from pos_in_item
1020
1021 when cut item is part of directory
1022 pos_in_item - number of first deleted entry
1023 cut_size - count of deleted entries
1024 */
1025 void leaf_cut_from_buffer (struct buffer_info * bi, int cut_item_num,
1026 int pos_in_item, int cut_size)
1027 {
1028 int nr;
1029 struct buffer_head * bh = bi->bi_bh;
1030 struct block_head * blkh;
1031 struct item_head * ih;
1032 int last_loc, unmoved_loc;
1033 int i;
1034
1035 nr = le16_to_cpu ((blkh = B_BLK_HEAD (bh))->blk_nr_item);
1036
1037 /* item head of truncated item */
1038 ih = B_N_PITEM_HEAD (bh, cut_item_num);
1039
1040 if (is_direntry_le_ih (ih)) {
1041 /* first cut entry ()*/
1042 cut_size = leaf_cut_entries (bh, ih, pos_in_item, cut_size);
1043 if (pos_in_item == 0) {
1044 /* change key */
1045 #ifdef CONFIG_REISERFS_CHECK
1046 if (cut_item_num)
1047 reiserfs_panic (0, "leaf_cut_from_buffer: 10190: "
1048 "when 0-th enrty of item is cut, that item must be first in the node, not %d-th", cut_item_num);
1049 #endif
1050 /* change item key by key of first entry in the item */
1051 set_le_ih_k_offset (ih, le32_to_cpu (B_I_DEH (bh, ih)->deh_offset));
1052 /*memcpy (&ih->ih_key.k_offset, &(B_I_DEH (bh, ih)->deh_offset), SHORT_KEY_SIZE);*/
1053 }
1054 } else {
1055 /* item is direct or indirect */
1056 #ifdef CONFIG_REISERFS_CHECK
1057 if (is_statdata_le_ih (ih))
1058 reiserfs_panic (0, "leaf_cut_from_buffer: 10195: item is stat data");
1059
1060 if (pos_in_item && pos_in_item + cut_size != le16_to_cpu (ih->ih_item_len) )
1061 reiserfs_panic (0, "cut_from_buf: 10200: invalid offset (%lu) or trunc_size (%lu) or ih_item_len (%lu)",
1062 pos_in_item, cut_size, le16_to_cpu (ih->ih_item_len));
1063 #endif
1064
1065 /* shift item body to left if cut is from the head of item */
1066 if (pos_in_item == 0) {
1067 memmove (bh->b_data + le16_to_cpu (ih->ih_item_location), bh->b_data + le16_to_cpu (ih->ih_item_location) + cut_size,
1068 le16_to_cpu (ih->ih_item_len) - cut_size);
1069
1070 /* change key of item */
1071 if (is_direct_le_ih (ih))
1072 set_le_ih_k_offset (ih, le_ih_k_offset (ih) + cut_size);
1073 else {
1074 set_le_ih_k_offset (ih, le_ih_k_offset (ih) + (cut_size / UNFM_P_SIZE) * bh->b_size);
1075 #ifdef CONFIG_REISERFS_CHECK
1076 if ( le16_to_cpu (ih->ih_item_len) == cut_size && get_ih_free_space (ih) )
1077 reiserfs_panic (0, "leaf_cut_from_buf: 10205: invalid ih_free_space (%h)", ih);
1078 #endif
1079 }
1080 }
1081 }
1082
1083
1084 /* location of the last item */
1085 last_loc = le16_to_cpu (ih[nr - cut_item_num - 1].ih_item_location);
1086
1087 /* location of the item, which is remaining at the same place */
1088 unmoved_loc = cut_item_num ? le16_to_cpu ((ih-1)->ih_item_location) : bh->b_size;
1089
1090
1091 /* shift */
1092 memmove (bh->b_data + last_loc + cut_size, bh->b_data + last_loc,
1093 unmoved_loc - last_loc - cut_size);
1094
1095 /* change item length */
1096 /* ih->ih_item_len -= cut_size;*/
1097 ih->ih_item_len = cpu_to_le16 (le16_to_cpu (ih->ih_item_len) - cut_size);
1098
1099 if (is_indirect_le_ih (ih)) {
1100 if (pos_in_item)
1101 set_ih_free_space (ih, 0);
1102 }
1103
1104 /* change locations */
1105 for (i = cut_item_num; i < nr; i ++)
1106 /* ih[i-cut_item_num].ih_item_location += cut_size;*/
1107 ih[i-cut_item_num].ih_item_location =
1108 cpu_to_le16 (le16_to_cpu (ih[i-cut_item_num].ih_item_location) + cut_size);
1109
1110 /* size, free space */
1111 blkh->blk_free_space = cpu_to_le16 (le16_to_cpu (blkh->blk_free_space) + cut_size);
1112
1113 do_balance_mark_leaf_dirty (bi->tb, bh, 0);
1114
1115 if (bi->bi_parent) {
1116 B_N_CHILD (bi->bi_parent, bi->bi_position)->dc_size -= cut_size;
1117 do_balance_mark_internal_dirty (bi->tb, bi->bi_parent, 0);
1118 }
1119 }
1120
1121
1122 /* delete del_num items from buffer starting from the first'th item */
1123 static void leaf_delete_items_entirely (struct buffer_info * bi,
1124 int first, int del_num)
1125 {
1126 struct buffer_head * bh = bi->bi_bh;
1127 int nr;
1128 int i, j;
1129 int last_loc, last_removed_loc;
1130 struct block_head * blkh;
1131 struct item_head * ih;
1132
1133 #ifdef CONFIG_REISERFS_CHECK
1134 if (bh == NULL)
1135 reiserfs_panic (0, "leaf_delete_items_entirely: 10210: buffer is 0");
1136
1137 if (del_num < 0)
1138 reiserfs_panic (0, "leaf_delete_items_entirely: 10215: del_num less than 0 (%d)", del_num);
1139 #endif /* CONFIG_REISERFS_CHECK */
1140
1141 if (del_num == 0)
1142 return;
1143
1144 nr = le16_to_cpu ((blkh = B_BLK_HEAD(bh))->blk_nr_item);
1145
1146 #ifdef CONFIG_REISERFS_CHECK
1147 if (first < 0 || first + del_num > nr)
1148 reiserfs_panic (0, "leaf_delete_items_entirely: 10220: first=%d, number=%d, there is %d items", first, del_num, nr);
1149 #endif /* CONFIG_REISERFS_CHECK */
1150
1151 if (first == 0 && del_num == nr) {
1152 /* this does not work */
1153 make_empty_node (bi);
1154
1155 do_balance_mark_leaf_dirty (bi->tb, bh, 0);
1156 return;
1157 }
1158
1159 ih = B_N_PITEM_HEAD (bh, first);
1160
1161 /* location of unmovable item */
1162 j = (first == 0) ? bh->b_size : (ih-1)->ih_item_location;
1163
1164 /* delete items */
1165 last_loc = ih[nr-1-first].ih_item_location;
1166 last_removed_loc = ih[del_num-1].ih_item_location;
1167
1168 memmove (bh->b_data + last_loc + j - last_removed_loc,
1169 bh->b_data + last_loc, last_removed_loc - last_loc);
1170
1171 /* delete item headers */
1172 memmove (ih, ih + del_num, (nr - first - del_num) * IH_SIZE);
1173
1174 /* change item location */
1175 for (i = first; i < nr - del_num; i ++)
1176 ih[i-first].ih_item_location += j - last_removed_loc;
1177
1178 /* sizes, item number */
1179 blkh->blk_nr_item = cpu_to_le16 (le16_to_cpu (blkh->blk_nr_item) - del_num);
1180 blkh->blk_free_space = cpu_to_le16 (le16_to_cpu (blkh->blk_free_space) + (j - last_removed_loc + IH_SIZE * del_num));
1181
1182 do_balance_mark_leaf_dirty (bi->tb, bh, 0);
1183
1184 if (bi->bi_parent) {
1185 B_N_CHILD (bi->bi_parent, bi->bi_position)->dc_size -= j - last_removed_loc + IH_SIZE * del_num;
1186 do_balance_mark_internal_dirty (bi->tb, bi->bi_parent, 0);
1187 }
1188 }
1189
1190
1191
1192
1193
1194 /* paste new_entry_count entries (new_dehs, records) into position before to item_num-th item */
1195 void leaf_paste_entries (
1196 struct buffer_head * bh,
1197 int item_num,
1198 int before,
1199 int new_entry_count,
1200 struct reiserfs_de_head * new_dehs,
1201 const char * records,
1202 int paste_size
1203 )
1204 {
1205 struct item_head * ih;
1206 char * item;
1207 struct reiserfs_de_head * deh;
1208 char * insert_point;
1209 int i, old_entry_num;
1210
1211 if (new_entry_count == 0)
1212 return;
1213
1214 ih = B_N_PITEM_HEAD(bh, item_num);
1215
1216 #ifdef CONFIG_REISERFS_CHECK
1217 /* make sure, that item is directory, and there are enough records in it */
1218 if (!is_direntry_le_ih (ih))
1219 reiserfs_panic (0, "leaf_paste_entries: 10225: item is not directory item");
1220
1221 if (I_ENTRY_COUNT (ih) < before)
1222 reiserfs_panic (0, "leaf_paste_entries: 10230: there are no entry we paste entries before. entry_count = %d, before = %d",
1223 I_ENTRY_COUNT (ih), before);
1224 #endif
1225
1226
1227 /* first byte of dest item */
1228 item = bh->b_data + ih->ih_item_location;
1229
1230 /* entry head array */
1231 deh = B_I_DEH (bh, ih);
1232
1233 /* new records will be pasted at this point */
1234 insert_point = item + (before ? deh[before - 1].deh_location : (ih->ih_item_len - paste_size));
1235
1236 /* adjust locations of records that will be AFTER new records */
1237 for (i = I_ENTRY_COUNT(ih) - 1; i >= before; i --)
1238 deh[i].deh_location += DEH_SIZE * new_entry_count;
1239
1240 /* adjust locations of records that will be BEFORE new records */
1241 for (i = 0; i < before; i ++)
1242 deh[i].deh_location += paste_size;
1243
1244 old_entry_num = I_ENTRY_COUNT(ih);
1245 I_ENTRY_COUNT(ih) += new_entry_count;
1246
1247 /* prepare space for pasted records */
1248 memmove (insert_point + paste_size, insert_point, item + (ih->ih_item_len - paste_size) - insert_point);
1249
1250 /* copy new records */
1251 memcpy (insert_point + DEH_SIZE * new_entry_count, records,
1252 paste_size - DEH_SIZE * new_entry_count);
1253
1254 /* prepare space for new entry heads */
1255 deh += before;
1256 memmove ((char *)(deh + new_entry_count), deh, insert_point - (char *)deh);
1257
1258 /* copy new entry heads */
1259 deh = (struct reiserfs_de_head *)((char *)deh);
1260 memcpy (deh, new_dehs, DEH_SIZE * new_entry_count);
1261
1262 /* set locations of new records */
1263 for (i = 0; i < new_entry_count; i ++)
1264 deh[i].deh_location +=
1265 (- new_dehs[new_entry_count - 1].deh_location + insert_point + DEH_SIZE * new_entry_count - item);
1266
1267
1268 /* change item key if neccessary (when we paste before 0-th entry */
1269 if (!before)
1270 {
1271 #ifdef CONFIG_REISERFS_CHECK
1272 /*
1273 if ( old_entry_num && COMP_SHORT_KEYS ((unsigned long *)&ih->ih_key.k_offset,
1274 &(new_dehs->deh_offset)) <= 0)
1275 reiserfs_panic (0, "leaf_paste_entries: 10235: new key must be less, that old key");
1276 */
1277 #endif
1278 set_le_ih_k_offset (ih, le32_to_cpu (new_dehs->deh_offset));
1279 /* memcpy (&ih->ih_key.k_offset,
1280 &new_dehs->deh_offset, SHORT_KEY_SIZE);*/
1281 }
1282
1283 #ifdef CONFIG_REISERFS_CHECK
1284 {
1285 int prev, next;
1286 /* check record locations */
1287 deh = B_I_DEH (bh, ih);
1288 for (i = 0; i < I_ENTRY_COUNT(ih); i ++) {
1289 next = (i < I_ENTRY_COUNT(ih) - 1) ? deh[i + 1].deh_location : 0;
1290 prev = (i != 0) ? deh[i - 1].deh_location : 0;
1291
1292 if (prev && prev <= deh[i].deh_location)
1293 reiserfs_warning ("vs-10240: leaf_paste_entries: directory item (%h) corrupted (prev %a, cur(%d) %a)\n",
1294 ih, deh + i - 1, i, deh + i);
1295 if (next && next >= deh[i].deh_location)
1296 reiserfs_warning ("vs-10250: leaf_paste_entries: directory item (%h) corrupted (cur(%d) %a, next %a)\n",
1297 ih, i, deh + i, deh + i + 1);
1298 }
1299 }
1300 #endif
1301
1302 }
1303
1304
1305
1306