]>
git.ipfire.org Git - thirdparty/xfsprogs-dev.git/blob - repair/btree.c
1 // SPDX-License-Identifier: GPL-2.0
3 * Copyright (c) 2007, Silicon Graphics, Inc. Barry Naujok <bnaujok@sgi.com>
11 * Maximum number of keys per node. Must be greater than 2 for the code
14 #define BTREE_KEY_MAX 7
15 #define BTREE_KEY_MIN (BTREE_KEY_MAX / 2)
17 #define BTREE_PTR_MAX (BTREE_KEY_MAX + 1)
20 unsigned long num_keys
;
21 unsigned long keys
[BTREE_KEY_MAX
];
22 struct btree_node
*ptrs
[BTREE_PTR_MAX
];
26 struct btree_node
*node
;
31 struct btree_node
*root_node
;
32 struct btree_cursor
*cursor
; /* track path to end leaf */
35 int keys_valid
; /* set if the cache is valid */
36 unsigned long cur_key
;
37 unsigned long next_key
;
39 unsigned long prev_key
;
43 unsigned long num_items
;
44 unsigned long max_items
;
68 static struct btree_node
*
69 btree_node_alloc(void)
71 return calloc(1, sizeof(struct btree_node
));
76 struct btree_node
*node
)
83 struct btree_node
*node
,
89 for (i
= 0; i
<= node
->num_keys
; i
++)
90 btree_free_nodes(node
->ptrs
[i
], level
- 1);
91 btree_node_free(node
);
96 struct btree_root
*root
)
98 memset(root
, 0, sizeof(struct btree_root
));
100 root
->cursor
= calloc(1, sizeof(struct btree_cursor
));
101 root
->root_node
= btree_node_alloc();
102 ASSERT(root
->root_node
);
104 root
->stats
.max_items
= 1;
105 root
->stats
.alloced
+= 1;
111 struct btree_root
*root
)
113 btree_free_nodes(root
->root_node
, root
->height
- 1);
117 root
->root_node
= NULL
;
122 struct btree_root
**root
)
124 *root
= calloc(1, sizeof(struct btree_root
));
130 struct btree_root
*root
)
138 struct btree_root
*root
)
146 struct btree_root
*root
)
148 return root
->root_node
->num_keys
== 0;
152 btree_invalidate_cursor(
153 struct btree_root
*root
)
155 root
->cursor
[0].node
= NULL
;
156 root
->keys_valid
= 0;
159 static inline unsigned long
161 struct btree_cursor
*cursor
,
164 while (cursor
->node
->num_keys
== cursor
->index
&& --height
> 0)
166 return cursor
->node
->keys
[cursor
->index
];
171 struct btree_root
*root
,
174 struct btree_cursor
*cur
= root
->cursor
;
176 struct btree_node
*node
;
178 if (cur
->index
> 0) {
180 *key
= cur
->node
->keys
[cur
->index
- 1];
181 return cur
->node
->ptrs
[cur
->index
- 1];
184 /* else need to go up and back down the tree to find the previous */
189 } while (++level
< root
->height
);
191 if (level
== root
->height
)
194 /* the key is in the current level */
196 *key
= cur
->node
->keys
[cur
->index
- 1];
198 /* descend back down the right side to get the pointer */
199 node
= cur
->node
->ptrs
[cur
->index
- 1];
201 node
= node
->ptrs
[node
->num_keys
];
207 struct btree_root
*root
,
210 struct btree_cursor
*cur
= root
->cursor
;
212 struct btree_node
*node
;
214 while (cur
->index
== cur
->node
->num_keys
) {
215 if (++level
== root
->height
)
222 *key
= btree_key_of_cursor(cur
, root
->height
);
225 return cur
->node
->ptrs
[cur
->index
+ 1];
228 node
= cur
->node
->ptrs
[cur
->index
+ 1];
230 node
= node
->ptrs
[0];
232 *key
= node
->keys
[0];
233 return node
->ptrs
[0];
237 * Lookup/Search functions
242 struct btree_root
*root
,
246 struct btree_cursor
*cur
= root
->cursor
+ root
->height
;
247 struct btree_node
*node
= root
->root_node
;
248 int height
= root
->height
;
252 while (--height
>= 0) {
254 for (i
= 0; i
< node
->num_keys
; i
++)
255 if (node
->keys
[i
] >= key
) {
262 node
= node
->ptrs
[i
];
264 root
->keys_valid
= key_found
;
269 root
->next_value
= NULL
; /* do on-demand next value lookup */
270 root
->prev_value
= btree_get_prev(root
, &root
->prev_key
);
276 struct btree_root
*root
,
279 if (root
->keys_valid
&& key
<= root
->cur_key
&&
280 (!root
->prev_value
|| key
> root
->prev_key
)) {
282 root
->stats
.cache_hits
++;
287 root
->stats
.cache_misses
++;
289 return btree_do_search(root
, key
);
294 struct btree_root
*root
,
296 unsigned long *actual_key
)
299 root
->stats
.find
+= 1;
301 if (!btree_search(root
, key
))
305 *actual_key
= root
->cur_key
;
306 return root
->cursor
->node
->ptrs
[root
->cursor
->index
];
311 struct btree_root
*root
,
315 root
->stats
.lookup
+= 1;
317 if (!btree_search(root
, key
) || root
->cur_key
!= key
)
319 return root
->cursor
->node
->ptrs
[root
->cursor
->index
];
324 struct btree_root
*root
,
327 if (!root
->keys_valid
)
330 *key
= root
->prev_key
;
331 return root
->prev_value
;
336 struct btree_root
*root
,
339 if (!root
->keys_valid
)
341 if (!root
->next_value
)
342 root
->next_value
= btree_get_next(root
, &root
->next_key
);
344 *key
= root
->next_key
;
345 return root
->next_value
;
349 btree_move_cursor_to_next(
350 struct btree_root
*root
,
353 struct btree_cursor
*cur
= root
->cursor
;
356 while (cur
->index
== cur
->node
->num_keys
) {
357 if (++level
== root
->height
)
364 *key
= btree_key_of_cursor(cur
, root
->height
);
365 return cur
->node
->ptrs
[cur
->index
];
368 while (--level
>= 0) {
369 root
->cursor
[level
].node
= cur
->node
->ptrs
[cur
->index
];
370 root
->cursor
[level
].index
= 0;
374 *key
= cur
->node
->keys
[0];
375 return cur
->node
->ptrs
[0];
380 struct btree_root
*root
,
385 if (!root
->keys_valid
)
388 root
->prev_key
= root
->cur_key
;
389 root
->prev_value
= root
->cursor
->node
->ptrs
[root
->cursor
->index
];
391 value
= btree_move_cursor_to_next(root
, &root
->cur_key
);
393 btree_invalidate_cursor(root
);
396 root
->next_value
= NULL
; /* on-demand next value fetch */
398 *key
= root
->cur_key
;
403 btree_move_cursor_to_prev(
404 struct btree_root
*root
,
407 struct btree_cursor
*cur
= root
->cursor
;
410 while (cur
->index
== 0) {
411 if (++level
== root
->height
)
416 if (key
) /* the key is in the current level */
417 *key
= cur
->node
->keys
[cur
->index
];
420 root
->cursor
[level
].node
= cur
->node
->ptrs
[cur
->index
];
421 root
->cursor
[level
].index
= root
->cursor
[level
].node
->num_keys
;
424 return cur
->node
->ptrs
[cur
->index
];
429 struct btree_root
*root
,
434 if (!root
->keys_valid
)
437 value
= btree_move_cursor_to_prev(root
, &root
->cur_key
);
440 root
->prev_value
= btree_get_prev(root
, &root
->prev_key
);
441 root
->next_value
= NULL
; /* on-demand next value fetch */
443 *key
= root
->cur_key
;
447 /* Update functions */
450 btree_update_node_key(
451 struct btree_root
*root
,
452 struct btree_cursor
*cursor
,
454 unsigned long new_key
)
459 root
->stats
.key_update
+= 1;
463 for (i
= level
; i
< root
->height
; i
++) {
464 if (cursor
->index
< cursor
->node
->num_keys
) {
465 cursor
->node
->keys
[cursor
->index
] = new_key
;
474 struct btree_root
*root
,
475 unsigned long old_key
,
476 unsigned long new_key
)
478 if (!btree_search(root
, old_key
) || root
->cur_key
!= old_key
)
481 if (root
->next_value
&& new_key
>= root
->next_key
)
484 if (root
->prev_value
&& new_key
<= root
->prev_key
)
487 btree_update_node_key(root
, root
->cursor
, 0, new_key
);
488 root
->cur_key
= new_key
;
495 struct btree_root
*root
,
502 if (!btree_search(root
, key
) || root
->cur_key
!= key
)
506 root
->stats
.value_update
+= 1;
508 root
->cursor
->node
->ptrs
[root
->cursor
->index
] = new_value
;
514 * Cursor modification functions - used for inserting and deleting
517 static struct btree_cursor
*
518 btree_copy_cursor_prev(
519 struct btree_root
*root
,
520 struct btree_cursor
*dest_cursor
,
523 struct btree_cursor
*src_cur
= root
->cursor
+ level
;
524 struct btree_cursor
*dst_cur
;
528 if (level
>= root
->height
)
531 while (src_cur
->index
== 0) {
532 if (++l
>= root
->height
)
536 for (i
= l
; i
< root
->height
; i
++)
537 dest_cursor
[i
] = *src_cur
++;
539 dst_cur
= dest_cursor
+ l
;
541 while (l
-- >= level
) {
542 dest_cursor
[l
].node
= dst_cur
->node
->ptrs
[dst_cur
->index
];
543 dest_cursor
[l
].index
= dest_cursor
[l
].node
->num_keys
;
549 static struct btree_cursor
*
550 btree_copy_cursor_next(
551 struct btree_root
*root
,
552 struct btree_cursor
*dest_cursor
,
555 struct btree_cursor
*src_cur
= root
->cursor
+ level
;
556 struct btree_cursor
*dst_cur
;
560 if (level
>= root
->height
)
563 while (src_cur
->index
== src_cur
->node
->num_keys
) {
564 if (++l
>= root
->height
)
568 for (i
= l
; i
< root
->height
; i
++)
569 dest_cursor
[i
] = *src_cur
++;
571 dst_cur
= dest_cursor
+ l
;
573 while (l
-- >= level
) {
574 dest_cursor
[l
].node
= dst_cur
->node
->ptrs
[dst_cur
->index
];
575 dest_cursor
[l
].index
= 0;
584 * Tries to move items in the current leaf to its sibling if it has space.
585 * Used in both insert and delete functions.
586 * Returns the number of items shifted.
591 struct btree_root
*root
,
593 struct btree_cursor
*prev_cursor
,
596 struct btree_node
*node
;
597 struct btree_node
*prev_node
;
598 int num_remain
; /* # of keys left in "node" */
602 if (!prev_cursor
|| !num_children
)
605 prev_node
= prev_cursor
[level
].node
;
606 node
= root
->cursor
[level
].node
;
608 ASSERT(num_children
> 0 && num_children
<= node
->num_keys
+ 1);
610 if ((prev_node
->num_keys
+ num_children
) > BTREE_KEY_MAX
)
614 root
->stats
.shift_prev
+= 1;
617 num_remain
= node
->num_keys
- num_children
;
618 ASSERT(num_remain
== -1 || num_remain
>= BTREE_KEY_MIN
);
620 /* shift parent keys around */
623 key
= node
->keys
[num_children
- 1];
625 key
= btree_key_of_cursor(root
->cursor
+ level
,
626 root
->height
- level
);
627 while (prev_cursor
[level
].index
== prev_cursor
[level
].node
->num_keys
) {
629 ASSERT(level
< root
->height
);
631 prev_node
->keys
[prev_node
->num_keys
] =
632 prev_cursor
[level
].node
->keys
[prev_cursor
[level
].index
];
633 prev_cursor
[level
].node
->keys
[prev_cursor
[level
].index
] = key
;
635 /* copy pointers and keys to the end of the prev node */
636 for (i
= 0; i
< num_children
- 1; i
++) {
637 prev_node
->keys
[prev_node
->num_keys
+ 1 + i
] = node
->keys
[i
];
638 prev_node
->ptrs
[prev_node
->num_keys
+ 1 + i
] = node
->ptrs
[i
];
640 prev_node
->ptrs
[prev_node
->num_keys
+ 1 + i
] = node
->ptrs
[i
];
641 prev_node
->num_keys
+= num_children
;
643 /* move remaining pointers/keys to start of node */
644 if (num_remain
>= 0) {
645 for (i
= 0; i
< num_remain
; i
++) {
646 node
->keys
[i
] = node
->keys
[num_children
+ i
];
647 node
->ptrs
[i
] = node
->ptrs
[num_children
+ i
];
649 node
->ptrs
[i
] = node
->ptrs
[num_children
+ i
];
650 node
->num_keys
= num_remain
;
659 struct btree_root
*root
,
661 struct btree_cursor
*next_cursor
,
664 struct btree_node
*node
;
665 struct btree_node
*next_node
;
666 int num_remain
; /* # of children left in node */
669 if (!next_cursor
|| !num_children
)
672 node
= root
->cursor
[level
].node
;
673 next_node
= next_cursor
[level
].node
;
675 ASSERT(num_children
> 0 && num_children
<= node
->num_keys
+ 1);
677 if ((next_node
->num_keys
+ num_children
) > BTREE_KEY_MAX
)
680 num_remain
= node
->num_keys
+ 1 - num_children
;
681 ASSERT(num_remain
== 0 || num_remain
> BTREE_KEY_MIN
);
684 root
->stats
.shift_next
+= 1;
687 /* make space for "num_children" items at beginning of next-leaf */
688 i
= next_node
->num_keys
;
689 next_node
->ptrs
[num_children
+ i
] = next_node
->ptrs
[i
];
691 next_node
->keys
[num_children
+ i
] = next_node
->keys
[i
];
692 next_node
->ptrs
[num_children
+ i
] = next_node
->ptrs
[i
];
695 /* update keys in parent and next node from parent */
698 ASSERT(level
< root
->height
);
699 } while (root
->cursor
[level
].index
==
700 root
->cursor
[level
].node
->num_keys
);
702 next_node
->keys
[num_children
- 1] =
703 root
->cursor
[level
].node
->keys
[root
->cursor
[level
].index
];
704 root
->cursor
[level
].node
->keys
[root
->cursor
[level
].index
] =
705 node
->keys
[node
->num_keys
- num_children
];
707 /* copy last "num_children" items from node into start of next-node */
708 for (i
= 0; i
< num_children
- 1; i
++) {
709 next_node
->keys
[i
] = node
->keys
[num_remain
+ i
];
710 next_node
->ptrs
[i
] = node
->ptrs
[num_remain
+ i
];
712 next_node
->ptrs
[i
] = node
->ptrs
[num_remain
+ i
];
713 next_node
->num_keys
+= num_children
;
716 node
->num_keys
-= num_children
;
724 * Insertion functions
727 static struct btree_node
*
728 btree_increase_height(
729 struct btree_root
*root
)
731 struct btree_node
*new_root
;
732 struct btree_cursor
*new_cursor
;
734 new_cursor
= realloc(root
->cursor
, (root
->height
+ 1) *
735 sizeof(struct btree_cursor
));
738 root
->cursor
= new_cursor
;
740 new_root
= btree_node_alloc();
745 root
->stats
.alloced
+= 1;
746 root
->stats
.inc_height
+= 1;
747 root
->stats
.max_items
*= BTREE_PTR_MAX
;
750 new_root
->ptrs
[0] = root
->root_node
;
751 root
->root_node
= new_root
;
753 root
->cursor
[root
->height
].node
= new_root
;
754 root
->cursor
[root
->height
].index
= 0;
763 struct btree_root
*root
,
769 static struct btree_node
*
771 struct btree_root
*root
,
776 struct btree_node
*node
= root
->cursor
[level
].node
;
777 struct btree_node
*new_node
;
780 new_node
= btree_node_alloc();
784 if (btree_insert_item(root
, level
+ 1, node
->keys
[BTREE_KEY_MIN
],
786 btree_node_free(new_node
);
791 root
->stats
.alloced
+= 1;
792 root
->stats
.split
+= 1;
795 for (i
= 0; i
< BTREE_KEY_MAX
- BTREE_KEY_MIN
- 1; i
++) {
796 new_node
->keys
[i
] = node
->keys
[BTREE_KEY_MIN
+ 1 + i
];
797 new_node
->ptrs
[i
] = node
->ptrs
[BTREE_KEY_MIN
+ 1 + i
];
799 new_node
->ptrs
[i
] = node
->ptrs
[BTREE_KEY_MIN
+ 1 + i
];
800 new_node
->num_keys
= BTREE_KEY_MAX
- BTREE_KEY_MIN
- 1;
802 node
->num_keys
= BTREE_KEY_MIN
;
803 if (key
< node
->keys
[BTREE_KEY_MIN
])
804 return node
; /* index doesn't change */
806 /* insertion point is in new node... */
807 *index
-= BTREE_KEY_MIN
+ 1;
812 btree_insert_shift_to_prev(
813 struct btree_root
*root
,
817 struct btree_cursor tmp_cursor
[root
->height
];
823 if (!btree_copy_cursor_prev(root
, tmp_cursor
, level
+ 1))
826 n
= min(*index
, (BTREE_PTR_MAX
- tmp_cursor
[level
].node
->num_keys
) / 2);
827 if (!n
|| !btree_shift_to_prev(root
, level
, tmp_cursor
, n
))
835 btree_insert_shift_to_next(
836 struct btree_root
*root
,
840 struct btree_cursor tmp_cursor
[root
->height
];
843 if (*index
>= BTREE_KEY_MAX
)
846 if (!btree_copy_cursor_next(root
, tmp_cursor
, level
+ 1))
849 n
= min(BTREE_KEY_MAX
- *index
,
850 (BTREE_PTR_MAX
- tmp_cursor
[level
].node
->num_keys
) / 2);
851 if (!n
|| !btree_shift_to_next(root
, level
, tmp_cursor
, n
))
858 struct btree_root
*root
,
863 struct btree_node
*node
= root
->cursor
[level
].node
;
864 int index
= root
->cursor
[level
].index
;
867 if (node
->num_keys
== BTREE_KEY_MAX
) {
868 if (btree_insert_shift_to_prev(root
, level
, &index
) == 0)
870 if (btree_insert_shift_to_next(root
, level
, &index
) == 0)
872 if (level
== root
->height
- 1) {
873 if (!btree_increase_height(root
))
876 node
= btree_split(root
, level
, key
, &index
);
881 ASSERT(index
<= node
->num_keys
);
884 node
->ptrs
[i
+ 1] = node
->ptrs
[i
];
885 while (--i
>= index
) {
886 node
->keys
[i
+ 1] = node
->keys
[i
];
887 node
->ptrs
[i
+ 1] = node
->ptrs
[i
];
891 node
->keys
[index
] = key
;
894 node
->ptrs
[index
] = value
;
896 node
->ptrs
[index
+ 1] = value
;
905 struct btree_root
*root
,
914 if (btree_search(root
, key
) && root
->cur_key
== key
)
918 root
->stats
.insert
+= 1;
919 root
->stats
.num_items
+= 1;
922 result
= btree_insert_item(root
, 0, key
, value
);
924 btree_invalidate_cursor(root
);
933 * Rather more complicated as deletions has 4 ways to go once a node
934 * ends up with less than the minimum number of keys:
935 * - move remainder to previous node
936 * - move remainder to next node
937 * (both will involve a parent deletion which may recurse)
938 * - balance by moving some items from previous node
939 * - balance by moving some items from next node
943 btree_decrease_height(
944 struct btree_root
*root
)
946 struct btree_node
*old_root
= root
->root_node
;
948 ASSERT(old_root
->num_keys
== 0);
951 root
->stats
.alloced
-= 1;
952 root
->stats
.dec_height
+= 1;
953 root
->stats
.max_items
/= BTREE_PTR_MAX
;
955 root
->root_node
= old_root
->ptrs
[0];
956 btree_node_free(old_root
);
961 btree_merge_with_prev(
962 struct btree_root
*root
,
964 struct btree_cursor
*prev_cursor
)
969 if (!btree_shift_to_prev(root
, level
, prev_cursor
,
970 root
->cursor
[level
].node
->num_keys
+ 1))
974 root
->stats
.merge_prev
+= 1;
980 btree_merge_with_next(
981 struct btree_root
*root
,
983 struct btree_cursor
*next_cursor
)
988 if (!btree_shift_to_next(root
, level
, next_cursor
,
989 root
->cursor
[level
].node
->num_keys
+ 1))
993 root
->stats
.merge_next
+= 1;
999 btree_balance_with_prev(
1000 struct btree_root
*root
,
1002 struct btree_cursor
*prev_cursor
)
1004 struct btree_cursor
*root_cursor
= root
->cursor
;
1008 ASSERT(prev_cursor
[level
].node
->num_keys
> BTREE_KEY_MIN
);
1011 root
->stats
.balance_prev
+= 1;
1014 * Move some nodes from the prev node into the current node.
1015 * As the shift operation is a right shift and is relative to
1016 * the root cursor, make the root cursor the prev cursor and
1017 * pass in the root cursor as the next cursor.
1020 root
->cursor
= prev_cursor
;
1021 if (!btree_shift_to_next(root
, level
, root_cursor
,
1022 (prev_cursor
[level
].node
->num_keys
+ 1 - BTREE_KEY_MIN
) / 2))
1024 root
->cursor
= root_cursor
;
1030 btree_balance_with_next(
1031 struct btree_root
*root
,
1033 struct btree_cursor
*next_cursor
)
1035 struct btree_cursor
*root_cursor
= root
->cursor
;
1039 assert(next_cursor
[level
].node
->num_keys
> BTREE_KEY_MIN
);
1042 root
->stats
.balance_next
+= 1;
1045 * move some nodes from the next node into the current node.
1046 * as the shift operation is a left shift and is relative to
1047 * the root cursor, make the root cursor the next cursor and
1048 * pass in the root cursor as the prev cursor.
1051 root
->cursor
= next_cursor
;
1052 if (!btree_shift_to_prev(root
, level
, root_cursor
,
1053 (next_cursor
[level
].node
->num_keys
+ 1 - BTREE_KEY_MIN
) / 2))
1055 root
->cursor
= root_cursor
;
1063 struct btree_root
*root
,
1067 * btree_delete_node:
1069 * Return 0 if it's done or 1 if the next level needs to be collapsed
1073 struct btree_root
*root
,
1076 struct btree_cursor prev_cursor
[root
->height
];
1077 struct btree_cursor next_cursor
[root
->height
];
1078 struct btree_cursor
*pc
;
1079 struct btree_cursor
*nc
;
1082 * the node has underflowed, grab or merge keys/items from a
1083 * neighbouring node.
1086 if (level
== root
->height
- 1) {
1087 if (level
> 0 && root
->root_node
->num_keys
== 0)
1088 btree_decrease_height(root
);
1092 pc
= btree_copy_cursor_prev(root
, prev_cursor
, level
+ 1);
1093 if (!btree_merge_with_prev(root
, level
, pc
)) {
1094 nc
= btree_copy_cursor_next(root
, next_cursor
, level
+ 1);
1095 if (!btree_merge_with_next(root
, level
, nc
)) {
1096 /* merging failed, try redistrubution */
1097 if (!btree_balance_with_prev(root
, level
, pc
) &&
1098 !btree_balance_with_next(root
, level
, nc
))
1100 return; /* when balancing, then the node isn't freed */
1105 root
->stats
.alloced
-= 1;
1107 btree_node_free(root
->cursor
[level
].node
);
1109 btree_delete_key(root
, level
+ 1);
1114 struct btree_root
*root
,
1117 struct btree_node
*node
= root
->cursor
[level
].node
;
1118 int index
= root
->cursor
[level
].index
;
1121 if (index
<= node
->num_keys
) {
1123 * if not deleting the last item, shift higher items down
1124 * to cover the item being deleted
1126 while (index
< node
->num_keys
) {
1127 node
->keys
[index
] = node
->keys
[index
+ 1];
1128 node
->ptrs
[index
] = node
->ptrs
[index
+ 1];
1131 node
->ptrs
[index
] = node
->ptrs
[index
+ 1];
1134 * else update the associated parent key as the last key
1135 * in the leaf has changed
1137 btree_update_node_key(root
, root
->cursor
, level
+ 1,
1138 node
->keys
[node
->num_keys
]);
1141 * if node underflows, either merge with sibling or rebalance
1144 if (node
->num_keys
< BTREE_KEY_MIN
)
1145 btree_delete_node(root
, level
);
1150 struct btree_root
*root
,
1155 value
= btree_lookup(root
, key
);
1160 root
->stats
.delete += 1;
1161 root
->stats
.num_items
-= 1;
1164 btree_delete_key(root
, 0);
1166 btree_invalidate_cursor(root
);
1174 struct btree_root
*root
,
1177 unsigned long max_items
= root
->stats
.max_items
*
1178 (root
->root_node
->num_keys
+ 1);
1180 fprintf(f
, "\tnum_items = %lu, max_items = %lu (%lu%%)\n",
1181 root
->stats
.num_items
, max_items
,
1182 root
->stats
.num_items
* 100 / max_items
);
1183 fprintf(f
, "\talloced = %d nodes, %lu bytes, %lu bytes per item\n",
1184 root
->stats
.alloced
,
1185 root
->stats
.alloced
* sizeof(struct btree_node
),
1186 root
->stats
.alloced
* sizeof(struct btree_node
) /
1187 root
->stats
.num_items
);
1188 fprintf(f
, "\tlookup = %d\n", root
->stats
.lookup
);
1189 fprintf(f
, "\tfind = %d\n", root
->stats
.find
);
1190 fprintf(f
, "\tcache_hits = %d\n", root
->stats
.cache_hits
);
1191 fprintf(f
, "\tcache_misses = %d\n", root
->stats
.cache_misses
);
1192 fprintf(f
, "\tkey_update = %d\n", root
->stats
.key_update
);
1193 fprintf(f
, "\tvalue_update = %d\n", root
->stats
.value_update
);
1194 fprintf(f
, "\tinsert = %d\n", root
->stats
.insert
);
1195 fprintf(f
, "\tshift_prev = %d\n", root
->stats
.shift_prev
);
1196 fprintf(f
, "\tshift_next = %d\n", root
->stats
.shift_next
);
1197 fprintf(f
, "\tsplit = %d\n", root
->stats
.split
);
1198 fprintf(f
, "\tinc_height = %d\n", root
->stats
.inc_height
);
1199 fprintf(f
, "\tdelete = %d\n", root
->stats
.delete);
1200 fprintf(f
, "\tmerge_prev = %d\n", root
->stats
.merge_prev
);
1201 fprintf(f
, "\tmerge_next = %d\n", root
->stats
.merge_next
);
1202 fprintf(f
, "\tbalance_prev = %d\n", root
->stats
.balance_prev
);
1203 fprintf(f
, "\tbalance_next = %d\n", root
->stats
.balance_next
);
1204 fprintf(f
, "\tdec_height = %d\n", root
->stats
.dec_height
);