| // SPDX-License-Identifier: GPL-2.0 |
| /* |
| * Copyright (c) 2007, Silicon Graphics, Inc. Barry Naujok <bnaujok@sgi.com> |
| * All Rights Reserved. |
| */ |
| |
| #include "libxfs.h" |
| #include "btree.h" |
| |
| /* |
| * Maximum number of keys per node. Must be greater than 2 for the code |
| * to work. |
| */ |
| #define BTREE_KEY_MAX 7 |
| #define BTREE_KEY_MIN (BTREE_KEY_MAX / 2) |
| |
| #define BTREE_PTR_MAX (BTREE_KEY_MAX + 1) |
| |
| struct btree_node { |
| unsigned long num_keys; |
| unsigned long keys[BTREE_KEY_MAX]; |
| struct btree_node *ptrs[BTREE_PTR_MAX]; |
| }; |
| |
| struct btree_cursor { |
| struct btree_node *node; |
| int index; |
| }; |
| |
| struct btree_root { |
| struct btree_node *root_node; |
| struct btree_cursor *cursor; /* track path to end leaf */ |
| int height; |
| /* lookup cache */ |
| int keys_valid; /* set if the cache is valid */ |
| unsigned long cur_key; |
| unsigned long next_key; |
| void *next_value; |
| unsigned long prev_key; |
| void *prev_value; |
| #ifdef BTREE_STATS |
| struct btree_stats { |
| unsigned long num_items; |
| unsigned long max_items; |
| int alloced; |
| int cache_hits; |
| int cache_misses; |
| int lookup; |
| int find; |
| int key_update; |
| int value_update; |
| int insert; |
| int delete; |
| int inc_height; |
| int dec_height; |
| int shift_prev; |
| int shift_next; |
| int split; |
| int merge_prev; |
| int merge_next; |
| int balance_prev; |
| int balance_next; |
| } stats; |
| #endif |
| }; |
| |
| |
| static struct btree_node * |
| btree_node_alloc(void) |
| { |
| return calloc(1, sizeof(struct btree_node)); |
| } |
| |
| static void |
| btree_node_free( |
| struct btree_node *node) |
| { |
| free(node); |
| } |
| |
| static void |
| btree_free_nodes( |
| struct btree_node *node, |
| int level) |
| { |
| int i; |
| |
| if (level) |
| for (i = 0; i <= node->num_keys; i++) |
| btree_free_nodes(node->ptrs[i], level - 1); |
| btree_node_free(node); |
| } |
| |
| static void |
| __btree_init( |
| struct btree_root *root) |
| { |
| memset(root, 0, sizeof(struct btree_root)); |
| root->height = 1; |
| root->cursor = calloc(1, sizeof(struct btree_cursor)); |
| root->root_node = btree_node_alloc(); |
| ASSERT(root->root_node); |
| #ifdef BTREE_STATS |
| root->stats.max_items = 1; |
| root->stats.alloced += 1; |
| #endif |
| } |
| |
| static void |
| __btree_free( |
| struct btree_root *root) |
| { |
| btree_free_nodes(root->root_node, root->height - 1); |
| free(root->cursor); |
| root->height = 0; |
| root->cursor = NULL; |
| root->root_node = NULL; |
| } |
| |
| void |
| btree_init( |
| struct btree_root **root) |
| { |
| *root = calloc(1, sizeof(struct btree_root)); |
| __btree_init(*root); |
| } |
| |
| void |
| btree_clear( |
| struct btree_root *root) |
| { |
| __btree_free(root); |
| __btree_init(root); |
| } |
| |
| void |
| btree_destroy( |
| struct btree_root *root) |
| { |
| __btree_free(root); |
| free(root); |
| } |
| |
| int |
| btree_is_empty( |
| struct btree_root *root) |
| { |
| return root->root_node->num_keys == 0; |
| } |
| |
| static inline void |
| btree_invalidate_cursor( |
| struct btree_root *root) |
| { |
| root->cursor[0].node = NULL; |
| root->keys_valid = 0; |
| } |
| |
| static inline unsigned long |
| btree_key_of_cursor( |
| struct btree_cursor *cursor, |
| int height) |
| { |
| while (cursor->node->num_keys == cursor->index && --height > 0) |
| cursor++; |
| return cursor->node->keys[cursor->index]; |
| } |
| |
| static void * |
| btree_get_prev( |
| struct btree_root *root, |
| unsigned long *key) |
| { |
| struct btree_cursor *cur = root->cursor; |
| int level = 0; |
| struct btree_node *node; |
| |
| if (cur->index > 0) { |
| if (key) |
| *key = cur->node->keys[cur->index - 1]; |
| return cur->node->ptrs[cur->index - 1]; |
| } |
| |
| /* else need to go up and back down the tree to find the previous */ |
| do { |
| if (cur->index) |
| break; |
| cur++; |
| } while (++level < root->height); |
| |
| if (level == root->height) |
| return NULL; |
| |
| /* the key is in the current level */ |
| if (key) |
| *key = cur->node->keys[cur->index - 1]; |
| |
| /* descend back down the right side to get the pointer */ |
| node = cur->node->ptrs[cur->index - 1]; |
| while (level--) |
| node = node->ptrs[node->num_keys]; |
| return node; |
| } |
| |
| static void * |
| btree_get_next( |
| struct btree_root *root, |
| unsigned long *key) |
| { |
| struct btree_cursor *cur = root->cursor; |
| int level = 0; |
| struct btree_node *node; |
| |
| while (cur->index == cur->node->num_keys) { |
| if (++level == root->height) |
| return NULL; |
| cur++; |
| } |
| if (level == 0) { |
| if (key) { |
| cur->index++; |
| *key = btree_key_of_cursor(cur, root->height); |
| cur->index--; |
| } |
| return cur->node->ptrs[cur->index + 1]; |
| } |
| |
| node = cur->node->ptrs[cur->index + 1]; |
| while (--level > 0) |
| node = node->ptrs[0]; |
| if (key) |
| *key = node->keys[0]; |
| return node->ptrs[0]; |
| } |
| |
| /* |
| * Lookup/Search functions |
| */ |
| |
| static int |
| btree_do_search( |
| struct btree_root *root, |
| unsigned long key) |
| { |
| unsigned long k = 0; |
| struct btree_cursor *cur = root->cursor + root->height; |
| struct btree_node *node = root->root_node; |
| int height = root->height; |
| int key_found = 0; |
| int i; |
| |
| while (--height >= 0) { |
| cur--; |
| for (i = 0; i < node->num_keys; i++) |
| if (node->keys[i] >= key) { |
| k = node->keys[i]; |
| key_found = 1; |
| break; |
| } |
| cur->node = node; |
| cur->index = i; |
| node = node->ptrs[i]; |
| } |
| root->keys_valid = key_found; |
| if (!key_found) |
| return 0; |
| |
| root->cur_key = k; |
| root->next_value = NULL; /* do on-demand next value lookup */ |
| root->prev_value = btree_get_prev(root, &root->prev_key); |
| return 1; |
| } |
| |
| static int |
| btree_search( |
| struct btree_root *root, |
| unsigned long key) |
| { |
| if (root->keys_valid && key <= root->cur_key && |
| (!root->prev_value || key > root->prev_key)) { |
| #ifdef BTREE_STATS |
| root->stats.cache_hits++; |
| #endif |
| return 1; |
| } |
| #ifdef BTREE_STATS |
| root->stats.cache_misses++; |
| #endif |
| return btree_do_search(root, key); |
| } |
| |
| void * |
| btree_find( |
| struct btree_root *root, |
| unsigned long key, |
| unsigned long *actual_key) |
| { |
| #ifdef BTREE_STATS |
| root->stats.find += 1; |
| #endif |
| if (!btree_search(root, key)) |
| return NULL; |
| |
| if (actual_key) |
| *actual_key = root->cur_key; |
| return root->cursor->node->ptrs[root->cursor->index]; |
| } |
| |
| void * |
| btree_lookup( |
| struct btree_root *root, |
| unsigned long key) |
| { |
| #ifdef BTREE_STATS |
| root->stats.lookup += 1; |
| #endif |
| if (!btree_search(root, key) || root->cur_key != key) |
| return NULL; |
| return root->cursor->node->ptrs[root->cursor->index]; |
| } |
| |
| void * |
| btree_peek_prev( |
| struct btree_root *root, |
| unsigned long *key) |
| { |
| if (!root->keys_valid) |
| return NULL; |
| if (key) |
| *key = root->prev_key; |
| return root->prev_value; |
| } |
| |
| void * |
| btree_peek_next( |
| struct btree_root *root, |
| unsigned long *key) |
| { |
| if (!root->keys_valid) |
| return NULL; |
| if (!root->next_value) |
| root->next_value = btree_get_next(root, &root->next_key); |
| if (key) |
| *key = root->next_key; |
| return root->next_value; |
| } |
| |
| static void * |
| btree_move_cursor_to_next( |
| struct btree_root *root, |
| unsigned long *key) |
| { |
| struct btree_cursor *cur = root->cursor; |
| int level = 0; |
| |
| while (cur->index == cur->node->num_keys) { |
| if (++level == root->height) |
| return NULL; |
| cur++; |
| } |
| cur->index++; |
| if (level == 0) { |
| if (key) |
| *key = btree_key_of_cursor(cur, root->height); |
| return cur->node->ptrs[cur->index]; |
| } |
| |
| while (--level >= 0) { |
| root->cursor[level].node = cur->node->ptrs[cur->index]; |
| root->cursor[level].index = 0; |
| cur--; |
| } |
| if (key) |
| *key = cur->node->keys[0]; |
| return cur->node->ptrs[0]; |
| } |
| |
| void * |
| btree_lookup_next( |
| struct btree_root *root, |
| unsigned long *key) |
| { |
| void *value; |
| |
| if (!root->keys_valid) |
| return NULL; |
| |
| root->prev_key = root->cur_key; |
| root->prev_value = root->cursor->node->ptrs[root->cursor->index]; |
| |
| value = btree_move_cursor_to_next(root, &root->cur_key); |
| if (!value) { |
| btree_invalidate_cursor(root); |
| return NULL; |
| } |
| root->next_value = NULL; /* on-demand next value fetch */ |
| if (key) |
| *key = root->cur_key; |
| return value; |
| } |
| |
| static void * |
| btree_move_cursor_to_prev( |
| struct btree_root *root, |
| unsigned long *key) |
| { |
| struct btree_cursor *cur = root->cursor; |
| int level = 0; |
| |
| while (cur->index == 0) { |
| if (++level == root->height) |
| return NULL; |
| cur++; |
| } |
| cur->index--; |
| if (key) /* the key is in the current level */ |
| *key = cur->node->keys[cur->index]; |
| while (level > 0) { |
| level--; |
| root->cursor[level].node = cur->node->ptrs[cur->index]; |
| root->cursor[level].index = root->cursor[level].node->num_keys; |
| cur--; |
| } |
| return cur->node->ptrs[cur->index]; |
| } |
| |
| void * |
| btree_lookup_prev( |
| struct btree_root *root, |
| unsigned long *key) |
| { |
| void *value; |
| |
| if (!root->keys_valid) |
| return NULL; |
| |
| value = btree_move_cursor_to_prev(root, &root->cur_key); |
| if (!value) |
| return NULL; |
| root->prev_value = btree_get_prev(root, &root->prev_key); |
| root->next_value = NULL; /* on-demand next value fetch */ |
| if (key) |
| *key = root->cur_key; |
| return value; |
| } |
| |
| /* Update functions */ |
| |
| static inline void |
| btree_update_node_key( |
| struct btree_root *root, |
| struct btree_cursor *cursor, |
| int level, |
| unsigned long new_key) |
| { |
| int i; |
| |
| #ifdef BTREE_STATS |
| root->stats.key_update += 1; |
| #endif |
| |
| cursor += level; |
| for (i = level; i < root->height; i++) { |
| if (cursor->index < cursor->node->num_keys) { |
| cursor->node->keys[cursor->index] = new_key; |
| break; |
| } |
| cursor++; |
| } |
| } |
| |
| int |
| btree_update_key( |
| struct btree_root *root, |
| unsigned long old_key, |
| unsigned long new_key) |
| { |
| if (!btree_search(root, old_key) || root->cur_key != old_key) |
| return ENOENT; |
| |
| if (root->next_value && new_key >= root->next_key) |
| return EINVAL; |
| |
| if (root->prev_value && new_key <= root->prev_key) |
| return EINVAL; |
| |
| btree_update_node_key(root, root->cursor, 0, new_key); |
| root->cur_key = new_key; |
| |
| return 0; |
| } |
| |
| int |
| btree_update_value( |
| struct btree_root *root, |
| unsigned long key, |
| void *new_value) |
| { |
| if (!new_value) |
| return EINVAL; |
| |
| if (!btree_search(root, key) || root->cur_key != key) |
| return ENOENT; |
| |
| #ifdef BTREE_STATS |
| root->stats.value_update += 1; |
| #endif |
| root->cursor->node->ptrs[root->cursor->index] = new_value; |
| |
| return 0; |
| } |
| |
| /* |
| * Cursor modification functions - used for inserting and deleting |
| */ |
| |
| static struct btree_cursor * |
| btree_copy_cursor_prev( |
| struct btree_root *root, |
| struct btree_cursor *dest_cursor, |
| int level) |
| { |
| struct btree_cursor *src_cur = root->cursor + level; |
| struct btree_cursor *dst_cur; |
| int l = level; |
| int i; |
| |
| if (level >= root->height) |
| return NULL; |
| |
| while (src_cur->index == 0) { |
| if (++l >= root->height) |
| return NULL; |
| src_cur++; |
| } |
| for (i = l; i < root->height; i++) |
| dest_cursor[i] = *src_cur++; |
| |
| dst_cur = dest_cursor + l; |
| dst_cur->index--; |
| while (l-- >= level) { |
| dest_cursor[l].node = dst_cur->node->ptrs[dst_cur->index]; |
| dest_cursor[l].index = dest_cursor[l].node->num_keys; |
| dst_cur--; |
| } |
| return dest_cursor; |
| } |
| |
| static struct btree_cursor * |
| btree_copy_cursor_next( |
| struct btree_root *root, |
| struct btree_cursor *dest_cursor, |
| int level) |
| { |
| struct btree_cursor *src_cur = root->cursor + level; |
| struct btree_cursor *dst_cur; |
| int l = level; |
| int i; |
| |
| if (level >= root->height) |
| return NULL; |
| |
| while (src_cur->index == src_cur->node->num_keys) { |
| if (++l >= root->height) |
| return NULL; |
| src_cur++; |
| } |
| for (i = l; i < root->height; i++) |
| dest_cursor[i] = *src_cur++; |
| |
| dst_cur = dest_cursor + l; |
| dst_cur->index++; |
| while (l-- >= level) { |
| dest_cursor[l].node = dst_cur->node->ptrs[dst_cur->index]; |
| dest_cursor[l].index = 0; |
| dst_cur--; |
| } |
| return dest_cursor; |
| } |
| |
| /* |
| * Shift functions |
| * |
| * Tries to move items in the current leaf to its sibling if it has space. |
| * Used in both insert and delete functions. |
| * Returns the number of items shifted. |
| */ |
| |
| static int |
| btree_shift_to_prev( |
| struct btree_root *root, |
| int level, |
| struct btree_cursor *prev_cursor, |
| int num_children) |
| { |
| struct btree_node *node; |
| struct btree_node *prev_node; |
| int num_remain; /* # of keys left in "node" */ |
| unsigned long key; |
| int i; |
| |
| if (!prev_cursor || !num_children) |
| return 0; |
| |
| prev_node = prev_cursor[level].node; |
| node = root->cursor[level].node; |
| |
| ASSERT(num_children > 0 && num_children <= node->num_keys + 1); |
| |
| if ((prev_node->num_keys + num_children) > BTREE_KEY_MAX) |
| return 0; |
| |
| #ifdef BTREE_STATS |
| root->stats.shift_prev += 1; |
| #endif |
| |
| num_remain = node->num_keys - num_children; |
| ASSERT(num_remain == -1 || num_remain >= BTREE_KEY_MIN); |
| |
| /* shift parent keys around */ |
| level++; |
| if (num_remain > 0) |
| key = node->keys[num_children - 1]; |
| else |
| key = btree_key_of_cursor(root->cursor + level, |
| root->height - level); |
| while (prev_cursor[level].index == prev_cursor[level].node->num_keys) { |
| level++; |
| ASSERT(level < root->height); |
| } |
| prev_node->keys[prev_node->num_keys] = |
| prev_cursor[level].node->keys[prev_cursor[level].index]; |
| prev_cursor[level].node->keys[prev_cursor[level].index] = key; |
| |
| /* copy pointers and keys to the end of the prev node */ |
| for (i = 0; i < num_children - 1; i++) { |
| prev_node->keys[prev_node->num_keys + 1 + i] = node->keys[i]; |
| prev_node->ptrs[prev_node->num_keys + 1 + i] = node->ptrs[i]; |
| } |
| prev_node->ptrs[prev_node->num_keys + 1 + i] = node->ptrs[i]; |
| prev_node->num_keys += num_children; |
| |
| /* move remaining pointers/keys to start of node */ |
| if (num_remain >= 0) { |
| for (i = 0; i < num_remain; i++) { |
| node->keys[i] = node->keys[num_children + i]; |
| node->ptrs[i] = node->ptrs[num_children + i]; |
| } |
| node->ptrs[i] = node->ptrs[num_children + i]; |
| node->num_keys = num_remain; |
| } else |
| node->num_keys = 0; |
| |
| return num_children; |
| } |
| |
| static int |
| btree_shift_to_next( |
| struct btree_root *root, |
| int level, |
| struct btree_cursor *next_cursor, |
| int num_children) |
| { |
| struct btree_node *node; |
| struct btree_node *next_node; |
| int num_remain; /* # of children left in node */ |
| int i; |
| |
| if (!next_cursor || !num_children) |
| return 0; |
| |
| node = root->cursor[level].node; |
| next_node = next_cursor[level].node; |
| |
| ASSERT(num_children > 0 && num_children <= node->num_keys + 1); |
| |
| if ((next_node->num_keys + num_children) > BTREE_KEY_MAX) |
| return 0; |
| |
| num_remain = node->num_keys + 1 - num_children; |
| ASSERT(num_remain == 0 || num_remain > BTREE_KEY_MIN); |
| |
| #ifdef BTREE_STATS |
| root->stats.shift_next += 1; |
| #endif |
| |
| /* make space for "num_children" items at beginning of next-leaf */ |
| i = next_node->num_keys; |
| next_node->ptrs[num_children + i] = next_node->ptrs[i]; |
| while (--i >= 0) { |
| next_node->keys[num_children + i] = next_node->keys[i]; |
| next_node->ptrs[num_children + i] = next_node->ptrs[i]; |
| } |
| |
| /* update keys in parent and next node from parent */ |
| do { |
| level++; |
| ASSERT(level < root->height); |
| } while (root->cursor[level].index == |
| root->cursor[level].node->num_keys); |
| |
| next_node->keys[num_children - 1] = |
| root->cursor[level].node->keys[root->cursor[level].index]; |
| root->cursor[level].node->keys[root->cursor[level].index] = |
| node->keys[node->num_keys - num_children]; |
| |
| /* copy last "num_children" items from node into start of next-node */ |
| for (i = 0; i < num_children - 1; i++) { |
| next_node->keys[i] = node->keys[num_remain + i]; |
| next_node->ptrs[i] = node->ptrs[num_remain + i]; |
| } |
| next_node->ptrs[i] = node->ptrs[num_remain + i]; |
| next_node->num_keys += num_children; |
| |
| if (num_remain > 0) |
| node->num_keys -= num_children; |
| else |
| node->num_keys = 0; |
| |
| return num_children; |
| } |
| |
| /* |
| * Insertion functions |
| */ |
| |
| static struct btree_node * |
| btree_increase_height( |
| struct btree_root *root) |
| { |
| struct btree_node *new_root; |
| struct btree_cursor *new_cursor; |
| |
| new_cursor = realloc(root->cursor, (root->height + 1) * |
| sizeof(struct btree_cursor)); |
| if (!new_cursor) |
| return NULL; |
| root->cursor = new_cursor; |
| |
| new_root = btree_node_alloc(); |
| if (!new_root) |
| return NULL; |
| |
| #ifdef BTREE_STATS |
| root->stats.alloced += 1; |
| root->stats.inc_height += 1; |
| root->stats.max_items *= BTREE_PTR_MAX; |
| #endif |
| |
| new_root->ptrs[0] = root->root_node; |
| root->root_node = new_root; |
| |
| root->cursor[root->height].node = new_root; |
| root->cursor[root->height].index = 0; |
| |
| root->height++; |
| |
| return new_root; |
| } |
| |
| static int |
| btree_insert_item( |
| struct btree_root *root, |
| int level, |
| unsigned long key, |
| void *value); |
| |
| |
| static struct btree_node * |
| btree_split( |
| struct btree_root *root, |
| int level, |
| unsigned long key, |
| int *index) |
| { |
| struct btree_node *node = root->cursor[level].node; |
| struct btree_node *new_node; |
| int i; |
| |
| new_node = btree_node_alloc(); |
| if (!new_node) |
| return NULL; |
| |
| if (btree_insert_item(root, level + 1, node->keys[BTREE_KEY_MIN], |
| new_node) != 0) { |
| btree_node_free(new_node); |
| return NULL; |
| } |
| |
| #ifdef BTREE_STATS |
| root->stats.alloced += 1; |
| root->stats.split += 1; |
| #endif |
| |
| for (i = 0; i < BTREE_KEY_MAX - BTREE_KEY_MIN - 1; i++) { |
| new_node->keys[i] = node->keys[BTREE_KEY_MIN + 1 + i]; |
| new_node->ptrs[i] = node->ptrs[BTREE_KEY_MIN + 1 + i]; |
| } |
| new_node->ptrs[i] = node->ptrs[BTREE_KEY_MIN + 1 + i]; |
| new_node->num_keys = BTREE_KEY_MAX - BTREE_KEY_MIN - 1; |
| |
| node->num_keys = BTREE_KEY_MIN; |
| if (key < node->keys[BTREE_KEY_MIN]) |
| return node; /* index doesn't change */ |
| |
| /* insertion point is in new node... */ |
| *index -= BTREE_KEY_MIN + 1; |
| return new_node; |
| } |
| |
| static int |
| btree_insert_shift_to_prev( |
| struct btree_root *root, |
| int level, |
| int *index) |
| { |
| struct btree_cursor tmp_cursor[root->height]; |
| int n; |
| |
| if (*index <= 0) |
| return -1; |
| |
| if (!btree_copy_cursor_prev(root, tmp_cursor, level + 1)) |
| return -1; |
| |
| n = min(*index, (BTREE_PTR_MAX - tmp_cursor[level].node->num_keys) / 2); |
| if (!n || !btree_shift_to_prev(root, level, tmp_cursor, n)) |
| return -1; |
| |
| *index -= n; |
| return 0; |
| } |
| |
| static int |
| btree_insert_shift_to_next( |
| struct btree_root *root, |
| int level, |
| int *index) |
| { |
| struct btree_cursor tmp_cursor[root->height]; |
| int n; |
| |
| if (*index >= BTREE_KEY_MAX) |
| return -1; |
| |
| if (!btree_copy_cursor_next(root, tmp_cursor, level + 1)) |
| return -1; |
| |
| n = min(BTREE_KEY_MAX - *index, |
| (BTREE_PTR_MAX - tmp_cursor[level].node->num_keys) / 2); |
| if (!n || !btree_shift_to_next(root, level, tmp_cursor, n)) |
| return -1; |
| return 0; |
| } |
| |
| static int |
| btree_insert_item( |
| struct btree_root *root, |
| int level, |
| unsigned long key, |
| void *value) |
| { |
| struct btree_node *node = root->cursor[level].node; |
| int index = root->cursor[level].index; |
| int i; |
| |
| if (node->num_keys == BTREE_KEY_MAX) { |
| if (btree_insert_shift_to_prev(root, level, &index) == 0) |
| goto insert; |
| if (btree_insert_shift_to_next(root, level, &index) == 0) |
| goto insert; |
| if (level == root->height - 1) { |
| if (!btree_increase_height(root)) |
| return ENOMEM; |
| } |
| node = btree_split(root, level, key, &index); |
| if (!node) |
| return ENOMEM; |
| } |
| insert: |
| ASSERT(index <= node->num_keys); |
| |
| i = node->num_keys; |
| node->ptrs[i + 1] = node->ptrs[i]; |
| while (--i >= index) { |
| node->keys[i + 1] = node->keys[i]; |
| node->ptrs[i + 1] = node->ptrs[i]; |
| } |
| |
| node->num_keys++; |
| node->keys[index] = key; |
| |
| if (level == 0) |
| node->ptrs[index] = value; |
| else |
| node->ptrs[index + 1] = value; |
| |
| return 0; |
| } |
| |
| |
| |
| int |
| btree_insert( |
| struct btree_root *root, |
| unsigned long key, |
| void *value) |
| { |
| int result; |
| |
| if (!value) |
| return EINVAL; |
| |
| if (btree_search(root, key) && root->cur_key == key) |
| return EEXIST; |
| |
| #ifdef BTREE_STATS |
| root->stats.insert += 1; |
| root->stats.num_items += 1; |
| #endif |
| |
| result = btree_insert_item(root, 0, key, value); |
| |
| btree_invalidate_cursor(root); |
| |
| return result; |
| } |
| |
| |
| /* |
| * Deletion functions |
| * |
| * Rather more complicated as deletions has 4 ways to go once a node |
| * ends up with less than the minimum number of keys: |
| * - move remainder to previous node |
| * - move remainder to next node |
| * (both will involve a parent deletion which may recurse) |
| * - balance by moving some items from previous node |
| * - balance by moving some items from next node |
| */ |
| |
| static void |
| btree_decrease_height( |
| struct btree_root *root) |
| { |
| struct btree_node *old_root = root->root_node; |
| |
| ASSERT(old_root->num_keys == 0); |
| |
| #ifdef BTREE_STATS |
| root->stats.alloced -= 1; |
| root->stats.dec_height += 1; |
| root->stats.max_items /= BTREE_PTR_MAX; |
| #endif |
| root->root_node = old_root->ptrs[0]; |
| btree_node_free(old_root); |
| root->height--; |
| } |
| |
| static int |
| btree_merge_with_prev( |
| struct btree_root *root, |
| int level, |
| struct btree_cursor *prev_cursor) |
| { |
| if (!prev_cursor) |
| return 0; |
| |
| if (!btree_shift_to_prev(root, level, prev_cursor, |
| root->cursor[level].node->num_keys + 1)) |
| return 0; |
| |
| #ifdef BTREE_STATS |
| root->stats.merge_prev += 1; |
| #endif |
| return 1; |
| } |
| |
| static int |
| btree_merge_with_next( |
| struct btree_root *root, |
| int level, |
| struct btree_cursor *next_cursor) |
| { |
| if (!next_cursor) |
| return 0; |
| |
| if (!btree_shift_to_next(root, level, next_cursor, |
| root->cursor[level].node->num_keys + 1)) |
| return 0; |
| |
| #ifdef BTREE_STATS |
| root->stats.merge_next += 1; |
| #endif |
| return 1; |
| } |
| |
| static int |
| btree_balance_with_prev( |
| struct btree_root *root, |
| int level, |
| struct btree_cursor *prev_cursor) |
| { |
| struct btree_cursor *root_cursor = root->cursor; |
| |
| if (!prev_cursor) |
| return 0; |
| ASSERT(prev_cursor[level].node->num_keys > BTREE_KEY_MIN); |
| |
| #ifdef BTREE_STATS |
| root->stats.balance_prev += 1; |
| #endif |
| /* |
| * Move some nodes from the prev node into the current node. |
| * As the shift operation is a right shift and is relative to |
| * the root cursor, make the root cursor the prev cursor and |
| * pass in the root cursor as the next cursor. |
| */ |
| |
| root->cursor = prev_cursor; |
| if (!btree_shift_to_next(root, level, root_cursor, |
| (prev_cursor[level].node->num_keys + 1 - BTREE_KEY_MIN) / 2)) |
| abort(); |
| root->cursor = root_cursor; |
| |
| return 1; |
| } |
| |
| static int |
| btree_balance_with_next( |
| struct btree_root *root, |
| int level, |
| struct btree_cursor *next_cursor) |
| { |
| struct btree_cursor *root_cursor = root->cursor; |
| |
| if (!next_cursor) |
| return 0; |
| assert(next_cursor[level].node->num_keys > BTREE_KEY_MIN); |
| |
| #ifdef btree_stats |
| root->stats.balance_next += 1; |
| #endif |
| /* |
| * move some nodes from the next node into the current node. |
| * as the shift operation is a left shift and is relative to |
| * the root cursor, make the root cursor the next cursor and |
| * pass in the root cursor as the prev cursor. |
| */ |
| |
| root->cursor = next_cursor; |
| if (!btree_shift_to_prev(root, level, root_cursor, |
| (next_cursor[level].node->num_keys + 1 - BTREE_KEY_MIN) / 2)) |
| abort(); |
| root->cursor = root_cursor; |
| |
| return 1; |
| |
| } |
| |
| static void |
| btree_delete_key( |
| struct btree_root *root, |
| int level); |
| |
| /* |
| * btree_delete_node: |
| * |
| * Return 0 if it's done or 1 if the next level needs to be collapsed |
| */ |
| static void |
| btree_delete_node( |
| struct btree_root *root, |
| int level) |
| { |
| struct btree_cursor prev_cursor[root->height]; |
| struct btree_cursor next_cursor[root->height]; |
| struct btree_cursor *pc; |
| struct btree_cursor *nc; |
| |
| /* |
| * the node has underflowed, grab or merge keys/items from a |
| * neighbouring node. |
| */ |
| |
| if (level == root->height - 1) { |
| if (level > 0 && root->root_node->num_keys == 0) |
| btree_decrease_height(root); |
| return; |
| } |
| |
| pc = btree_copy_cursor_prev(root, prev_cursor, level + 1); |
| if (!btree_merge_with_prev(root, level, pc)) { |
| nc = btree_copy_cursor_next(root, next_cursor, level + 1); |
| if (!btree_merge_with_next(root, level, nc)) { |
| /* merging failed, try redistrubution */ |
| if (!btree_balance_with_prev(root, level, pc) && |
| !btree_balance_with_next(root, level, nc)) |
| abort(); |
| return; /* when balancing, then the node isn't freed */ |
| } |
| } |
| |
| #ifdef BTREE_STATS |
| root->stats.alloced -= 1; |
| #endif |
| btree_node_free(root->cursor[level].node); |
| |
| btree_delete_key(root, level + 1); |
| } |
| |
| static void |
| btree_delete_key( |
| struct btree_root *root, |
| int level) |
| { |
| struct btree_node *node = root->cursor[level].node; |
| int index = root->cursor[level].index; |
| |
| node->num_keys--; |
| if (index <= node->num_keys) { |
| /* |
| * if not deleting the last item, shift higher items down |
| * to cover the item being deleted |
| */ |
| while (index < node->num_keys) { |
| node->keys[index] = node->keys[index + 1]; |
| node->ptrs[index] = node->ptrs[index + 1]; |
| index++; |
| } |
| node->ptrs[index] = node->ptrs[index + 1]; |
| } else { |
| /* |
| * else update the associated parent key as the last key |
| * in the leaf has changed |
| */ |
| btree_update_node_key(root, root->cursor, level + 1, |
| node->keys[node->num_keys]); |
| } |
| /* |
| * if node underflows, either merge with sibling or rebalance |
| * with sibling. |
| */ |
| if (node->num_keys < BTREE_KEY_MIN) |
| btree_delete_node(root, level); |
| } |
| |
| void * |
| btree_delete( |
| struct btree_root *root, |
| unsigned long key) |
| { |
| void *value; |
| |
| value = btree_lookup(root, key); |
| if (!value) |
| return NULL; |
| |
| #ifdef BTREE_STATS |
| root->stats.delete += 1; |
| root->stats.num_items -= 1; |
| #endif |
| |
| btree_delete_key(root, 0); |
| |
| btree_invalidate_cursor(root); |
| |
| return value; |
| } |
| |
| #ifdef BTREE_STATS |
| void |
| btree_print_stats( |
| struct btree_root *root, |
| FILE *f) |
| { |
| unsigned long max_items = root->stats.max_items * |
| (root->root_node->num_keys + 1); |
| |
| fprintf(f, "\tnum_items = %lu, max_items = %lu (%lu%%)\n", |
| root->stats.num_items, max_items, |
| root->stats.num_items * 100 / max_items); |
| fprintf(f, "\talloced = %d nodes, %lu bytes, %lu bytes per item\n", |
| root->stats.alloced, |
| root->stats.alloced * sizeof(struct btree_node), |
| root->stats.alloced * sizeof(struct btree_node) / |
| root->stats.num_items); |
| fprintf(f, "\tlookup = %d\n", root->stats.lookup); |
| fprintf(f, "\tfind = %d\n", root->stats.find); |
| fprintf(f, "\tcache_hits = %d\n", root->stats.cache_hits); |
| fprintf(f, "\tcache_misses = %d\n", root->stats.cache_misses); |
| fprintf(f, "\tkey_update = %d\n", root->stats.key_update); |
| fprintf(f, "\tvalue_update = %d\n", root->stats.value_update); |
| fprintf(f, "\tinsert = %d\n", root->stats.insert); |
| fprintf(f, "\tshift_prev = %d\n", root->stats.shift_prev); |
| fprintf(f, "\tshift_next = %d\n", root->stats.shift_next); |
| fprintf(f, "\tsplit = %d\n", root->stats.split); |
| fprintf(f, "\tinc_height = %d\n", root->stats.inc_height); |
| fprintf(f, "\tdelete = %d\n", root->stats.delete); |
| fprintf(f, "\tmerge_prev = %d\n", root->stats.merge_prev); |
| fprintf(f, "\tmerge_next = %d\n", root->stats.merge_next); |
| fprintf(f, "\tbalance_prev = %d\n", root->stats.balance_prev); |
| fprintf(f, "\tbalance_next = %d\n", root->stats.balance_next); |
| fprintf(f, "\tdec_height = %d\n", root->stats.dec_height); |
| } |
| #endif |