diff options
Diffstat (limited to 'fs/btrfs/ctree.c')
-rw-r--r-- | fs/btrfs/ctree.c | 249 |
1 files changed, 186 insertions, 63 deletions
diff --git a/fs/btrfs/ctree.c b/fs/btrfs/ctree.c index 6f0522f21082..6b64f49a0279 100644 --- a/fs/btrfs/ctree.c +++ b/fs/btrfs/ctree.c | |||
@@ -20,6 +20,11 @@ static void release_path(struct ctree_root *root, struct ctree_path *p) | |||
20 | } | 20 | } |
21 | } | 21 | } |
22 | 22 | ||
23 | /* | ||
24 | * The leaf data grows from end-to-front in the node. | ||
25 | * this returns the address of the start of the last item, | ||
26 | * which is the stop of the leaf data stack | ||
27 | */ | ||
23 | static inline unsigned int leaf_data_end(struct leaf *leaf) | 28 | static inline unsigned int leaf_data_end(struct leaf *leaf) |
24 | { | 29 | { |
25 | unsigned int nr = leaf->header.nritems; | 30 | unsigned int nr = leaf->header.nritems; |
@@ -28,6 +33,11 @@ static inline unsigned int leaf_data_end(struct leaf *leaf) | |||
28 | return leaf->items[nr-1].offset; | 33 | return leaf->items[nr-1].offset; |
29 | } | 34 | } |
30 | 35 | ||
36 | /* | ||
37 | * The space between the end of the leaf items and | ||
38 | * the start of the leaf data. IOW, how much room | ||
39 | * the leaf has left for both items and data | ||
40 | */ | ||
31 | static inline int leaf_free_space(struct leaf *leaf) | 41 | static inline int leaf_free_space(struct leaf *leaf) |
32 | { | 42 | { |
33 | int data_end = leaf_data_end(leaf); | 43 | int data_end = leaf_data_end(leaf); |
@@ -36,6 +46,9 @@ static inline int leaf_free_space(struct leaf *leaf) | |||
36 | return (char *)(leaf->data + data_end) - (char *)items_end; | 46 | return (char *)(leaf->data + data_end) - (char *)items_end; |
37 | } | 47 | } |
38 | 48 | ||
49 | /* | ||
50 | * compare two keys in a memcmp fashion | ||
51 | */ | ||
39 | int comp_keys(struct key *k1, struct key *k2) | 52 | int comp_keys(struct key *k1, struct key *k2) |
40 | { | 53 | { |
41 | if (k1->objectid > k2->objectid) | 54 | if (k1->objectid > k2->objectid) |
@@ -52,6 +65,16 @@ int comp_keys(struct key *k1, struct key *k2) | |||
52 | return -1; | 65 | return -1; |
53 | return 0; | 66 | return 0; |
54 | } | 67 | } |
68 | |||
69 | /* | ||
70 | * search for key in the array p. items p are item_size apart | ||
71 | * and there are 'max' items in p | ||
72 | * the slot in the array is returned via slot, and it points to | ||
73 | * the place where you would insert key if it is not found in | ||
74 | * the array. | ||
75 | * | ||
76 | * slot may point to max if the key is bigger than all of the keys | ||
77 | */ | ||
55 | int generic_bin_search(char *p, int item_size, struct key *key, | 78 | int generic_bin_search(char *p, int item_size, struct key *key, |
56 | int max, int *slot) | 79 | int max, int *slot) |
57 | { | 80 | { |
@@ -92,6 +115,14 @@ int bin_search(struct node *c, struct key *key, int *slot) | |||
92 | return -1; | 115 | return -1; |
93 | } | 116 | } |
94 | 117 | ||
118 | /* | ||
119 | * look for key in the tree. path is filled in with nodes along the way | ||
120 | * if key is found, we return zero and you can find the item in the leaf | ||
121 | * level of the path (level 0) | ||
122 | * | ||
123 | * If the key isn't found, the path points to the slot where it should | ||
124 | * be inserted. | ||
125 | */ | ||
95 | int search_slot(struct ctree_root *root, struct key *key, struct ctree_path *p) | 126 | int search_slot(struct ctree_root *root, struct key *key, struct ctree_path *p) |
96 | { | 127 | { |
97 | struct tree_buffer *b = root->node; | 128 | struct tree_buffer *b = root->node; |
@@ -120,12 +151,18 @@ int search_slot(struct ctree_root *root, struct key *key, struct ctree_path *p) | |||
120 | return -1; | 151 | return -1; |
121 | } | 152 | } |
122 | 153 | ||
154 | /* | ||
155 | * adjust the pointers going up the tree, starting at level | ||
156 | * making sure the right key of each node is points to 'key'. | ||
157 | * This is used after shifting pointers to the left, so it stops | ||
158 | * fixing up pointers when a given leaf/node is not in slot 0 of the | ||
159 | * higher levels | ||
160 | */ | ||
123 | static void fixup_low_keys(struct ctree_root *root, | 161 | static void fixup_low_keys(struct ctree_root *root, |
124 | struct ctree_path *path, struct key *key, | 162 | struct ctree_path *path, struct key *key, |
125 | int level) | 163 | int level) |
126 | { | 164 | { |
127 | int i; | 165 | int i; |
128 | /* adjust the pointers going up the tree */ | ||
129 | for (i = level; i < MAX_LEVEL; i++) { | 166 | for (i = level; i < MAX_LEVEL; i++) { |
130 | struct node *t; | 167 | struct node *t; |
131 | int tslot = path->slots[i]; | 168 | int tslot = path->slots[i]; |
@@ -139,64 +176,16 @@ static void fixup_low_keys(struct ctree_root *root, | |||
139 | } | 176 | } |
140 | } | 177 | } |
141 | 178 | ||
142 | int __insert_ptr(struct ctree_root *root, | 179 | /* |
143 | struct ctree_path *path, struct key *key, | 180 | * try to push data from one node into the next node left in the |
144 | u64 blocknr, int slot, int level) | 181 | * tree. The src node is found at specified level in the path. |
145 | { | 182 | * If some bytes were pushed, return 0, otherwise return 1. |
146 | struct node *c; | 183 | * |
147 | struct node *lower; | 184 | * Lower nodes/leaves in the path are not touched, higher nodes may |
148 | struct key *lower_key; | 185 | * be modified to reflect the push. |
149 | int nritems; | 186 | * |
150 | /* need a new root */ | 187 | * The path is altered to reflect the push. |
151 | if (!path->nodes[level]) { | 188 | */ |
152 | struct tree_buffer *t; | ||
153 | t = alloc_free_block(root); | ||
154 | c = &t->node; | ||
155 | memset(c, 0, sizeof(c)); | ||
156 | c->header.nritems = 2; | ||
157 | c->header.flags = node_level(level); | ||
158 | c->header.blocknr = t->blocknr; | ||
159 | lower = &path->nodes[level-1]->node; | ||
160 | if (is_leaf(lower->header.flags)) | ||
161 | lower_key = &((struct leaf *)lower)->items[0].key; | ||
162 | else | ||
163 | lower_key = lower->keys; | ||
164 | memcpy(c->keys, lower_key, sizeof(struct key)); | ||
165 | memcpy(c->keys + 1, key, sizeof(struct key)); | ||
166 | c->blockptrs[0] = path->nodes[level-1]->blocknr; | ||
167 | c->blockptrs[1] = blocknr; | ||
168 | /* the path has an extra ref to root->node */ | ||
169 | tree_block_release(root, root->node); | ||
170 | root->node = t; | ||
171 | t->count++; | ||
172 | write_tree_block(root, t); | ||
173 | path->nodes[level] = t; | ||
174 | path->slots[level] = 0; | ||
175 | if (c->keys[1].objectid == 0) | ||
176 | BUG(); | ||
177 | return 0; | ||
178 | } | ||
179 | lower = &path->nodes[level]->node; | ||
180 | nritems = lower->header.nritems; | ||
181 | if (slot > nritems) | ||
182 | BUG(); | ||
183 | if (nritems == NODEPTRS_PER_BLOCK) | ||
184 | BUG(); | ||
185 | if (slot != nritems) { | ||
186 | memmove(lower->keys + slot + 1, lower->keys + slot, | ||
187 | (nritems - slot) * sizeof(struct key)); | ||
188 | memmove(lower->blockptrs + slot + 1, lower->blockptrs + slot, | ||
189 | (nritems - slot) * sizeof(u64)); | ||
190 | } | ||
191 | memcpy(lower->keys + slot, key, sizeof(struct key)); | ||
192 | lower->blockptrs[slot] = blocknr; | ||
193 | lower->header.nritems++; | ||
194 | if (lower->keys[1].objectid == 0) | ||
195 | BUG(); | ||
196 | write_tree_block(root, path->nodes[level]); | ||
197 | return 0; | ||
198 | } | ||
199 | |||
200 | int push_node_left(struct ctree_root *root, struct ctree_path *path, int level) | 189 | int push_node_left(struct ctree_root *root, struct ctree_path *path, int level) |
201 | { | 190 | { |
202 | int slot; | 191 | int slot; |
@@ -259,6 +248,16 @@ int push_node_left(struct ctree_root *root, struct ctree_path *path, int level) | |||
259 | return 0; | 248 | return 0; |
260 | } | 249 | } |
261 | 250 | ||
251 | /* | ||
252 | * try to push data from one node into the next node right in the | ||
253 | * tree. The src node is found at specified level in the path. | ||
254 | * If some bytes were pushed, return 0, otherwise return 1. | ||
255 | * | ||
256 | * Lower nodes/leaves in the path are not touched, higher nodes may | ||
257 | * be modified to reflect the push. | ||
258 | * | ||
259 | * The path is altered to reflect the push. | ||
260 | */ | ||
262 | int push_node_right(struct ctree_root *root, struct ctree_path *path, int level) | 261 | int push_node_right(struct ctree_root *root, struct ctree_path *path, int level) |
263 | { | 262 | { |
264 | int slot; | 263 | int slot; |
@@ -270,8 +269,11 @@ int push_node_right(struct ctree_root *root, struct ctree_path *path, int level) | |||
270 | int dst_nritems; | 269 | int dst_nritems; |
271 | int src_nritems; | 270 | int src_nritems; |
272 | 271 | ||
272 | /* can't push from the root */ | ||
273 | if (level == MAX_LEVEL - 1 || path->nodes[level + 1] == 0) | 273 | if (level == MAX_LEVEL - 1 || path->nodes[level + 1] == 0) |
274 | return 1; | 274 | return 1; |
275 | |||
276 | /* only try to push inside the node higher up */ | ||
275 | slot = path->slots[level + 1]; | 277 | slot = path->slots[level + 1]; |
276 | if (slot == NODEPTRS_PER_BLOCK - 1) | 278 | if (slot == NODEPTRS_PER_BLOCK - 1) |
277 | return 1; | 279 | return 1; |
@@ -315,7 +317,7 @@ int push_node_right(struct ctree_root *root, struct ctree_path *path, int level) | |||
315 | write_tree_block(root, t); | 317 | write_tree_block(root, t); |
316 | write_tree_block(root, src_buffer); | 318 | write_tree_block(root, src_buffer); |
317 | 319 | ||
318 | /* then fixup the leaf pointer in the path */ | 320 | /* then fixup the pointers in the path */ |
319 | if (path->slots[level] >= src->header.nritems) { | 321 | if (path->slots[level] >= src->header.nritems) { |
320 | path->slots[level] -= src->header.nritems; | 322 | path->slots[level] -= src->header.nritems; |
321 | tree_block_release(root, path->nodes[level]); | 323 | tree_block_release(root, path->nodes[level]); |
@@ -327,6 +329,76 @@ int push_node_right(struct ctree_root *root, struct ctree_path *path, int level) | |||
327 | return 0; | 329 | return 0; |
328 | } | 330 | } |
329 | 331 | ||
332 | /* | ||
333 | * worker function to insert a single pointer in a node. | ||
334 | * the node should have enough room for the pointer already | ||
335 | * slot and level indicate where you want the key to go, and | ||
336 | * blocknr is the block the key points to. | ||
337 | */ | ||
338 | int __insert_ptr(struct ctree_root *root, | ||
339 | struct ctree_path *path, struct key *key, | ||
340 | u64 blocknr, int slot, int level) | ||
341 | { | ||
342 | struct node *c; | ||
343 | struct node *lower; | ||
344 | struct key *lower_key; | ||
345 | int nritems; | ||
346 | /* need a new root */ | ||
347 | if (!path->nodes[level]) { | ||
348 | struct tree_buffer *t; | ||
349 | t = alloc_free_block(root); | ||
350 | c = &t->node; | ||
351 | memset(c, 0, sizeof(c)); | ||
352 | c->header.nritems = 2; | ||
353 | c->header.flags = node_level(level); | ||
354 | c->header.blocknr = t->blocknr; | ||
355 | lower = &path->nodes[level-1]->node; | ||
356 | if (is_leaf(lower->header.flags)) | ||
357 | lower_key = &((struct leaf *)lower)->items[0].key; | ||
358 | else | ||
359 | lower_key = lower->keys; | ||
360 | memcpy(c->keys, lower_key, sizeof(struct key)); | ||
361 | memcpy(c->keys + 1, key, sizeof(struct key)); | ||
362 | c->blockptrs[0] = path->nodes[level-1]->blocknr; | ||
363 | c->blockptrs[1] = blocknr; | ||
364 | /* the path has an extra ref to root->node */ | ||
365 | tree_block_release(root, root->node); | ||
366 | root->node = t; | ||
367 | t->count++; | ||
368 | write_tree_block(root, t); | ||
369 | path->nodes[level] = t; | ||
370 | path->slots[level] = 0; | ||
371 | if (c->keys[1].objectid == 0) | ||
372 | BUG(); | ||
373 | return 0; | ||
374 | } | ||
375 | lower = &path->nodes[level]->node; | ||
376 | nritems = lower->header.nritems; | ||
377 | if (slot > nritems) | ||
378 | BUG(); | ||
379 | if (nritems == NODEPTRS_PER_BLOCK) | ||
380 | BUG(); | ||
381 | if (slot != nritems) { | ||
382 | memmove(lower->keys + slot + 1, lower->keys + slot, | ||
383 | (nritems - slot) * sizeof(struct key)); | ||
384 | memmove(lower->blockptrs + slot + 1, lower->blockptrs + slot, | ||
385 | (nritems - slot) * sizeof(u64)); | ||
386 | } | ||
387 | memcpy(lower->keys + slot, key, sizeof(struct key)); | ||
388 | lower->blockptrs[slot] = blocknr; | ||
389 | lower->header.nritems++; | ||
390 | if (lower->keys[1].objectid == 0) | ||
391 | BUG(); | ||
392 | write_tree_block(root, path->nodes[level]); | ||
393 | return 0; | ||
394 | } | ||
395 | |||
396 | |||
397 | /* | ||
398 | * insert a key,blocknr pair into the tree at a given level | ||
399 | * If the node at that level in the path doesn't have room, | ||
400 | * it is split or shifted as appropriate. | ||
401 | */ | ||
330 | int insert_ptr(struct ctree_root *root, | 402 | int insert_ptr(struct ctree_root *root, |
331 | struct ctree_path *path, struct key *key, | 403 | struct ctree_path *path, struct key *key, |
332 | u64 blocknr, int level) | 404 | u64 blocknr, int level) |
@@ -340,6 +412,15 @@ int insert_ptr(struct ctree_root *root, | |||
340 | int mid; | 412 | int mid; |
341 | int bal_start = -1; | 413 | int bal_start = -1; |
342 | 414 | ||
415 | /* | ||
416 | * check to see if we need to make room in the node for this | ||
417 | * pointer. If we do, keep walking the tree, making sure there | ||
418 | * is enough room in each level for the required insertions. | ||
419 | * | ||
420 | * The bal array is filled in with any nodes to be inserted | ||
421 | * due to splitting. Once we've done all the splitting required | ||
422 | * do the inserts based on the data in the bal array. | ||
423 | */ | ||
343 | memset(bal, 0, ARRAY_SIZE(bal)); | 424 | memset(bal, 0, ARRAY_SIZE(bal)); |
344 | while(t && t->node.header.nritems == NODEPTRS_PER_BLOCK) { | 425 | while(t && t->node.header.nritems == NODEPTRS_PER_BLOCK) { |
345 | c = &t->node; | 426 | c = &t->node; |
@@ -373,6 +454,11 @@ int insert_ptr(struct ctree_root *root, | |||
373 | bal_level += 1; | 454 | bal_level += 1; |
374 | t = path->nodes[bal_level]; | 455 | t = path->nodes[bal_level]; |
375 | } | 456 | } |
457 | /* | ||
458 | * bal_start tells us the first level in the tree that needed to | ||
459 | * be split. Go through the bal array inserting the new nodes | ||
460 | * as needed. The path is fixed as we go. | ||
461 | */ | ||
376 | while(bal_start > 0) { | 462 | while(bal_start > 0) { |
377 | b_buffer = bal[bal_start]; | 463 | b_buffer = bal[bal_start]; |
378 | c = &path->nodes[bal_start]->node; | 464 | c = &path->nodes[bal_start]->node; |
@@ -390,10 +476,16 @@ int insert_ptr(struct ctree_root *root, | |||
390 | if (!bal[bal_start]) | 476 | if (!bal[bal_start]) |
391 | break; | 477 | break; |
392 | } | 478 | } |
479 | /* Now that the tree has room, insert the requested pointer */ | ||
393 | return __insert_ptr(root, path, key, blocknr, path->slots[level] + 1, | 480 | return __insert_ptr(root, path, key, blocknr, path->slots[level] + 1, |
394 | level); | 481 | level); |
395 | } | 482 | } |
396 | 483 | ||
484 | /* | ||
485 | * how many bytes are required to store the items in a leaf. start | ||
486 | * and nr indicate which items in the leaf to check. This totals up the | ||
487 | * space used both by the item structs and the item data | ||
488 | */ | ||
397 | int leaf_space_used(struct leaf *l, int start, int nr) | 489 | int leaf_space_used(struct leaf *l, int start, int nr) |
398 | { | 490 | { |
399 | int data_len; | 491 | int data_len; |
@@ -407,6 +499,10 @@ int leaf_space_used(struct leaf *l, int start, int nr) | |||
407 | return data_len; | 499 | return data_len; |
408 | } | 500 | } |
409 | 501 | ||
502 | /* | ||
503 | * push some data in the path leaf to the left, trying to free up at | ||
504 | * least data_size bytes. returns zero if the push worked, nonzero otherwise | ||
505 | */ | ||
410 | int push_leaf_left(struct ctree_root *root, struct ctree_path *path, | 506 | int push_leaf_left(struct ctree_root *root, struct ctree_path *path, |
411 | int data_size) | 507 | int data_size) |
412 | { | 508 | { |
@@ -498,6 +594,10 @@ int push_leaf_left(struct ctree_root *root, struct ctree_path *path, | |||
498 | return 0; | 594 | return 0; |
499 | } | 595 | } |
500 | 596 | ||
597 | /* | ||
598 | * split the path's leaf in two, making sure there is at least data_size | ||
599 | * available for the resulting leaf level of the path. | ||
600 | */ | ||
501 | int split_leaf(struct ctree_root *root, struct ctree_path *path, int data_size) | 601 | int split_leaf(struct ctree_root *root, struct ctree_path *path, int data_size) |
502 | { | 602 | { |
503 | struct tree_buffer *l_buf = path->nodes[0]; | 603 | struct tree_buffer *l_buf = path->nodes[0]; |
@@ -548,9 +648,10 @@ int split_leaf(struct ctree_root *root, struct ctree_path *path, int data_size) | |||
548 | l->data + leaf_data_end(l), data_copy_size); | 648 | l->data + leaf_data_end(l), data_copy_size); |
549 | rt_data_off = LEAF_DATA_SIZE - | 649 | rt_data_off = LEAF_DATA_SIZE - |
550 | (l->items[mid].offset + l->items[mid].size); | 650 | (l->items[mid].offset + l->items[mid].size); |
551 | for (i = 0; i < right->header.nritems; i++) { | 651 | |
652 | for (i = 0; i < right->header.nritems; i++) | ||
552 | right->items[i].offset += rt_data_off; | 653 | right->items[i].offset += rt_data_off; |
553 | } | 654 | |
554 | l->header.nritems = mid; | 655 | l->header.nritems = mid; |
555 | ret = insert_ptr(root, path, &right->items[0].key, | 656 | ret = insert_ptr(root, path, &right->items[0].key, |
556 | right_buffer->blocknr, 1); | 657 | right_buffer->blocknr, 1); |
@@ -570,6 +671,10 @@ int split_leaf(struct ctree_root *root, struct ctree_path *path, int data_size) | |||
570 | return ret; | 671 | return ret; |
571 | } | 672 | } |
572 | 673 | ||
674 | /* | ||
675 | * Given a key and some data, insert an item into the tree. | ||
676 | * This does all the path init required, making room in the tree if needed. | ||
677 | */ | ||
573 | int insert_item(struct ctree_root *root, struct key *key, | 678 | int insert_item(struct ctree_root *root, struct key *key, |
574 | void *data, int data_size) | 679 | void *data, int data_size) |
575 | { | 680 | { |
@@ -582,6 +687,7 @@ int insert_item(struct ctree_root *root, struct key *key, | |||
582 | unsigned int data_end; | 687 | unsigned int data_end; |
583 | struct ctree_path path; | 688 | struct ctree_path path; |
584 | 689 | ||
690 | /* create a root if there isn't one */ | ||
585 | if (!root->node) { | 691 | if (!root->node) { |
586 | struct tree_buffer *t; | 692 | struct tree_buffer *t; |
587 | t = alloc_free_block(root); | 693 | t = alloc_free_block(root); |
@@ -602,6 +708,8 @@ int insert_item(struct ctree_root *root, struct key *key, | |||
602 | slot_orig = path.slots[0]; | 708 | slot_orig = path.slots[0]; |
603 | leaf_buf = path.nodes[0]; | 709 | leaf_buf = path.nodes[0]; |
604 | leaf = &leaf_buf->leaf; | 710 | leaf = &leaf_buf->leaf; |
711 | |||
712 | /* make room if needed */ | ||
605 | if (leaf_free_space(leaf) < sizeof(struct item) + data_size) { | 713 | if (leaf_free_space(leaf) < sizeof(struct item) + data_size) { |
606 | split_leaf(root, &path, data_size); | 714 | split_leaf(root, &path, data_size); |
607 | leaf_buf = path.nodes[0]; | 715 | leaf_buf = path.nodes[0]; |
@@ -638,6 +746,7 @@ int insert_item(struct ctree_root *root, struct key *key, | |||
638 | data_end, old_data - data_end); | 746 | data_end, old_data - data_end); |
639 | data_end = old_data; | 747 | data_end = old_data; |
640 | } | 748 | } |
749 | /* copy the new data in */ | ||
641 | memcpy(&leaf->items[slot].key, key, sizeof(struct key)); | 750 | memcpy(&leaf->items[slot].key, key, sizeof(struct key)); |
642 | leaf->items[slot].offset = data_end - data_size; | 751 | leaf->items[slot].offset = data_end - data_size; |
643 | leaf->items[slot].size = data_size; | 752 | leaf->items[slot].size = data_size; |
@@ -650,6 +759,14 @@ int insert_item(struct ctree_root *root, struct key *key, | |||
650 | return 0; | 759 | return 0; |
651 | } | 760 | } |
652 | 761 | ||
762 | /* | ||
763 | * delete the pointer from a given level in the path. The path is not | ||
764 | * fixed up, so after calling this it is not valid at that level. | ||
765 | * | ||
766 | * If the delete empties a node, the node is removed from the tree, | ||
767 | * continuing all the way the root if required. The root is converted into | ||
768 | * a leaf if all the nodes are emptied. | ||
769 | */ | ||
653 | int del_ptr(struct ctree_root *root, struct ctree_path *path, int level) | 770 | int del_ptr(struct ctree_root *root, struct ctree_path *path, int level) |
654 | { | 771 | { |
655 | int slot; | 772 | int slot; |
@@ -705,6 +822,10 @@ int del_ptr(struct ctree_root *root, struct ctree_path *path, int level) | |||
705 | return 0; | 822 | return 0; |
706 | } | 823 | } |
707 | 824 | ||
825 | /* | ||
826 | * delete the item at the leaf level in path. If that empties | ||
827 | * the leaf, remove it from the tree | ||
828 | */ | ||
708 | int del_item(struct ctree_root *root, struct ctree_path *path) | 829 | int del_item(struct ctree_root *root, struct ctree_path *path) |
709 | { | 830 | { |
710 | int slot; | 831 | int slot; |
@@ -732,6 +853,7 @@ int del_item(struct ctree_root *root, struct ctree_path *path) | |||
732 | (leaf->header.nritems - slot - 1)); | 853 | (leaf->header.nritems - slot - 1)); |
733 | } | 854 | } |
734 | leaf->header.nritems -= 1; | 855 | leaf->header.nritems -= 1; |
856 | /* delete the leaf if we've emptied it */ | ||
735 | if (leaf->header.nritems == 0) { | 857 | if (leaf->header.nritems == 0) { |
736 | if (leaf_buf == root->node) { | 858 | if (leaf_buf == root->node) { |
737 | leaf->header.flags = node_level(0); | 859 | leaf->header.flags = node_level(0); |
@@ -742,6 +864,7 @@ int del_item(struct ctree_root *root, struct ctree_path *path) | |||
742 | if (slot == 0) | 864 | if (slot == 0) |
743 | fixup_low_keys(root, path, &leaf->items[0].key, 1); | 865 | fixup_low_keys(root, path, &leaf->items[0].key, 1); |
744 | write_tree_block(root, leaf_buf); | 866 | write_tree_block(root, leaf_buf); |
867 | /* delete the leaf if it is mostly empty */ | ||
745 | if (leaf_space_used(leaf, 0, leaf->header.nritems) < | 868 | if (leaf_space_used(leaf, 0, leaf->header.nritems) < |
746 | LEAF_DATA_SIZE / 4) { | 869 | LEAF_DATA_SIZE / 4) { |
747 | /* push_leaf_left fixes the path. | 870 | /* push_leaf_left fixes the path. |
@@ -837,7 +960,7 @@ int main() { | |||
837 | int i; | 960 | int i; |
838 | int num; | 961 | int num; |
839 | int ret; | 962 | int ret; |
840 | int run_size = 1000000; | 963 | int run_size = 25000; |
841 | int max_key = 100000000; | 964 | int max_key = 100000000; |
842 | int tree_size = 0; | 965 | int tree_size = 0; |
843 | struct ctree_path path; | 966 | struct ctree_path path; |