reiserfs-3.6.19.rar

/* * Copyright 1996-2004 by Hans Reiser, licensing governed by * reiserfsprogs/README */ /** ** old_item_num ** old_entry_num ** set_entry_sizes ** create_virtual_node ** check_left ** check_right ** directory_part_size ** get_num_ver ** item_length ** set_parameters ** is_leaf_removable ** are_leaves_removable ** get_empty_nodes ** get_lfree ** get_rfree ** is_left_neighbor_in_cache ** decrement_key ** get_far_parent ** get_parents ** can_node_be_removed ** ip_check_balance ** dc_check_balance_internal ** dc_check_balance_leaf ** dc_check_balance ** check_balance ** get_direct_parent ** get_neighbors ** fix_nodes ** ** **/ #include "includes.h" /* To make any changes in the tree we find a node, that contains item to be changed/deleted or position in the node we insert a new item to. We call this node S. To do balancing we need to decide what we will shift to left/right neighbor, or to a new node, where new item will be etc. To make this analysis simpler we build virtual node. Virtual node is an array of items, that will replace items of node S. (For instance if we are going to delete an item, virtual node does not contain it). Virtual node keeps information about item sizes and types, mergeability of first and last items, sizes of all entries in directory item. We use this array of items when calculating what we can shift to neighbors and how many nodes we have to have if we do not any shiftings, if we shift to left/right neighbor or to both. */ /* taking item number in virtual node, returns number of item, that it has in source buffer */ static inline int old_item_num (int new_num, int affected_item_num, int mode) { if (mode == M_PASTE || mode == M_CUT || new_num < affected_item_num) return new_num; if (mode == M_INSERT) return new_num - 1; /* delete mode */ return new_num + 1; } /* function returns old entry number in directory item in real node using new entry number in virtual item in virtual node */ static inline int old_entry_num (int new_num, int affected_item_num, int new_entry_num, int pos_in_item, int mode) { if ( mode == M_INSERT || mode == M_DELETE) return new_entry_num; if (new_num != affected_item_num) { /* cut or paste is applied to another item */ return new_entry_num; } if (new_entry_num < pos_in_item) return new_entry_num; if (mode == M_CUT) return new_entry_num + 1; return new_entry_num - 1; } /* * Create an array of sizes of directory entries for virtual item */ static void set_entry_sizes (struct tree_balance * tb, int old_num, int new_num, struct buffer_head * bh, struct item_head * ih) { struct virtual_node * vn = tb->tb_vn; int i; struct reiserfs_de_head * deh; struct virtual_item * vi; deh = B_I_DEH (bh, ih); /* seek to given virtual item in array of virtual items */ vi = vn->vn_vi + new_num; /* virtual directory item have this amount of entry after */ vi->vi_entry_count = get_ih_entry_count (ih) + ((old_num == vn->vn_affected_item_num) ? ((vn->vn_mode == M_CUT) ? -1 : (vn->vn_mode == M_PASTE ? 1 : 0)) : 0); vi->vi_entry_sizes = (__u16 *)vn->vn_free_ptr; vn->vn_free_ptr += vi->vi_entry_count * sizeof (__u16); /* set sizes of old entries */ for (i = 0; i < vi->vi_entry_count; i ++) { int j; j = old_entry_num (old_num, vn->vn_affected_item_num, i, vn->vn_pos_in_item, vn->vn_mode); vi->vi_entry_sizes[i] = entry_length (ih, &(deh[j]), j) + DEH_SIZE; } /* set size of pasted entry */ if (old_num == vn->vn_affected_item_num && vn->vn_mode == M_PASTE) vi->vi_entry_sizes[vn->vn_pos_in_item] = tb->insert_size[0]; } static void create_virtual_node (struct tree_balance * tb, int h) { struct item_head * ih; struct virtual_node * vn = tb->tb_vn; int new_num; struct buffer_head * Sh; /* this comes from tb->S[h] */ Sh = PATH_H_PBUFFER (tb->tb_path, h); /* size of changed node */ vn->vn_size = MAX_CHILD_SIZE (Sh->b_size) - get_blkh_free_space (B_BLK_HEAD (Sh)) + tb->insert_size[h]; /* for internal nodes array if virtual items is not created */ if (h) { vn->vn_nr_item = (vn->vn_size - DC_SIZE) / (DC_SIZE + KEY_SIZE); return; } /* number of items in virtual node */ vn->vn_nr_item = B_NR_ITEMS (Sh) + ((vn->vn_mode == M_INSERT)? 1 : 0) - ((vn->vn_mode == M_DELETE)? 1 : 0); /* first virtual item */ vn->vn_vi = (struct virtual_item *)(tb->tb_vn + 1); memset (vn->vn_vi, 0, vn->vn_nr_item * sizeof (struct virtual_item)); vn->vn_free_ptr += vn->vn_nr_item * sizeof (struct virtual_item); /* first item in the node */ ih = B_N_PITEM_HEAD (Sh, 0); /* define the mergeability for 0-th item (if it is not being deleted) */ if (is_left_mergeable (tb->tb_fs, tb->tb_path) == 1 && (vn->vn_mode != M_DELETE || vn->vn_affected_item_num)) vn->vn_vi[0].vi_type |= VI_TYPE_LEFT_MERGEABLE; /* go through all items those remain in the virtual node (except for the new (inserted) one) */ for (new_num = 0; new_num < vn->vn_nr_item; new_num ++) { int j; if (vn->vn_affected_item_num == new_num && vn->vn_mode == M_INSERT) continue; /* get item number in source node */ j = old_item_num (new_num, vn->vn_affected_item_num, vn->vn_mode); vn->vn_vi[new_num].vi_item_len += get_ih_item_len (&ih[j]) + IH_SIZE; if (I_IS_STAT_DATA_ITEM (ih + j)) { vn->vn_vi[new_num].vi_type |= VI_TYPE_STAT_DATA; continue; } /* set type of item */ if (I_IS_DIRECT_ITEM (ih + j)) vn->vn_vi[new_num].vi_type |= VI_TYPE_DIRECT; if (I_IS_INDIRECT_ITEM (ih + j)) vn->vn_vi[new_num].vi_type |= VI_TYPE_INDIRECT; if (I_IS_DIRECTORY_ITEM (ih + j)) { set_entry_sizes (tb, j, new_num, Sh, ih + j); vn->vn_vi[new_num].vi_type |= VI_TYPE_DIRECTORY; if (get_key_offset_v1 (&ih[j].ih_key) == DOT_OFFSET) vn->vn_vi[new_num].vi_type |= VI_TYPE_FIRST_DIRECTORY_ITEM; } vn->vn_vi[new_num].vi_item_offset = get_offset (&(ih + j)->ih_key); if (new_num != vn->vn_affected_item_num) /* this is not being changed */ continue; if (vn->vn_mode == M_PASTE || vn->vn_mode == M_CUT) vn->vn_vi[new_num].vi_item_len += tb->insert_size[0]; } /* virtual inserted item is not defined yet */ if (vn->vn_mode == M_INSERT) { vn->vn_vi[vn->vn_affected_item_num].vi_item_len = tb->insert_size[0]; vn->vn_vi[vn->vn_affected_item_num].vi_item_offset = get_offset (&vn->vn_ins_ih->ih_key); switch (get_type (&vn->vn_ins_ih->ih_key)) { case TYPE_STAT_DATA: vn->vn_vi[vn->vn_affected_item_num].vi_type |= VI_TYPE_STAT_DATA; break; case TYPE_DIRECT: vn->vn_vi[vn->vn_affected_item_num].vi_type |= VI_TYPE_DIRECT; break; case TYPE_INDIRECT: vn->vn_vi[vn->vn_affected_item_num].vi_type |= VI_TYPE_INDIRECT; break; default: /* inseted item is directory (it must be item with "." and "..") */ vn->vn_vi[vn->vn_affected_item_num].vi_type |= (VI_TYPE_DIRECTORY | VI_TYPE_FIRST_DIRECTORY_ITEM | VI_TYPE_INSERTED_DIRECTORY_ITEM); /* this directory item can not be split, so do not set sizes of entries */ break; } } /* set right merge flag we take right delimiting key and check whether it is a mergeable item */ if (tb->CFR[0]) { ih = (struct item_head *)B_N_PDELIM_KEY (tb->CFR[0], tb->rkey[0]); if (is_right_mergeable (tb->tb_fs, tb->tb_path) == 1 && (vn->vn_mode != M_DELETE || vn->vn_affected_item_num != B_NR_ITEMS (Sh) - 1)) vn->vn_vi[vn->vn_nr_item-1].vi_type |= VI_TYPE_RIGHT_MERGEABLE; } } /* using virtual node check, how many items can be shifted to left neighbor */ static int check_left (struct tree_balance * tb, int h, int cur_free) { int i; struct virtual_node * vn = tb->tb_vn; int d_size, ih_size, bytes = -1; /* internal level */ if (h > 0) { if (!cur_fr