| 0,0 → 1,428 |
|---|
| /* |
| * Copyright (C) 2006 Jakub Jermar |
| * All rights reserved. |
| * |
| * Redistribution and use in source and binary forms, with or without |
| * modification, are permitted provided that the following conditions |
| * are met: |
| * |
| * - Redistributions of source code must retain the above copyright |
| * notice, this list of conditions and the following disclaimer. |
| * - Redistributions in binary form must reproduce the above copyright |
| * notice, this list of conditions and the following disclaimer in the |
| * documentation and/or other materials provided with the distribution. |
| * - The name of the author may not be used to endorse or promote products |
| * derived from this software without specific prior written permission. |
| * |
| * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR |
| * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES |
| * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. |
| * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, |
| * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT |
| * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
| * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
| * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
| * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF |
| * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
| */ |
| |
| /* |
| * This B-tree has the following properties: |
| * - it is a ballanced 2-3-4 tree (i.e. M = 4) |
| * - values (i.e. pointers to values) are stored only in leaves |
| * - leaves are linked in a list |
| * - technically, it is a B+-tree (because of the previous properties) |
| * |
| * Some of the functions below take pointer to the right-hand |
| * side subtree pointer as parameter. Note that this is sufficient |
| * because: |
| * - New root node is passed the left-hand side subtree pointer |
| * directly. |
| * - node_split() always creates the right sibling and preserves |
| * the original node (which becomes the left sibling). |
| * There is always pointer to the left-hand side subtree |
| * (i.e. left sibling) in the parent node. |
| */ |
| |
| #include <adt/btree.h> |
| #include <adt/list.h> |
| #include <mm/slab.h> |
| #include <debug.h> |
| #include <panic.h> |
| #include <typedefs.h> |
| #include <print.h> |
| |
| static void _btree_insert(btree_t *t, __native key, void *value, btree_node_t *rsubtree, btree_node_t *node); |
| static void node_initialize(btree_node_t *node); |
| static void node_insert_key(btree_node_t *node, __native key, void *value, btree_node_t *rsubtree); |
| static btree_node_t *node_split(btree_node_t *node, __native key, void *value, btree_node_t *rsubtree, __native *median); |
| |
| #define ROOT_NODE(n) (!(n)->parent) |
| #define INDEX_NODE(n) ((n)->subtree[0] != NULL) |
| #define LEAF_NODE(n) ((n)->subtree[0] == NULL) |
| |
| #define MEDIAN_LOW_INDEX(n) (((n)->keys-1)/2) |
| #define MEDIAN_HIGH_INDEX(n) ((n)->keys/2) |
| #define MEDIAN_LOW(n) ((n)->key[MEDIAN_LOW_INDEX((n))]); |
| #define MEDIAN_HIGH(n) ((n)->key[MEDIAN_HIGH_INDEX((n))]); |
| |
| /** Create empty B-tree. |
| * |
| * @param t B-tree. |
| */ |
| void btree_create(btree_t *t) |
| { |
| list_initialize(&t->leaf_head); |
| t->root = (btree_node_t *) malloc(sizeof(btree_node_t), 0); |
| node_initialize(t->root); |
| list_append(&t->root->leaf_link, &t->leaf_head); |
| } |
| |
| /** Destroy empty B-tree. */ |
| void btree_destroy(btree_t *t) |
| { |
| ASSERT(!t->root->keys); |
| free(t->root); |
| } |
| |
| /** Insert key-value pair into B-tree. |
| * |
| * @param t B-tree. |
| * @param key Key to be inserted. |
| * @param value Value to be inserted. |
| * @param leaf_node Leaf node where the insertion should begin. |
| */ |
| void btree_insert(btree_t *t, __native key, void *value, btree_node_t *leaf_node) |
| { |
| btree_node_t *lnode; |
| |
| ASSERT(value); |
| |
| lnode = leaf_node; |
| if (!lnode) { |
| if (btree_search(t, key, &lnode)) { |
| panic("B-tree %P already contains key %d\n", t, key); |
| } |
| } |
| |
| _btree_insert(t, key, value, NULL, lnode); |
| } |
| |
| /** Recursively insert into B-tree. |
| * |
| * @param t B-tree. |
| * @param key Key to be inserted. |
| * @param value Value to be inserted. |
| * @param rsubtree Right subtree of the inserted key. |
| * @param node Start inserting into this node. |
| */ |
| void _btree_insert(btree_t *t, __native key, void *value, btree_node_t *rsubtree, btree_node_t *node) |
| { |
| if (node->keys < BTREE_MAX_KEYS) { |
| /* |
| * Node conatins enough space, the key can be stored immediately. |
| */ |
| node_insert_key(node, key, value, rsubtree); |
| } else { |
| btree_node_t *rnode; |
| __native median; |
| |
| /* |
| * Node is full. |
| * Split it and insert the smallest key from the node containing |
| * bigger keys (i.e. the original node) into its parent. |
| */ |
| |
| rnode = node_split(node, key, value, rsubtree, &median); |
| |
| if (LEAF_NODE(node)) { |
| list_append(&rnode->leaf_link, &node->leaf_link); |
| } |
| |
| if (ROOT_NODE(node)) { |
| /* |
| * We split the root node. Create new root. |
| */ |
| |
| t->root = (btree_node_t *) malloc(sizeof(btree_node_t), 0); |
| node->parent = t->root; |
| rnode->parent = t->root; |
| node_initialize(t->root); |
| |
| /* |
| * Left-hand side subtree will be the old root (i.e. node). |
| * Right-hand side subtree will be rnode. |
| */ |
| t->root->subtree[0] = node; |
| |
| t->root->depth = node->depth + 1; |
| } |
| _btree_insert(t, median, NULL, rnode, node->parent); |
| } |
| |
| } |
| |
| /* TODO */ |
| void btree_remove(btree_t *t, __native key) |
| { |
| } |
| |
| /** Search key in a B-tree. |
| * |
| * @param t B-tree. |
| * @param key Key to be searched. |
| * @param leaf_node Address where to put pointer to visited leaf node. |
| * |
| * @return Pointer to value or NULL if there is no such key. |
| */ |
| void *btree_search(btree_t *t, __native key, btree_node_t **leaf_node) |
| { |
| btree_node_t *cur, *next; |
| void *val = NULL; |
| |
| /* |
| * Iteratively descend to the leaf that can contain searched key. |
| */ |
| for (cur = t->root; cur; cur = next) { |
| int i; |
| |
| /* Last iteration will set this with proper leaf node address. */ |
| *leaf_node = cur; |
| for (i = 0; i < cur->keys; i++) { |
| if (key <= cur->key[i]) { |
| val = cur->value[i]; |
| next = cur->subtree[i]; |
| |
| /* |
| * Check if there is anywhere to descend. |
| */ |
| if (!next) { |
| /* |
| * Leaf-level. |
| */ |
| return (key == cur->key[i]) ? val : NULL; |
| } |
| goto descend; |
| } |
| } |
| next = cur->subtree[i]; |
| descend: |
| ; |
| } |
| |
| /* |
| * The key was not found in the *leaf_node and is greater than any of its keys. |
| */ |
| return NULL; |
| } |
| |
| /** Get pointer to value with the smallest key within the node. |
| * |
| * Can be only used on leaf-level nodes. |
| * |
| * @param node B-tree node. |
| * |
| * @return Pointer to value assiciated with the smallest key. |
| */ |
| void *btree_node_min(btree_node_t *node) |
| { |
| ASSERT(LEAF_NODE(node)); |
| ASSERT(node->keys); |
| return node->value[0]; |
| } |
| |
| /** Get pointer to value with the biggest key within the node. |
| * |
| * Can be only used on leaf-level nodes. |
| * |
| * @param node B-tree node. |
| * |
| * @return Pointer to value assiciated with the biggest key. |
| */ |
| void *btree_node_max(btree_node_t *node) |
| { |
| ASSERT(LEAF_NODE(node)); |
| ASSERT(node->keys); |
| return node->value[node->keys - 1]; |
| } |
| |
| /** Initialize B-tree node. |
| * |
| * @param node B-tree node. |
| */ |
| void node_initialize(btree_node_t *node) |
| { |
| int i; |
| |
| node->keys = 0; |
| |
| /* Clean also space for the extra key. */ |
| for (i = 0; i < BTREE_MAX_KEYS + 1; i++) { |
| node->key[i] = 0; |
| node->value[i] = NULL; |
| node->subtree[i] = NULL; |
| } |
| node->subtree[i] = NULL; |
| |
| node->parent = NULL; |
| |
| link_initialize(&node->leaf_link); |
| |
| link_initialize(&node->bfs_link); |
| node->depth = 0; |
| } |
| |
| /** Insert key-value-left-subtree triplet into B-tree non-full node. |
| * |
| * It is actually possible to have more keys than BTREE_MAX_KEYS. |
| * This feature is used during splitting the node when the |
| * number of keys is BTREE_MAX_KEYS + 1. |
| * |
| * @param node B-tree node into wich the new key is to be inserted. |
| * @param key The key to be inserted. |
| * @param value Pointer to value to be inserted. |
| * @param rsubtree Pointer to the right subtree. |
| */ |
| void node_insert_key(btree_node_t *node, __native key, void *value, btree_node_t *rsubtree) |
| { |
| int i; |
| |
| for (i = 0; i < node->keys; i++) { |
| if (key < node->key[i]) { |
| int j; |
| |
| for (j = node->keys; j > i; j--) { |
| node->key[j] = node->key[j - 1]; |
| node->value[j] = node->value[j - 1]; |
| node->subtree[j + 1] = node->subtree[j]; |
| } |
| break; |
| } |
| } |
| |
| node->key[i] = key; |
| node->value[i] = value; |
| node->subtree[i + 1] = rsubtree; |
| |
| node->keys++; |
| } |
| |
| /** Split full B-tree node and insert new key-value-left-subtree triplet. |
| * |
| * This function will split a node and return pointer to a newly created |
| * node containing keys greater than the lesser of medians (or median) |
| * of the old keys and the newly added key. It will also write the |
| * median key to a memory address supplied by the caller. |
| * |
| * If the node being split is an index node, the median will be |
| * removed from the original node. If the node is a leaf node, |
| * the median will be preserved. |
| * |
| * @param node B-tree node wich is going to be split. |
| * @param key The key to be inserted. |
| * @param value Pointer to the value to be inserted. |
| * @param rsubtree Pointer to the right subtree of the key being added. |
| * @param median Address in memory, where the median key will be stored. |
| * |
| * @return Newly created right sibling of node. |
| */ |
| btree_node_t *node_split(btree_node_t *node, __native key, void *value, btree_node_t *rsubtree, __native *median) |
| { |
| btree_node_t *rnode; |
| int i, j; |
| |
| ASSERT(median); |
| ASSERT(node->keys == BTREE_MAX_KEYS); |
| |
| /* |
| * Use the extra space to store the extra node. |
| */ |
| node_insert_key(node, key, value, rsubtree); |
| |
| /* |
| * Compute median of keys. |
| */ |
| *median = MEDIAN_LOW(node); |
| |
| rnode = (btree_node_t *) malloc(sizeof(btree_node_t), 0); |
| node_initialize(rnode); |
| rnode->parent = node->parent; |
| rnode->depth = node->depth; |
| |
| /* |
| * Copy big keys, values and subtree pointers to the new right sibling. |
| */ |
| for (i = MEDIAN_LOW_INDEX(node) + 1, j = 0; i < node->keys; i++, j++) { |
| rnode->key[j] = node->key[i]; |
| rnode->value[j] = node->value[i]; |
| rnode->subtree[j] = node->subtree[i]; |
| |
| /* |
| * Fix parent links in subtrees. |
| */ |
| if (rnode->subtree[j]) |
| rnode->subtree[j]->parent = rnode; |
| |
| } |
| rnode->subtree[j] = node->subtree[i]; |
| if (rnode->subtree[j]) |
| rnode->subtree[j]->parent = rnode; |
| rnode->keys = j; |
| |
| /* |
| * Shrink the old node. |
| * If this is an index node, remove the median. |
| */ |
| node->keys = MEDIAN_LOW_INDEX(node) + 1; |
| if (INDEX_NODE(node)) |
| node->keys--; |
| |
| return rnode; |
| } |
| |
| /** Print B-tree. |
| * |
| * @param t Print out B-tree. |
| */ |
| void btree_print(btree_t *t) |
| { |
| int i, depth = t->root->depth; |
| link_t head; |
| |
| list_initialize(&head); |
| list_append(&t->root->bfs_link, &head); |
| |
| /* |
| * Use BFS search to print out the tree. |
| * Levels are distinguished from one another by node->depth. |
| */ |
| while (!list_empty(&head)) { |
| link_t *hlp; |
| btree_node_t *node; |
| |
| hlp = head.next; |
| ASSERT(hlp != &head); |
| node = list_get_instance(hlp, btree_node_t, bfs_link); |
| list_remove(hlp); |
| |
| ASSERT(node); |
| |
| if (node->depth != depth) { |
| printf("\n"); |
| depth = node->depth; |
| } |
| |
| printf("("); |
| for (i = 0; i < node->keys; i++) { |
| printf("%d,", node->key[i]); |
| if (node->depth && node->subtree[i]) { |
| list_append(&node->subtree[i]->bfs_link, &head); |
| } |
| } |
| if (node->depth && node->subtree[i]) { |
| list_append(&node->subtree[i]->bfs_link, &head); |
| } |
| printf(")"); |
| } |
| printf("\n"); |
| } |