Lines Matching +full:left +full:- +full:shifted
15 * will shift to left/right neighbor, or to a new node, where new item
23 * have to have if we do not any shiftings, if we shift to left/right
39 "vs-8005: for INSERT mode and item number of inserted item"); in old_item_num()
41 return new_num - 1; in old_item_num()
45 "vs-8010: old_item_num: mode must be M_DELETE (mode = \'%c\'", in old_item_num()
54 struct virtual_node *vn = tb->tb_vn; in create_virtual_node()
56 struct buffer_head *Sh; /* this comes from tb->S[h] */ in create_virtual_node()
58 Sh = PATH_H_PBUFFER(tb->tb_path, h); in create_virtual_node()
61 vn->vn_size = in create_virtual_node()
62 MAX_CHILD_SIZE(Sh) - B_FREE_SPACE(Sh) + tb->insert_size[h]; in create_virtual_node()
66 vn->vn_nr_item = (vn->vn_size - DC_SIZE) / (DC_SIZE + KEY_SIZE); in create_virtual_node()
71 vn->vn_nr_item = in create_virtual_node()
72 B_NR_ITEMS(Sh) + ((vn->vn_mode == M_INSERT) ? 1 : 0) - in create_virtual_node()
73 ((vn->vn_mode == M_DELETE) ? 1 : 0); in create_virtual_node()
76 vn->vn_vi = (struct virtual_item *)(tb->tb_vn + 1); in create_virtual_node()
77 memset(vn->vn_vi, 0, vn->vn_nr_item * sizeof(struct virtual_item)); in create_virtual_node()
78 vn->vn_free_ptr += vn->vn_nr_item * sizeof(struct virtual_item); in create_virtual_node()
83 /* define the mergeability for 0-th item (if it is not being deleted) */ in create_virtual_node()
84 if (op_is_left_mergeable(&ih->ih_key, Sh->b_size) in create_virtual_node()
85 && (vn->vn_mode != M_DELETE || vn->vn_affected_item_num)) in create_virtual_node()
86 vn->vn_vi[0].vi_type |= VI_TYPE_LEFT_MERGEABLE; in create_virtual_node()
92 for (new_num = 0; new_num < vn->vn_nr_item; new_num++) { in create_virtual_node()
94 struct virtual_item *vi = vn->vn_vi + new_num; in create_virtual_node()
96 ((new_num != vn->vn_affected_item_num) ? 0 : 1); in create_virtual_node()
98 if (is_affected && vn->vn_mode == M_INSERT) in create_virtual_node()
102 j = old_item_num(new_num, vn->vn_affected_item_num, in create_virtual_node()
103 vn->vn_mode); in create_virtual_node()
105 vi->vi_item_len += ih_item_len(ih + j) + IH_SIZE; in create_virtual_node()
106 vi->vi_ih = ih + j; in create_virtual_node()
107 vi->vi_item = ih_item_body(Sh, ih + j); in create_virtual_node()
108 vi->vi_uarea = vn->vn_free_ptr; in create_virtual_node()
114 vn->vn_free_ptr += in create_virtual_node()
115 op_create_vi(vn, vi, is_affected, tb->insert_size[0]); in create_virtual_node()
116 if (tb->vn_buf + tb->vn_buf_size < vn->vn_free_ptr) in create_virtual_node()
117 reiserfs_panic(tb->tb_sb, "vs-8030", in create_virtual_node()
124 if (vn->vn_mode == M_PASTE || vn->vn_mode == M_CUT) { in create_virtual_node()
125 vn->vn_vi[new_num].vi_item_len += tb->insert_size[0]; in create_virtual_node()
127 vi->vi_new_data = vn->vn_data; in create_virtual_node()
132 if (vn->vn_mode == M_INSERT) { in create_virtual_node()
133 struct virtual_item *vi = vn->vn_vi + vn->vn_affected_item_num; in create_virtual_node()
135 RFALSE(vn->vn_ins_ih == NULL, in create_virtual_node()
136 "vs-8040: item header of inserted item is not specified"); in create_virtual_node()
137 vi->vi_item_len = tb->insert_size[0]; in create_virtual_node()
138 vi->vi_ih = vn->vn_ins_ih; in create_virtual_node()
139 vi->vi_item = vn->vn_data; in create_virtual_node()
140 vi->vi_uarea = vn->vn_free_ptr; in create_virtual_node()
143 tb->insert_size[0]); in create_virtual_node()
150 if (tb->CFR[0]) { in create_virtual_node()
153 key = internal_key(tb->CFR[0], tb->rkey[0]); in create_virtual_node()
154 if (op_is_left_mergeable(key, Sh->b_size) in create_virtual_node()
155 && (vn->vn_mode != M_DELETE in create_virtual_node()
156 || vn->vn_affected_item_num != B_NR_ITEMS(Sh) - 1)) in create_virtual_node()
157 vn->vn_vi[vn->vn_nr_item - 1].vi_type |= in create_virtual_node()
161 if (op_is_left_mergeable(key, Sh->b_size) && in create_virtual_node()
162 !(vn->vn_mode != M_DELETE in create_virtual_node()
163 || vn->vn_affected_item_num != B_NR_ITEMS(Sh) - 1)) { in create_virtual_node()
177 print_block(Sh, 0, -1, -1); in create_virtual_node()
178 reiserfs_panic(tb->tb_sb, "vs-8045", in create_virtual_node()
181 key, vn->vn_affected_item_num, in create_virtual_node()
182 vn->vn_mode, M_DELETE); in create_virtual_node()
192 * shifted to left neighbor
197 struct virtual_node *vn = tb->tb_vn; in check_left()
201 RFALSE(cur_free < 0, "vs-8050: cur_free (%d) < 0", cur_free); in check_left()
205 tb->lnum[h] = cur_free / (DC_SIZE + KEY_SIZE); in check_left()
211 if (!cur_free || !vn->vn_nr_item) { in check_left()
213 tb->lnum[h] = 0; in check_left()
214 tb->lbytes = -1; in check_left()
218 RFALSE(!PATH_H_PPARENT(tb->tb_path, 0), in check_left()
219 "vs-8055: parent does not exist or invalid"); in check_left()
221 vi = vn->vn_vi; in check_left()
223 (vn->vn_size - in check_left()
224 ((vi->vi_type & VI_TYPE_LEFT_MERGEABLE) ? IH_SIZE : 0))) { in check_left()
227 RFALSE(vn->vn_mode == M_INSERT || vn->vn_mode == M_PASTE, in check_left()
228 "vs-8055: invalid mode or balance condition failed"); in check_left()
230 tb->lnum[0] = vn->vn_nr_item; in check_left()
231 tb->lbytes = -1; in check_left()
237 /* first item may be merge with last item in left neighbor */ in check_left()
238 if (vi->vi_type & VI_TYPE_LEFT_MERGEABLE) in check_left()
239 d_size = -((int)IH_SIZE), ih_size = 0; in check_left()
241 tb->lnum[0] = 0; in check_left()
242 for (i = 0; i < vn->vn_nr_item; in check_left()
244 d_size += vi->vi_item_len; in check_left()
246 /* the item can be shifted entirely */ in check_left()
247 cur_free -= d_size; in check_left()
248 tb->lnum[0]++; in check_left()
252 /* the item cannot be shifted entirely, try to split it */ in check_left()
260 tb->lbytes = -1; in check_left()
263 cur_free -= ih_size; in check_left()
265 tb->lbytes = op_check_left(vi, cur_free, 0, 0); in check_left()
266 if (tb->lbytes != -1) in check_left()
267 /* count partially shifted item */ in check_left()
268 tb->lnum[0]++; in check_left()
278 * shifted to right neighbor
283 struct virtual_node *vn = tb->tb_vn; in check_right()
287 RFALSE(cur_free < 0, "vs-8070: cur_free < 0"); in check_right()
291 tb->rnum[h] = cur_free / (DC_SIZE + KEY_SIZE); in check_right()
297 if (!cur_free || !vn->vn_nr_item) { in check_right()
299 tb->rnum[h] = 0; in check_right()
300 tb->rbytes = -1; in check_right()
304 RFALSE(!PATH_H_PPARENT(tb->tb_path, 0), in check_right()
305 "vs-8075: parent does not exist or invalid"); in check_right()
307 vi = vn->vn_vi + vn->vn_nr_item - 1; in check_right()
309 (vn->vn_size - in check_right()
310 ((vi->vi_type & VI_TYPE_RIGHT_MERGEABLE) ? IH_SIZE : 0))) { in check_right()
313 RFALSE(vn->vn_mode == M_INSERT || vn->vn_mode == M_PASTE, in check_right()
314 "vs-8080: invalid mode or balance condition failed"); in check_right()
316 tb->rnum[h] = vn->vn_nr_item; in check_right()
317 tb->rbytes = -1; in check_right()
324 if (vi->vi_type & VI_TYPE_RIGHT_MERGEABLE) in check_right()
325 d_size = -(int)IH_SIZE, ih_size = 0; in check_right()
327 tb->rnum[0] = 0; in check_right()
328 for (i = vn->vn_nr_item - 1; i >= 0; in check_right()
329 i--, d_size = 0, ih_size = IH_SIZE, vi--) { in check_right()
330 d_size += vi->vi_item_len; in check_right()
332 /* the item can be shifted entirely */ in check_right()
333 cur_free -= d_size; in check_right()
334 tb->rnum[0]++; in check_right()
345 tb->rbytes = -1; in check_right()
353 cur_free -= ih_size; /* cur_free is still > 0 */ in check_right()
355 tb->rbytes = op_check_right(vi, cur_free); in check_right()
356 if (tb->rbytes != -1) in check_right()
357 /* count partially shifted item */ in check_right()
358 tb->rnum[0]++; in check_right()
367 * from - number of items, which are shifted to left neighbor entirely
368 * to - number of item, which are shifted to right neighbor entirely
369 * from_bytes - number of bytes of boundary item (or directory entries)
370 * which are shifted to left neighbor
371 * to_bytes - number of bytes of boundary item (or directory entries)
372 * which are shifted to right neighbor
380 struct virtual_node *vn = tb->tb_vn; in get_num_ver()
391 * number of first bytes (entries for directory) of start_item-th item in get_num_ver()
397 * number of last bytes (entries for directory) of end_item-th item in get_num_ver()
408 split_item_positions[0] = -1; in get_num_ver()
409 split_item_positions[1] = -1; in get_num_ver()
417 RFALSE(tb->insert_size[h] < 0 || (mode != M_INSERT && mode != M_PASTE), in get_num_ver()
418 "vs-8100: insert_size < 0 in overflow"); in get_num_ver()
420 max_node_size = MAX_CHILD_SIZE(PATH_H_PBUFFER(tb->tb_path, h)); in get_num_ver()
423 * snum012 [0-2] - number of items, that lay in get_num_ver()
426 snum012[3] = -1; /* s1bytes */ in get_num_ver()
427 snum012[4] = -1; /* s2bytes */ in get_num_ver()
431 i = ((to - from) * (KEY_SIZE + DC_SIZE) + DC_SIZE); in get_num_ver()
441 /* start from 'from'-th item */ in get_num_ver()
444 start_bytes = ((from_bytes != -1) ? from_bytes : 0); in get_num_ver()
446 /* last included item is the 'end_item'-th one */ in get_num_ver()
447 end_item = vn->vn_nr_item - to - 1; in get_num_ver()
448 /* do not count last 'end_bytes' units of 'end_item'-th item */ in get_num_ver()
449 end_bytes = (to_bytes != -1) ? to_bytes : 0; in get_num_ver()
452 * go through all item beginning from the start_item-th item in get_num_ver()
453 * and ending by the end_item-th item. Do not count first in get_num_ver()
454 * 'start_bytes' units of 'start_item'-th item and last in get_num_ver()
455 * 'end_bytes' of 'end_item'-th item in get_num_ver()
458 struct virtual_item *vi = vn->vn_vi + i; in get_num_ver()
461 RFALSE(needed_nodes > 3, "vs-8105: too many nodes are needed"); in get_num_ver()
464 current_item_size = vi->vi_item_len; in get_num_ver()
468 * of from-th item in get_num_ver()
470 current_item_size -= in get_num_ver()
474 current_item_size -= in get_num_ver()
479 snum012[needed_nodes - 1]++; in get_num_ver()
490 RFALSE(is_direct_le_ih(vi->vi_ih), in get_num_ver()
491 "vs-8110: " in get_num_ver()
501 i--; in get_num_ver()
513 free_space = max_node_size - total_node_size - IH_SIZE; in get_num_ver()
521 if (units == -1) { in get_num_ver()
522 needed_nodes++, i--, total_node_size = 0; in get_num_ver()
529 snum012[needed_nodes - 1 + 3] = units; in get_num_ver()
532 reiserfs_warning(tb->tb_sb, "vs-8111", in get_num_ver()
534 snum012[needed_nodes - 1]++; in get_num_ver()
535 split_item_positions[needed_nodes - 1] = i; in get_num_ver()
537 /* continue from the same item with start_bytes != -1 */ in get_num_ver()
539 i--; in get_num_ver()
544 * sum012[4] (if it is not -1) contains number of units of which in get_num_ver()
545 * are to be in S1new, snum012[3] - to be in S0. They are supposed in get_num_ver()
556 && from_bytes != -1) ? from_bytes : 0); in get_num_ver()
559 && end_bytes != -1) ? end_bytes : 0); in get_num_ver()
566 op_unit_num(&vn->vn_vi[split_item_num]) - snum012[4] - in get_num_ver()
567 bytes_to_r - bytes_to_l - bytes_to_S1new; in get_num_ver()
569 if (vn->vn_vi[split_item_num].vi_index != TYPE_DIRENTRY && in get_num_ver()
570 vn->vn_vi[split_item_num].vi_index != TYPE_INDIRECT) in get_num_ver()
571 reiserfs_warning(tb->tb_sb, "vs-8115", in get_num_ver()
584 && from_bytes != -1) ? from_bytes : 0); in get_num_ver()
587 && end_bytes != -1) ? end_bytes : 0); in get_num_ver()
590 && snum012[4] != -1) ? snum012[4] : 0); in get_num_ver()
594 op_unit_num(&vn->vn_vi[split_item_num]) - snum012[3] - in get_num_ver()
595 bytes_to_r - bytes_to_l - bytes_to_S2new; in get_num_ver()
609 * lnum number of items from S[h] that must be shifted to L[h];
610 * rnum number of items from S[h] that must be shifted to R[h];
613 * lbytes number of bytes which flow to the left neighbor from the
614 * item that is not shifted entirely
616 * item that is not shifted entirely
625 tb->lnum[h] = lnum; in set_parameters()
626 tb->rnum[h] = rnum; in set_parameters()
627 tb->blknum[h] = blk_num; in set_parameters()
632 tb->s0num = *s012++; in set_parameters()
633 tb->snum[0] = *s012++; in set_parameters()
634 tb->snum[1] = *s012++; in set_parameters()
635 tb->sbytes[0] = *s012++; in set_parameters()
636 tb->sbytes[1] = *s012; in set_parameters()
638 tb->lbytes = lb; in set_parameters()
639 tb->rbytes = rb; in set_parameters()
641 PROC_INFO_ADD(tb->tb_sb, lnum[h], lnum); in set_parameters()
642 PROC_INFO_ADD(tb->tb_sb, rnum[h], rnum); in set_parameters()
644 PROC_INFO_ADD(tb->tb_sb, lbytes[h], lb); in set_parameters()
645 PROC_INFO_ADD(tb->tb_sb, rbytes[h], rb); in set_parameters()
649 * check if node disappears if we shift tb->lnum[0] items to left
650 * neighbor and tb->rnum[0] to the right one.
654 struct virtual_node *vn = tb->tb_vn; in is_leaf_removable()
660 * number of items that will be shifted to left (right) neighbor in is_leaf_removable()
663 to_left = tb->lnum[0] - ((tb->lbytes != -1) ? 1 : 0); in is_leaf_removable()
664 to_right = tb->rnum[0] - ((tb->rbytes != -1) ? 1 : 0); in is_leaf_removable()
665 remain_items = vn->vn_nr_item; in is_leaf_removable()
668 remain_items -= (to_left + to_right); in is_leaf_removable()
670 /* all content of node can be shifted to neighbors */ in is_leaf_removable()
672 set_parameters(tb, 0, to_left, vn->vn_nr_item - to_left, 0, in is_leaf_removable()
673 NULL, -1, -1); in is_leaf_removable()
678 if (remain_items > 1 || tb->lbytes == -1 || tb->rbytes == -1) in is_leaf_removable()
684 size = op_unit_num(&vn->vn_vi[to_left]); in is_leaf_removable()
686 if (tb->lbytes + tb->rbytes >= size) { in is_leaf_removable()
688 tb->lbytes, -1); in is_leaf_removable()
698 struct virtual_node *vn = tb->tb_vn; in are_leaves_removable()
702 S0 = PATH_H_PBUFFER(tb->tb_path, 0); in are_leaves_removable()
705 if (vn->vn_nr_item) { in are_leaves_removable()
706 if (vn->vn_vi[0].vi_type & VI_TYPE_LEFT_MERGEABLE) in are_leaves_removable()
709 if (vn->vn_vi[vn->vn_nr_item - 1]. in are_leaves_removable()
717 "vs-8125: item number must be 1: it is %d", in are_leaves_removable()
721 if (tb->CFR[0] in are_leaves_removable()
722 && !comp_short_le_keys(&ih->ih_key, in are_leaves_removable()
723 internal_key(tb->CFR[0], in are_leaves_removable()
724 tb->rkey[0]))) in are_leaves_removable()
727 * somewhere at the left side should exist first in are_leaves_removable()
739 * we might check that left neighbor exists in are_leaves_removable()
743 "vs-8130: first directory item can not be removed until directory is not empty"); in are_leaves_removable()
748 if (MAX_CHILD_SIZE(S0) + vn->vn_size <= rfree + lfree + ih_size) { in are_leaves_removable()
749 set_parameters(tb, 0, -1, -1, -1, NULL, -1, -1); in are_leaves_removable()
750 PROC_INFO_INC(tb->tb_sb, leaves_removable); in are_leaves_removable()
763 to_l = (MAX_NR_KEY(Sh)+1 - lpar + vn->vn_nr_item + 1) / 2 -\
764 (MAX_NR_KEY(Sh) + 1 - lpar);\
766 set_parameters (tb, h, to_l, 0, lnver, NULL, -1, -1);\
772 tb->lbytes, -1);\
774 set_parameters (tb, h, lpar - (tb->lbytes!=-1), 0, lnver, snum012+lset,\
775 -1, -1);\
783 to_r = (MAX_NR_KEY(Sh)+1 - rpar + vn->vn_nr_item + 1) / 2 - (MAX_NR_KEY(Sh) + 1 - rpar);\
785 set_parameters (tb, h, 0, to_r, rnver, NULL, -1, -1);\
791 -1, tb->rbytes);\
793 set_parameters (tb, h, 0, rpar - (tb->rbytes!=-1), rnver, snum012+rset,\
794 -1, -1);\
801 pathrelse(tb->tb_path); in free_buffers_in_tb()
804 brelse(tb->L[i]); in free_buffers_in_tb()
805 brelse(tb->R[i]); in free_buffers_in_tb()
806 brelse(tb->FL[i]); in free_buffers_in_tb()
807 brelse(tb->FR[i]); in free_buffers_in_tb()
808 brelse(tb->CFL[i]); in free_buffers_in_tb()
809 brelse(tb->CFR[i]); in free_buffers_in_tb()
811 tb->L[i] = NULL; in free_buffers_in_tb()
812 tb->R[i] = NULL; in free_buffers_in_tb()
813 tb->FL[i] = NULL; in free_buffers_in_tb()
814 tb->FR[i] = NULL; in free_buffers_in_tb()
815 tb->CFL[i] = NULL; in free_buffers_in_tb()
816 tb->CFR[i] = NULL; in free_buffers_in_tb()
822 * Returns: SCHEDULE_OCCURRED - schedule occurred while the function worked;
823 * CARRY_ON - schedule didn't occur while the function worked;
824 * NO_DISK_SPACE - no disk space.
826 /* The function is NOT SCHEDULE-SAFE! */
829 struct buffer_head *new_bh, *Sh = PATH_H_PBUFFER(tb->tb_path, h); in get_empty_nodes()
834 struct super_block *sb = tb->tb_sb; in get_empty_nodes()
840 * number_of_freeblk = tb->cur_blknum can be non-zero if a schedule in get_empty_nodes()
857 for (counter = 0, number_of_freeblk = tb->cur_blknum; in get_empty_nodes()
859 number_of_freeblk -= in get_empty_nodes()
860 (tb->blknum[counter]) ? (tb->blknum[counter] - in get_empty_nodes()
865 amount_needed = (Sh) ? (tb->blknum[h] - 1) : 1; in get_empty_nodes()
871 amount_needed -= number_of_freeblk; in get_empty_nodes()
876 * No need to check quota - is not allocated for blocks used in get_empty_nodes()
888 "PAP-8135: reiserfs_new_blocknrs failed when got new blocks"); in get_empty_nodes()
894 "PAP-8140: journaled or dirty buffer %b for the new block", in get_empty_nodes()
898 RFALSE(tb->FEB[tb->cur_blknum], in get_empty_nodes()
899 "PAP-8141: busy slot for new buffer"); in get_empty_nodes()
902 tb->FEB[tb->cur_blknum++] = new_bh; in get_empty_nodes()
912 * Get free space of the left neighbor, which is stored in the parent
913 * node of the left neighbor.
920 if ((f = PATH_H_PPARENT(tb->tb_path, h)) == NULL || in get_lfree()
921 (l = tb->FL[h]) == NULL) in get_lfree()
925 order = PATH_H_B_ITEM_ORDER(tb->tb_path, h) - 1; in get_lfree()
931 return (MAX_CHILD_SIZE(f) - dc_size(B_N_CHILD(f, order))); in get_lfree()
943 if ((f = PATH_H_PPARENT(tb->tb_path, h)) == NULL || in get_rfree()
944 (r = tb->FR[h]) == NULL) in get_rfree()
948 order = PATH_H_B_ITEM_ORDER(tb->tb_path, h) + 1; in get_rfree()
954 return (MAX_CHILD_SIZE(f) - dc_size(B_N_CHILD(f, order))); in get_rfree()
958 /* Check whether left neighbor is in memory. */
961 struct buffer_head *father, *left; in is_left_neighbor_in_cache() local
962 struct super_block *sb = tb->tb_sb; in is_left_neighbor_in_cache()
966 /* Father of the left neighbor does not exist. */ in is_left_neighbor_in_cache()
967 if (!tb->FL[h]) in is_left_neighbor_in_cache()
971 father = PATH_H_PBUFFER(tb->tb_path, h + 1); in is_left_neighbor_in_cache()
975 !B_IS_IN_TREE(tb->FL[h]) || in is_left_neighbor_in_cache()
977 !buffer_uptodate(tb->FL[h]), in is_left_neighbor_in_cache()
978 "vs-8165: F[h] (%b) or FL[h] (%b) is invalid", in is_left_neighbor_in_cache()
979 father, tb->FL[h]); in is_left_neighbor_in_cache()
982 * Get position of the pointer to the left neighbor in is_left_neighbor_in_cache()
983 * into the left father. in is_left_neighbor_in_cache()
985 left_neighbor_position = (father == tb->FL[h]) ? in is_left_neighbor_in_cache()
986 tb->lkey[h] : B_NR_ITEMS(tb->FL[h]); in is_left_neighbor_in_cache()
987 /* Get left neighbor block number. */ in is_left_neighbor_in_cache()
989 B_N_CHILD_NUM(tb->FL[h], left_neighbor_position); in is_left_neighbor_in_cache()
990 /* Look for the left neighbor in the cache. */ in is_left_neighbor_in_cache()
991 if ((left = sb_find_get_block(sb, left_neighbor_blocknr))) { in is_left_neighbor_in_cache()
993 RFALSE(buffer_uptodate(left) && !B_IS_IN_TREE(left), in is_left_neighbor_in_cache()
994 "vs-8170: left neighbor (%b %z) is not in the tree", in is_left_neighbor_in_cache()
995 left, left); in is_left_neighbor_in_cache()
996 put_bh(left); in is_left_neighbor_in_cache()
1009 item_ops[cpu_key_k_type(key)]->decrement_key(key); in decrement_key()
1013 * Calculate far left/right parent of the left/right neighbor of the
1014 * current node, that is calculate the left/right (FL[h]/FR[h]) neighbor
1016 * Calculate left/right common parent of the current node and L[h]/R[h].
1017 * Calculate left/right delimiting key position.
1018 * Returns: PATH_INCORRECT - path in the tree is not correct
1019 * SCHEDULE_OCCURRED - schedule occurred while the function worked
1020 * CARRY_ON - schedule didn't occur while the function
1030 struct treepath *path = tb->tb_path; in get_far_parent()
1045 "PAP-8180: invalid path length"); in get_far_parent()
1047 for (; counter > FIRST_PATH_ELEMENT_OFFSET; counter--) { in get_far_parent()
1053 (parent = PATH_OFFSET_PBUFFER(path, counter - 1))) in get_far_parent()
1059 counter - 1)) > in get_far_parent()
1068 PATH_OFFSET_PBUFFER(path, counter)->b_blocknr) in get_far_parent()
1080 /*(*pcom_father = parent)->b_count++; */ in get_far_parent()
1092 (tb->tb_path, in get_far_parent()
1093 FIRST_PATH_ELEMENT_OFFSET)->b_blocknr == in get_far_parent()
1094 SB_ROOT_BLOCK(tb->tb_sb)) { in get_far_parent()
1102 "PAP-8185: (%b %z) level too small", in get_far_parent()
1110 int depth = reiserfs_write_unlock_nested(tb->tb_sb); in get_far_parent()
1112 reiserfs_write_lock_nested(tb->tb_sb, depth); in get_far_parent()
1121 * left/right neighbor. Now we are getting the parent of the in get_far_parent()
1122 * left/right neighbor. in get_far_parent()
1125 /* Form key to get parent of the left/right neighbor. */ in get_far_parent()
1129 LEFT_PARENTS) ? (tb->lkey[h - 1] = in get_far_parent()
1130 position - in get_far_parent()
1131 1) : (tb->rkey[h - in get_far_parent()
1139 (tb->tb_sb, &s_lr_father_key, &s_path_to_neighbor_father, in get_far_parent()
1153 "PAP-8190: (%b %z) level too small", *pfather, *pfather); in get_far_parent()
1155 FIRST_PATH_ELEMENT_OFFSET, "PAP-8192: path length is too small"); in get_far_parent()
1157 s_path_to_neighbor_father.path_length--; in get_far_parent()
1167 * Calculate numbers of left and right delimiting keys position:
1169 * Returns: SCHEDULE_OCCURRED - schedule occurred while the function worked
1170 * CARRY_ON - schedule didn't occur while the function worked
1174 struct treepath *path = tb->tb_path; in get_parents()
1177 path_offset = PATH_H_PATH_OFFSET(tb->tb_path, h); in get_parents()
1187 brelse(tb->FL[h]); in get_parents()
1188 brelse(tb->CFL[h]); in get_parents()
1189 brelse(tb->FR[h]); in get_parents()
1190 brelse(tb->CFR[h]); in get_parents()
1191 tb->FL[h] = NULL; in get_parents()
1192 tb->CFL[h] = NULL; in get_parents()
1193 tb->FR[h] = NULL; in get_parents()
1194 tb->CFR[h] = NULL; in get_parents()
1199 position = PATH_OFFSET_POSITION(path, path_offset - 1); in get_parents()
1202 curf = PATH_OFFSET_PBUFFER(path, path_offset - 1); in get_parents()
1203 curcf = PATH_OFFSET_PBUFFER(path, path_offset - 1); in get_parents()
1206 tb->lkey[h] = position - 1; in get_parents()
1210 * left neighbor of the current node. Calculate current in get_parents()
1222 brelse(tb->FL[h]); in get_parents()
1223 tb->FL[h] = curf; /* New initialization of FL[h]. */ in get_parents()
1224 brelse(tb->CFL[h]); in get_parents()
1225 tb->CFL[h] = curcf; /* New initialization of CFL[h]. */ in get_parents()
1229 "PAP-8195: FL (%b) or CFL (%b) is invalid", curf, curcf); in get_parents()
1247 curf = PATH_OFFSET_PBUFFER(path, path_offset - 1); in get_parents()
1248 curcf = PATH_OFFSET_PBUFFER(path, path_offset - 1); in get_parents()
1251 tb->rkey[h] = position; in get_parents()
1254 brelse(tb->FR[h]); in get_parents()
1256 tb->FR[h] = curf; in get_parents()
1258 brelse(tb->CFR[h]); in get_parents()
1260 tb->CFR[h] = curcf; in get_parents()
1264 "PAP-8205: FR (%b) or CFR (%b) is invalid", curf, curcf); in get_parents()
1276 struct buffer_head *Sh = PATH_H_PBUFFER(tb->tb_path, h); in can_node_be_removed()
1277 int levbytes = tb->insert_size[h]; in can_node_be_removed()
1282 if (tb->CFR[h]) in can_node_be_removed()
1283 r_key = internal_key(tb->CFR[h], tb->rkey[h]); in can_node_be_removed()
1287 - in can_node_be_removed()
1289 && op_is_left_mergeable(&ih->ih_key, Sh->b_size)) ? IH_SIZE : 0) in can_node_be_removed()
1290 - in can_node_be_removed()
1292 && op_is_left_mergeable(r_key, Sh->b_size)) ? IH_SIZE : 0) in can_node_be_removed()
1298 tb->s0num = in can_node_be_removed()
1301 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1); in can_node_be_removed()
1305 PROC_INFO_INC(tb->tb_sb, can_node_be_removed[h]); in can_node_be_removed()
1317 * mode i - insert, p - paste;
1318 * Returns: 1 - schedule occurred;
1319 * 0 - balancing for higher levels needed;
1320 * -1 - no balancing for higher levels needed;
1321 * -2 - no disk space.
1326 struct virtual_node *vn = tb->tb_vn; in ip_check_balance()
1340 * we shift to the left, rnver is the number if we shift to the in ip_check_balance()
1359 * and 5th - s2bytes in ip_check_balance()
1362 * 0,1 - do not shift and do not shift but bottle in ip_check_balance()
1363 * 2 - shift only whole item to left in ip_check_balance()
1364 * 3 - shift to left and bottle as much as possible in ip_check_balance()
1365 * 4,5 - shift to right (whole items and as much as possible in ip_check_balance()
1366 * 6,7 - shift to both directions (whole items and as much as possible) in ip_check_balance()
1373 Sh = PATH_H_PBUFFER(tb->tb_path, h); in ip_check_balance()
1374 levbytes = tb->insert_size[h]; in ip_check_balance()
1379 reiserfs_panic(tb->tb_sb, "vs-8210", in ip_check_balance()
1384 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1); in ip_check_balance()
1391 reiserfs_panic(tb->tb_sb, "vs-8215", "incorrect " in ip_check_balance()
1408 if (can_node_be_removed(vn->vn_mode, lfree, sfree, rfree, tb, h) == in ip_check_balance()
1415 * determine maximal number of items we can shift to the left in ip_check_balance()
1417 * that can flow to the left neighbor from the left most liquid in ip_check_balance()
1418 * item that cannot be shifted from S[0] entirely (returned value) in ip_check_balance()
1426 * item that cannot be shifted from S[0] entirely (returned value) in ip_check_balance()
1434 if (h && (tb->rnum[h] + tb->lnum[h] >= vn->vn_nr_item + 1)) { in ip_check_balance()
1441 * routine we set the left node equal to the right node, in ip_check_balance()
1446 ((MAX_NR_KEY(Sh) << 1) + 2 - tb->lnum[h] - tb->rnum[h] + in ip_check_balance()
1447 vn->vn_nr_item + 1) / 2 - (MAX_NR_KEY(Sh) + 1 - in ip_check_balance()
1448 tb->rnum[h]); in ip_check_balance()
1449 set_parameters(tb, h, vn->vn_nr_item + 1 - to_r, to_r, 0, NULL, in ip_check_balance()
1450 -1, -1); in ip_check_balance()
1459 (tb->lnum[h] >= vn->vn_nr_item + 1 || in ip_check_balance()
1460 tb->rnum[h] >= vn->vn_nr_item + 1), in ip_check_balance()
1461 "vs-8220: tree is not balanced on internal level"); in ip_check_balance()
1462 RFALSE(!h && ((tb->lnum[h] >= vn->vn_nr_item && (tb->lbytes == -1)) || in ip_check_balance()
1463 (tb->rnum[h] >= vn->vn_nr_item && (tb->rbytes == -1))), in ip_check_balance()
1464 "vs-8225: tree is not balanced on leaf level"); in ip_check_balance()
1483 tb->s0num = vn->vn_nr_item; in ip_check_balance()
1484 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1); in ip_check_balance()
1494 * lpar, rpar - number of items we can shift to left/right in ip_check_balance()
1496 * nset, lset, rset, lrset - shows, whether flowing items in ip_check_balance()
1512 lpar = tb->lnum[h]; in ip_check_balance()
1513 rpar = tb->rnum[h]; in ip_check_balance()
1517 * nothing is shifted to the neighbors, as well as number of in ip_check_balance()
1523 nver = get_num_ver(vn->vn_mode, tb, h, in ip_check_balance()
1524 0, -1, h ? vn->vn_nr_item : 0, -1, in ip_check_balance()
1532 * between S[0] and S1 (S1 - the first new node) in ip_check_balance()
1534 nver1 = get_num_ver(vn->vn_mode, tb, h, in ip_check_balance()
1535 0, -1, 0, -1, in ip_check_balance()
1544 * most liquid item to be shifted are shifted to the left in ip_check_balance()
1550 lnver = get_num_ver(vn->vn_mode, tb, h, in ip_check_balance()
1551 lpar - ((h || tb->lbytes == -1) ? 0 : 1), in ip_check_balance()
1552 -1, h ? vn->vn_nr_item : 0, -1, in ip_check_balance()
1557 lnver1 = get_num_ver(vn->vn_mode, tb, h, in ip_check_balance()
1558 lpar - in ip_check_balance()
1559 ((tb->lbytes != -1) ? 1 : 0), in ip_check_balance()
1560 tb->lbytes, 0, -1, in ip_check_balance()
1568 * r_shift_num first items and r_shift_bytes of the left most in ip_check_balance()
1569 * liquid item to be shifted are shifted to the right neighbor, in ip_check_balance()
1575 rnver = get_num_ver(vn->vn_mode, tb, h, in ip_check_balance()
1576 0, -1, in ip_check_balance()
1577 h ? (vn->vn_nr_item - rpar) : (rpar - in ip_check_balance()
1578 ((tb-> in ip_check_balance()
1580 -1) ? 1 : in ip_check_balance()
1581 0)), -1, in ip_check_balance()
1586 rnver1 = get_num_ver(vn->vn_mode, tb, h, in ip_check_balance()
1587 0, -1, in ip_check_balance()
1588 (rpar - in ip_check_balance()
1589 ((tb->rbytes != -1) ? 1 : 0)), in ip_check_balance()
1590 tb->rbytes, in ip_check_balance()
1599 * items are shifted in both directions, as well as number in ip_check_balance()
1605 lrnver = get_num_ver(vn->vn_mode, tb, h, in ip_check_balance()
1606 lpar - ((h || tb->lbytes == -1) ? 0 : 1), in ip_check_balance()
1607 -1, in ip_check_balance()
1608 h ? (vn->vn_nr_item - rpar) : (rpar - in ip_check_balance()
1609 ((tb-> in ip_check_balance()
1611 -1) ? 1 : in ip_check_balance()
1612 0)), -1, in ip_check_balance()
1617 lrnver1 = get_num_ver(vn->vn_mode, tb, h, in ip_check_balance()
1618 lpar - in ip_check_balance()
1619 ((tb->lbytes != -1) ? 1 : 0), in ip_check_balance()
1620 tb->lbytes, in ip_check_balance()
1621 (rpar - in ip_check_balance()
1622 ((tb->rbytes != -1) ? 1 : 0)), in ip_check_balance()
1623 tb->rbytes, in ip_check_balance()
1639 (tb->lnum[h] != 1 || in ip_check_balance()
1640 tb->rnum[h] != 1 || in ip_check_balance()
1642 || h != 1), "vs-8230: bad h"); in ip_check_balance()
1644 set_parameters(tb, h, tb->lnum[h], tb->rnum[h], in ip_check_balance()
1646 tb->lbytes, tb->rbytes); in ip_check_balance()
1649 tb->lnum[h] - in ip_check_balance()
1650 ((tb->lbytes == -1) ? 0 : 1), in ip_check_balance()
1651 tb->rnum[h] - in ip_check_balance()
1652 ((tb->rbytes == -1) ? 0 : 1), in ip_check_balance()
1653 lrnver, snum012 + lrset, -1, -1); in ip_check_balance()
1663 set_parameters(tb, h, 0, 0, nver, snum012 + nset, -1, in ip_check_balance()
1664 -1); in ip_check_balance()
1670 * direction either to the left or to the right is required in ip_check_balance()
1674 * if shifting to the left is better than in ip_check_balance()
1684 * shifting to the left in ip_check_balance()
1717 * mode i - insert, p - paste;
1718 * Returns: 1 - schedule occurred;
1719 * 0 - balancing for higher levels needed;
1720 * -1 - no balancing for higher levels needed;
1721 * -2 - no disk space.
1724 * the internal part of S+tree is as for the B-trees.
1728 struct virtual_node *vn = tb->tb_vn; in dc_check_balance_internal()
1738 Sh = PATH_H_PBUFFER(tb->tb_path, h); in dc_check_balance_internal()
1739 Fh = PATH_H_PPARENT(tb->tb_path, h); in dc_check_balance_internal()
1742 * using tb->insert_size[h], which is negative in this case, in dc_check_balance_internal()
1751 if (vn->vn_nr_item > 0) { in dc_check_balance_internal()
1752 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1); in dc_check_balance_internal()
1760 set_parameters(tb, h, 0, 0, 0, NULL, -1, -1); in dc_check_balance_internal()
1779 if (vn->vn_nr_item >= MIN_NR_KEY(Sh)) { in dc_check_balance_internal()
1784 if (vn->vn_nr_item == MIN_NR_KEY(Sh)) { in dc_check_balance_internal()
1786 if (tb->lnum[h] >= vn->vn_nr_item + 1) { in dc_check_balance_internal()
1792 PATH_H_B_ITEM_ORDER(tb->tb_path, in dc_check_balance_internal()
1794 0) ? B_NR_ITEMS(tb->FL[h]) : n - 1; in dc_check_balance_internal()
1795 n = dc_size(B_N_CHILD(tb->FL[h], order_L)) / in dc_check_balance_internal()
1797 set_parameters(tb, h, -n - 1, 0, 0, NULL, -1, in dc_check_balance_internal()
1798 -1); in dc_check_balance_internal()
1803 if (tb->rnum[h] >= vn->vn_nr_item + 1) { in dc_check_balance_internal()
1809 PATH_H_B_ITEM_ORDER(tb->tb_path, in dc_check_balance_internal()
1812 n = dc_size(B_N_CHILD(tb->FR[h], order_R)) / in dc_check_balance_internal()
1814 set_parameters(tb, h, 0, -n - 1, 0, NULL, -1, in dc_check_balance_internal()
1815 -1); in dc_check_balance_internal()
1824 if (tb->rnum[h] + tb->lnum[h] >= vn->vn_nr_item + 1) { in dc_check_balance_internal()
1828 ((MAX_NR_KEY(Sh) << 1) + 2 - tb->lnum[h] - in dc_check_balance_internal()
1829 tb->rnum[h] + vn->vn_nr_item + 1) / 2 - in dc_check_balance_internal()
1830 (MAX_NR_KEY(Sh) + 1 - tb->rnum[h]); in dc_check_balance_internal()
1831 set_parameters(tb, h, vn->vn_nr_item + 1 - to_r, to_r, in dc_check_balance_internal()
1832 0, NULL, -1, -1); in dc_check_balance_internal()
1837 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1); in dc_check_balance_internal()
1845 /* Check whether we can merge S[h] with left neighbor. */ in dc_check_balance_internal()
1846 if (tb->lnum[h] >= vn->vn_nr_item + 1) in dc_check_balance_internal()
1848 || tb->rnum[h] < vn->vn_nr_item + 1 || !tb->FR[h]) { in dc_check_balance_internal()
1854 PATH_H_B_ITEM_ORDER(tb->tb_path, in dc_check_balance_internal()
1856 0) ? B_NR_ITEMS(tb->FL[h]) : n - 1; in dc_check_balance_internal()
1857 n = dc_size(B_N_CHILD(tb->FL[h], order_L)) / (DC_SIZE + in dc_check_balance_internal()
1859 set_parameters(tb, h, -n - 1, 0, 0, NULL, -1, -1); in dc_check_balance_internal()
1864 if (tb->rnum[h] >= vn->vn_nr_item + 1) { in dc_check_balance_internal()
1870 PATH_H_B_ITEM_ORDER(tb->tb_path, in dc_check_balance_internal()
1872 n = dc_size(B_N_CHILD(tb->FR[h], order_R)) / (DC_SIZE + in dc_check_balance_internal()
1874 set_parameters(tb, h, 0, -n - 1, 0, NULL, -1, -1); in dc_check_balance_internal()
1879 if (tb->rnum[h] + tb->lnum[h] >= vn->vn_nr_item + 1) { in dc_check_balance_internal()
1883 ((MAX_NR_KEY(Sh) << 1) + 2 - tb->lnum[h] - tb->rnum[h] + in dc_check_balance_internal()
1884 vn->vn_nr_item + 1) / 2 - (MAX_NR_KEY(Sh) + 1 - in dc_check_balance_internal()
1885 tb->rnum[h]); in dc_check_balance_internal()
1886 set_parameters(tb, h, vn->vn_nr_item + 1 - to_r, to_r, 0, NULL, in dc_check_balance_internal()
1887 -1, -1); in dc_check_balance_internal()
1892 RFALSE(!tb->FL[h] && !tb->FR[h], "vs-8235: trying to borrow for root"); in dc_check_balance_internal()
1895 if (is_left_neighbor_in_cache(tb, h) || !tb->FR[h]) { in dc_check_balance_internal()
1899 (MAX_NR_KEY(Sh) + 1 - tb->lnum[h] + vn->vn_nr_item + in dc_check_balance_internal()
1900 1) / 2 - (vn->vn_nr_item + 1); in dc_check_balance_internal()
1901 set_parameters(tb, h, -from_l, 0, 1, NULL, -1, -1); in dc_check_balance_internal()
1906 -((MAX_NR_KEY(Sh) + 1 - tb->rnum[h] + vn->vn_nr_item + in dc_check_balance_internal()
1907 1) / 2 - (vn->vn_nr_item + 1)), 1, NULL, -1, -1); in dc_check_balance_internal()
1919 * mode i - insert, p - paste;
1920 * Returns: 1 - schedule occurred;
1921 * 0 - balancing for higher levels needed;
1922 * -1 - no balancing for higher levels needed;
1923 * -2 - no disk space.
1927 struct virtual_node *vn = tb->tb_vn; in dc_check_balance_leaf()
1947 S0 = PATH_H_PBUFFER(tb->tb_path, 0); in dc_check_balance_leaf()
1948 F0 = PATH_H_PPARENT(tb->tb_path, 0); in dc_check_balance_leaf()
1950 levbytes = tb->insert_size[h]; in dc_check_balance_leaf()
1956 RFALSE(-levbytes >= maxsize - B_FREE_SPACE(S0), in dc_check_balance_leaf()
1957 "vs-8240: attempt to create empty buffer tree"); in dc_check_balance_leaf()
1959 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1); in dc_check_balance_leaf()
1977 * determine maximal number of items we can shift to the left/right in dc_check_balance_leaf()
1979 * left/right neighbor from the left/right most liquid item that in dc_check_balance_leaf()
1980 * cannot be shifted from S[0] entirely in dc_check_balance_leaf()
1985 /* check whether we can merge S with left neighbor. */ in dc_check_balance_leaf()
1986 if (tb->lnum[0] >= vn->vn_nr_item && tb->lbytes == -1) in dc_check_balance_leaf()
1987 …if (is_left_neighbor_in_cache(tb, h) || ((tb->rnum[0] - ((tb->rbytes == -1) ? 0 : 1)) < vn->vn_nr_… in dc_check_balance_leaf()
1988 !tb->FR[h]) { in dc_check_balance_leaf()
1990 RFALSE(!tb->FL[h], in dc_check_balance_leaf()
1991 "vs-8245: dc_check_balance_leaf: FL[h] must exist"); in dc_check_balance_leaf()
1993 /* set parameter to merge S[0] with its left neighbor */ in dc_check_balance_leaf()
1994 set_parameters(tb, h, -1, 0, 0, NULL, -1, -1); in dc_check_balance_leaf()
1999 if (tb->rnum[0] >= vn->vn_nr_item && tb->rbytes == -1) { in dc_check_balance_leaf()
2000 set_parameters(tb, h, 0, -1, 0, NULL, -1, -1); in dc_check_balance_leaf()
2012 tb->s0num = vn->vn_nr_item; in dc_check_balance_leaf()
2013 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1); in dc_check_balance_leaf()
2025 * mode d - delete, c - cut.
2026 * Returns: 1 - schedule occurred;
2027 * 0 - balancing for higher levels needed;
2028 * -1 - no balancing for higher levels needed;
2029 * -2 - no disk space.
2033 RFALSE(!(PATH_H_PBUFFER(tb->tb_path, h)), in dc_check_balance()
2034 "vs-8250: S is not initialized"); in dc_check_balance()
2055 * mode i - insert, p - paste, d - delete, c - cut.
2056 * Returns: 1 - schedule occurred;
2057 * 0 - balancing for higher levels needed;
2058 * -1 - no balancing for higher levels needed;
2059 * -2 - no disk space.
2070 vn = tb->tb_vn = (struct virtual_node *)(tb->vn_buf); in check_balance()
2071 vn->vn_free_ptr = (char *)(tb->tb_vn + 1); in check_balance()
2072 vn->vn_mode = mode; in check_balance()
2073 vn->vn_affected_item_num = inum; in check_balance()
2074 vn->vn_pos_in_item = pos_in_item; in check_balance()
2075 vn->vn_ins_ih = ins_ih; in check_balance()
2076 vn->vn_data = data; in check_balance()
2078 RFALSE(mode == M_INSERT && !vn->vn_ins_ih, in check_balance()
2079 "vs-8255: ins_ih can not be 0 in insert mode"); in check_balance()
2082 if (tb->insert_size[h] > 0) in check_balance()
2093 struct treepath *path = tb->tb_path; in get_direct_parent()
2095 path_offset = PATH_H_PATH_OFFSET(tb->tb_path, h); in get_direct_parent()
2100 RFALSE(path_offset < FIRST_PATH_ELEMENT_OFFSET - 1, in get_direct_parent()
2101 "PAP-8260: invalid offset in the path"); in get_direct_parent()
2103 if (PATH_OFFSET_PBUFFER(path, FIRST_PATH_ELEMENT_OFFSET)-> in get_direct_parent()
2104 b_blocknr == SB_ROOT_BLOCK(tb->tb_sb)) { in get_direct_parent()
2106 PATH_OFFSET_PBUFFER(path, path_offset - 1) = NULL; in get_direct_parent()
2107 PATH_OFFSET_POSITION(path, path_offset - 1) = 0; in get_direct_parent()
2116 (bh = PATH_OFFSET_PBUFFER(path, path_offset - 1))) in get_direct_parent()
2121 path_offset - 1)) > B_NR_ITEMS(bh)) in get_direct_parent()
2126 PATH_OFFSET_PBUFFER(path, path_offset)->b_blocknr) in get_direct_parent()
2130 int depth = reiserfs_write_unlock_nested(tb->tb_sb); in get_direct_parent()
2132 reiserfs_write_lock_nested(tb->tb_sb, depth); in get_direct_parent()
2148 * Returns: SCHEDULE_OCCURRED - schedule occurred while the function worked;
2149 * CARRY_ON - schedule didn't occur while the function worked;
2154 path_offset = PATH_H_PATH_OFFSET(tb->tb_path, h + 1); in get_neighbors()
2156 struct super_block *sb = tb->tb_sb; in get_neighbors()
2162 if (tb->lnum[h]) { in get_neighbors()
2163 /* We need left neighbor to balance S[h]. */ in get_neighbors()
2165 bh = PATH_OFFSET_PBUFFER(tb->tb_path, path_offset); in get_neighbors()
2167 RFALSE(bh == tb->FL[h] && in get_neighbors()
2168 !PATH_OFFSET_POSITION(tb->tb_path, path_offset), in get_neighbors()
2169 "PAP-8270: invalid position in the parent"); in get_neighbors()
2173 tb->FL[h]) ? tb->lkey[h] : B_NR_ITEMS(tb-> in get_neighbors()
2175 son_number = B_N_CHILD_NUM(tb->FL[h], child_position); in get_neighbors()
2176 depth = reiserfs_write_unlock_nested(tb->tb_sb); in get_neighbors()
2178 reiserfs_write_lock_nested(tb->tb_sb, depth); in get_neighbors()
2187 RFALSE(!B_IS_IN_TREE(tb->FL[h]) || in get_neighbors()
2188 child_position > B_NR_ITEMS(tb->FL[h]) || in get_neighbors()
2189 B_N_CHILD_NUM(tb->FL[h], child_position) != in get_neighbors()
2190 bh->b_blocknr, "PAP-8275: invalid parent"); in get_neighbors()
2191 RFALSE(!B_IS_IN_TREE(bh), "PAP-8280: invalid child"); in get_neighbors()
2194 MAX_CHILD_SIZE(bh) - in get_neighbors()
2195 dc_size(B_N_CHILD(tb->FL[0], child_position)), in get_neighbors()
2196 "PAP-8290: invalid child size of left neighbor"); in get_neighbors()
2198 brelse(tb->L[h]); in get_neighbors()
2199 tb->L[h] = bh; in get_neighbors()
2203 if (tb->rnum[h]) { in get_neighbors()
2205 bh = PATH_OFFSET_PBUFFER(tb->tb_path, path_offset); in get_neighbors()
2207 RFALSE(bh == tb->FR[h] && in get_neighbors()
2208 PATH_OFFSET_POSITION(tb->tb_path, in get_neighbors()
2211 "PAP-8295: invalid position in the parent"); in get_neighbors()
2214 (bh == tb->FR[h]) ? tb->rkey[h] + 1 : 0; in get_neighbors()
2215 son_number = B_N_CHILD_NUM(tb->FR[h], child_position); in get_neighbors()
2216 depth = reiserfs_write_unlock_nested(tb->tb_sb); in get_neighbors()
2218 reiserfs_write_lock_nested(tb->tb_sb, depth); in get_neighbors()
2226 brelse(tb->R[h]); in get_neighbors()
2227 tb->R[h] = bh; in get_neighbors()
2231 MAX_CHILD_SIZE(bh) - in get_neighbors()
2232 dc_size(B_N_CHILD(tb->FR[0], child_position)), in get_neighbors()
2233 "PAP-8300: invalid child size of right neighbor (%d != %d - %d)", in get_neighbors()
2235 dc_size(B_N_CHILD(tb->FR[0], child_position))); in get_neighbors()
2245 unsigned long blocksize = sb->s_blocksize; in get_virtual_node_size()
2249 max_num_of_items = (blocksize - BLKH_SIZE) / (IH_SIZE + MIN_ITEM_LEN); in get_virtual_node_size()
2250 max_num_of_entries = (blocksize - BLKH_SIZE - IH_SIZE) / in get_virtual_node_size()
2271 size = get_virtual_node_size(tb->tb_sb, PATH_PLAST_BUFFER(tb->tb_path)); in get_mem_for_virtual_node()
2274 if (size > tb->vn_buf_size) { in get_mem_for_virtual_node()
2275 if (tb->vn_buf) { in get_mem_for_virtual_node()
2277 kfree(tb->vn_buf); in get_mem_for_virtual_node()
2283 tb->vn_buf_size = size; in get_mem_for_virtual_node()
2297 tb->vn_buf_size = 0; in get_mem_for_virtual_node()
2299 tb->vn_buf = buf; in get_mem_for_virtual_node()
2304 tb->vn_buf = buf; in get_mem_for_virtual_node()
2319 if (atomic_read(&(bh->b_count)) <= 0) in tb_buffer_sanity_check()
2321 reiserfs_panic(sb, "jmacd-1", "negative or zero " in tb_buffer_sanity_check()
2326 reiserfs_panic(sb, "jmacd-2", "buffer is not up " in tb_buffer_sanity_check()
2331 reiserfs_panic(sb, "jmacd-3", "buffer is not " in tb_buffer_sanity_check()
2335 if (bh->b_bdev != sb->s_bdev) in tb_buffer_sanity_check()
2336 reiserfs_panic(sb, "jmacd-4", "buffer has wrong " in tb_buffer_sanity_check()
2340 if (bh->b_size != sb->s_blocksize) in tb_buffer_sanity_check()
2341 reiserfs_panic(sb, "jmacd-5", "buffer has wrong " in tb_buffer_sanity_check()
2345 if (bh->b_blocknr > SB_BLOCK_COUNT(sb)) in tb_buffer_sanity_check()
2346 reiserfs_panic(sb, "jmacd-6", "buffer block " in tb_buffer_sanity_check()
2376 for (i = tb->tb_path->path_length; in wait_tb_buffers_until_unlocked()
2377 !locked && i > ILLEGAL_PATH_ELEMENT_OFFSET; i--) { in wait_tb_buffers_until_unlocked()
2378 if (PATH_OFFSET_PBUFFER(tb->tb_path, i)) { in wait_tb_buffers_until_unlocked()
2382 * in the tree --clm in wait_tb_buffers_until_unlocked()
2385 if (PATH_PLAST_BUFFER(tb->tb_path) == in wait_tb_buffers_until_unlocked()
2386 PATH_OFFSET_PBUFFER(tb->tb_path, i)) in wait_tb_buffers_until_unlocked()
2387 tb_buffer_sanity_check(tb->tb_sb, in wait_tb_buffers_until_unlocked()
2389 (tb->tb_path, in wait_tb_buffers_until_unlocked()
2391 tb->tb_path-> in wait_tb_buffers_until_unlocked()
2392 path_length - i); in wait_tb_buffers_until_unlocked()
2394 if (!clear_all_dirty_bits(tb->tb_sb, in wait_tb_buffers_until_unlocked()
2396 (tb->tb_path, in wait_tb_buffers_until_unlocked()
2399 PATH_OFFSET_PBUFFER(tb->tb_path, in wait_tb_buffers_until_unlocked()
2405 for (i = 0; !locked && i < MAX_HEIGHT && tb->insert_size[i]; in wait_tb_buffers_until_unlocked()
2408 if (tb->lnum[i]) { in wait_tb_buffers_until_unlocked()
2410 if (tb->L[i]) { in wait_tb_buffers_until_unlocked()
2411 tb_buffer_sanity_check(tb->tb_sb, in wait_tb_buffers_until_unlocked()
2412 tb->L[i], in wait_tb_buffers_until_unlocked()
2415 (tb->tb_sb, tb->L[i])) in wait_tb_buffers_until_unlocked()
2416 locked = tb->L[i]; in wait_tb_buffers_until_unlocked()
2419 if (!locked && tb->FL[i]) { in wait_tb_buffers_until_unlocked()
2420 tb_buffer_sanity_check(tb->tb_sb, in wait_tb_buffers_until_unlocked()
2421 tb->FL[i], in wait_tb_buffers_until_unlocked()
2424 (tb->tb_sb, tb->FL[i])) in wait_tb_buffers_until_unlocked()
2425 locked = tb->FL[i]; in wait_tb_buffers_until_unlocked()
2428 if (!locked && tb->CFL[i]) { in wait_tb_buffers_until_unlocked()
2429 tb_buffer_sanity_check(tb->tb_sb, in wait_tb_buffers_until_unlocked()
2430 tb->CFL[i], in wait_tb_buffers_until_unlocked()
2433 (tb->tb_sb, tb->CFL[i])) in wait_tb_buffers_until_unlocked()
2434 locked = tb->CFL[i]; in wait_tb_buffers_until_unlocked()
2439 if (!locked && (tb->rnum[i])) { in wait_tb_buffers_until_unlocked()
2441 if (tb->R[i]) { in wait_tb_buffers_until_unlocked()
2442 tb_buffer_sanity_check(tb->tb_sb, in wait_tb_buffers_until_unlocked()
2443 tb->R[i], in wait_tb_buffers_until_unlocked()
2446 (tb->tb_sb, tb->R[i])) in wait_tb_buffers_until_unlocked()
2447 locked = tb->R[i]; in wait_tb_buffers_until_unlocked()
2450 if (!locked && tb->FR[i]) { in wait_tb_buffers_until_unlocked()
2451 tb_buffer_sanity_check(tb->tb_sb, in wait_tb_buffers_until_unlocked()
2452 tb->FR[i], in wait_tb_buffers_until_unlocked()
2455 (tb->tb_sb, tb->FR[i])) in wait_tb_buffers_until_unlocked()
2456 locked = tb->FR[i]; in wait_tb_buffers_until_unlocked()
2459 if (!locked && tb->CFR[i]) { in wait_tb_buffers_until_unlocked()
2460 tb_buffer_sanity_check(tb->tb_sb, in wait_tb_buffers_until_unlocked()
2461 tb->CFR[i], in wait_tb_buffers_until_unlocked()
2464 (tb->tb_sb, tb->CFR[i])) in wait_tb_buffers_until_unlocked()
2465 locked = tb->CFR[i]; in wait_tb_buffers_until_unlocked()
2477 * That code is inside CONFIG_REISERFS_CHECK as well. --clm in wait_tb_buffers_until_unlocked()
2480 if (tb->FEB[i]) { in wait_tb_buffers_until_unlocked()
2482 (tb->tb_sb, tb->FEB[i])) in wait_tb_buffers_until_unlocked()
2483 locked = tb->FEB[i]; in wait_tb_buffers_until_unlocked()
2492 reiserfs_warning(tb->tb_sb, "reiserfs-8200", in wait_tb_buffers_until_unlocked()
2503 depth = reiserfs_write_unlock_nested(tb->tb_sb); in wait_tb_buffers_until_unlocked()
2505 reiserfs_write_lock_nested(tb->tb_sb, depth); in wait_tb_buffers_until_unlocked()
2527 * Grumble grumble. -Hans
2532 * are needed and then getting as many of them in parallel as possible? -Hans
2535 * op_mode i - insert, d - delete, c - cut (truncate), p - paste (append)
2538 * pos_in_item - comment this if you can
2541 * Returns: 1 - schedule occurred while the function worked;
2542 * 0 - schedule didn't occur while the function worked;
2543 * -1 - if no_disk_space
2549 int ret, h, item_num = PATH_LAST_POSITION(tb->tb_path); in fix_nodes()
2557 struct buffer_head *tbS0 = PATH_PLAST_BUFFER(tb->tb_path); in fix_nodes()
2559 ++REISERFS_SB(tb->tb_sb)->s_fix_nodes; in fix_nodes()
2561 pos_in_item = tb->tb_path->pos_in_item; in fix_nodes()
2563 tb->fs_gen = get_generation(tb->tb_sb); in fix_nodes()
2571 reiserfs_prepare_for_journal(tb->tb_sb, in fix_nodes()
2572 SB_BUFFER_WITH_SB(tb->tb_sb), 1); in fix_nodes()
2573 journal_mark_dirty(tb->transaction_handle, in fix_nodes()
2574 SB_BUFFER_WITH_SB(tb->tb_sb)); in fix_nodes()
2580 int depth = reiserfs_write_unlock_nested(tb->tb_sb); in fix_nodes()
2582 reiserfs_write_lock_nested(tb->tb_sb, depth); in fix_nodes()
2587 if (REISERFS_SB(tb->tb_sb)->cur_tb) { in fix_nodes()
2589 reiserfs_panic(tb->tb_sb, "PAP-8305", in fix_nodes()
2594 reiserfs_panic(tb->tb_sb, "PAP-8320", "S[0] (%b %z) is " in fix_nodes()
2603 reiserfs_panic(tb->tb_sb, "PAP-8330", "Incorrect " in fix_nodes()
2604 "item number %d (in S0 - %d) in case " in fix_nodes()
2612 print_block(tbS0, 0, -1, -1); in fix_nodes()
2613 reiserfs_panic(tb->tb_sb, "PAP-8335", "Incorrect " in fix_nodes()
2617 tb->insert_size[0]); in fix_nodes()
2621 reiserfs_panic(tb->tb_sb, "PAP-8340", "Incorrect mode " in fix_nodes()
2627 /* FIXME: maybe -ENOMEM when tb->vn_buf == 0? Now just repeat */ in fix_nodes()
2631 for (h = 0; h < MAX_HEIGHT && tb->insert_size[h]; h++) { in fix_nodes()
2644 if (h != MAX_HEIGHT - 1) in fix_nodes()
2645 tb->insert_size[h + 1] = 0; in fix_nodes()
2671 if (!PATH_H_PBUFFER(tb->tb_path, h)) { in fix_nodes()
2673 RFALSE(tb->blknum[h] != 1, in fix_nodes()
2674 "PAP-8350: creating new empty root"); in fix_nodes()
2676 if (h < MAX_HEIGHT - 1) in fix_nodes()
2677 tb->insert_size[h + 1] = 0; in fix_nodes()
2678 } else if (!PATH_H_PBUFFER(tb->tb_path, h + 1)) { in fix_nodes()
2685 if (tb->blknum[h] > 1) { in fix_nodes()
2687 RFALSE(h == MAX_HEIGHT - 1, in fix_nodes()
2688 "PAP-8355: attempt to create too high of a tree"); in fix_nodes()
2690 tb->insert_size[h + 1] = in fix_nodes()
2692 KEY_SIZE) * (tb->blknum[h] - 1) + in fix_nodes()
2694 } else if (h < MAX_HEIGHT - 1) in fix_nodes()
2695 tb->insert_size[h + 1] = 0; in fix_nodes()
2697 tb->insert_size[h + 1] = in fix_nodes()
2698 (DC_SIZE + KEY_SIZE) * (tb->blknum[h] - 1); in fix_nodes()
2719 * failure. If the first is the case - the search will be in fix_nodes()
2720 * repeated. For now - free all resources acquired so far except in fix_nodes()
2728 pathrelse_and_restore(tb->tb_sb, tb->tb_path); in fix_nodes()
2730 pathrelse(tb->tb_path); in fix_nodes()
2735 reiserfs_restore_prepared_buffer(tb->tb_sb, in fix_nodes()
2736 tb->L[i]); in fix_nodes()
2737 reiserfs_restore_prepared_buffer(tb->tb_sb, in fix_nodes()
2738 tb->R[i]); in fix_nodes()
2739 reiserfs_restore_prepared_buffer(tb->tb_sb, in fix_nodes()
2740 tb->FL[i]); in fix_nodes()
2741 reiserfs_restore_prepared_buffer(tb->tb_sb, in fix_nodes()
2742 tb->FR[i]); in fix_nodes()
2743 reiserfs_restore_prepared_buffer(tb->tb_sb, in fix_nodes()
2744 tb-> in fix_nodes()
2746 reiserfs_restore_prepared_buffer(tb->tb_sb, in fix_nodes()
2747 tb-> in fix_nodes()
2751 brelse(tb->L[i]); in fix_nodes()
2752 brelse(tb->R[i]); in fix_nodes()
2753 brelse(tb->FL[i]); in fix_nodes()
2754 brelse(tb->FR[i]); in fix_nodes()
2755 brelse(tb->CFL[i]); in fix_nodes()
2756 brelse(tb->CFR[i]); in fix_nodes()
2758 tb->L[i] = NULL; in fix_nodes()
2759 tb->R[i] = NULL; in fix_nodes()
2760 tb->FL[i] = NULL; in fix_nodes()
2761 tb->FR[i] = NULL; in fix_nodes()
2762 tb->CFL[i] = NULL; in fix_nodes()
2763 tb->CFR[i] = NULL; in fix_nodes()
2768 if (tb->FEB[i]) in fix_nodes()
2770 (tb->tb_sb, tb->FEB[i]); in fix_nodes()
2783 pathrelse_and_restore(tb->tb_sb, tb->tb_path); in unfix_nodes()
2787 reiserfs_restore_prepared_buffer(tb->tb_sb, tb->L[i]); in unfix_nodes()
2788 reiserfs_restore_prepared_buffer(tb->tb_sb, tb->R[i]); in unfix_nodes()
2789 reiserfs_restore_prepared_buffer(tb->tb_sb, tb->FL[i]); in unfix_nodes()
2790 reiserfs_restore_prepared_buffer(tb->tb_sb, tb->FR[i]); in unfix_nodes()
2791 reiserfs_restore_prepared_buffer(tb->tb_sb, tb->CFL[i]); in unfix_nodes()
2792 reiserfs_restore_prepared_buffer(tb->tb_sb, tb->CFR[i]); in unfix_nodes()
2794 brelse(tb->L[i]); in unfix_nodes()
2795 brelse(tb->R[i]); in unfix_nodes()
2796 brelse(tb->FL[i]); in unfix_nodes()
2797 brelse(tb->FR[i]); in unfix_nodes()
2798 brelse(tb->CFL[i]); in unfix_nodes()
2799 brelse(tb->CFR[i]); in unfix_nodes()
2804 if (tb->FEB[i]) { in unfix_nodes()
2805 b_blocknr_t blocknr = tb->FEB[i]->b_blocknr; in unfix_nodes()
2807 * de-allocated block which was not used by in unfix_nodes()
2810 brelse(tb->FEB[i]); in unfix_nodes()
2811 reiserfs_free_block(tb->transaction_handle, NULL, in unfix_nodes()
2814 if (tb->used[i]) { in unfix_nodes()
2816 brelse(tb->used[i]); in unfix_nodes()
2820 kfree(tb->vn_buf); in unfix_nodes()