/* * Copyright 2000 by Hans Reiser, licensing governed by reiserfs/README */ #include <linux/time.h>#include <linux/slab.h>#include <linux/string.h>#include "reiserfs.h"#include <linux/buffer_head.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. */ /* * Takes 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) { RFALSE(new_num == 0, "vs-8005: for INSERT mode and item number of inserted item"); return new_num - 1; } RFALSE(mode != M_DELETE, "vs-8010: old_item_num: mode must be M_DELETE (mode = \'%c\'", mode); /* delete mode */ return new_num + 1;} 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_FREE_SPACE(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 = item_head(Sh, 0); /* define the mergeability for 0-th item (if it is not being deleted) */ if (op_is_left_mergeable(&ih->ih_key, Sh->b_size) && (vn->vn_mode != M_DELETE || vn->vn_affected_item_num)) vn->vn_vi[0].vi_type |= VI_TYPE_LEFT_MERGEABLE; /* * go through all items that 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; struct virtual_item *vi = vn->vn_vi + new_num; int is_affected = ((new_num != vn->vn_affected_item_num) ? 0 : 1); if (is_affected && 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); vi->vi_item_len += ih_item_len(ih + j) + IH_SIZE; vi->vi_ih = ih + j; vi->vi_item = ih_item_body(Sh, ih + j); vi->vi_uarea = vn->vn_free_ptr; /* * FIXME: there is no check that item operation did not * consume too much memory */ vn->vn_free_ptr += op_create_vi(vn, vi, is_affected, tb->insert_size[0]); if (tb->vn_buf + tb->vn_buf_size < vn->vn_free_ptr) reiserfs_panic(tb->tb_sb, "vs-8030", "virtual node space consumed"); if (!is_affected) /* 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]; /* pointer to data which is going to be pasted */ vi->vi_new_data = vn->vn_data; } } /* virtual inserted item is not defined yet */ if (vn->vn_mode == M_INSERT) { struct virtual_item *vi = vn->vn_vi + vn->vn_affected_item_num; RFALSE(vn->vn_ins_ih == NULL, "vs-8040: item header of inserted item is not specified"); vi->vi_item_len = tb->insert_size[0]; vi->vi_ih = vn->vn_ins_ih; vi->vi_item = vn->vn_data; vi->vi_uarea = vn->vn_free_ptr; op_create_vi(vn, vi, 0 /*not pasted or cut */ , tb->insert_size[0]); } /* * set right merge flag we take right delimiting key and * check whether it is a mergeable item */ if (tb->CFR[0]) { struct reiserfs_key *key; key = internal_key(tb->CFR[0], tb->rkey[0]); if (op_is_left_mergeable(key, Sh->b_size) && (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; #ifdef CONFIG_REISERFS_CHECK if (op_is_left_mergeable(key, Sh->b_size) && !(vn->vn_mode != M_DELETE || vn->vn_affected_item_num != B_NR_ITEMS(Sh) - 1)) { /* * we delete last item and it could be merged * with right neighbor's first item */ if (! (B_NR_ITEMS(Sh) == 1 && is_direntry_le_ih(item_head(Sh, 0)) && ih_entry_count(item_head(Sh, 0)) == 1)) { /* * node contains more than 1 item, or item * is not directory item, or this item * contains more than 1 entry */ print_block(Sh, 0, -1, -1); reiserfs_panic(tb->tb_sb, "vs-8045", "rdkey %k, affected item==%d " "(mode==%c) Must be %c", key, vn->vn_affected_item_num, vn->vn_mode, M_DELETE); } }#endif }} /* * Using virtual node check, how many items can be * shifted to left neighbor */static void check_left(struct tree_balance *tb, int h, int cur_free){ int i; struct virtual_node *vn = tb->tb_vn; struct virtual_item *vi; int d_size, ih_size; RFALSE(cur_free < 0, "vs-8050: cur_free (%d) < 0", cur_free); /* internal level */ if (h > 0) { tb->lnum[h] = cur_free / (DC_SIZE + KEY_SIZE); return; } /* leaf level */ if (!cur_free || !vn->vn_nr_item) { /* no free space or nothing to move */ tb->lnum[h] = 0; tb->lbytes = -1; return; } RFALSE(!PATH_H_PPARENT(tb->tb_path, 0), "vs-8055: parent does not exist or invalid"); vi = vn->vn_vi; if ((unsigned int)cur_free >= (vn->vn_size - ((vi->vi_type & VI_TYPE_LEFT_MERGEABLE) ? IH_SIZE : 0))) { /* all contents of S[0] fits into L[0] */ RFALSE(vn->vn_mode == M_INSERT || vn->vn_mode == M_PASTE, "vs-8055: invalid mode or balance condition failed"); tb->lnum[0] = vn->vn_nr_item; tb->lbytes = -1; return; } d_size = 0, ih_size = IH_SIZE; /* first item may be merge with last item in left neighbor */ if (vi->vi_type & VI_TYPE_LEFT_MERGEABLE) d_size = -((int)IH_SIZE), ih_size = 0; tb->lnum[0] = 0; for (i = 0; i < vn->vn_nr_item; i++, ih_size = IH_SIZE, d_size = 0, vi++) { d_size += vi->vi_item_len; if (cur_free >= d_size) { /* the item can be shifted entirely */ cur_free -= d_size; tb->lnum[0]++; continue; } /* the item cannot be shifted entirely, try to split it */ /* * check whether L[0] can hold ih and at least one byte * of the item body */ /* cannot shift even a part of the current item */ if (cur_free <= ih_size) { tb->lbytes = -1; return; } cur_free -= ih_size; tb->lbytes = op_check_left(vi, cur_free, 0, 0); if (tb->lbytes != -1) /* count partially shifted item */ tb->lnum[0]++; break; } return;} /* * Using virtual node check, how many items can be * shifted to right neighbor */static void check_right(struct tree_balance *tb, int h, int cur_free){ int i; struct virtual_node *vn = tb->tb_vn; struct virtual_item *vi; int d_size, ih_size; RFALSE(cur_free < 0, "vs-8070: cur_free < 0"); /* internal level */ if (h > 0) { tb->rnum[h] = cur_free / (DC_SIZE + KEY_SIZE); return; } /* leaf level */ if (!cur_free || !vn->vn_nr_item) { /* no free space */ tb->rnum[h] = 0; tb->rbytes = -1; return; } RFALSE(!PATH_H_PPARENT(tb->tb_path, 0), "vs-8075: parent does not exist or invalid"); vi = vn->vn_vi + vn->vn_nr_item - 1; if ((unsigned int)cur_free >= (vn->vn_size - ((vi->vi_type & VI_TYPE_RIGHT_MERGEABLE) ? IH_SIZE : 0))) { /* all contents of S[0] fits into R[0] */ RFALSE(vn->vn_mode == M_INSERT || vn->vn_mode == M_PASTE, "vs-8080: invalid mode or balance condition failed"); tb->rnum[h] = vn->vn_nr_item; tb->rbytes = -1; return; } d_size = 0, ih_size = IH_SIZE; /* last item may be merge with first item in right neighbor */ if (vi->vi_type & VI_TYPE_RIGHT_MERGEABLE) d_size = -(int)IH_SIZE, ih_size = 0; tb->rnum[0] = 0; for (i = vn->vn_nr_item - 1; i >= 0; i--, d_size = 0, ih_size = IH_SIZE, vi--) { d_size += vi->vi_item_len; if (cur_free >= d_size) { /* the item can be shifted entirely */ cur_free -= d_size; tb->rnum[0]++; continue; } /* * check whether R[0] can hold ih and at least one * byte of the item body */ /* cannot shift even a part of the current item */ if (cur_free <= ih_size) { tb->rbytes = -1; return; } /* * R[0] can hold the header of the item and at least * one byte of its body */ cur_free -= ih_size; /* cur_free is still > 0 */ tb->rbytes = op_check_right(vi, cur_free); if (tb->rbytes != -1) /* count partially shifted item */ tb->rnum[0]++; break; } return;} /* * from - number of items, which are shifted to left neighbor entirely * to - number of item, which are shifted to right neighbor entirely * from_bytes - number of bytes of boundary item (or directory entries) * which are shifted to left neighbor * to_bytes - number of bytes of boundary item (or directory entries) * which are shifted to right neighbor */static int get_num_ver(int mode, struct tree_balance *tb, int h, int from, int from_bytes, int to, int to_bytes, short *snum012, int flow){ int i; int cur_free; int units; struct virtual_node *vn = tb->tb_vn; int total_node_size, max_node_size, current_item_size; int needed_nodes; /* position of item we start filling node from */ int start_item; /* position of item we finish filling node by */ int end_item; /* * number of first bytes (entries for directory) of start_item-th item * we do not include into node that is being filled */ int start_bytes; /* * number of last bytes (entries for directory) of end_item-th item * we do node include into node that is being filled */ int end_bytes; /* * these are positions in virtual item of items, that are split * between S[0] and S1new and S1new and S2new */ int split_item_positions[2]; split_item_positions[0] = -1; split_item_positions[1] = -1; /* * We only create additional nodes if we are in insert or paste mode * or we are in replace mode at the internal level. If h is 0 and * the mode is M_REPLACE then in fix_nodes we change the mode to * paste or insert before we get here in the code. */ RFALSE(tb->insert_size[h] < 0 || (mode != M_INSERT && mode != M_PASTE), "vs-8100: insert_size < 0 in overflow"); max_node_size = MAX_CHILD_SIZE(PATH_H_PBUFFER(tb->tb_path, h)); /* * snum012 [0-2] - number of items, that lay * to S[0], first new node and second new node */ snum012[3] = -1; /* s1bytes */ snum012[4] = -1; /* s2bytes */ /* internal level */ if (h > 0) { i = ((to - from) * (KEY_SIZE + DC_SIZE) + DC_SIZE); if (i == max_node_size) return 1; return (i / max_node_size + 1); } /* leaf level */ needed_nodes = 1; total_node_size = 0; cur_free = max_node_size; /* start from 'from'-th item */ start_item = from; /* skip its first 'start_bytes' units */ start_bytes = ((from_bytes != -1) ? from_bytes : 0); /* last included item is the 'end_item'-th one */ end_item = vn->vn_nr_item - to - 1; /* do not count last 'end_bytes' units of 'end_item'-th item */ end_bytes = (to_bytes != -1) ? to_bytes : 0; /* * go through all item beginning from the start_item-th item * and ending by the end_item-th item. Do not count first * 'start_bytes' units of 'start_item'-th item and last * 'end_bytes' of 'end_item'-th item */ for (i = start_item; i <= end_item; i++) { struct virtual_item *vi = vn->vn_vi + i; int skip_from_end = ((i == end_item) ? end_bytes : 0); RFALSE(needed_nodes > 3, "vs-8105: too many nodes are needed"); /* get size of current item */ current_item_size = vi->vi_item_len; /* * do not take in calculation head part (from_bytes) * of from-th item */ current_item_size -= op_part_size(vi, 0 /*from start */ , start_bytes); /* do not take in calculation tail part of last item */ current_item_size -= op_part_size(vi, 1 /*from end */ , skip_from_end); /* if item fits into current node entierly */ if (total_node_size + current_item_size <= max_node_size) { snum012[needed_nodes - 1]++; total_node_size += current_item_size; start_bytes = 0; continue; } /* * virtual item length is longer, than max size of item in * a node. It is impossible for direct item */ if (current_item_size > max_node_size) { RFALSE(is_direct_le_ih(vi->vi_ih), "vs-8110: " "direct item length is %d. It can not be longer than %d", current_item_size, max_node_size); /* we will try to split it */ flow = 1; } /* as we do not split items, take new node and continue */Lines 1–500 of 2825. Load more
/* * Copyright 2000 by Hans Reiser, licensing governed by reiserfs/README */ #include <linux/time.h> #include <linux/slab.h> #include <linux/string.h> #include "reiserfs.h" #include <linux/buffer_head.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. */ /* * Takes 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) { RFALSE(new_num == 0, "vs-8005: for INSERT mode and item number of inserted item"); return new_num - 1; } RFALSE(mode != M_DELETE, "vs-8010: old_item_num: mode must be M_DELETE (mode = \'%c\'", mode); /* delete mode */ return new_num + 1; } 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_FREE_SPACE(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 = item_head(Sh, 0); /* define the mergeability for 0-th item (if it is not being deleted) */ if (op_is_left_mergeable(&ih->ih_key, Sh->b_size) && (vn->vn_mode != M_DELETE || vn->vn_affected_item_num)) vn->vn_vi[0].vi_type |= VI_TYPE_LEFT_MERGEABLE; /* * go through all items that 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; struct virtual_item *vi = vn->vn_vi + new_num; int is_affected = ((new_num != vn->vn_affected_item_num) ? 0 : 1); if (is_affected && 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); vi->vi_item_len += ih_item_len(ih + j) + IH_SIZE; vi->vi_ih = ih + j; vi->vi_item = ih_item_body(Sh, ih + j); vi->vi_uarea = vn->vn_free_ptr; /* * FIXME: there is no check that item operation did not * consume too much memory */ vn->vn_free_ptr += op_create_vi(vn, vi, is_affected, tb->insert_size[0]); if (tb->vn_buf + tb->vn_buf_size < vn->vn_free_ptr) reiserfs_panic(tb->tb_sb, "vs-8030", "virtual node space consumed"); if (!is_affected) /* 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]; /* pointer to data which is going to be pasted */ vi->vi_new_data = vn->vn_data; } } /* virtual inserted item is not defined yet */ if (vn->vn_mode == M_INSERT) { struct virtual_item *vi = vn->vn_vi + vn->vn_affected_item_num; RFALSE(vn->vn_ins_ih == NULL, "vs-8040: item header of inserted item is not specified"); vi->vi_item_len = tb->insert_size[0]; vi->vi_ih = vn->vn_ins_ih; vi->vi_item = vn->vn_data; vi->vi_uarea = vn->vn_free_ptr; op_create_vi(vn, vi, 0 /*not pasted or cut */ , tb->insert_size[0]); } /* * set right merge flag we take right delimiting key and * check whether it is a mergeable item */ if (tb->CFR[0]) { struct reiserfs_key *key; key = internal_key(tb->CFR[0], tb->rkey[0]); if (op_is_left_mergeable(key, Sh->b_size) && (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; #ifdef CONFIG_REISERFS_CHECK if (op_is_left_mergeable(key, Sh->b_size) && !(vn->vn_mode != M_DELETE || vn->vn_affected_item_num != B_NR_ITEMS(Sh) - 1)) { /* * we delete last item and it could be merged * with right neighbor's first item */ if (! (B_NR_ITEMS(Sh) == 1 && is_direntry_le_ih(item_head(Sh, 0)) && ih_entry_count(item_head(Sh, 0)) == 1)) { /* * node contains more than 1 item, or item * is not directory item, or this item * contains more than 1 entry */ print_block(Sh, 0, -1, -1); reiserfs_panic(tb->tb_sb, "vs-8045", "rdkey %k, affected item==%d " "(mode==%c) Must be %c", key, vn->vn_affected_item_num, vn->vn_mode, M_DELETE); } } #endif } } /* * Using virtual node check, how many items can be * shifted to left neighbor */ static void check_left(struct tree_balance *tb, int h, int cur_free) { int i; struct virtual_node *vn = tb->tb_vn; struct virtual_item *vi; int d_size, ih_size; RFALSE(cur_free < 0, "vs-8050: cur_free (%d) < 0", cur_free); /* internal level */ if (h > 0) { tb->lnum[h] = cur_free / (DC_SIZE + KEY_SIZE); return; } /* leaf level */ if (!cur_free || !vn->vn_nr_item) { /* no free space or nothing to move */ tb->lnum[h] = 0; tb->lbytes = -1; return; } RFALSE(!PATH_H_PPARENT(tb->tb_path, 0), "vs-8055: parent does not exist or invalid"); vi = vn->vn_vi; if ((unsigned int)cur_free >= (vn->vn_size - ((vi->vi_type & VI_TYPE_LEFT_MERGEABLE) ? IH_SIZE : 0))) { /* all contents of S[0] fits into L[0] */ RFALSE(vn->vn_mode == M_INSERT || vn->vn_mode == M_PASTE, "vs-8055: invalid mode or balance condition failed"); tb->lnum[0] = vn->vn_nr_item; tb->lbytes = -1; return; } d_size = 0, ih_size = IH_SIZE; /* first item may be merge with last item in left neighbor */ if (vi->vi_type & VI_TYPE_LEFT_MERGEABLE) d_size = -((int)IH_SIZE), ih_size = 0; tb->lnum[0] = 0; for (i = 0; i < vn->vn_nr_item; i++, ih_size = IH_SIZE, d_size = 0, vi++) { d_size += vi->vi_item_len; if (cur_free >= d_size) { /* the item can be shifted entirely */ cur_free -= d_size; tb->lnum[0]++; continue; } /* the item cannot be shifted entirely, try to split it */ /* * check whether L[0] can hold ih and at least one byte * of the item body */ /* cannot shift even a part of the current item */ if (cur_free <= ih_size) { tb->lbytes = -1; return; } cur_free -= ih_size; tb->lbytes = op_check_left(vi, cur_free, 0, 0); if (tb->lbytes != -1) /* count partially shifted item */ tb->lnum[0]++; break; } return; } /* * Using virtual node check, how many items can be * shifted to right neighbor */ static void check_right(struct tree_balance *tb, int h, int cur_free) { int i; struct virtual_node *vn = tb->tb_vn; struct virtual_item *vi; int d_size, ih_size; RFALSE(cur_free < 0, "vs-8070: cur_free < 0"); /* internal level */ if (h > 0) { tb->rnum[h] = cur_free / (DC_SIZE + KEY_SIZE); return; } /* leaf level */ if (!cur_free || !vn->vn_nr_item) { /* no free space */ tb->rnum[h] = 0; tb->rbytes = -1; return; } RFALSE(!PATH_H_PPARENT(tb->tb_path, 0), "vs-8075: parent does not exist or invalid"); vi = vn->vn_vi + vn->vn_nr_item - 1; if ((unsigned int)cur_free >= (vn->vn_size - ((vi->vi_type & VI_TYPE_RIGHT_MERGEABLE) ? IH_SIZE : 0))) { /* all contents of S[0] fits into R[0] */ RFALSE(vn->vn_mode == M_INSERT || vn->vn_mode == M_PASTE, "vs-8080: invalid mode or balance condition failed"); tb->rnum[h] = vn->vn_nr_item; tb->rbytes = -1; return; } d_size = 0, ih_size = IH_SIZE; /* last item may be merge with first item in right neighbor */ if (vi->vi_type & VI_TYPE_RIGHT_MERGEABLE) d_size = -(int)IH_SIZE, ih_size = 0; tb->rnum[0] = 0; for (i = vn->vn_nr_item - 1; i >= 0; i--, d_size = 0, ih_size = IH_SIZE, vi--) { d_size += vi->vi_item_len; if (cur_free >= d_size) { /* the item can be shifted entirely */ cur_free -= d_size; tb->rnum[0]++; continue; } /* * check whether R[0] can hold ih and at least one * byte of the item body */ /* cannot shift even a part of the current item */ if (cur_free <= ih_size) { tb->rbytes = -1; return; } /* * R[0] can hold the header of the item and at least * one byte of its body */ cur_free -= ih_size; /* cur_free is still > 0 */ tb->rbytes = op_check_right(vi, cur_free); if (tb->rbytes != -1) /* count partially shifted item */ tb->rnum[0]++; break; } return; } /* * from - number of items, which are shifted to left neighbor entirely * to - number of item, which are shifted to right neighbor entirely * from_bytes - number of bytes of boundary item (or directory entries) * which are shifted to left neighbor * to_bytes - number of bytes of boundary item (or directory entries) * which are shifted to right neighbor */ static int get_num_ver(int mode, struct tree_balance *tb, int h, int from, int from_bytes, int to, int to_bytes, short *snum012, int flow) { int i; int cur_free; int units; struct virtual_node *vn = tb->tb_vn; int total_node_size, max_node_size, current_item_size; int needed_nodes; /* position of item we start filling node from */ int start_item; /* position of item we finish filling node by */ int end_item; /* * number of first bytes (entries for directory) of start_item-th item * we do not include into node that is being filled */ int start_bytes; /* * number of last bytes (entries for directory) of end_item-th item * we do node include into node that is being filled */ int end_bytes; /* * these are positions in virtual item of items, that are split * between S[0] and S1new and S1new and S2new */ int split_item_positions[2]; split_item_positions[0] = -1; split_item_positions[1] = -1; /* * We only create additional nodes if we are in insert or paste mode * or we are in replace mode at the internal level. If h is 0 and * the mode is M_REPLACE then in fix_nodes we change the mode to * paste or insert before we get here in the code. */ RFALSE(tb->insert_size[h] < 0 || (mode != M_INSERT && mode != M_PASTE), "vs-8100: insert_size < 0 in overflow"); max_node_size = MAX_CHILD_SIZE(PATH_H_PBUFFER(tb->tb_path, h)); /* * snum012 [0-2] - number of items, that lay * to S[0], first new node and second new node */ snum012[3] = -1; /* s1bytes */ snum012[4] = -1; /* s2bytes */ /* internal level */ if (h > 0) { i = ((to - from) * (KEY_SIZE + DC_SIZE) + DC_SIZE); if (i == max_node_size) return 1; return (i / max_node_size + 1); } /* leaf level */ needed_nodes = 1; total_node_size = 0; cur_free = max_node_size; /* start from 'from'-th item */ start_item = from; /* skip its first 'start_bytes' units */ start_bytes = ((from_bytes != -1) ? from_bytes : 0); /* last included item is the 'end_item'-th one */ end_item = vn->vn_nr_item - to - 1; /* do not count last 'end_bytes' units of 'end_item'-th item */ end_bytes = (to_bytes != -1) ? to_bytes : 0; /* * go through all item beginning from the start_item-th item * and ending by the end_item-th item. Do not count first * 'start_bytes' units of 'start_item'-th item and last * 'end_bytes' of 'end_item'-th item */ for (i = start_item; i <= end_item; i++) { struct virtual_item *vi = vn->vn_vi + i; int skip_from_end = ((i == end_item) ? end_bytes : 0); RFALSE(needed_nodes > 3, "vs-8105: too many nodes are needed"); /* get size of current item */ current_item_size = vi->vi_item_len; /* * do not take in calculation head part (from_bytes) * of from-th item */ current_item_size -= op_part_size(vi, 0 /*from start */ , start_bytes); /* do not take in calculation tail part of last item */ current_item_size -= op_part_size(vi, 1 /*from end */ , skip_from_end); /* if item fits into current node entierly */ if (total_node_size + current_item_size <= max_node_size) { snum012[needed_nodes - 1]++; total_node_size += current_item_size; start_bytes = 0; continue; } /* * virtual item length is longer, than max size of item in * a node. It is impossible for direct item */ if (current_item_size > max_node_size) { RFALSE(is_direct_le_ih(vi->vi_ih), "vs-8110: " "direct item length is %d. It can not be longer than %d", current_item_size, max_node_size); /* we will try to split it */ flow = 1; } /* as we do not split items, take new node and continue */