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"); |
} |