e497fd963118d7f271fbbc6e99961032f51ecf05
3 #include "kerncompat.h"
4 #include "radix-tree.h"
7 #include "print-tree.h"
9 int split_node(struct ctree_root
*root
, struct ctree_path
*path
, int level
);
10 int split_leaf(struct ctree_root
*root
, struct ctree_path
*path
, int data_size
);
11 int push_node_left(struct ctree_root
*root
, struct ctree_path
*path
, int level
);
12 int push_node_right(struct ctree_root
*root
,
13 struct ctree_path
*path
, int level
);
14 int del_ptr(struct ctree_root
*root
, struct ctree_path
*path
, int level
);
16 inline void init_path(struct ctree_path
*p
)
18 memset(p
, 0, sizeof(*p
));
21 void release_path(struct ctree_root
*root
, struct ctree_path
*p
)
24 for (i
= 0; i
< MAX_LEVEL
; i
++) {
27 tree_block_release(root
, p
->nodes
[i
]);
32 * The leaf data grows from end-to-front in the node.
33 * this returns the address of the start of the last item,
34 * which is the stop of the leaf data stack
36 static inline unsigned int leaf_data_end(struct leaf
*leaf
)
38 unsigned int nr
= leaf
->header
.nritems
;
40 return sizeof(leaf
->data
);
41 return leaf
->items
[nr
-1].offset
;
45 * The space between the end of the leaf items and
46 * the start of the leaf data. IOW, how much room
47 * the leaf has left for both items and data
49 int leaf_free_space(struct leaf
*leaf
)
51 int data_end
= leaf_data_end(leaf
);
52 int nritems
= leaf
->header
.nritems
;
53 char *items_end
= (char *)(leaf
->items
+ nritems
+ 1);
54 return (char *)(leaf
->data
+ data_end
) - (char *)items_end
;
58 * compare two keys in a memcmp fashion
60 int comp_keys(struct key
*k1
, struct key
*k2
)
62 if (k1
->objectid
> k2
->objectid
)
64 if (k1
->objectid
< k2
->objectid
)
66 if (k1
->flags
> k2
->flags
)
68 if (k1
->flags
< k2
->flags
)
70 if (k1
->offset
> k2
->offset
)
72 if (k1
->offset
< k2
->offset
)
78 * search for key in the array p. items p are item_size apart
79 * and there are 'max' items in p
80 * the slot in the array is returned via slot, and it points to
81 * the place where you would insert key if it is not found in
84 * slot may point to max if the key is bigger than all of the keys
86 int generic_bin_search(char *p
, int item_size
, struct key
*key
,
96 mid
= (low
+ high
) / 2;
97 tmp
= (struct key
*)(p
+ mid
* item_size
);
98 ret
= comp_keys(tmp
, key
);
113 int bin_search(struct node
*c
, struct key
*key
, int *slot
)
115 if (is_leaf(c
->header
.flags
)) {
116 struct leaf
*l
= (struct leaf
*)c
;
117 return generic_bin_search((void *)l
->items
, sizeof(struct item
),
118 key
, c
->header
.nritems
, slot
);
120 return generic_bin_search((void *)c
->keys
, sizeof(struct key
),
121 key
, c
->header
.nritems
, slot
);
127 * look for key in the tree. path is filled in with nodes along the way
128 * if key is found, we return zero and you can find the item in the leaf
129 * level of the path (level 0)
131 * If the key isn't found, the path points to the slot where it should
134 int search_slot(struct ctree_root
*root
, struct key
*key
,
135 struct ctree_path
*p
, int ins_len
)
137 struct tree_buffer
*b
= root
->node
;
146 level
= node_level(c
->header
.flags
);
148 ret
= bin_search(c
, key
, &slot
);
149 if (!is_leaf(c
->header
.flags
)) {
152 p
->slots
[level
] = slot
;
154 c
->header
.nritems
== NODEPTRS_PER_BLOCK
) {
155 int sret
= split_node(root
, p
, level
);
161 slot
= p
->slots
[level
];
162 } else if (ins_len
< 0 &&
163 c
->header
.nritems
<= NODEPTRS_PER_BLOCK
/4) {
164 u64 blocknr
= b
->blocknr
;
165 slot
= p
->slots
[level
+1];
167 if (push_node_left(root
, p
, level
))
168 push_node_right(root
, p
, level
);
169 if (c
->header
.nritems
== 0 &&
170 level
< MAX_LEVEL
- 1 &&
171 p
->nodes
[level
+ 1]) {
172 int tslot
= p
->slots
[level
+ 1];
174 p
->slots
[level
+ 1] = slot
;
175 del_ptr(root
, p
, level
+ 1);
176 p
->slots
[level
+ 1] = tslot
;
177 tree_block_release(root
, b
);
178 free_extent(root
, blocknr
, 1);
180 tree_block_release(root
, b
);
184 slot
= p
->slots
[level
];
186 b
= read_tree_block(root
, c
->blockptrs
[slot
]);
189 struct leaf
*l
= (struct leaf
*)c
;
190 p
->slots
[level
] = slot
;
191 if (ins_len
> 0 && leaf_free_space(l
) <
192 sizeof(struct item
) + ins_len
) {
193 int sret
= split_leaf(root
, p
, ins_len
);
205 * adjust the pointers going up the tree, starting at level
206 * making sure the right key of each node is points to 'key'.
207 * This is used after shifting pointers to the left, so it stops
208 * fixing up pointers when a given leaf/node is not in slot 0 of the
211 static void fixup_low_keys(struct ctree_root
*root
,
212 struct ctree_path
*path
, struct key
*key
,
216 for (i
= level
; i
< MAX_LEVEL
; i
++) {
218 int tslot
= path
->slots
[i
];
221 t
= &path
->nodes
[i
]->node
;
222 memcpy(t
->keys
+ tslot
, key
, sizeof(*key
));
223 write_tree_block(root
, path
->nodes
[i
]);
230 * try to push data from one node into the next node left in the
231 * tree. The src node is found at specified level in the path.
232 * If some bytes were pushed, return 0, otherwise return 1.
234 * Lower nodes/leaves in the path are not touched, higher nodes may
235 * be modified to reflect the push.
237 * The path is altered to reflect the push.
239 int push_node_left(struct ctree_root
*root
, struct ctree_path
*path
, int level
)
247 struct tree_buffer
*t
;
248 struct tree_buffer
*right_buf
;
250 if (level
== MAX_LEVEL
- 1 || path
->nodes
[level
+ 1] == 0)
252 slot
= path
->slots
[level
+ 1];
256 t
= read_tree_block(root
,
257 path
->nodes
[level
+ 1]->node
.blockptrs
[slot
- 1]);
259 right_buf
= path
->nodes
[level
];
260 right
= &right_buf
->node
;
261 left_nritems
= left
->header
.nritems
;
262 right_nritems
= right
->header
.nritems
;
263 push_items
= NODEPTRS_PER_BLOCK
- (left_nritems
+ 1);
264 if (push_items
<= 0) {
265 tree_block_release(root
, t
);
269 if (right_nritems
< push_items
)
270 push_items
= right_nritems
;
271 memcpy(left
->keys
+ left_nritems
, right
->keys
,
272 push_items
* sizeof(struct key
));
273 memcpy(left
->blockptrs
+ left_nritems
, right
->blockptrs
,
274 push_items
* sizeof(u64
));
275 memmove(right
->keys
, right
->keys
+ push_items
,
276 (right_nritems
- push_items
) * sizeof(struct key
));
277 memmove(right
->blockptrs
, right
->blockptrs
+ push_items
,
278 (right_nritems
- push_items
) * sizeof(u64
));
279 right
->header
.nritems
-= push_items
;
280 left
->header
.nritems
+= push_items
;
282 /* adjust the pointers going up the tree */
283 fixup_low_keys(root
, path
, right
->keys
, level
+ 1);
285 write_tree_block(root
, t
);
286 write_tree_block(root
, right_buf
);
288 /* then fixup the leaf pointer in the path */
289 if (path
->slots
[level
] < push_items
) {
290 path
->slots
[level
] += left_nritems
;
291 tree_block_release(root
, path
->nodes
[level
]);
292 path
->nodes
[level
] = t
;
293 path
->slots
[level
+ 1] -= 1;
295 path
->slots
[level
] -= push_items
;
296 tree_block_release(root
, t
);
302 * try to push data from one node into the next node right in the
303 * tree. The src node is found at specified level in the path.
304 * If some bytes were pushed, return 0, otherwise return 1.
306 * Lower nodes/leaves in the path are not touched, higher nodes may
307 * be modified to reflect the push.
309 * The path is altered to reflect the push.
311 int push_node_right(struct ctree_root
*root
, struct ctree_path
*path
, int level
)
314 struct tree_buffer
*t
;
315 struct tree_buffer
*src_buffer
;
322 /* can't push from the root */
323 if (level
== MAX_LEVEL
- 1 || path
->nodes
[level
+ 1] == 0)
326 /* only try to push inside the node higher up */
327 slot
= path
->slots
[level
+ 1];
328 if (slot
== NODEPTRS_PER_BLOCK
- 1)
331 if (slot
>= path
->nodes
[level
+ 1]->node
.header
.nritems
-1)
334 t
= read_tree_block(root
,
335 path
->nodes
[level
+ 1]->node
.blockptrs
[slot
+ 1]);
337 src_buffer
= path
->nodes
[level
];
338 src
= &src_buffer
->node
;
339 dst_nritems
= dst
->header
.nritems
;
340 src_nritems
= src
->header
.nritems
;
341 push_items
= NODEPTRS_PER_BLOCK
- (dst_nritems
+ 1);
342 if (push_items
<= 0) {
343 tree_block_release(root
, t
);
347 if (src_nritems
< push_items
)
348 push_items
= src_nritems
;
349 memmove(dst
->keys
+ push_items
, dst
->keys
,
350 dst_nritems
* sizeof(struct key
));
351 memcpy(dst
->keys
, src
->keys
+ src_nritems
- push_items
,
352 push_items
* sizeof(struct key
));
354 memmove(dst
->blockptrs
+ push_items
, dst
->blockptrs
,
355 dst_nritems
* sizeof(u64
));
356 memcpy(dst
->blockptrs
, src
->blockptrs
+ src_nritems
- push_items
,
357 push_items
* sizeof(u64
));
359 src
->header
.nritems
-= push_items
;
360 dst
->header
.nritems
+= push_items
;
362 /* adjust the pointers going up the tree */
363 memcpy(path
->nodes
[level
+ 1]->node
.keys
+ path
->slots
[level
+ 1] + 1,
364 dst
->keys
, sizeof(struct key
));
366 write_tree_block(root
, path
->nodes
[level
+ 1]);
367 write_tree_block(root
, t
);
368 write_tree_block(root
, src_buffer
);
370 /* then fixup the pointers in the path */
371 if (path
->slots
[level
] >= src
->header
.nritems
) {
372 path
->slots
[level
] -= src
->header
.nritems
;
373 tree_block_release(root
, path
->nodes
[level
]);
374 path
->nodes
[level
] = t
;
375 path
->slots
[level
+ 1] += 1;
377 tree_block_release(root
, t
);
382 static int insert_new_root(struct ctree_root
*root
,
383 struct ctree_path
*path
, int level
)
385 struct tree_buffer
*t
;
388 struct key
*lower_key
;
390 BUG_ON(path
->nodes
[level
]);
391 BUG_ON(path
->nodes
[level
-1] != root
->node
);
393 t
= alloc_free_block(root
);
395 memset(c
, 0, sizeof(c
));
396 c
->header
.nritems
= 1;
397 c
->header
.flags
= node_level(level
);
398 c
->header
.blocknr
= t
->blocknr
;
399 c
->header
.parentid
= root
->node
->node
.header
.parentid
;
400 lower
= &path
->nodes
[level
-1]->node
;
401 if (is_leaf(lower
->header
.flags
))
402 lower_key
= &((struct leaf
*)lower
)->items
[0].key
;
404 lower_key
= lower
->keys
;
405 memcpy(c
->keys
, lower_key
, sizeof(struct key
));
406 c
->blockptrs
[0] = path
->nodes
[level
-1]->blocknr
;
407 /* the super has an extra ref to root->node */
408 tree_block_release(root
, root
->node
);
411 write_tree_block(root
, t
);
412 path
->nodes
[level
] = t
;
413 path
->slots
[level
] = 0;
418 * worker function to insert a single pointer in a node.
419 * the node should have enough room for the pointer already
420 * slot and level indicate where you want the key to go, and
421 * blocknr is the block the key points to.
423 int insert_ptr(struct ctree_root
*root
,
424 struct ctree_path
*path
, struct key
*key
,
425 u64 blocknr
, int slot
, int level
)
430 BUG_ON(!path
->nodes
[level
]);
431 lower
= &path
->nodes
[level
]->node
;
432 nritems
= lower
->header
.nritems
;
435 if (nritems
== NODEPTRS_PER_BLOCK
)
437 if (slot
!= nritems
) {
438 memmove(lower
->keys
+ slot
+ 1, lower
->keys
+ slot
,
439 (nritems
- slot
) * sizeof(struct key
));
440 memmove(lower
->blockptrs
+ slot
+ 1, lower
->blockptrs
+ slot
,
441 (nritems
- slot
) * sizeof(u64
));
443 memcpy(lower
->keys
+ slot
, key
, sizeof(struct key
));
444 lower
->blockptrs
[slot
] = blocknr
;
445 lower
->header
.nritems
++;
446 if (lower
->keys
[1].objectid
== 0)
448 write_tree_block(root
, path
->nodes
[level
]);
452 int split_node(struct ctree_root
*root
, struct ctree_path
*path
, int level
)
454 struct tree_buffer
*t
;
456 struct tree_buffer
*split_buffer
;
461 ret
= push_node_left(root
, path
, level
);
464 ret
= push_node_right(root
, path
, level
);
467 t
= path
->nodes
[level
];
469 if (t
== root
->node
) {
470 /* trying to split the root, lets make a new one */
471 ret
= insert_new_root(root
, path
, level
+ 1);
475 split_buffer
= alloc_free_block(root
);
476 split
= &split_buffer
->node
;
477 split
->header
.flags
= c
->header
.flags
;
478 split
->header
.blocknr
= split_buffer
->blocknr
;
479 split
->header
.parentid
= root
->node
->node
.header
.parentid
;
480 mid
= (c
->header
.nritems
+ 1) / 2;
481 memcpy(split
->keys
, c
->keys
+ mid
,
482 (c
->header
.nritems
- mid
) * sizeof(struct key
));
483 memcpy(split
->blockptrs
, c
->blockptrs
+ mid
,
484 (c
->header
.nritems
- mid
) * sizeof(u64
));
485 split
->header
.nritems
= c
->header
.nritems
- mid
;
486 c
->header
.nritems
= mid
;
487 write_tree_block(root
, t
);
488 write_tree_block(root
, split_buffer
);
489 insert_ptr(root
, path
, split
->keys
, split_buffer
->blocknr
,
490 path
->slots
[level
+ 1] + 1, level
+ 1);
491 if (path
->slots
[level
] >= mid
) {
492 path
->slots
[level
] -= mid
;
493 tree_block_release(root
, t
);
494 path
->nodes
[level
] = split_buffer
;
495 path
->slots
[level
+ 1] += 1;
497 tree_block_release(root
, split_buffer
);
503 * how many bytes are required to store the items in a leaf. start
504 * and nr indicate which items in the leaf to check. This totals up the
505 * space used both by the item structs and the item data
507 int leaf_space_used(struct leaf
*l
, int start
, int nr
)
510 int end
= start
+ nr
- 1;
514 data_len
= l
->items
[start
].offset
+ l
->items
[start
].size
;
515 data_len
= data_len
- l
->items
[end
].offset
;
516 data_len
+= sizeof(struct item
) * nr
;
521 * push some data in the path leaf to the left, trying to free up at
522 * least data_size bytes. returns zero if the push worked, nonzero otherwise
524 int push_leaf_left(struct ctree_root
*root
, struct ctree_path
*path
,
527 struct tree_buffer
*right_buf
= path
->nodes
[0];
528 struct leaf
*right
= &right_buf
->leaf
;
529 struct tree_buffer
*t
;
537 int old_left_nritems
;
539 slot
= path
->slots
[1];
543 if (!path
->nodes
[1]) {
546 t
= read_tree_block(root
, path
->nodes
[1]->node
.blockptrs
[slot
- 1]);
548 free_space
= leaf_free_space(left
);
549 if (free_space
< data_size
+ sizeof(struct item
)) {
550 tree_block_release(root
, t
);
553 for (i
= 0; i
< right
->header
.nritems
; i
++) {
554 item
= right
->items
+ i
;
555 if (path
->slots
[0] == i
)
556 push_space
+= data_size
+ sizeof(*item
);
557 if (item
->size
+ sizeof(*item
) + push_space
> free_space
)
560 push_space
+= item
->size
+ sizeof(*item
);
562 if (push_items
== 0) {
563 tree_block_release(root
, t
);
566 /* push data from right to left */
567 memcpy(left
->items
+ left
->header
.nritems
,
568 right
->items
, push_items
* sizeof(struct item
));
569 push_space
= LEAF_DATA_SIZE
- right
->items
[push_items
-1].offset
;
570 memcpy(left
->data
+ leaf_data_end(left
) - push_space
,
571 right
->data
+ right
->items
[push_items
- 1].offset
,
573 old_left_nritems
= left
->header
.nritems
;
574 BUG_ON(old_left_nritems
< 0);
576 for(i
= old_left_nritems
; i
< old_left_nritems
+ push_items
; i
++) {
577 left
->items
[i
].offset
-= LEAF_DATA_SIZE
-
578 left
->items
[old_left_nritems
-1].offset
;
580 left
->header
.nritems
+= push_items
;
582 /* fixup right node */
583 push_space
= right
->items
[push_items
-1].offset
- leaf_data_end(right
);
584 memmove(right
->data
+ LEAF_DATA_SIZE
- push_space
, right
->data
+
585 leaf_data_end(right
), push_space
);
586 memmove(right
->items
, right
->items
+ push_items
,
587 (right
->header
.nritems
- push_items
) * sizeof(struct item
));
588 right
->header
.nritems
-= push_items
;
589 push_space
= LEAF_DATA_SIZE
;
591 for (i
= 0; i
< right
->header
.nritems
; i
++) {
592 right
->items
[i
].offset
= push_space
- right
->items
[i
].size
;
593 push_space
= right
->items
[i
].offset
;
596 write_tree_block(root
, t
);
597 write_tree_block(root
, right_buf
);
599 fixup_low_keys(root
, path
, &right
->items
[0].key
, 1);
601 /* then fixup the leaf pointer in the path */
602 if (path
->slots
[0] < push_items
) {
603 path
->slots
[0] += old_left_nritems
;
604 tree_block_release(root
, path
->nodes
[0]);
608 tree_block_release(root
, t
);
609 path
->slots
[0] -= push_items
;
611 BUG_ON(path
->slots
[0] < 0);
616 * split the path's leaf in two, making sure there is at least data_size
617 * available for the resulting leaf level of the path.
619 int split_leaf(struct ctree_root
*root
, struct ctree_path
*path
, int data_size
)
621 struct tree_buffer
*l_buf
= path
->nodes
[0];
622 struct leaf
*l
= &l_buf
->leaf
;
627 struct tree_buffer
*right_buffer
;
628 int space_needed
= data_size
+ sizeof(struct item
);
634 if (push_leaf_left(root
, path
, data_size
) == 0) {
635 l_buf
= path
->nodes
[0];
637 if (leaf_free_space(l
) >= sizeof(struct item
) + data_size
)
640 if (!path
->nodes
[1]) {
641 ret
= insert_new_root(root
, path
, 1);
645 slot
= path
->slots
[0];
646 nritems
= l
->header
.nritems
;
647 mid
= (nritems
+ 1)/ 2;
649 right_buffer
= alloc_free_block(root
);
650 BUG_ON(!right_buffer
);
651 BUG_ON(mid
== nritems
);
652 right
= &right_buffer
->leaf
;
653 memset(right
, 0, sizeof(*right
));
655 if (leaf_space_used(l
, mid
, nritems
- mid
) + space_needed
>
659 if (leaf_space_used(l
, 0, mid
+ 1) + space_needed
>
663 right
->header
.nritems
= nritems
- mid
;
664 right
->header
.blocknr
= right_buffer
->blocknr
;
665 right
->header
.flags
= node_level(0);
666 right
->header
.parentid
= root
->node
->node
.header
.parentid
;
667 data_copy_size
= l
->items
[mid
].offset
+ l
->items
[mid
].size
-
669 memcpy(right
->items
, l
->items
+ mid
,
670 (nritems
- mid
) * sizeof(struct item
));
671 memcpy(right
->data
+ LEAF_DATA_SIZE
- data_copy_size
,
672 l
->data
+ leaf_data_end(l
), data_copy_size
);
673 rt_data_off
= LEAF_DATA_SIZE
-
674 (l
->items
[mid
].offset
+ l
->items
[mid
].size
);
676 for (i
= 0; i
< right
->header
.nritems
; i
++)
677 right
->items
[i
].offset
+= rt_data_off
;
679 l
->header
.nritems
= mid
;
680 ret
= insert_ptr(root
, path
, &right
->items
[0].key
,
681 right_buffer
->blocknr
, path
->slots
[1] + 1, 1);
682 write_tree_block(root
, right_buffer
);
683 write_tree_block(root
, l_buf
);
685 BUG_ON(path
->slots
[0] != slot
);
687 tree_block_release(root
, path
->nodes
[0]);
688 path
->nodes
[0] = right_buffer
;
689 path
->slots
[0] -= mid
;
692 tree_block_release(root
, right_buffer
);
693 BUG_ON(path
->slots
[0] < 0);
698 * Given a key and some data, insert an item into the tree.
699 * This does all the path init required, making room in the tree if needed.
701 int insert_item(struct ctree_root
*root
, struct key
*key
,
702 void *data
, int data_size
)
708 struct tree_buffer
*leaf_buf
;
709 unsigned int nritems
;
710 unsigned int data_end
;
711 struct ctree_path path
;
713 /* create a root if there isn't one */
717 ret
= search_slot(root
, key
, &path
, data_size
);
719 release_path(root
, &path
);
723 slot_orig
= path
.slots
[0];
724 leaf_buf
= path
.nodes
[0];
725 leaf
= &leaf_buf
->leaf
;
727 nritems
= leaf
->header
.nritems
;
728 data_end
= leaf_data_end(leaf
);
730 if (leaf_free_space(leaf
) < sizeof(struct item
) + data_size
)
733 slot
= path
.slots
[0];
736 fixup_low_keys(root
, &path
, key
, 1);
737 if (slot
!= nritems
) {
739 unsigned int old_data
= leaf
->items
[slot
].offset
+
740 leaf
->items
[slot
].size
;
743 * item0..itemN ... dataN.offset..dataN.size .. data0.size
745 /* first correct the data pointers */
746 for (i
= slot
; i
< nritems
; i
++)
747 leaf
->items
[i
].offset
-= data_size
;
749 /* shift the items */
750 memmove(leaf
->items
+ slot
+ 1, leaf
->items
+ slot
,
751 (nritems
- slot
) * sizeof(struct item
));
754 memmove(leaf
->data
+ data_end
- data_size
, leaf
->data
+
755 data_end
, old_data
- data_end
);
758 /* copy the new data in */
759 memcpy(&leaf
->items
[slot
].key
, key
, sizeof(struct key
));
760 leaf
->items
[slot
].offset
= data_end
- data_size
;
761 leaf
->items
[slot
].size
= data_size
;
762 memcpy(leaf
->data
+ data_end
- data_size
, data
, data_size
);
763 leaf
->header
.nritems
+= 1;
764 write_tree_block(root
, leaf_buf
);
765 if (leaf_free_space(leaf
) < 0)
767 release_path(root
, &path
);
772 * delete the pointer from a given node.
774 * If the delete empties a node, the node is removed from the tree,
775 * continuing all the way the root if required. The root is converted into
776 * a leaf if all the nodes are emptied.
778 int del_ptr(struct ctree_root
*root
, struct ctree_path
*path
, int level
)
781 struct tree_buffer
*t
;
787 t
= path
->nodes
[level
];
791 slot
= path
->slots
[level
];
792 nritems
= node
->header
.nritems
;
794 if (slot
!= nritems
-1) {
795 memmove(node
->keys
+ slot
, node
->keys
+ slot
+ 1,
796 sizeof(struct key
) * (nritems
- slot
- 1));
797 memmove(node
->blockptrs
+ slot
,
798 node
->blockptrs
+ slot
+ 1,
799 sizeof(u64
) * (nritems
- slot
- 1));
801 node
->header
.nritems
--;
802 write_tree_block(root
, t
);
803 blocknr
= t
->blocknr
;
804 if (node
->header
.nritems
!= 0) {
806 fixup_low_keys(root
, path
, node
->keys
,
810 if (t
== root
->node
) {
811 /* just turn the root into a leaf and break */
812 root
->node
->node
.header
.flags
= node_level(0);
813 write_tree_block(root
, t
);
817 free_extent(root
, blocknr
, 1);
818 if (!path
->nodes
[level
])
825 * delete the item at the leaf level in path. If that empties
826 * the leaf, remove it from the tree
828 int del_item(struct ctree_root
*root
, struct ctree_path
*path
)
832 struct tree_buffer
*leaf_buf
;
836 leaf_buf
= path
->nodes
[0];
837 leaf
= &leaf_buf
->leaf
;
838 slot
= path
->slots
[0];
839 doff
= leaf
->items
[slot
].offset
;
840 dsize
= leaf
->items
[slot
].size
;
842 if (slot
!= leaf
->header
.nritems
- 1) {
844 int data_end
= leaf_data_end(leaf
);
845 memmove(leaf
->data
+ data_end
+ dsize
,
846 leaf
->data
+ data_end
,
848 for (i
= slot
+ 1; i
< leaf
->header
.nritems
; i
++)
849 leaf
->items
[i
].offset
+= dsize
;
850 memmove(leaf
->items
+ slot
, leaf
->items
+ slot
+ 1,
851 sizeof(struct item
) *
852 (leaf
->header
.nritems
- slot
- 1));
854 leaf
->header
.nritems
-= 1;
855 /* delete the leaf if we've emptied it */
856 if (leaf
->header
.nritems
== 0) {
857 if (leaf_buf
== root
->node
) {
858 leaf
->header
.flags
= node_level(0);
859 write_tree_block(root
, leaf_buf
);
861 del_ptr(root
, path
, 1);
862 free_extent(root
, leaf_buf
->blocknr
, 1);
865 int used
= leaf_space_used(leaf
, 0, leaf
->header
.nritems
);
867 fixup_low_keys(root
, path
, &leaf
->items
[0].key
, 1);
868 write_tree_block(root
, leaf_buf
);
869 /* delete the leaf if it is mostly empty */
870 if (used
< LEAF_DATA_SIZE
/ 3) {
871 /* push_leaf_left fixes the path.
872 * make sure the path still points to our leaf
873 * for possible call to del_ptr below
875 slot
= path
->slots
[1];
877 push_leaf_left(root
, path
, 1);
878 if (leaf
->header
.nritems
== 0) {
879 u64 blocknr
= leaf_buf
->blocknr
;
880 path
->slots
[1] = slot
;
881 del_ptr(root
, path
, 1);
882 tree_block_release(root
, leaf_buf
);
883 free_extent(root
, blocknr
, 1);
885 tree_block_release(root
, leaf_buf
);
892 int next_leaf(struct ctree_root
*root
, struct ctree_path
*path
)
897 struct tree_buffer
*c
;
898 struct tree_buffer
*next
= NULL
;
900 while(level
< MAX_LEVEL
) {
901 if (!path
->nodes
[level
])
903 slot
= path
->slots
[level
] + 1;
904 c
= path
->nodes
[level
];
905 if (slot
>= c
->node
.header
.nritems
) {
909 blocknr
= c
->node
.blockptrs
[slot
];
911 tree_block_release(root
, next
);
912 next
= read_tree_block(root
, blocknr
);
915 path
->slots
[level
] = slot
;
918 c
= path
->nodes
[level
];
919 tree_block_release(root
, c
);
920 path
->nodes
[level
] = next
;
921 path
->slots
[level
] = 0;
924 next
= read_tree_block(root
, next
->node
.blockptrs
[0]);
929 /* for testing only */
930 int next_key(int i
, int max_key
) {
931 return rand() % max_key
;
936 struct ctree_root
*root
;
938 struct key last
= { (u64
)-1, 0, 0};
943 int run_size
= 20000000;
944 int max_key
= 100000000;
946 struct ctree_path path
;
947 struct ctree_super_block super
;
952 root
= open_ctree("dbfile", &super
);
955 for (i
= 0; i
< run_size
; i
++) {
957 num
= next_key(i
, max_key
);
959 sprintf(buf
, "string-%d", num
);
961 printf("insert %d:%d\n", num
, i
);
965 ret
= insert_item(root
, &ins
, buf
, strlen(buf
));
970 write_ctree_super(root
, &super
);
973 root
= open_ctree("dbfile", &super
);
974 printf("starting search\n");
976 for (i
= 0; i
< run_size
; i
++) {
977 num
= next_key(i
, max_key
);
981 printf("search %d:%d\n", num
, i
);
982 ret
= search_slot(root
, &ins
, &path
, 0);
984 print_tree(root
, root
->node
);
985 printf("unable to find %d\n", num
);
988 release_path(root
, &path
);
990 write_ctree_super(root
, &super
);
992 root
= open_ctree("dbfile", &super
);
993 printf("node %p level %d total ptrs %d free spc %lu\n", root
->node
,
994 node_level(root
->node
->node
.header
.flags
),
995 root
->node
->node
.header
.nritems
,
996 NODEPTRS_PER_BLOCK
- root
->node
->node
.header
.nritems
);
997 printf("all searches good, deleting some items\n");
1000 for (i
= 0 ; i
< run_size
/4; i
++) {
1001 num
= next_key(i
, max_key
);
1004 ret
= search_slot(root
, &ins
, &path
, -1);
1007 printf("del %d:%d\n", num
, i
);
1008 ret
= del_item(root
, &path
);
1013 release_path(root
, &path
);
1015 write_ctree_super(root
, &super
);
1017 root
= open_ctree("dbfile", &super
);
1019 for (i
= 0; i
< run_size
; i
++) {
1021 num
= next_key(i
, max_key
);
1022 sprintf(buf
, "string-%d", num
);
1025 printf("insert %d:%d\n", num
, i
);
1026 ret
= insert_item(root
, &ins
, buf
, strlen(buf
));
1031 write_ctree_super(root
, &super
);
1033 root
= open_ctree("dbfile", &super
);
1035 printf("starting search2\n");
1036 for (i
= 0; i
< run_size
; i
++) {
1037 num
= next_key(i
, max_key
);
1041 printf("search %d:%d\n", num
, i
);
1042 ret
= search_slot(root
, &ins
, &path
, 0);
1044 print_tree(root
, root
->node
);
1045 printf("unable to find %d\n", num
);
1048 release_path(root
, &path
);
1050 printf("starting big long delete run\n");
1051 while(root
->node
&& root
->node
->node
.header
.nritems
> 0) {
1054 ins
.objectid
= (u64
)-1;
1056 ret
= search_slot(root
, &ins
, &path
, -1);
1060 leaf
= &path
.nodes
[0]->leaf
;
1061 slot
= path
.slots
[0];
1062 if (slot
!= leaf
->header
.nritems
)
1064 while(path
.slots
[0] > 0) {
1066 slot
= path
.slots
[0];
1067 leaf
= &path
.nodes
[0]->leaf
;
1069 if (comp_keys(&last
, &leaf
->items
[slot
].key
) <= 0)
1071 memcpy(&last
, &leaf
->items
[slot
].key
, sizeof(last
));
1072 if (tree_size
% 10000 == 0)
1073 printf("big del %d:%d\n", tree_size
, i
);
1074 ret
= del_item(root
, &path
);
1076 printf("del_item returned %d\n", ret
);
1081 release_path(root
, &path
);
1083 printf("tree size is now %d\n", tree_size
);
1084 printf("map tree\n");
1085 write_ctree_super(root
, &super
);
This page took 0.054736 seconds and 5 git commands to generate.