Index: kernel/generic/include/adt/avl.h =================================================================== --- kernel/generic/include/adt/avl.h (revision 358ec1390336e7c5e3015493822825c0d34dca53) +++ kernel/generic/include/adt/avl.h (revision 358ec1390336e7c5e3015493822825c0d34dca53) @@ -0,0 +1,139 @@ +/* + * 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 + */ + + +#ifndef KERN_AVLTREE_H_ +#define KERN_AVLTREE_H_ + +#include + +/** + * Macro for getting a pointer to the structure which contains the avltree + * structure. + * + * @param link Pointer to the avltree structure. + * @param type Name of the outer structure. + * @param member Name of avltree attribute in the outer structure. + */ +#define avltree_get_instance(link, type, member) \ + ((type *)(((uint8_t *)(link)) - ((uint8_t *) &(((type *) NULL)->member)))) + + +typedef struct avltree_node avltree_node_t; +typedef struct avltree avltree_t; + + +/** AVL tree node structure. */ +struct avltree_node +{ + /** + * Pointer to the left descendant of this node. + * + * All keys of nodes in the left subtree are less than the key of this + * node. + */ + struct avltree_node *lft; + + /** + * Pointer to the right descendant of this node. + * + * All keys of nodes in the right subtree are greater than the key of + * this node. + */ + struct avltree_node *rgt; + + /** Pointer to the parent node. Root node has NULL parent. */ + struct avltree_node *par; + + /** Node's key. */ + uint64_t key; + + /** + * Difference between the heights of the left and the right subtree of + * this node. + */ + int8_t balance; +}; + +/** AVL tree structure. */ +struct avltree +{ + /** AVL root node pointer */ + struct avltree_node *root; + + /** + * Base of the tree is a value that is smaller or equal than every value + * in the tree (valid for positive keys otherwise ignore this atribute). + * + * The base is added to the current key when a new node is inserted into + * the tree. The base is changed to the key of the node which is deleted + * with avltree_delete_min(). + */ + uint64_t base; +}; + + +/** Create empty AVL tree. + * + * @param t AVL tree. + */ +static inline void avltree_create (avltree_t *t) +{ + t->root = NULL; + t->base = 0; +} + +/** Initialize node. + * + * @param node Node which is initialized. + */ +static inline void avltree_node_initialize(avltree_node_t *node) +{ + node->key = 0; + node->lft = NULL; + node->rgt = NULL; + node->par = NULL; + node->balance = 0; +} + +extern avltree_node_t *avltree_find_min(avltree_t *t); +extern avltree_node_t *avltree_search(avltree_t *t, uint64_t key); +extern void avltree_insert(avltree_t *t, avltree_node_t *newnode); +extern void avltree_delete(avltree_t *t, avltree_node_t *node); +extern bool avltree_delete_min(avltree_t *t); + +#endif + +/** @} + */ Index: kernel/generic/src/adt/avl.c =================================================================== --- kernel/generic/src/adt/avl.c (revision 358ec1390336e7c5e3015493822825c0d34dca53) +++ kernel/generic/src/adt/avl.c (revision 358ec1390336e7c5e3015493822825c0d34dca53) @@ -0,0 +1,712 @@ +/* + * 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 +#include + + +#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, uint64_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; +} + +/** 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; + uint64_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 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 new node into previously found leaf place. + */ + *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. + */ + top->lft = par->rgt; + if (top->lft != NULL) + top->lft->par = top; + par->par = top->par; + top->par = par; + par->rgt = top; + par->balance = 0; + top->balance = 0; + *dpc = par; + } else { + /* + * LR rotation. + */ + ASSERT(par->balance == 1); + + gpa = par->rgt; + par->rgt = gpa->lft; + if (gpa->lft != NULL) + gpa->lft->par = par; + gpa->lft = par; + par->par = gpa; + top->lft = gpa->rgt; + if (gpa->rgt != NULL) + gpa->rgt->par = top; + gpa->rgt = top; + gpa->par = top->par; + top->par = gpa; + + if (gpa->balance == -1) { + par->balance = 0; + top->balance = 1; + } else if (gpa->balance == 0) { + par->balance = 0; + top->balance = 0; + } else { + par->balance = -1; + top->balance = 0; + } + gpa->balance = 0; + *dpc = gpa; + } + } else if (top->balance == 2) { + par = top->rgt; + if (par->balance == 1) { + /* + * RR rotation. + */ + top->rgt = par->lft; + if (top->rgt != NULL) + top->rgt->par = top; + par->par = top->par; + top->par = par; + par->lft = top; + par->balance = 0; + top->balance = 0; + *dpc = par; + } else { + /* + * RL rotation. + */ + ASSERT(par->balance == -1); + + gpa = par->lft; + par->lft = gpa->rgt; + if (gpa->rgt != NULL) + gpa->rgt->par = par; + gpa->rgt = par; + par->par = gpa; + top->rgt = gpa->lft; + if (gpa->lft != NULL) + gpa->lft->par = top; + gpa->lft = top; + gpa->par = top->par; + top->par = gpa; + + if (gpa->balance == 1) { + par->balance = 0; + top->balance = -1; + } else if (gpa->balance == 0) { + par->balance = 0; + top->balance = 0; + } else { + par->balance = 1; + top->balance = 0; + } + gpa->balance = 0; + *dpc = gpa; + } + } 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(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_LR() REBALANCE(lft, rgt, 1) +#define REBALANCE_RL() REBALANCE(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_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_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; +} + +/** @} + */ +