/branches/network/kernel/generic/src/adt/avl.c |
---|
0,0 → 1,730 |
/* |
* Copyright (c) 2007 Vojtech Mencl |
* 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. |
*/ |
/** @addtogroup genericadt |
* @{ |
*/ |
/** |
* @file |
* @brief AVL tree implementation. |
* |
* This file implements AVL tree type and operations. |
* |
* Implemented AVL tree has the following properties: |
* @li It is a binary search tree with non-unique keys. |
* @li Difference of heights of the left and the right subtree of every node is |
* one at maximum. |
* |
* Every node has a pointer to its parent which allows insertion of multiple |
* identical keys into the tree. |
* |
* Be careful when using this tree because of the base atribute which is added |
* to every inserted node key. There is no rule in which order nodes with the |
* same key are visited. |
*/ |
#include <adt/avl.h> |
#include <debug.h> |
#define LEFT 0 |
#define RIGHT 1 |
/** Search for the first occurence of the given key in an AVL tree. |
* |
* @param t AVL tree. |
* @param key Key to be searched. |
* |
* @return Pointer to a node or NULL if there is no such key. |
*/ |
avltree_node_t *avltree_search(avltree_t *t, avltree_key_t key) |
{ |
avltree_node_t *p; |
/* |
* Iteratively descend to the leaf that can contain the searched key. |
*/ |
p = t->root; |
while (p != NULL) { |
if (p->key > key) |
p = p->lft; |
else if (p->key < key) |
p = p->rgt; |
else |
return p; |
} |
return NULL; |
} |
/** Find the node with the smallest key in an AVL tree. |
* |
* @param t AVL tree. |
* |
* @return Pointer to a node or NULL if there is no node in the tree. |
*/ |
avltree_node_t *avltree_find_min(avltree_t *t) |
{ |
avltree_node_t *p = t->root; |
/* |
* Check whether the tree is empty. |
*/ |
if (!p) |
return NULL; |
/* |
* Iteratively descend to the leftmost leaf in the tree. |
*/ |
while (p->lft != NULL) |
p = p->lft; |
return p; |
} |
#define REBALANCE_INSERT_XX(DIR1, DIR2) \ |
top->DIR1 = par->DIR2; \ |
if (top->DIR1 != NULL) \ |
top->DIR1->par = top; \ |
par->par = top->par; \ |
top->par = par; \ |
par->DIR2 = top; \ |
par->balance = 0; \ |
top->balance = 0; \ |
*dpc = par; |
#define REBALANCE_INSERT_LL() REBALANCE_INSERT_XX(lft, rgt) |
#define REBALANCE_INSERT_RR() REBALANCE_INSERT_XX(rgt, lft) |
#define REBALANCE_INSERT_XY(DIR1, DIR2, SGN) \ |
gpa = par->DIR2; \ |
par->DIR2 = gpa->DIR1; \ |
if (gpa->DIR1 != NULL) \ |
gpa->DIR1->par = par; \ |
gpa->DIR1 = par; \ |
par->par = gpa; \ |
top->DIR1 = gpa->DIR2; \ |
if (gpa->DIR2 != NULL) \ |
gpa->DIR2->par = top; \ |
gpa->DIR2 = top; \ |
gpa->par = top->par; \ |
top->par = gpa; \ |
\ |
if (gpa->balance == -1 * SGN) { \ |
par->balance = 0; \ |
top->balance = 1 * SGN; \ |
} else if (gpa->balance == 0) { \ |
par->balance = 0; \ |
top->balance = 0; \ |
} else { \ |
par->balance = -1 * SGN; \ |
top->balance = 0; \ |
} \ |
gpa->balance = 0; \ |
*dpc = gpa; |
#define REBALANCE_INSERT_LR() REBALANCE_INSERT_XY(lft, rgt, 1) |
#define REBALANCE_INSERT_RL() REBALANCE_INSERT_XY(rgt, lft, -1) |
/** Insert new node into AVL tree. |
* |
* @param t AVL tree. |
* @param newnode New node to be inserted. |
*/ |
void avltree_insert(avltree_t *t, avltree_node_t *newnode) |
{ |
avltree_node_t *par; |
avltree_node_t *gpa; |
avltree_node_t *top; |
avltree_node_t **dpc; |
avltree_key_t key; |
ASSERT(t); |
ASSERT(newnode); |
/* |
* Creating absolute key. |
*/ |
key = newnode->key + t->base; |
/* |
* Iteratively descend to the leaf that can contain the new node. |
* Last node with non-zero balance in the way to leaf is stored as top - |
* it is a place of possible inbalance. |
*/ |
dpc = &t->root; |
gpa = NULL; |
top = t->root; |
while ((par = (*dpc)) != NULL) { |
if (par->balance != 0) { |
top = par; |
} |
gpa = par; |
dpc = par->key > key ? &par->lft: &par->rgt; |
} |
/* |
* Initialize the new node. |
*/ |
newnode->key = key; |
newnode->lft = NULL; |
newnode->rgt = NULL; |
newnode->par = gpa; |
newnode->balance = 0; |
/* |
* Insert first node into the empty tree. |
*/ |
if (t->root == NULL) { |
*dpc = newnode; |
return; |
} |
/* |
* Insert the new node into the previously found leaf position. |
*/ |
*dpc = newnode; |
/* |
* If the tree contains one node - end. |
*/ |
if (top == NULL) |
return; |
/* |
* Store pointer of top's father which points to the node with |
* potentially broken balance (top). |
*/ |
if (top->par == NULL) { |
dpc = &t->root; |
} else { |
if (top->par->lft == top) |
dpc = &top->par->lft; |
else |
dpc = &top->par->rgt; |
} |
/* |
* Repair all balances on the way from top node to the newly inserted |
* node. |
*/ |
par = top; |
while (par != newnode) { |
if (par->key > key) { |
par->balance--; |
par = par->lft; |
} else { |
par->balance++; |
par = par->rgt; |
} |
} |
/* |
* To balance the tree, we must check and balance top node. |
*/ |
if (top->balance == -2) { |
par = top->lft; |
if (par->balance == -1) { |
/* |
* LL rotation. |
*/ |
REBALANCE_INSERT_LL(); |
} else { |
/* |
* LR rotation. |
*/ |
ASSERT(par->balance == 1); |
REBALANCE_INSERT_LR(); |
} |
} else if (top->balance == 2) { |
par = top->rgt; |
if (par->balance == 1) { |
/* |
* RR rotation. |
*/ |
REBALANCE_INSERT_RR(); |
} else { |
/* |
* RL rotation. |
*/ |
ASSERT(par->balance == -1); |
REBALANCE_INSERT_RL(); |
} |
} else { |
/* |
* Balance is not broken, insertion is finised. |
*/ |
return; |
} |
} |
/** Repair the tree after reparenting node u. |
* |
* If node u has no parent, mark it as the root of the whole tree. Otherwise |
* node v represents stale address of one of the children of node u's parent. |
* Replace v with w as node u parent's child (for most uses, u and w will be the |
* same). |
* |
* @param t AVL tree. |
* @param u Node whose new parent has a stale child pointer. |
* @param v Stale child of node u's new parent. |
* @param w New child of node u's new parent. |
* @param dir If not NULL, address of the variable where to store information |
* about whether w replaced v in the left or the right subtree of |
* u's new parent. |
* @param ro Read only operation; do not modify any tree pointers. This is |
* useful for tracking direction via the dir pointer. |
* |
* @return Zero if w became the new root of the tree, otherwise return |
* non-zero. |
*/ |
static int |
repair(avltree_t *t, avltree_node_t *u, avltree_node_t *v, avltree_node_t *w, |
int *dir, int ro) |
{ |
if (u->par == NULL) { |
if (!ro) |
t->root = w; |
return 0; |
} else { |
if (u->par->lft == v) { |
if (!ro) |
u->par->lft = w; |
if (dir) |
*dir = LEFT; |
} else { |
ASSERT(u->par->rgt == v); |
if (!ro) |
u->par->rgt = w; |
if (dir) |
*dir = RIGHT; |
} |
} |
return 1; |
} |
#define REBALANCE_DELETE(DIR1, DIR2, SIGN) \ |
if (cur->balance == -1 * SIGN) { \ |
par->balance = 0; \ |
gpa->balance = 1 * SIGN; \ |
if (gpa->DIR1) \ |
gpa->DIR1->par = gpa; \ |
par->DIR2->par = par; \ |
} else if (cur->balance == 0) { \ |
par->balance = 0; \ |
gpa->balance = 0; \ |
if (gpa->DIR1) \ |
gpa->DIR1->par = gpa; \ |
if (par->DIR2) \ |
par->DIR2->par = par; \ |
} else { \ |
par->balance = -1 * SIGN; \ |
gpa->balance = 0; \ |
if (par->DIR2) \ |
par->DIR2->par = par; \ |
gpa->DIR1->par = gpa; \ |
} \ |
cur->balance = 0; |
#define REBALANCE_DELETE_LR() REBALANCE_DELETE(lft, rgt, 1) |
#define REBALANCE_DELETE_RL() REBALANCE_DELETE(rgt, lft, -1) |
/** Delete a node from the AVL tree. |
* |
* Because multiple identical keys are allowed, the parent pointers are |
* essential during deletion. |
* |
* @param t AVL tree structure. |
* @param node Address of the node which will be deleted. |
*/ |
void avltree_delete(avltree_t *t, avltree_node_t *node) |
{ |
avltree_node_t *cur; |
avltree_node_t *par; |
avltree_node_t *gpa; |
int dir; |
ASSERT(t); |
ASSERT(node); |
if (node->lft == NULL) { |
if (node->rgt) { |
/* |
* Replace the node with its only right son. |
* |
* Balance of the right son will be repaired in the |
* balancing cycle. |
*/ |
cur = node->rgt; |
cur->par = node->par; |
gpa = cur; |
dir = RIGHT; |
cur->balance = node->balance; |
} else { |
if (node->par == NULL) { |
/* |
* The tree has only one node - it will become |
* an empty tree and the balancing can end. |
*/ |
t->root = NULL; |
return; |
} |
/* |
* The node has no child, it will be deleted with no |
* substitution. |
*/ |
gpa = node->par; |
cur = NULL; |
dir = (gpa->lft == node) ? LEFT: RIGHT; |
} |
} else { |
/* |
* The node has the left son. Find a node with the smallest key |
* in the left subtree and replace the deleted node with that |
* node. |
*/ |
for (cur = node->lft; cur->rgt != NULL; cur = cur->rgt) |
; |
if (cur != node->lft) { |
/* |
* The rightmost node of the deleted node's left subtree |
* was found. Replace the deleted node with this node. |
* Cutting off of the found node has two cases that |
* depend on its left son. |
*/ |
if (cur->lft) { |
/* |
* The found node has a left son. |
*/ |
gpa = cur->lft; |
gpa->par = cur->par; |
dir = LEFT; |
gpa->balance = cur->balance; |
} else { |
dir = RIGHT; |
gpa = cur->par; |
} |
cur->par->rgt = cur->lft; |
cur->lft = node->lft; |
cur->lft->par = cur; |
} else { |
/* |
* The left son of the node hasn't got a right son. The |
* left son will take the deleted node's place. |
*/ |
dir = LEFT; |
gpa = cur; |
} |
if (node->rgt) |
node->rgt->par = cur; |
cur->rgt = node->rgt; |
cur->balance = node->balance; |
cur->par = node->par; |
} |
/* |
* Repair the parent node's pointer which pointed previously to the |
* deleted node. |
*/ |
(void) repair(t, node, node, cur, NULL, false); |
/* |
* Repair cycle which repairs balances of nodes on the way from from the |
* cut-off node up to the root. |
*/ |
for (;;) { |
if (dir == LEFT) { |
/* |
* Deletion was made in the left subtree. |
*/ |
gpa->balance++; |
if (gpa->balance == 1) { |
/* |
* Stop balancing, the tree is balanced. |
*/ |
break; |
} else if (gpa->balance == 2) { |
/* |
* Bad balance, heights of left and right |
* subtrees differ more than by one. |
*/ |
par = gpa->rgt; |
if (par->balance == -1) { |
/* |
* RL rotation. |
*/ |
cur = par->lft; |
par->lft = cur->rgt; |
cur->rgt = par; |
gpa->rgt = cur->lft; |
cur->lft = gpa; |
/* |
* Repair balances and paternity of |
* children, depending on the balance |
* factor of the grand child (cur). |
*/ |
REBALANCE_DELETE_RL(); |
/* |
* Repair paternity. |
*/ |
cur->par = gpa->par; |
gpa->par = cur; |
par->par = cur; |
if (!repair(t, cur, gpa, cur, &dir, |
false)) |
break; |
gpa = cur->par; |
} else { |
/* |
* RR rotation. |
*/ |
gpa->rgt = par->lft; |
if (par->lft) |
par->lft->par = gpa; |
par->lft = gpa; |
/* |
* Repair paternity. |
*/ |
par->par = gpa->par; |
gpa->par = par; |
if (par->balance == 0) { |
/* |
* The right child of the |
* balanced node is balanced, |
* after RR rotation is done, |
* the whole tree will be |
* balanced. |
*/ |
par->balance = -1; |
gpa->balance = 1; |
(void) repair(t, par, gpa, par, |
NULL, false); |
break; |
} else { |
par->balance = 0; |
gpa->balance = 0; |
if (!repair(t, par, gpa, par, |
&dir, false)) |
break; |
} |
gpa = par->par; |
} |
} else { |
/* |
* Repair the pointer which pointed to the |
* balanced node. If it was root then balancing |
* is finished else continue with the next |
* iteration (parent node). |
*/ |
if (!repair(t, gpa, gpa, NULL, &dir, true)) |
break; |
gpa = gpa->par; |
} |
} else { |
/* |
* Deletion was made in the right subtree. |
*/ |
gpa->balance--; |
if (gpa->balance == -1) { |
/* |
* Stop balancing, the tree is balanced. |
*/ |
break; |
} else if (gpa->balance == -2) { |
/* |
* Bad balance, heights of left and right |
* subtrees differ more than by one. |
*/ |
par = gpa->lft; |
if (par->balance == 1) { |
/* |
* LR rotation. |
*/ |
cur = par->rgt; |
par->rgt = cur->lft; |
cur->lft = par; |
gpa->lft = cur->rgt; |
cur->rgt = gpa; |
/* |
* Repair balances and paternity of |
* children, depending on the balance |
* factor of the grand child (cur). |
*/ |
REBALANCE_DELETE_LR(); |
/* |
* Repair paternity. |
*/ |
cur->par = gpa->par; |
gpa->par = cur; |
par->par = cur; |
if (!repair(t, cur, gpa, cur, &dir, |
false)) |
break; |
gpa = cur->par; |
} else { |
/* |
* LL rotation. |
*/ |
gpa->lft = par->rgt; |
if (par->rgt) |
par->rgt->par = gpa; |
par->rgt = gpa; |
/* |
* Repair paternity. |
*/ |
par->par = gpa->par; |
gpa->par = par; |
if (par->balance == 0) { |
/* |
* The left child of the |
* balanced node is balanced, |
* after LL rotation is done, |
* the whole tree will be |
* balanced. |
*/ |
par->balance = 1; |
gpa->balance = -1; |
(void) repair(t, par, gpa, par, |
NULL, false); |
break; |
} else { |
par->balance = 0; |
gpa->balance = 0; |
if (!repair(t, par, gpa, par, |
&dir, false)) |
break; |
} |
gpa = par->par; |
} |
} else { |
/* |
* Repair the pointer which pointed to the |
* balanced node. If it was root then balancing |
* is finished. Otherwise continue with the next |
* iteration (parent node). |
*/ |
if (!repair(t, gpa, gpa, NULL, &dir, true)) |
break; |
gpa = gpa->par; |
} |
} |
} |
} |
/** Delete a node with the smallest key from the AVL tree. |
* |
* @param t AVL tree structure. |
*/ |
bool avltree_delete_min(avltree_t *t) |
{ |
avltree_node_t *node; |
/* |
* Start searching for the smallest key in the tree starting in the root |
* node and continue in cycle to the leftmost node in the tree (which |
* must have the smallest key). |
*/ |
node = t->root; |
if (!node) |
return false; |
while (node->lft != NULL) |
node = node->lft; |
avltree_delete(t, node); |
return true; |
} |
/** Walk a subtree of an AVL tree in-order and apply a supplied walker on each |
* visited node. |
* |
* @param node Node representing the root of an AVL subtree to be |
* walked. |
* @param walker Walker function that will be appliad on each visited |
* node. |
* @param arg Argument for the walker. |
* |
* @return Zero if the walk should stop or non-zero otherwise. |
*/ |
static bool _avltree_walk(avltree_node_t *node, avltree_walker_t walker, |
void *arg) |
{ |
if (node->lft) { |
if (!_avltree_walk(node->lft, walker, arg)) |
return false; |
} |
if (!walker(node, arg)) |
return false; |
if (node->rgt) { |
if (!_avltree_walk(node->rgt, walker, arg)) |
return false; |
} |
return true; |
} |
/** Walk the AVL tree in-order and apply the walker function on each visited |
* node. |
* |
* @param t AVL tree to be walked. |
* @param walker Walker function that will be called on each visited |
* node. |
* @param arg Argument for the walker. |
*/ |
void avltree_walk(avltree_t *t, avltree_walker_t walker, void *arg) |
{ |
_avltree_walk(t->root, walker, arg); |
} |
/** @} |
*/ |
/branches/network/kernel/generic/src/adt/btree.c |
---|
0,0 → 1,1002 |
/* |
* 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. |
*/ |
/** @addtogroup genericadt |
* @{ |
*/ |
/** |
* @file |
* @brief B+tree implementation. |
* |
* This file implements B+tree type and operations. |
* |
* The B+tree has the following properties: |
* @li it is a ballanced 3-4-5 tree (i.e. BTREE_M = 5) |
* @li values (i.e. pointers to values) are stored only in leaves |
* @li leaves are linked in a list |
* |
* Be carefull when using these trees. They need to allocate |
* and deallocate memory for their index nodes and as such |
* can sleep. |
*/ |
#include <adt/btree.h> |
#include <adt/list.h> |
#include <mm/slab.h> |
#include <debug.h> |
#include <panic.h> |
#include <print.h> |
static void btree_destroy_subtree(btree_node_t *root); |
static void _btree_insert(btree_t *t, btree_key_t key, void *value, btree_node_t *rsubtree, btree_node_t *node); |
static void _btree_remove(btree_t *t, btree_key_t key, btree_node_t *node); |
static void node_initialize(btree_node_t *node); |
static void node_insert_key_and_lsubtree(btree_node_t *node, btree_key_t key, void *value, btree_node_t *lsubtree); |
static void node_insert_key_and_rsubtree(btree_node_t *node, btree_key_t key, void *value, btree_node_t *rsubtree); |
static void node_remove_key_and_lsubtree(btree_node_t *node, btree_key_t key); |
static void node_remove_key_and_rsubtree(btree_node_t *node, btree_key_t key); |
static btree_node_t *node_split(btree_node_t *node, btree_key_t key, void *value, btree_node_t *rsubtree, btree_key_t *median); |
static btree_node_t *node_combine(btree_node_t *node); |
static index_t find_key_by_subtree(btree_node_t *node, btree_node_t *subtree, bool right); |
static void rotate_from_right(btree_node_t *lnode, btree_node_t *rnode, index_t idx); |
static void rotate_from_left(btree_node_t *lnode, btree_node_t *rnode, index_t idx); |
static bool try_insert_by_rotation_to_left(btree_node_t *node, btree_key_t key, void *value, btree_node_t *rsubtree); |
static bool try_insert_by_rotation_to_right(btree_node_t *node, btree_key_t key, void *value, btree_node_t *rsubtree); |
static bool try_rotation_from_left(btree_node_t *rnode); |
static bool try_rotation_from_right(btree_node_t *lnode); |
#define ROOT_NODE(n) (!(n)->parent) |
#define INDEX_NODE(n) ((n)->subtree[0] != NULL) |
#define LEAF_NODE(n) ((n)->subtree[0] == NULL) |
#define FILL_FACTOR ((BTREE_M-1)/2) |
#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))]); |
static slab_cache_t *btree_node_slab; |
/** Initialize B-trees. */ |
void btree_init(void) |
{ |
btree_node_slab = slab_cache_create("btree_node_slab", sizeof(btree_node_t), 0, NULL, NULL, SLAB_CACHE_MAGDEFERRED); |
} |
/** Create empty B-tree. |
* |
* @param t B-tree. |
*/ |
void btree_create(btree_t *t) |
{ |
list_initialize(&t->leaf_head); |
t->root = (btree_node_t *) slab_alloc(btree_node_slab, 0); |
node_initialize(t->root); |
list_append(&t->root->leaf_link, &t->leaf_head); |
} |
/** Destroy empty B-tree. */ |
void btree_destroy(btree_t *t) |
{ |
btree_destroy_subtree(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, btree_key_t 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); |
} |
/** Destroy subtree rooted in a node. |
* |
* @param root Root of the subtree. |
*/ |
void btree_destroy_subtree(btree_node_t *root) |
{ |
count_t i; |
if (root->keys) { |
for (i = 0; i < root->keys + 1; i++) { |
if (root->subtree[i]) |
btree_destroy_subtree(root->subtree[i]); |
} |
} |
slab_free(btree_node_slab, root); |
} |
/** 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, btree_key_t 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_and_rsubtree(node, key, value, rsubtree); |
} else if (try_insert_by_rotation_to_left(node, key, value, rsubtree)) { |
/* |
* The key-value-rsubtree triplet has been inserted because |
* some keys could have been moved to the left sibling. |
*/ |
} else if (try_insert_by_rotation_to_right(node, key, value, rsubtree)) { |
/* |
* The key-value-rsubtree triplet has been inserted because |
* some keys could have been moved to the right sibling. |
*/ |
} else { |
btree_node_t *rnode; |
btree_key_t median; |
/* |
* Node is full and both siblings (if both exist) are full too. |
* Split the node and insert the smallest key from the node containing |
* bigger keys (i.e. the new node) into its parent. |
*/ |
rnode = node_split(node, key, value, rsubtree, &median); |
if (LEAF_NODE(node)) { |
list_prepend(&rnode->leaf_link, &node->leaf_link); |
} |
if (ROOT_NODE(node)) { |
/* |
* We split the root node. Create new root. |
*/ |
t->root = (btree_node_t *) slab_alloc(btree_node_slab, 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); |
} |
} |
/** Remove B-tree node. |
* |
* @param t B-tree. |
* @param key Key to be removed from the B-tree along with its associated value. |
* @param leaf_node If not NULL, pointer to the leaf node where the key is found. |
*/ |
void btree_remove(btree_t *t, btree_key_t key, btree_node_t *leaf_node) |
{ |
btree_node_t *lnode; |
lnode = leaf_node; |
if (!lnode) { |
if (!btree_search(t, key, &lnode)) { |
panic("B-tree %p does not contain key %d\n", t, key); |
} |
} |
_btree_remove(t, key, lnode); |
} |
/** Recursively remove B-tree node. |
* |
* @param t B-tree. |
* @param key Key to be removed from the B-tree along with its associated value. |
* @param node Node where the key being removed resides. |
*/ |
void _btree_remove(btree_t *t, btree_key_t key, btree_node_t *node) |
{ |
if (ROOT_NODE(node)) { |
if (node->keys == 1 && node->subtree[0]) { |
/* |
* Free the current root and set new root. |
*/ |
t->root = node->subtree[0]; |
t->root->parent = NULL; |
slab_free(btree_node_slab, node); |
} else { |
/* |
* Remove the key from the root node. |
* Note that the right subtree is removed because when |
* combining two nodes, the left-side sibling is preserved |
* and the right-side sibling is freed. |
*/ |
node_remove_key_and_rsubtree(node, key); |
} |
return; |
} |
if (node->keys <= FILL_FACTOR) { |
/* |
* If the node is below the fill factor, |
* try to borrow keys from left or right sibling. |
*/ |
if (!try_rotation_from_left(node)) |
try_rotation_from_right(node); |
} |
if (node->keys > FILL_FACTOR) { |
count_t i; |
/* |
* The key can be immediatelly removed. |
* |
* Note that the right subtree is removed because when |
* combining two nodes, the left-side sibling is preserved |
* and the right-side sibling is freed. |
*/ |
node_remove_key_and_rsubtree(node, key); |
for (i = 0; i < node->parent->keys; i++) { |
if (node->parent->key[i] == key) |
node->parent->key[i] = node->key[0]; |
} |
} else { |
index_t idx; |
btree_node_t *rnode, *parent; |
/* |
* The node is below the fill factor as well as its left and right sibling. |
* Resort to combining the node with one of its siblings. |
* The node which is on the left is preserved and the node on the right is |
* freed. |
*/ |
parent = node->parent; |
node_remove_key_and_rsubtree(node, key); |
rnode = node_combine(node); |
if (LEAF_NODE(rnode)) |
list_remove(&rnode->leaf_link); |
idx = find_key_by_subtree(parent, rnode, true); |
ASSERT((int) idx != -1); |
slab_free(btree_node_slab, rnode); |
_btree_remove(t, parent->key[idx], parent); |
} |
} |
/** 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, btree_key_t key, btree_node_t **leaf_node) |
{ |
btree_node_t *cur, *next; |
/* |
* Iteratively descend to the leaf that can contain the searched key. |
*/ |
for (cur = t->root; cur; cur = next) { |
/* Last iteration will set this with proper leaf node address. */ |
*leaf_node = cur; |
/* |
* The key can be in the leftmost subtree. |
* Test it separately. |
*/ |
if (key < cur->key[0]) { |
next = cur->subtree[0]; |
continue; |
} else { |
void *val; |
count_t i; |
/* |
* Now if the key is smaller than cur->key[i] |
* it can only mean that the value is in cur->subtree[i] |
* or it is not in the tree at all. |
*/ |
for (i = 1; i < cur->keys; i++) { |
if (key < cur->key[i]) { |
next = cur->subtree[i]; |
val = cur->value[i - 1]; |
if (LEAF_NODE(cur)) |
return key == cur->key[i - 1] ? val : NULL; |
goto descend; |
} |
} |
/* |
* Last possibility is that the key is in the rightmost subtree. |
*/ |
next = cur->subtree[i]; |
val = cur->value[i - 1]; |
if (LEAF_NODE(cur)) |
return key == cur->key[i - 1] ? val : NULL; |
} |
descend: |
; |
} |
/* |
* The key was not found in the *leaf_node and is smaller than any of its keys. |
*/ |
return NULL; |
} |
/** Return pointer to B-tree leaf node's left neighbour. |
* |
* @param t B-tree. |
* @param node Node whose left neighbour will be returned. |
* |
* @return Left neighbour of the node or NULL if the node does not have the left neighbour. |
*/ |
btree_node_t *btree_leaf_node_left_neighbour(btree_t *t, btree_node_t *node) |
{ |
ASSERT(LEAF_NODE(node)); |
if (node->leaf_link.prev != &t->leaf_head) |
return list_get_instance(node->leaf_link.prev, btree_node_t, leaf_link); |
else |
return NULL; |
} |
/** Return pointer to B-tree leaf node's right neighbour. |
* |
* @param t B-tree. |
* @param node Node whose right neighbour will be returned. |
* |
* @return Right neighbour of the node or NULL if the node does not have the right neighbour. |
*/ |
btree_node_t *btree_leaf_node_right_neighbour(btree_t *t, btree_node_t *node) |
{ |
ASSERT(LEAF_NODE(node)); |
if (node->leaf_link.next != &t->leaf_head) |
return list_get_instance(node->leaf_link.next, btree_node_t, leaf_link); |
else |
return NULL; |
} |
/** 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-lsubtree triplet into B-tree node. |
* |
* It is actually possible to have more keys than BTREE_MAX_KEYS. |
* This feature is used during insert by right rotation. |
* |
* @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 lsubtree Pointer to the left subtree. |
*/ |
void node_insert_key_and_lsubtree(btree_node_t *node, btree_key_t key, void *value, btree_node_t *lsubtree) |
{ |
count_t i; |
for (i = 0; i < node->keys; i++) { |
if (key < node->key[i]) { |
count_t 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]; |
} |
node->subtree[j + 1] = node->subtree[j]; |
break; |
} |
} |
node->key[i] = key; |
node->value[i] = value; |
node->subtree[i] = lsubtree; |
node->keys++; |
} |
/** Insert key-value-rsubtree triplet into B-tree 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. Insert by left rotation |
* also makes use of this feature. |
* |
* @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_and_rsubtree(btree_node_t *node, btree_key_t key, void *value, btree_node_t *rsubtree) |
{ |
count_t i; |
for (i = 0; i < node->keys; i++) { |
if (key < node->key[i]) { |
count_t 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++; |
} |
/** Remove key and its left subtree pointer from B-tree node. |
* |
* Remove the key and eliminate gaps in node->key array. |
* Note that the value pointer and the left subtree pointer |
* is removed from the node as well. |
* |
* @param node B-tree node. |
* @param key Key to be removed. |
*/ |
void node_remove_key_and_lsubtree(btree_node_t *node, btree_key_t key) |
{ |
count_t i, j; |
for (i = 0; i < node->keys; i++) { |
if (key == node->key[i]) { |
for (j = i + 1; j < node->keys; j++) { |
node->key[j - 1] = node->key[j]; |
node->value[j - 1] = node->value[j]; |
node->subtree[j - 1] = node->subtree[j]; |
} |
node->subtree[j - 1] = node->subtree[j]; |
node->keys--; |
return; |
} |
} |
panic("node %p does not contain key %d\n", node, key); |
} |
/** Remove key and its right subtree pointer from B-tree node. |
* |
* Remove the key and eliminate gaps in node->key array. |
* Note that the value pointer and the right subtree pointer |
* is removed from the node as well. |
* |
* @param node B-tree node. |
* @param key Key to be removed. |
*/ |
void node_remove_key_and_rsubtree(btree_node_t *node, btree_key_t key) |
{ |
count_t i, j; |
for (i = 0; i < node->keys; i++) { |
if (key == node->key[i]) { |
for (j = i + 1; j < node->keys; j++) { |
node->key[j - 1] = node->key[j]; |
node->value[j - 1] = node->value[j]; |
node->subtree[j] = node->subtree[j + 1]; |
} |
node->keys--; |
return; |
} |
} |
panic("node %p does not contain key %d\n", node, key); |
} |
/** Split full B-tree node and insert new key-value-right-subtree triplet. |
* |
* This function will split a node and return a pointer to a newly created |
* node containing keys greater than or equal to the greater 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 not be |
* included in the new node. If the node is a leaf node, |
* the median will be copied there. |
* |
* @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, btree_key_t key, void *value, btree_node_t *rsubtree, btree_key_t *median) |
{ |
btree_node_t *rnode; |
count_t i, j; |
ASSERT(median); |
ASSERT(node->keys == BTREE_MAX_KEYS); |
/* |
* Use the extra space to store the extra node. |
*/ |
node_insert_key_and_rsubtree(node, key, value, rsubtree); |
/* |
* Compute median of keys. |
*/ |
*median = MEDIAN_HIGH(node); |
/* |
* Allocate and initialize new right sibling. |
*/ |
rnode = (btree_node_t *) slab_alloc(btree_node_slab, 0); |
node_initialize(rnode); |
rnode->parent = node->parent; |
rnode->depth = node->depth; |
/* |
* Copy big keys, values and subtree pointers to the new right sibling. |
* If this is an index node, do not copy the median. |
*/ |
i = (count_t) INDEX_NODE(node); |
for (i += MEDIAN_HIGH_INDEX(node), 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; /* Set number of keys of the new node. */ |
node->keys /= 2; /* Shrink the old node. */ |
return rnode; |
} |
/** Combine node with any of its siblings. |
* |
* The siblings are required to be below the fill factor. |
* |
* @param node Node to combine with one of its siblings. |
* |
* @return Pointer to the rightmost of the two nodes. |
*/ |
btree_node_t *node_combine(btree_node_t *node) |
{ |
index_t idx; |
btree_node_t *rnode; |
count_t i; |
ASSERT(!ROOT_NODE(node)); |
idx = find_key_by_subtree(node->parent, node, false); |
if (idx == node->parent->keys) { |
/* |
* Rightmost subtree of its parent, combine with the left sibling. |
*/ |
idx--; |
rnode = node; |
node = node->parent->subtree[idx]; |
} else { |
rnode = node->parent->subtree[idx + 1]; |
} |
/* Index nodes need to insert parent node key in between left and right node. */ |
if (INDEX_NODE(node)) |
node->key[node->keys++] = node->parent->key[idx]; |
/* Copy the key-value-subtree triplets from the right node. */ |
for (i = 0; i < rnode->keys; i++) { |
node->key[node->keys + i] = rnode->key[i]; |
node->value[node->keys + i] = rnode->value[i]; |
if (INDEX_NODE(node)) { |
node->subtree[node->keys + i] = rnode->subtree[i]; |
rnode->subtree[i]->parent = node; |
} |
} |
if (INDEX_NODE(node)) { |
node->subtree[node->keys + i] = rnode->subtree[i]; |
rnode->subtree[i]->parent = node; |
} |
node->keys += rnode->keys; |
return rnode; |
} |
/** Find key by its left or right subtree. |
* |
* @param node B-tree node. |
* @param subtree Left or right subtree of a key found in node. |
* @param right If true, subtree is a right subtree. If false, subtree is a left subtree. |
* |
* @return Index of the key associated with the subtree. |
*/ |
index_t find_key_by_subtree(btree_node_t *node, btree_node_t *subtree, bool right) |
{ |
count_t i; |
for (i = 0; i < node->keys + 1; i++) { |
if (subtree == node->subtree[i]) |
return i - (int) (right != false); |
} |
panic("node %p does not contain subtree %p\n", node, subtree); |
} |
/** Rotate one key-value-rsubtree triplet from the left sibling to the right sibling. |
* |
* The biggest key and its value and right subtree is rotated from the left node |
* to the right. If the node is an index node, than the parent node key belonging to |
* the left node takes part in the rotation. |
* |
* @param lnode Left sibling. |
* @param rnode Right sibling. |
* @param idx Index of the parent node key that is taking part in the rotation. |
*/ |
void rotate_from_left(btree_node_t *lnode, btree_node_t *rnode, index_t idx) |
{ |
btree_key_t key; |
key = lnode->key[lnode->keys - 1]; |
if (LEAF_NODE(lnode)) { |
void *value; |
value = lnode->value[lnode->keys - 1]; |
node_remove_key_and_rsubtree(lnode, key); |
node_insert_key_and_lsubtree(rnode, key, value, NULL); |
lnode->parent->key[idx] = key; |
} else { |
btree_node_t *rsubtree; |
rsubtree = lnode->subtree[lnode->keys]; |
node_remove_key_and_rsubtree(lnode, key); |
node_insert_key_and_lsubtree(rnode, lnode->parent->key[idx], NULL, rsubtree); |
lnode->parent->key[idx] = key; |
/* Fix parent link of the reconnected right subtree. */ |
rsubtree->parent = rnode; |
} |
} |
/** Rotate one key-value-lsubtree triplet from the right sibling to the left sibling. |
* |
* The smallest key and its value and left subtree is rotated from the right node |
* to the left. If the node is an index node, than the parent node key belonging to |
* the right node takes part in the rotation. |
* |
* @param lnode Left sibling. |
* @param rnode Right sibling. |
* @param idx Index of the parent node key that is taking part in the rotation. |
*/ |
void rotate_from_right(btree_node_t *lnode, btree_node_t *rnode, index_t idx) |
{ |
btree_key_t key; |
key = rnode->key[0]; |
if (LEAF_NODE(rnode)) { |
void *value; |
value = rnode->value[0]; |
node_remove_key_and_lsubtree(rnode, key); |
node_insert_key_and_rsubtree(lnode, key, value, NULL); |
rnode->parent->key[idx] = rnode->key[0]; |
} else { |
btree_node_t *lsubtree; |
lsubtree = rnode->subtree[0]; |
node_remove_key_and_lsubtree(rnode, key); |
node_insert_key_and_rsubtree(lnode, rnode->parent->key[idx], NULL, lsubtree); |
rnode->parent->key[idx] = key; |
/* Fix parent link of the reconnected left subtree. */ |
lsubtree->parent = lnode; |
} |
} |
/** Insert key-value-rsubtree triplet and rotate the node to the left, if this operation can be done. |
* |
* Left sibling of the node (if it exists) is checked for free space. |
* If there is free space, the key is inserted and the smallest key of |
* the node is moved there. The index node which is the parent of both |
* nodes is fixed. |
* |
* @param node B-tree node. |
* @param inskey Key to be inserted. |
* @param insvalue Value to be inserted. |
* @param rsubtree Right subtree of inskey. |
* |
* @return True if the rotation was performed, false otherwise. |
*/ |
bool try_insert_by_rotation_to_left(btree_node_t *node, btree_key_t inskey, void *insvalue, btree_node_t *rsubtree) |
{ |
index_t idx; |
btree_node_t *lnode; |
/* |
* If this is root node, the rotation can not be done. |
*/ |
if (ROOT_NODE(node)) |
return false; |
idx = find_key_by_subtree(node->parent, node, true); |
if ((int) idx == -1) { |
/* |
* If this node is the leftmost subtree of its parent, |
* the rotation can not be done. |
*/ |
return false; |
} |
lnode = node->parent->subtree[idx]; |
if (lnode->keys < BTREE_MAX_KEYS) { |
/* |
* The rotaion can be done. The left sibling has free space. |
*/ |
node_insert_key_and_rsubtree(node, inskey, insvalue, rsubtree); |
rotate_from_right(lnode, node, idx); |
return true; |
} |
return false; |
} |
/** Insert key-value-rsubtree triplet and rotate the node to the right, if this operation can be done. |
* |
* Right sibling of the node (if it exists) is checked for free space. |
* If there is free space, the key is inserted and the biggest key of |
* the node is moved there. The index node which is the parent of both |
* nodes is fixed. |
* |
* @param node B-tree node. |
* @param inskey Key to be inserted. |
* @param insvalue Value to be inserted. |
* @param rsubtree Right subtree of inskey. |
* |
* @return True if the rotation was performed, false otherwise. |
*/ |
bool try_insert_by_rotation_to_right(btree_node_t *node, btree_key_t inskey, void *insvalue, btree_node_t *rsubtree) |
{ |
index_t idx; |
btree_node_t *rnode; |
/* |
* If this is root node, the rotation can not be done. |
*/ |
if (ROOT_NODE(node)) |
return false; |
idx = find_key_by_subtree(node->parent, node, false); |
if (idx == node->parent->keys) { |
/* |
* If this node is the rightmost subtree of its parent, |
* the rotation can not be done. |
*/ |
return false; |
} |
rnode = node->parent->subtree[idx + 1]; |
if (rnode->keys < BTREE_MAX_KEYS) { |
/* |
* The rotaion can be done. The right sibling has free space. |
*/ |
node_insert_key_and_rsubtree(node, inskey, insvalue, rsubtree); |
rotate_from_left(node, rnode, idx); |
return true; |
} |
return false; |
} |
/** Rotate in a key from the left sibling or from the index node, if this operation can be done. |
* |
* @param rnode Node into which to add key from its left sibling or from the index node. |
* |
* @return True if the rotation was performed, false otherwise. |
*/ |
bool try_rotation_from_left(btree_node_t *rnode) |
{ |
index_t idx; |
btree_node_t *lnode; |
/* |
* If this is root node, the rotation can not be done. |
*/ |
if (ROOT_NODE(rnode)) |
return false; |
idx = find_key_by_subtree(rnode->parent, rnode, true); |
if ((int) idx == -1) { |
/* |
* If this node is the leftmost subtree of its parent, |
* the rotation can not be done. |
*/ |
return false; |
} |
lnode = rnode->parent->subtree[idx]; |
if (lnode->keys > FILL_FACTOR) { |
rotate_from_left(lnode, rnode, idx); |
return true; |
} |
return false; |
} |
/** Rotate in a key from the right sibling or from the index node, if this operation can be done. |
* |
* @param lnode Node into which to add key from its right sibling or from the index node. |
* |
* @return True if the rotation was performed, false otherwise. |
*/ |
bool try_rotation_from_right(btree_node_t *lnode) |
{ |
index_t idx; |
btree_node_t *rnode; |
/* |
* If this is root node, the rotation can not be done. |
*/ |
if (ROOT_NODE(lnode)) |
return false; |
idx = find_key_by_subtree(lnode->parent, lnode, false); |
if (idx == lnode->parent->keys) { |
/* |
* If this node is the rightmost subtree of its parent, |
* the rotation can not be done. |
*/ |
return false; |
} |
rnode = lnode->parent->subtree[idx + 1]; |
if (rnode->keys > FILL_FACTOR) { |
rotate_from_right(lnode, rnode, idx); |
return true; |
} |
return false; |
} |
/** Print B-tree. |
* |
* @param t Print out B-tree. |
*/ |
void btree_print(btree_t *t) |
{ |
count_t i; |
int depth = t->root->depth; |
link_t head, *cur; |
printf("Printing B-tree:\n"); |
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("%llu%s", node->key[i], i < node->keys - 1 ? "," : ""); |
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"); |
printf("Printing list of leaves:\n"); |
for (cur = t->leaf_head.next; cur != &t->leaf_head; cur = cur->next) { |
btree_node_t *node; |
node = list_get_instance(cur, btree_node_t, leaf_link); |
ASSERT(node); |
printf("("); |
for (i = 0; i < node->keys; i++) |
printf("%llu%s", node->key[i], i < node->keys - 1 ? "," : ""); |
printf(")"); |
} |
printf("\n"); |
} |
/** @} |
*/ |
/branches/network/kernel/generic/src/adt/hash_table.c |
---|
0,0 → 1,176 |
/* |
* 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. |
*/ |
/** @addtogroup genericadt |
* @{ |
*/ |
/** |
* @file |
* @brief Implementation of generic chained hash table. |
* |
* This file contains implementation of generic chained hash table. |
*/ |
#include <adt/hash_table.h> |
#include <adt/list.h> |
#include <arch/types.h> |
#include <debug.h> |
#include <mm/slab.h> |
#include <memstr.h> |
/** Create chained hash table. |
* |
* @param h Hash table structure. Will be initialized by this call. |
* @param m Number of slots in the hash table. |
* @param max_keys Maximal number of keys needed to identify an item. |
* @param op Hash table operations structure. |
*/ |
void hash_table_create(hash_table_t *h, count_t m, count_t max_keys, hash_table_operations_t *op) |
{ |
index_t i; |
ASSERT(h); |
ASSERT(op && op->hash && op->compare); |
ASSERT(max_keys > 0); |
h->entry = (link_t *) malloc(m * sizeof(link_t), 0); |
if (!h->entry) { |
panic("cannot allocate memory for hash table\n"); |
} |
memsetb((uintptr_t) h->entry, m * sizeof(link_t), 0); |
for (i = 0; i < m; i++) |
list_initialize(&h->entry[i]); |
h->entries = m; |
h->max_keys = max_keys; |
h->op = op; |
} |
/** Insert item into hash table. |
* |
* @param h Hash table. |
* @param key Array of all keys necessary to compute hash index. |
* @param item Item to be inserted into the hash table. |
*/ |
void hash_table_insert(hash_table_t *h, unative_t key[], link_t *item) |
{ |
index_t chain; |
ASSERT(item); |
ASSERT(h && h->op && h->op->hash && h->op->compare); |
chain = h->op->hash(key); |
ASSERT(chain < h->entries); |
list_append(item, &h->entry[chain]); |
} |
/** Search hash table for an item matching keys. |
* |
* @param h Hash table. |
* @param key Array of all keys needed to compute hash index. |
* |
* @return Matching item on success, NULL if there is no such item. |
*/ |
link_t *hash_table_find(hash_table_t *h, unative_t key[]) |
{ |
link_t *cur; |
index_t chain; |
ASSERT(h && h->op && h->op->hash && h->op->compare); |
chain = h->op->hash(key); |
ASSERT(chain < h->entries); |
for (cur = h->entry[chain].next; cur != &h->entry[chain]; cur = cur->next) { |
if (h->op->compare(key, h->max_keys, cur)) { |
/* |
* The entry is there. |
*/ |
return cur; |
} |
} |
return NULL; |
} |
/** Remove all matching items from hash table. |
* |
* For each removed item, h->remove_callback() is called. |
* |
* @param h Hash table. |
* @param key Array of keys that will be compared against items of the hash table. |
* @param keys Number of keys in the key array. |
*/ |
void hash_table_remove(hash_table_t *h, unative_t key[], count_t keys) |
{ |
index_t chain; |
link_t *cur; |
ASSERT(h && h->op && h->op->hash && h->op->compare && h->op->remove_callback); |
ASSERT(keys <= h->max_keys); |
if (keys == h->max_keys) { |
/* |
* All keys are known, hash_table_find() can be used to find the entry. |
*/ |
cur = hash_table_find(h, key); |
if (cur) { |
list_remove(cur); |
h->op->remove_callback(cur); |
} |
return; |
} |
/* |
* Fewer keys were passed. |
* Any partially matching entries are to be removed. |
*/ |
for (chain = 0; chain < h->entries; chain++) { |
for (cur = h->entry[chain].next; cur != &h->entry[chain]; cur = cur->next) { |
if (h->op->compare(key, keys, cur)) { |
link_t *hlp; |
hlp = cur; |
cur = cur->prev; |
list_remove(hlp); |
h->op->remove_callback(hlp); |
continue; |
} |
} |
} |
} |
/** @} |
*/ |
/branches/network/kernel/generic/src/adt/bitmap.c |
---|
0,0 → 1,188 |
/* |
* 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. |
*/ |
/** @addtogroup genericadt |
* @{ |
*/ |
/** |
* @file |
* @brief Implementation of bitmap ADT. |
* |
* This file implements bitmap ADT and provides functions for |
* setting and clearing ranges of bits. |
*/ |
#include <adt/bitmap.h> |
#include <arch/types.h> |
#include <align.h> |
#include <debug.h> |
#include <macros.h> |
#define ALL_ONES 0xff |
#define ALL_ZEROES 0x00 |
/** Initialize bitmap. |
* |
* No portion of the bitmap is set or cleared by this function. |
* |
* @param bitmap Bitmap structure. |
* @param map Address of the memory used to hold the map. |
* @param bits Number of bits stored in bitmap. |
*/ |
void bitmap_initialize(bitmap_t *bitmap, uint8_t *map, count_t bits) |
{ |
bitmap->map = map; |
bitmap->bits = bits; |
} |
/** Set range of bits. |
* |
* @param bitmap Bitmap structure. |
* @param start Starting bit. |
* @param bits Number of bits to set. |
*/ |
void bitmap_set_range(bitmap_t *bitmap, index_t start, count_t bits) |
{ |
index_t i=0; |
index_t aligned_start; |
count_t lub; /* leading unaligned bits */ |
count_t amb; /* aligned middle bits */ |
count_t tab; /* trailing aligned bits */ |
ASSERT(start + bits <= bitmap->bits); |
aligned_start = ALIGN_UP(start, 8); |
lub = min(aligned_start - start, bits); |
amb = bits > lub ? bits - lub : 0; |
tab = amb % 8; |
if ( start + bits < aligned_start ) { |
/* |
* Set bits in the middle of byte |
*/ |
bitmap->map[start / 8] |= ((1 << lub)-1) << (start&7); |
return; |
} |
if (lub) { |
/* |
* Make sure to set any leading unaligned bits. |
*/ |
bitmap->map[start / 8] |= ~((1 << (8 - lub)) - 1); |
} |
for (i = 0; i < amb / 8; i++) { |
/* |
* The middle bits can be set byte by byte. |
*/ |
bitmap->map[aligned_start / 8 + i] = ALL_ONES; |
} |
if (tab) { |
/* |
* Make sure to set any trailing aligned bits. |
*/ |
bitmap->map[aligned_start / 8 + i] |= (1 << tab) - 1; |
} |
} |
/** Clear range of bits. |
* |
* @param bitmap Bitmap structure. |
* @param start Starting bit. |
* @param bits Number of bits to clear. |
*/ |
void bitmap_clear_range(bitmap_t *bitmap, index_t start, count_t bits) |
{ |
index_t i=0; |
index_t aligned_start; |
count_t lub; /* leading unaligned bits */ |
count_t amb; /* aligned middle bits */ |
count_t tab; /* trailing aligned bits */ |
ASSERT(start + bits <= bitmap->bits); |
aligned_start = ALIGN_UP(start, 8); |
lub = min(aligned_start - start, bits); |
amb = bits > lub ? bits - lub : 0; |
tab = amb % 8; |
if ( start + bits < aligned_start ) |
{ |
/* |
* Set bits in the middle of byte |
*/ |
bitmap->map[start / 8] &= ~(((1 << lub)-1) << (start&7)); |
return; |
} |
if (lub) { |
/* |
* Make sure to clear any leading unaligned bits. |
*/ |
bitmap->map[start / 8] &= (1 << (8 - lub)) - 1; |
} |
for (i = 0; i < amb / 8; i++) { |
/* |
* The middle bits can be cleared byte by byte. |
*/ |
bitmap->map[aligned_start / 8 + i] = ALL_ZEROES; |
} |
if (tab) { |
/* |
* Make sure to clear any trailing aligned bits. |
*/ |
bitmap->map[aligned_start / 8 + i] &= ~((1 << tab) - 1); |
} |
} |
/** Copy portion of one bitmap into another bitmap. |
* |
* @param dst Destination bitmap. |
* @param src Source bitmap. |
* @param bits Number of bits to copy. |
*/ |
void bitmap_copy(bitmap_t *dst, bitmap_t *src, count_t bits) |
{ |
index_t i; |
ASSERT(bits <= dst->bits); |
ASSERT(bits <= src->bits); |
for (i = 0; i < bits / 8; i++) |
dst->map[i] = src->map[i]; |
if (bits % 8) { |
bitmap_clear_range(dst, i * 8, bits % 8); |
dst->map[i] |= src->map[i] & ((1 << (bits % 8)) - 1); |
} |
} |
/** @} |
*/ |
/branches/network/kernel/generic/src/adt/list.c |
---|
0,0 → 1,94 |
/* |
* Copyright (c) 2004 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. |
*/ |
/** @addtogroup genericadt |
* @{ |
*/ |
/** |
* @file |
* @brief Functions completing doubly linked circular list implementaion. |
* |
* This file contains some of the functions implementing doubly linked circular lists. |
* However, this ADT is mostly implemented in @ref list.h. |
*/ |
#include <adt/list.h> |
/** Check for membership |
* |
* Check whether link is contained in the list head. |
* The membership is defined as pointer equivalence. |
* |
* @param link Item to look for. |
* @param head List to look in. |
* |
* @return true if link is contained in head, false otherwise. |
* |
*/ |
bool list_member(const link_t *link, const link_t *head) |
{ |
bool found = false; |
link_t *hlp = head->next; |
while (hlp != head) { |
if (hlp == link) { |
found = true; |
break; |
} |
hlp = hlp->next; |
} |
return found; |
} |
/** Concatenate two lists |
* |
* Concatenate lists head1 and head2, producing a single |
* list head1 containing items from both (in head1, head2 |
* order) and empty list head2. |
* |
* @param head1 First list and concatenated output |
* @param head2 Second list and empty output. |
* |
*/ |
void list_concat(link_t *head1, link_t *head2) |
{ |
if (list_empty(head2)) |
return; |
head2->next->prev = head1->prev; |
head2->prev->next = head1; |
head1->prev->next = head2->next; |
head1->prev = head2->prev; |
list_initialize(head2); |
} |
/** @} |
*/ |