| /* |
| * Copyright 1996-2003 by Hans Reiser, licensing governed by |
| * reiserfsprogs/README |
| */ |
| |
| #include "includes.h" |
| |
| |
| /* these are used in do_balance.c */ |
| |
| /* leaf_move_items |
| leaf_shift_left |
| leaf_shift_right |
| leaf_delete_items |
| leaf_insert_into_buf |
| leaf_paste_in_buffer |
| leaf_cut_from_buffer |
| leaf_paste_entries |
| */ |
| |
| |
| extern struct tree_balance init_tb; |
| extern int init_item_pos; |
| extern int init_pos_in_item; |
| extern int init_mode; |
| |
| |
| |
| /* copy copy_count entries from source directory item to dest buffer (creating new item if needed) */ |
| static void leaf_copy_dir_entries (reiserfs_filsys_t * fs, |
| struct buffer_info * dest_bi, struct buffer_head * source, |
| int last_first, int item_num, int from, int copy_count) |
| { |
| struct buffer_head * dest = dest_bi->bi_bh; |
| int item_num_in_dest; /* either the number of target item, |
| or if we must create a new item, |
| the number of the item we will |
| create it next to */ |
| struct item_head * ih; |
| struct reiserfs_de_head * deh; |
| int copy_records_len; /* length of all records in item to be copied */ |
| char * records; |
| |
| ih = B_N_PITEM_HEAD (source, item_num); |
| |
| /* length of all record to be copied and first byte of the last of them */ |
| deh = B_I_DEH (source, ih); |
| if (copy_count) { |
| copy_records_len = (from ? get_deh_location (&deh[from - 1]) : get_ih_item_len (ih)) - |
| get_deh_location (&deh[from + copy_count - 1]); |
| records = source->b_data + get_ih_location (ih) + get_deh_location (&deh[from + copy_count - 1]); |
| } else { |
| copy_records_len = 0; |
| records = 0; |
| } |
| |
| /* when copy last to first, dest buffer can contain 0 items */ |
| item_num_in_dest = (last_first == LAST_TO_FIRST) ? (( B_NR_ITEMS(dest) ) ? 0 : -1) : (B_NR_ITEMS(dest) - 1); |
| |
| /* if there are no items in dest or the first/last item in dest is not item of the same directory */ |
| if ( (item_num_in_dest == - 1) || |
| (last_first == FIRST_TO_LAST && are_items_mergeable (B_N_PITEM_HEAD (dest, item_num_in_dest), ih, dest->b_size) == 0) || |
| (last_first == LAST_TO_FIRST && are_items_mergeable (ih, B_N_PITEM_HEAD (dest, item_num_in_dest), dest->b_size) == 0)) { |
| /* create new item in dest */ |
| struct item_head new_ih; |
| |
| /* form item header */ |
| memcpy (&new_ih.ih_key, &ih->ih_key, KEY_SIZE); |
| |
| /* calculate item len */ |
| set_ih_item_len (&new_ih, DEH_SIZE * copy_count + copy_records_len); |
| set_ih_entry_count (&new_ih, 0); |
| |
| if (last_first == LAST_TO_FIRST) { |
| /* form key by the following way */ |
| if (from < get_ih_entry_count (ih)) { |
| set_key_offset_v1 (&new_ih.ih_key, get_deh_offset (&deh[from])); |
| } else { |
| /* no entries will be copied to this item in this function */ |
| set_key_offset_v1 (&new_ih.ih_key, MAX_KEY1_OFFSET); |
| } |
| set_key_uniqueness (&new_ih.ih_key, DIRENTRY_UNIQUENESS); |
| } |
| set_ih_key_format (&new_ih, get_ih_key_format (ih)); |
| set_ih_flags (&new_ih, get_ih_flags (ih)); |
| |
| /* insert item into dest buffer */ |
| leaf_insert_into_buf (fs, dest_bi, (last_first == LAST_TO_FIRST) ? 0 : B_NR_ITEMS(dest), &new_ih, NULL, 0); |
| } else { |
| /* prepare space for entries */ |
| leaf_paste_in_buffer (fs, dest_bi, (last_first == FIRST_TO_LAST) ? (B_NR_ITEMS(dest) - 1) : 0, 0xffff /*MAX_US_INT */, |
| DEH_SIZE * copy_count + copy_records_len, records, 0); |
| } |
| |
| item_num_in_dest = (last_first == FIRST_TO_LAST) ? (B_NR_ITEMS(dest)-1) : 0; |
| |
| leaf_paste_entries (dest_bi->bi_bh, item_num_in_dest, |
| (last_first == FIRST_TO_LAST) ? get_ih_entry_count (B_N_PITEM_HEAD (dest, item_num_in_dest)) : 0, |
| copy_count, deh + from, records, |
| DEH_SIZE * copy_count + copy_records_len |
| ); |
| } |
| |
| |
| /* Copy the first (if last_first == FIRST_TO_LAST) or last (last_first == LAST_TO_FIRST) item or |
| part of it or nothing (see the return 0 below) from SOURCE to the end |
| (if last_first) or beginning (!last_first) of the DEST */ |
| /* returns 1 if anything was copied, else 0 */ |
| static int leaf_copy_boundary_item (reiserfs_filsys_t * fs, |
| struct buffer_info * dest_bi, struct buffer_head * src, int last_first, |
| int bytes_or_entries) |
| { |
| struct buffer_head * dest = dest_bi->bi_bh; |
| int dest_nr_item, src_nr_item; /* number of items in the source and destination buffers */ |
| struct item_head * ih; |
| struct item_head * dih; |
| |
| dest_nr_item = B_NR_ITEMS(dest); |
| |
| if ( last_first == FIRST_TO_LAST ) { |
| /* if ( DEST is empty or first item of SOURCE and last item of DEST are the items of different objects |
| or of different types ) then there is no need to treat this item differently from the other items |
| that we copy, so we return */ |
| ih = B_N_PITEM_HEAD (src, 0); |
| dih = B_N_PITEM_HEAD (dest, dest_nr_item - 1); |
| if (!dest_nr_item || (are_items_mergeable (dih, ih, src->b_size) == 0)) |
| /* there is nothing to merge */ |
| return 0; |
| |
| if ( I_IS_DIRECTORY_ITEM(ih) ) { |
| if ( bytes_or_entries == -1 ) |
| /* copy all entries to dest */ |
| bytes_or_entries = get_ih_entry_count(ih); |
| leaf_copy_dir_entries (fs, dest_bi, src, FIRST_TO_LAST, 0, 0, bytes_or_entries); |
| return 1; |
| } |
| |
| /* copy part of the body of the first item of SOURCE to the end of the body of the last item of the DEST |
| part defined by 'bytes_or_entries'; if bytes_or_entries == -1 copy whole body; don't create new item header |
| */ |
| if ( bytes_or_entries == -1 ) |
| bytes_or_entries = get_ih_item_len (ih); |
| |
| /* merge first item (or its part) of src buffer with the last |
| item of dest buffer. Both are of the same file */ |
| leaf_paste_in_buffer (fs, dest_bi, dest_nr_item - 1, get_ih_item_len (dih), |
| bytes_or_entries, B_I_PITEM(src,ih), 0); |
| |
| if (I_IS_INDIRECT_ITEM(dih)) { |
| if (bytes_or_entries == get_ih_item_len (ih)) |
| //dih->u.ih_free_space = ih->u.ih_free_space; |
| set_ih_free_space (dih, get_ih_free_space (ih)); |
| } |
| |
| return 1; |
| } |
| |
| |
| /* copy boundary item to right (last_first == LAST_TO_FIRST) */ |
| |
| /* ( DEST is empty or last item of SOURCE and first item of DEST |
| are the items of different object or of different types ) |
| */ |
| src_nr_item = B_NR_ITEMS (src); |
| ih = B_N_PITEM_HEAD (src, src_nr_item - 1); |
| dih = B_N_PITEM_HEAD (dest, 0); |
| |
| if (!dest_nr_item || are_items_mergeable (ih, dih, src->b_size) == 0) |
| return 0; |
| |
| if ( I_IS_DIRECTORY_ITEM(ih)) { |
| if ( bytes_or_entries == -1 ) |
| /* bytes_or_entries = entries number in last item body of SOURCE */ |
| bytes_or_entries = get_ih_entry_count(ih); |
| |
| leaf_copy_dir_entries (fs, dest_bi, src, LAST_TO_FIRST, src_nr_item - 1, get_ih_entry_count(ih) - bytes_or_entries, |
| bytes_or_entries); |
| return 1; |
| } |
| |
| /* copy part of the body of the last item of SOURCE to the begin of the body of the first item of the DEST; |
| part defined by 'bytes_or_entries'; if byte_or_entriess == -1 copy whole body; change first item key of the DEST; |
| don't create new item header |
| */ |
| |
| if ( bytes_or_entries == -1 ) { |
| /* bytes_or_entries = length of last item body of SOURCE */ |
| bytes_or_entries = get_ih_item_len (ih); |
| |
| /* change first item key of the DEST */ |
| //dih->ih_key.k_offset = ih->ih_key.k_offset; |
| set_offset (key_format (&dih->ih_key), &dih->ih_key, get_offset (&ih->ih_key)); |
| |
| /* item becomes non-mergeable */ |
| /* or mergeable if left item was */ |
| //dih->ih_key.k_uniqueness = ih->ih_key.k_uniqueness; |
| set_type (key_format (&dih->ih_key), &dih->ih_key, get_type (&ih->ih_key)); |
| } else { |
| /* merge to right only part of item */ |
| /* change first item key of the DEST */ |
| if ( I_IS_DIRECT_ITEM(dih) ) { |
| //dih->ih_key.k_offset -= bytes_or_entries; |
| set_offset (key_format (&dih->ih_key), &dih->ih_key, get_offset (&dih->ih_key) - bytes_or_entries); |
| } else { |
| //dih->ih_key.k_offset -= ((bytes_or_entries/UNFM_P_SIZE)*dest->b_size); |
| set_offset (key_format (&dih->ih_key), &dih->ih_key, |
| get_offset (&dih->ih_key) - ((bytes_or_entries/UNFM_P_SIZE)*dest->b_size)); |
| } |
| } |
| |
| leaf_paste_in_buffer (fs, dest_bi, 0, 0, bytes_or_entries, B_I_PITEM(src,ih) + get_ih_item_len (ih) - bytes_or_entries, 0); |
| return 1; |
| } |
| |
| |
| /* copy cpy_mun items from buffer src to buffer dest |
| * last_first == FIRST_TO_LAST means, that we copy cpy_num items beginning from first-th item in src to tail of dest |
| * last_first == LAST_TO_FIRST means, that we copy cpy_num items beginning from first-th item in src to head of dest |
| */ |
| static void leaf_copy_items_entirely (reiserfs_filsys_t * fs, struct buffer_info * dest_bi, |
| struct buffer_head * src, int last_first, |
| int first, int cpy_num) |
| { |
| struct buffer_head * dest; |
| int nr; |
| int dest_before; |
| int last_loc, last_inserted_loc, location; |
| int i, j; |
| struct block_head * blkh; |
| struct item_head * ih; |
| |
| dest = dest_bi->bi_bh; |
| |
| if (cpy_num == 0) |
| return; |
| |
| blkh = B_BLK_HEAD(dest); |
| nr = get_blkh_nr_items (blkh); |
| |
| /* we will insert items before 0-th or nr-th item in dest buffer. It depends of last_first parameter */ |
| dest_before = (last_first == LAST_TO_FIRST) ? 0 : nr; |
| |
| /* location of head of first new item */ |
| ih = B_N_PITEM_HEAD (dest, dest_before); |
| |
| /* prepare space for headers */ |
| memmove (ih + cpy_num, ih, (nr-dest_before) * IH_SIZE); |
| |
| /* copy item headers */ |
| memcpy (ih, B_N_PITEM_HEAD (src, first), cpy_num * IH_SIZE); |
| |
| set_blkh_free_space (blkh, get_blkh_free_space (blkh) - IH_SIZE * cpy_num); |
| |
| /* location of unmovable item */ |
| j = location = (dest_before == 0) ? dest->b_size : get_ih_location (ih-1); |
| for (i = dest_before; i < nr + cpy_num; i ++) { |
| location -= get_ih_item_len (&ih[i-dest_before]); |
| set_ih_location (&ih[i-dest_before], location); |
| } |
| |
| /* prepare space for items */ |
| last_loc = get_ih_location (&ih[nr+cpy_num-1-dest_before]); |
| last_inserted_loc = get_ih_location (&ih[cpy_num-1]); |
| |
| /* check free space */ |
| memmove (dest->b_data + last_loc, |
| dest->b_data + last_loc + j - last_inserted_loc, |
| last_inserted_loc - last_loc); |
| |
| /* copy items */ |
| memcpy (dest->b_data + last_inserted_loc, B_N_PITEM(src,(first + cpy_num - 1)), |
| j - last_inserted_loc); |
| |
| /* sizes, item number */ |
| set_blkh_nr_items (blkh, get_blkh_nr_items (blkh) + cpy_num); |
| set_blkh_free_space (blkh, |
| get_blkh_free_space (blkh) - (j - last_inserted_loc)); |
| |
| mark_buffer_dirty (dest); |
| |
| if (dest_bi->bi_parent) { |
| struct disk_child * dc; |
| dc = B_N_CHILD (dest_bi->bi_parent, dest_bi->bi_position); |
| set_dc_child_size (dc, get_dc_child_size (dc) + j - last_inserted_loc + IH_SIZE * cpy_num); |
| mark_buffer_dirty(dest_bi->bi_parent); |
| } |
| } |
| |
| |
| /* This function splits the (liquid) item into two items (useful when |
| shifting part of an item into another node.) */ |
| static void leaf_item_bottle (reiserfs_filsys_t * fs, |
| struct buffer_info * dest_bi, struct buffer_head * src, int last_first, |
| int item_num, int cpy_bytes) |
| { |
| struct buffer_head * dest = dest_bi->bi_bh; |
| struct item_head * ih; |
| |
| if ( last_first == FIRST_TO_LAST ) { |
| /* if ( if item in position item_num in buffer SOURCE is directory item ) */ |
| if (I_IS_DIRECTORY_ITEM(ih = B_N_PITEM_HEAD(src,item_num))) |
| leaf_copy_dir_entries (fs, dest_bi, src, FIRST_TO_LAST, item_num, 0, cpy_bytes); |
| else { |
| struct item_head n_ih; |
| |
| /* copy part of the body of the item number 'item_num' of SOURCE to the end of the DEST |
| part defined by 'cpy_bytes'; create new item header; change old item_header (????); |
| n_ih = new item_header; |
| */ |
| memcpy (&n_ih, ih, IH_SIZE); |
| set_ih_item_len (&n_ih, cpy_bytes); |
| if (I_IS_INDIRECT_ITEM(ih)) { |
| //n_ih.u.ih_free_space = 0; |
| set_ih_free_space (&n_ih, 0);; |
| } |
| |
| //n_ih.ih_version = ih->ih_version; |
| set_ih_key_format (&n_ih, get_ih_key_format (ih)); |
| set_ih_flags (&n_ih, get_ih_flags (ih)); |
| leaf_insert_into_buf (fs, dest_bi, B_NR_ITEMS(dest), &n_ih, B_N_PITEM (src, item_num), 0); |
| } |
| } else { |
| /* if ( if item in position item_num in buffer SOURCE is directory item ) */ |
| if (I_IS_DIRECTORY_ITEM(ih = B_N_PITEM_HEAD (src, item_num))) |
| leaf_copy_dir_entries (fs, dest_bi, src, LAST_TO_FIRST, item_num, get_ih_entry_count(ih) - cpy_bytes, cpy_bytes); |
| else { |
| struct item_head n_ih; |
| |
| /* copy part of the body of the item number 'item_num' of SOURCE to the begin of the DEST |
| part defined by 'cpy_bytes'; create new item header; |
| n_ih = new item_header; |
| */ |
| memcpy (&n_ih, ih, SHORT_KEY_SIZE); |
| |
| if (I_IS_DIRECT_ITEM(ih)) { |
| //n_ih.ih_key.k_offset = ih->ih_key.k_offset + ih->ih_item_len - cpy_bytes; |
| set_offset (key_format (&ih->ih_key), &n_ih.ih_key, get_offset (&ih->ih_key) + get_ih_item_len (ih) - cpy_bytes); |
| //n_ih.ih_key.k_uniqueness = TYPE_DIRECT; |
| set_type (key_format (&ih->ih_key), &n_ih.ih_key, TYPE_DIRECT); |
| //n_ih.u.ih_free_space = USHRT_MAX; |
| set_ih_free_space (&n_ih, USHRT_MAX); |
| } else { |
| /* indirect item */ |
| //n_ih.ih_key.k_offset = ih->ih_key.k_offset + (ih->ih_item_len - cpy_bytes) / UNFM_P_SIZE * dest->b_size; |
| set_offset (key_format (&ih->ih_key), &n_ih.ih_key, |
| get_offset (&ih->ih_key) + (get_ih_item_len (ih) - cpy_bytes) / UNFM_P_SIZE * dest->b_size); |
| //n_ih.ih_key.k_uniqueness = TYPE_INDIRECT; |
| set_type (key_format (&ih->ih_key), &n_ih.ih_key, TYPE_INDIRECT); |
| //n_ih.u.ih_free_space = ih->u.ih_free_space; |
| set_ih_free_space (&n_ih, get_ih_free_space (ih)); |
| } |
| |
| /* set item length */ |
| set_ih_item_len (&n_ih, cpy_bytes); |
| //n_ih.ih_version = ih->ih_version; |
| set_ih_key_format (&n_ih, get_ih_key_format (ih)); |
| set_ih_flags (&n_ih, get_ih_flags (ih)); |
| leaf_insert_into_buf (fs, dest_bi, 0, &n_ih, B_N_PITEM(src,item_num) + get_ih_item_len (ih) - cpy_bytes, 0); |
| } |
| } |
| } |
| |
| |
| /* If cpy_bytes equals minus one than copy cpy_num whole items from SOURCE to DEST. |
| If cpy_bytes not equal to minus one than copy cpy_num-1 whole items from SOURCE to DEST. |
| From last item copy cpy_num bytes for regular item and cpy_num directory entries for |
| directory item. */ |
| static int leaf_copy_items (reiserfs_filsys_t * fs, |
| struct buffer_info * dest_bi, struct buffer_head * src, |
| int last_first, int cpy_num, |
| int cpy_bytes) |
| { |
| struct buffer_head * dest; |
| int pos, i, src_nr_item, bytes; |
| |
| dest = dest_bi->bi_bh; |
| if ( cpy_num == 0 ) |
| return 0; |
| |
| if ( last_first == FIRST_TO_LAST ) { |
| /* copy items to left */ |
| pos = 0; |
| if ( cpy_num == 1 ) |
| bytes = cpy_bytes; |
| else |
| bytes = -1; |
| |
| /* copy the first item or it part or nothing to the end of the DEST (i = leaf_copy_boundary_item(DEST,SOURCE,0,bytes)) */ |
| i = leaf_copy_boundary_item (fs, dest_bi, src, FIRST_TO_LAST, bytes); |
| cpy_num -= i; |
| if ( cpy_num == 0 ) |
| return i; |
| pos += i; |
| if ( cpy_bytes == -1 ) |
| /* copy first cpy_num items starting from position 'pos' of SOURCE to end of DEST */ |
| leaf_copy_items_entirely(fs, dest_bi, src, FIRST_TO_LAST, pos, cpy_num); |
| else { |
| /* copy first cpy_num-1 items starting from position 'pos-1' of the SOURCE to the end of the DEST */ |
| leaf_copy_items_entirely(fs, dest_bi, src, FIRST_TO_LAST, pos, cpy_num-1); |
| |
| /* copy part of the item which number is cpy_num+pos-1 to the end of the DEST */ |
| leaf_item_bottle (fs, dest_bi, src, FIRST_TO_LAST, cpy_num+pos-1, cpy_bytes); |
| } |
| } else { |
| /* copy items to right */ |
| src_nr_item = B_NR_ITEMS (src); |
| if ( cpy_num == 1 ) |
| bytes = cpy_bytes; |
| else |
| bytes = -1; |
| |
| /* copy the last item or it part or nothing to the begin of the DEST (i = leaf_copy_boundary_item(DEST,SOURCE,1,bytes)); */ |
| i = leaf_copy_boundary_item (fs, dest_bi, src, LAST_TO_FIRST, bytes); |
| |
| cpy_num -= i; |
| if ( cpy_num == 0 ) |
| return i; |
| |
| pos = src_nr_item - cpy_num - i; |
| if ( cpy_bytes == -1 ) { |
| /* starting from position 'pos' copy last cpy_num items of SOURCE to begin of DEST */ |
| leaf_copy_items_entirely(fs, dest_bi, src, LAST_TO_FIRST, pos, cpy_num); |
| } else { |
| /* copy last cpy_num-1 items starting from position 'pos+1' of the SOURCE to the begin of the DEST; */ |
| leaf_copy_items_entirely(fs, dest_bi, src, LAST_TO_FIRST, pos+1, cpy_num-1); |
| |
| /* copy part of the item which number is pos to the begin of the DEST */ |
| leaf_item_bottle (fs, dest_bi, src, LAST_TO_FIRST, pos, cpy_bytes); |
| } |
| } |
| return i; |
| } |
| |
| |
| /* there are types of coping: from S[0] to L[0], from S[0] to R[0], |
| from R[0] to L[0]. for each of these we have to define parent and |
| positions of destination and source buffers */ |
| static void leaf_define_dest_src_infos (int shift_mode, struct tree_balance * tb, struct buffer_info * dest_bi, |
| struct buffer_info * src_bi, int * first_last, |
| struct buffer_head * Snew) |
| { |
| /* define dest, src, dest parent, dest position */ |
| switch (shift_mode) { |
| case LEAF_FROM_S_TO_L: /* it is used in leaf_shift_left */ |
| src_bi->bi_bh = PATH_PLAST_BUFFER (tb->tb_path); |
| src_bi->bi_parent = PATH_H_PPARENT (tb->tb_path, 0); |
| src_bi->bi_position = PATH_H_B_ITEM_ORDER (tb->tb_path, 0); /* src->b_item_order */ |
| dest_bi->bi_bh = tb->L[0]; |
| dest_bi->bi_parent = tb->FL[0]; |
| dest_bi->bi_position = get_left_neighbor_position (tb, 0); |
| *first_last = FIRST_TO_LAST; |
| break; |
| |
| case LEAF_FROM_S_TO_R: /* it is used in leaf_shift_right */ |
| src_bi->bi_bh = PATH_PLAST_BUFFER (tb->tb_path); |
| src_bi->bi_parent = PATH_H_PPARENT (tb->tb_path, 0); |
| src_bi->bi_position = PATH_H_B_ITEM_ORDER (tb->tb_path, 0); |
| dest_bi->bi_bh = tb->R[0]; |
| dest_bi->bi_parent = tb->FR[0]; |
| dest_bi->bi_position = get_right_neighbor_position (tb, 0); |
| *first_last = LAST_TO_FIRST; |
| break; |
| |
| case LEAF_FROM_R_TO_L: /* it is used in balance_leaf_when_delete */ |
| src_bi->bi_bh = tb->R[0]; |
| src_bi->bi_parent = tb->FR[0]; |
| src_bi->bi_position = get_right_neighbor_position (tb, 0); |
| dest_bi->bi_bh = tb->L[0]; |
| dest_bi->bi_parent = tb->FL[0]; |
| dest_bi->bi_position = get_left_neighbor_position (tb, 0); |
| *first_last = FIRST_TO_LAST; |
| break; |
| |
| case LEAF_FROM_L_TO_R: /* it is used in balance_leaf_when_delete */ |
| src_bi->bi_bh = tb->L[0]; |
| src_bi->bi_parent = tb->FL[0]; |
| src_bi->bi_position = get_left_neighbor_position (tb, 0); |
| dest_bi->bi_bh = tb->R[0]; |
| dest_bi->bi_parent = tb->FR[0]; |
| dest_bi->bi_position = get_right_neighbor_position (tb, 0); |
| *first_last = LAST_TO_FIRST; |
| break; |
| |
| case LEAF_FROM_S_TO_SNEW: |
| src_bi->bi_bh = PATH_PLAST_BUFFER (tb->tb_path); |
| src_bi->bi_parent = PATH_H_PPARENT (tb->tb_path, 0); |
| src_bi->bi_position = PATH_H_B_ITEM_ORDER (tb->tb_path, 0); |
| dest_bi->bi_bh = Snew; |
| dest_bi->bi_parent = 0; |
| dest_bi->bi_position = 0; |
| *first_last = LAST_TO_FIRST; |
| break; |
| |
| default: |
| reiserfs_panic (0, "vs-10250: leaf_define_dest_src_infos: shift type is unknown (%d)", shift_mode); |
| } |
| } |
| |
| |
| |
| |
| /* copy mov_num items and mov_bytes of the (mov_num-1)th item to |
| neighbor. Delete them from source */ |
| int leaf_move_items (int shift_mode, struct tree_balance * tb, |
| int mov_num, int mov_bytes, struct buffer_head * Snew) |
| { |
| int ret_value; |
| struct buffer_info dest_bi, src_bi; |
| int first_last; |
| |
| leaf_define_dest_src_infos (shift_mode, tb, &dest_bi, &src_bi, &first_last, Snew); |
| |
| ret_value = leaf_copy_items (tb->tb_fs, &dest_bi, src_bi.bi_bh, first_last, mov_num, mov_bytes); |
| |
| leaf_delete_items (tb->tb_fs, &src_bi, first_last, (first_last == FIRST_TO_LAST) ? 0 : |
| (B_NR_ITEMS(src_bi.bi_bh) - mov_num), mov_num, mov_bytes); |
| |
| |
| return ret_value; |
| } |
| |
| |
| /* Shift shift_num items (and shift_bytes of last shifted item if shift_bytes != -1) |
| from S[0] to L[0] and replace the delimiting key */ |
| int leaf_shift_left (struct tree_balance * tb, int shift_num, int shift_bytes) |
| { |
| struct buffer_head * S0 = PATH_PLAST_BUFFER (tb->tb_path); |
| int i; |
| |
| /* move shift_num (and shift_bytes bytes) items from S[0] to left neighbor L[0] */ |
| i = leaf_move_items (LEAF_FROM_S_TO_L, tb, shift_num, shift_bytes, 0); |
| |
| if ( shift_num ) { |
| if (B_NR_ITEMS (S0) == 0) { |
| /* everything is moved from S[0] */ |
| if (PATH_H_POSITION (tb->tb_path, 1) == 0) |
| replace_key(tb->tb_fs, tb->CFL[0], tb->lkey[0], PATH_H_PPARENT (tb->tb_path, 0), 0); |
| } else { |
| /* replace lkey in CFL[0] by 0-th key from S[0]; */ |
| replace_key(tb->tb_fs, tb->CFL[0], tb->lkey[0], S0, 0); |
| |
| } |
| } |
| |
| return i; |
| } |
| |
| |
| |
| |
| |
| /* CLEANING STOPPED HERE */ |
| |
| |
| |
| |
| /* Shift shift_num (shift_bytes) items from S[0] to the right neighbor, and replace the delimiting key */ |
| int leaf_shift_right (struct tree_balance * tb, int shift_num, int shift_bytes) |
| { |
| int ret_value; |
| |
| /* move shift_num (and shift_bytes) items from S[0] to right neighbor R[0] */ |
| ret_value = leaf_move_items (LEAF_FROM_S_TO_R, tb, shift_num, shift_bytes, 0); |
| |
| /* replace rkey in CFR[0] by the 0-th key from R[0] */ |
| if (shift_num) { |
| replace_key(tb->tb_fs, tb->CFR[0], tb->rkey[0], tb->R[0], 0); |
| } |
| |
| return ret_value; |
| } |
| |
| |
| |
| static void leaf_delete_items_entirely (reiserfs_filsys_t * sb, |
| /*struct reiserfs_transaction_handle *th,*/ |
| struct buffer_info * bi, |
| int first, |
| int del_num); |
| /* If del_bytes == -1, starting from position 'first' delete del_num items in whole in buffer CUR. |
| If not. |
| If last_first == 0. Starting from position 'first' delete del_num-1 items in whole. Delete part of body of |
| the first item. Part defined by del_bytes. Don't delete first item header |
| If last_first == 1. Starting from position 'first+1' delete del_num-1 items in whole. Delete part of body of |
| the last item . Part defined by del_bytes. Don't delete last item header. |
| */ |
| void leaf_delete_items (reiserfs_filsys_t * fs, |
| struct buffer_info * cur_bi, |
| int last_first, |
| int first, int del_num, int del_bytes) |
| { |
| struct buffer_head * bh; |
| int item_amount = B_NR_ITEMS (bh = cur_bi->bi_bh); |
| |
| if ( del_num == 0 ) |
| return; |
| |
| if ( first == 0 && del_num == item_amount && del_bytes == -1 ) { |
| make_empty_node (cur_bi); |
| mark_buffer_dirty (bh); |
| return; |
| } |
| |
| if ( del_bytes == -1 ) |
| /* delete del_num items beginning from item in position first */ |
| leaf_delete_items_entirely (fs, cur_bi, first, del_num); |
| else { |
| if ( last_first == FIRST_TO_LAST ) { |
| /* delete del_num-1 items beginning from item in position first */ |
| leaf_delete_items_entirely (fs, cur_bi, first, del_num-1); |
| |
| /* delete the part of the first item of the bh do not |
| delete item header */ |
| leaf_cut_from_buffer (fs, cur_bi, 0, 0, del_bytes); |
| } else { |
| struct item_head * ih; |
| int len; |
| |
| /* delete del_num-1 items beginning from item in position first+1 */ |
| leaf_delete_items_entirely (fs, cur_bi, first+1, del_num-1); |
| |
| if (I_IS_DIRECTORY_ITEM(ih = B_N_PITEM_HEAD(bh, B_NR_ITEMS(bh)-1))) /* the last item is directory */ |
| /* len = numbers of directory entries in this item */ |
| len = get_ih_entry_count(ih); |
| else |
| /* len = body len of item */ |
| len = get_ih_item_len (ih); |
| |
| /* delete the part of the last item of the bh |
| do not delete item header |
| */ |
| leaf_cut_from_buffer (fs, cur_bi, B_NR_ITEMS(bh) - 1, len - del_bytes, del_bytes); |
| } |
| } |
| } |
| |
| |
| /* insert item into the leaf node in position before */ |
| void leaf_insert_into_buf (reiserfs_filsys_t * s, |
| struct buffer_info * bi, |
| int before, |
| struct item_head * inserted_item_ih, |
| const char * inserted_item_body, |
| int zeros_number |
| ) |
| { |
| struct buffer_head * bh = bi->bi_bh; |
| int nr; |
| struct block_head * blkh; |
| struct item_head * ih; |
| int i; |
| int last_loc, unmoved_loc; |
| char * to; |
| |
| blkh = B_BLK_HEAD (bh); |
| nr = get_blkh_nr_items (blkh); |
| |
| /* get item new item must be inserted before */ |
| ih = B_N_PITEM_HEAD (bh, before); |
| |
| /* prepare space for the body of new item */ |
| last_loc = nr ? get_ih_location (&ih[nr - before - 1]) : bh->b_size; |
| unmoved_loc = before ? get_ih_location (ih-1) : bh->b_size; |
| |
| memmove (bh->b_data + last_loc - get_ih_item_len (inserted_item_ih), |
| bh->b_data + last_loc, unmoved_loc - last_loc); |
| |
| to = bh->b_data + unmoved_loc - get_ih_item_len (inserted_item_ih); |
| memset (to, 0, zeros_number); |
| to += zeros_number; |
| |
| /* copy body to prepared space */ |
| if (inserted_item_body) |
| //if (mem_mode == REISERFS_USER_MEM) |
| // copy_from_user (to, inserted_item_body, inserted_item_ih->ih_item_len - zeros_number); |
| //else { |
| memmove (to, inserted_item_body, get_ih_item_len (inserted_item_ih) - zeros_number); |
| //} |
| else |
| memset(to, '\0', get_ih_item_len (inserted_item_ih) - zeros_number); |
| |
| /* insert item header */ |
| memmove (ih + 1, ih, IH_SIZE * (nr - before)); |
| memmove (ih, inserted_item_ih, IH_SIZE); |
| |
| /* change locations */ |
| for (i = before; i < nr + 1; i ++) { |
| unmoved_loc -= get_ih_item_len (&ih[i-before]); |
| set_ih_location (&ih[i-before], unmoved_loc); |
| } |
| |
| /* sizes, free space, item number */ |
| set_blkh_nr_items (blkh, get_blkh_nr_items (blkh) + 1); |
| set_blkh_free_space (blkh, get_blkh_free_space (blkh) - |
| (IH_SIZE + get_ih_item_len (inserted_item_ih))); |
| |
| mark_buffer_dirty(bh) ; |
| |
| if (bi->bi_parent) { |
| struct disk_child * dc; |
| |
| dc = B_N_CHILD (bi->bi_parent, bi->bi_position); |
| set_dc_child_size (dc, get_dc_child_size (dc) + IH_SIZE + get_ih_item_len (inserted_item_ih)); |
| mark_buffer_dirty(bi->bi_parent) ; |
| } |
| |
| if (is_a_leaf(bh->b_data, bh->b_size) != THE_LEAF) |
| reiserfs_panic ("leaf_insert_into_buf: bad leaf %lu: %b", bh->b_blocknr, bh); |
| } |
| |
| |
| /* paste paste_size bytes to affected_item_num-th item. |
| When item is a directory, this only prepare space for new entries */ |
| void leaf_paste_in_buffer (reiserfs_filsys_t * fs, |
| struct buffer_info * bi, |
| int affected_item_num, |
| int pos_in_item, |
| int paste_size, |
| const char * body, |
| int zeros_number) |
| { |
| struct buffer_head * bh = bi->bi_bh; |
| int nr; |
| struct block_head * blkh; |
| struct item_head * ih; |
| int i; |
| int last_loc, unmoved_loc; |
| |
| |
| blkh = B_BLK_HEAD (bh); |
| nr = get_blkh_nr_items (blkh); |
| |
| /* item to be appended */ |
| ih = B_N_PITEM_HEAD(bh, affected_item_num); |
| |
| last_loc = get_ih_location (&ih[nr - affected_item_num - 1]); |
| unmoved_loc = affected_item_num ? get_ih_location (ih-1) : bh->b_size; |
| |
| /* prepare space */ |
| memmove (bh->b_data + last_loc - paste_size, bh->b_data + last_loc, |
| unmoved_loc - last_loc); |
| |
| |
| /* change locations */ |
| for (i = affected_item_num; i < nr; i ++) |
| set_ih_location (&ih[i-affected_item_num], get_ih_location (&ih[i-affected_item_num]) - paste_size); |
| |
| if ( body ) { |
| if (!I_IS_DIRECTORY_ITEM(ih)) { |
| //if (mem_mode == REISERFS_USER_MEM) { |
| //memset (bh->b_data + unmoved_loc - paste_size, 0, zeros_number); |
| //copy_from_user (bh->b_data + unmoved_loc - paste_size + zeros_number, body, paste_size - zeros_number); |
| //} else |
| { |
| if (!pos_in_item) { |
| /* shift data to right */ |
| memmove (bh->b_data + get_ih_location (ih) + paste_size, |
| bh->b_data + get_ih_location (ih), get_ih_item_len (ih)); |
| /* paste data in the head of item */ |
| memset (bh->b_data + get_ih_location (ih), 0, zeros_number); |
| memcpy (bh->b_data + get_ih_location (ih) + zeros_number, body, paste_size - zeros_number); |
| } else { |
| memset (bh->b_data + unmoved_loc - paste_size, 0, zeros_number); |
| memcpy (bh->b_data + unmoved_loc - paste_size + zeros_number, body, paste_size - zeros_number); |
| } |
| } |
| } |
| } |
| else |
| memset(bh->b_data + unmoved_loc - paste_size,'\0',paste_size); |
| |
| set_ih_item_len (ih, get_ih_item_len (ih) + paste_size); |
| |
| /* change free space */ |
| set_blkh_free_space (blkh, get_blkh_free_space (blkh) - paste_size); |
| |
| mark_buffer_dirty(bh) ; |
| |
| if (bi->bi_parent) { |
| struct disk_child * dc; |
| |
| dc = B_N_CHILD (bi->bi_parent, bi->bi_position); |
| set_dc_child_size (dc, get_dc_child_size (dc) + paste_size); |
| mark_buffer_dirty(bi->bi_parent); |
| } |
| if (is_a_leaf(bh->b_data, bh->b_size) != THE_LEAF) |
| reiserfs_panic ("leaf_paste_in_buffer: bad leaf %lu: %b", bh->b_blocknr, bh); |
| } |
| |
| |
| /* cuts DEL_COUNT entries beginning from FROM-th entry. Directory item |
| does not have free space, so it moves DEHs and remaining records as |
| necessary. Return value is size of removed part of directory item |
| in bytes. */ |
| static int leaf_cut_entries (struct buffer_head * bh, |
| struct item_head * ih, |
| int from, int del_count) |
| { |
| char * item; |
| struct reiserfs_de_head * deh; |
| int prev_record_offset; /* offset of record, that is (from-1)th */ |
| char * prev_record; /* */ |
| int cut_records_len; /* length of all removed records */ |
| int i; |
| int entry_count; |
| |
| |
| /* first byte of item */ |
| item = B_I_PITEM (bh, ih); |
| |
| /* entry head array */ |
| deh = B_I_DEH (bh, ih); |
| entry_count = get_ih_entry_count (ih); |
| |
| if (del_count == 0) { |
| int shift; |
| int last_location; |
| |
| last_location = get_deh_location (deh + entry_count - 1); |
| shift = last_location - DEH_SIZE * entry_count; |
| |
| memmove (deh + entry_count, item + last_location, |
| get_ih_item_len (ih) - last_location); |
| for (i = 0; i < entry_count; i ++) |
| set_deh_location (&deh[i], get_deh_location (&deh[i]) - shift); |
| |
| return shift; |
| } |
| |
| /* first byte of remaining entries, those are BEFORE cut entries |
| (prev_record) and length of all removed records (cut_records_len) */ |
| prev_record_offset = (from ? get_deh_location (&deh[from - 1]) : get_ih_item_len (ih)); |
| cut_records_len = prev_record_offset/*from_record*/ - get_deh_location (&deh[from + del_count - 1]); |
| prev_record = item + prev_record_offset; |
| |
| |
| /* adjust locations of remaining entries */ |
| for (i = get_ih_entry_count (ih) - 1; i > from + del_count - 1; i --) { |
| set_deh_location (deh + i, get_deh_location (deh + i) - (DEH_SIZE * del_count)); |
| } |
| |
| for (i = 0; i < from; i ++) { |
| set_deh_location (deh + i, get_deh_location (deh + i) - (DEH_SIZE * del_count + cut_records_len)); |
| } |
| |
| set_ih_entry_count (ih, get_ih_entry_count (ih) - del_count); |
| |
| /* shift entry head array and entries those are AFTER removed entries */ |
| memmove ((char *)(deh + from), |
| deh + from + del_count, |
| prev_record - cut_records_len - (char *)(deh + from + del_count)); |
| |
| /* shift records, those are BEFORE removed entries */ |
| memmove (prev_record - cut_records_len - DEH_SIZE * del_count, |
| prev_record, item + get_ih_item_len (ih) - prev_record); |
| |
| return DEH_SIZE * del_count + cut_records_len; |
| } |
| |
| |
| /* when cut item is part of regular file |
| pos_in_item - first byte that must be cut |
| cut_size - number of bytes to be cut beginning from pos_in_item |
| |
| when cut item is part of directory |
| pos_in_item - number of first deleted entry |
| cut_size - count of deleted entries |
| */ |
| void leaf_cut_from_buffer (reiserfs_filsys_t * fs, |
| struct buffer_info * bi, int cut_item_num, |
| int pos_in_item, int cut_size) |
| { |
| int nr; |
| struct buffer_head * bh = bi->bi_bh; |
| struct block_head * blkh; |
| struct item_head * ih; |
| int last_loc, unmoved_loc; |
| int i; |
| |
| blkh = B_BLK_HEAD (bh); |
| nr = get_blkh_nr_items (blkh); |
| |
| /* item head of truncated item */ |
| ih = B_N_PITEM_HEAD (bh, cut_item_num); |
| |
| if (I_IS_DIRECTORY_ITEM (ih)) { |
| /* first cut entry ()*/ |
| cut_size = leaf_cut_entries (bh, ih, pos_in_item, cut_size); |
| if (pos_in_item == 0) { |
| /* change item key by key of first entry in the item */ |
| set_key_offset_v1 (&ih->ih_key, get_deh_offset (B_I_DEH (bh, ih))); |
| /*memcpy (&ih->ih_key.k_offset, &(B_I_DEH (bh, ih)->deh_offset), SHORT_KEY_SIZE);*/ |
| } |
| } else { |
| /* item is direct or indirect */ |
| /* shift item body to left if cut is from the head of item */ |
| if (pos_in_item == 0) { |
| memmove (bh->b_data + get_ih_location (ih), |
| bh->b_data + get_ih_location (ih) + cut_size, |
| get_ih_item_len (ih) - cut_size); |
| |
| /* change key of item */ |
| if (I_IS_DIRECT_ITEM(ih)) { |
| //ih->ih_key.k_offset += cut_size; |
| set_offset (key_format (&ih->ih_key), &ih->ih_key, get_offset (&ih->ih_key) + cut_size); |
| } else { |
| //ih->ih_key.k_offset += (cut_size / UNFM_P_SIZE) * bh->b_size; |
| set_offset (key_format (&ih->ih_key), &ih->ih_key, |
| get_offset (&ih->ih_key) + (cut_size / UNFM_P_SIZE) * bh->b_size); |
| } |
| } |
| } |
| |
| |
| /* location of the last item */ |
| last_loc = get_ih_location (&ih[nr - cut_item_num - 1]); |
| |
| /* location of the item, which is remaining at the same place */ |
| unmoved_loc = cut_item_num ? get_ih_location (ih-1) : bh->b_size; |
| |
| |
| /* shift */ |
| memmove (bh->b_data + last_loc + cut_size, bh->b_data + last_loc, |
| unmoved_loc - last_loc - cut_size); |
| |
| /* change item length */ |
| set_ih_item_len (ih, get_ih_item_len (ih) - cut_size); |
| |
| if (I_IS_INDIRECT_ITEM(ih)) { |
| if (pos_in_item) |
| //ih->u.ih_free_space = 0; |
| set_ih_free_space (ih, 0); |
| } |
| |
| /* change locations */ |
| for (i = cut_item_num; i < nr; i ++) { |
| set_ih_location (&ih[i-cut_item_num], get_ih_location (&ih[i-cut_item_num]) + cut_size); |
| } |
| |
| /* size, free space */ |
| set_blkh_free_space (blkh, get_blkh_free_space (blkh) + cut_size); |
| |
| mark_buffer_dirty(bh); |
| |
| if (bi->bi_parent) { |
| struct disk_child * dc; |
| |
| dc = B_N_CHILD (bi->bi_parent, bi->bi_position); |
| set_dc_child_size (dc, get_dc_child_size (dc) - cut_size); |
| mark_buffer_dirty(bi->bi_parent); |
| } |
| if (is_a_leaf(bh->b_data, bh->b_size) != THE_LEAF) |
| reiserfs_panic ("leaf_cut_from_buffer: bad leaf %lu: %b", |
| bh->b_blocknr, bh); |
| } |
| |
| |
| /* delete del_num items from buffer starting from the first'th item */ |
| static void leaf_delete_items_entirely (reiserfs_filsys_t * fs, |
| struct buffer_info * bi, |
| int first, int del_num) |
| { |
| struct buffer_head * bh = bi->bi_bh; |
| int nr; |
| int i, j; |
| int last_loc, last_removed_loc; |
| struct block_head * blkh; |
| struct item_head * ih; |
| |
| if (del_num == 0) |
| return; |
| |
| blkh = B_BLK_HEAD (bh); |
| nr = get_blkh_nr_items (blkh); |
| |
| if (first == 0 && del_num == nr) { |
| /* this does not work */ |
| make_empty_node (bi); |
| |
| mark_buffer_dirty(bh); |
| return; |
| } |
| |
| ih = B_N_PITEM_HEAD (bh, first); |
| |
| /* location of unmovable item */ |
| j = (first == 0) ? bh->b_size : get_ih_location (ih-1); |
| |
| /* delete items */ |
| last_loc = get_ih_location (&ih[nr - 1 - first]); |
| last_removed_loc = get_ih_location (&ih[del_num-1]); |
| |
| memmove (bh->b_data + last_loc + j - last_removed_loc, |
| bh->b_data + last_loc, last_removed_loc - last_loc); |
| |
| /* delete item headers */ |
| memmove (ih, ih + del_num, (nr - first - del_num) * IH_SIZE); |
| |
| /* change item location */ |
| for (i = first; i < nr - del_num; i ++) { |
| set_ih_location (&ih[i-first], get_ih_location (&ih[i-first]) + j - last_removed_loc); |
| } |
| |
| /* sizes, item number */ |
| set_blkh_nr_items (blkh, get_blkh_nr_items (blkh)/*nr*/ - del_num); |
| set_blkh_free_space (blkh, get_blkh_free_space (blkh) + j - last_removed_loc + IH_SIZE * del_num); |
| |
| mark_buffer_dirty(bh); |
| |
| if (bi->bi_parent) { |
| struct disk_child * dc; |
| |
| dc = B_N_CHILD (bi->bi_parent, bi->bi_position); |
| set_dc_child_size (dc, get_dc_child_size (dc) - |
| (j - last_removed_loc + IH_SIZE * del_num)); |
| mark_buffer_dirty(bi->bi_parent); |
| } |
| if (is_a_leaf(bh->b_data, bh->b_size) != THE_LEAF) |
| reiserfs_panic ("leaf_delete_items_entirely: bad leaf %lu: %b", bh->b_blocknr, bh); |
| } |
| |
| |
| |
| |
| |
| /* paste new_entry_count entries (new_dehs, records) into position before to item_num-th item */ |
| void leaf_paste_entries (struct buffer_head * bh, |
| int item_num, int before, int new_entry_count, |
| struct reiserfs_de_head * new_dehs, |
| const char * records, int paste_size) |
| { |
| struct item_head * ih; |
| char * item; |
| struct reiserfs_de_head * deh; |
| char * insert_point; |
| int i, old_entry_num; |
| |
| if (new_entry_count == 0) |
| return; |
| |
| ih = B_N_PITEM_HEAD(bh, item_num); |
| |
| /* first byte of dest item */ |
| item = B_I_PITEM (bh, ih); |
| |
| /* entry head array */ |
| deh = B_I_DEH (bh, ih); |
| |
| /* new records will be pasted at this point */ |
| insert_point = item + (before ? get_deh_location (&deh[before - 1]) : (get_ih_item_len (ih) - paste_size)); |
| |
| /* adjust locations of records that will be AFTER new records */ |
| for (i = get_ih_entry_count (ih) - 1; i >= before; i --) |
| set_deh_location (deh + i, get_deh_location (deh + i) + DEH_SIZE * new_entry_count); |
| |
| /* adjust locations of records that will be BEFORE new records */ |
| for (i = 0; i < before; i ++) |
| set_deh_location (deh + i, get_deh_location (deh + i) + paste_size); |
| |
| old_entry_num = get_ih_entry_count (ih); |
| //I_ENTRY_COUNT(ih) += new_entry_count; |
| set_ih_entry_count (ih, old_entry_num + new_entry_count); |
| |
| /* prepare space for pasted records */ |
| memmove (insert_point + paste_size, insert_point, item + (get_ih_item_len (ih) - paste_size) - insert_point); |
| |
| /* copy new records */ |
| memcpy (insert_point + DEH_SIZE * new_entry_count, records, |
| paste_size - DEH_SIZE * new_entry_count); |
| |
| /* prepare space for new entry heads */ |
| deh += before; |
| memmove ((char *)(deh + new_entry_count), deh, insert_point - (char *)deh); |
| |
| /* copy new entry heads */ |
| memcpy (deh, new_dehs, DEH_SIZE * new_entry_count); |
| |
| /* set locations of new records */ |
| for (i = 0; i < new_entry_count; i ++) |
| set_deh_location (deh + i, |
| get_deh_location (deh + i) + (- get_deh_location (&new_dehs[new_entry_count - 1]) + |
| insert_point + DEH_SIZE * new_entry_count - item)); |
| |
| |
| /* change item key if neccessary (when we paste before 0-th entry */ |
| if (!before) |
| set_key_offset_v1 (&ih->ih_key, get_deh_offset (new_dehs)); |
| } |
| |
| |
| |
| /* wrappers for operations on one separated node */ |
| |
| void delete_item (reiserfs_filsys_t * fs, |
| struct buffer_head * bh, int item_num) |
| { |
| struct buffer_info bi; |
| |
| bi.bi_bh = bh; |
| bi.bi_parent = 0; |
| bi.bi_position = 0; |
| leaf_delete_items_entirely (fs, &bi, item_num, 1); |
| } |
| |
| |
| void cut_entry (reiserfs_filsys_t * fs, struct buffer_head * bh, |
| int item_num, int entry_num, int del_count) |
| { |
| struct buffer_info bi; |
| |
| bi.bi_bh = bh; |
| bi.bi_parent = 0; |
| bi.bi_position = 0; |
| leaf_cut_from_buffer (fs, &bi, item_num, entry_num, del_count); |
| } |
| |