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; +} + +/** @} + */ + Index: kernel/test/avltree/avltree1.c =================================================================== --- kernel/test/avltree/avltree1.c (revision 358ec1390336e7c5e3015493822825c0d34dca53) +++ kernel/test/avltree/avltree1.c (revision 358ec1390336e7c5e3015493822825c0d34dca53) @@ -0,0 +1,286 @@ +/* + * 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. + */ + +#include +#include +#include +#include +#include + +#define NODE_COUNT 100 + +static avltree_t avltree; + +/* + * avl tree nodes in array for faster allocation + */ +static avltree_node_t avltree_nodes[NODE_COUNT]; + +/* + * head of free nodes' list: + */ +static avltree_node_t *first_free_node = NULL; + +static int test_tree_balance(avltree_node_t *node); +static avltree_node_t *test_tree_parents(avltree_node_t *node); +static void print_tree_structure_flat (avltree_node_t *node, int level); +static avltree_node_t *alloc_avltree_node(void); + +static avltree_node_t *test_tree_parents(avltree_node_t *node) +{ + avltree_node_t *tmp; + + if (!node) + return NULL; + + if (node->lft) { + tmp = test_tree_parents(node->lft); + if (tmp != node) { + printf("Bad parent pointer key: %d, address: %p\n", + tmp->key, node->lft); + } + } + if (node->rgt) { + tmp = test_tree_parents(node->rgt); + if (tmp != node) { + printf("Bad parent pointer key: %d, address: %p\n", + tmp->key,node->rgt); + } + } + return node->par; +} + +int test_tree_balance(avltree_node_t *node) +{ + int h1, h2, diff; + + if (!node) + return 0; + h1 = test_tree_balance(node->lft); + h2 = test_tree_balance(node->rgt); + diff = h2 - h1; + if (diff != node->balance || (diff != -1 && diff != 0 && diff != 1)) { + printf("Bad balance\n"); + } + return h1 > h2 ? h1 + 1 : h2 + 1; +} + +/** + * Prints the structure of the node, which is level levels from the top of the + * tree. + */ +static void print_tree_structure_flat(avltree_node_t *node, int level) +{ + /* + * You can set the maximum level as high as you like. + * Most of the time, you'll want to debug code using small trees, + * so that a large level indicates a loop, which is a bug. + */ + if (level > 16) { + printf("[...]"); + return; + } + + if (node == NULL) + return; + + printf("%d[%d]", node->key, node->balance); + if (node->lft != NULL || node->rgt != NULL) { + printf("("); + + print_tree_structure_flat(node->lft, level + 1); + if (node->rgt != NULL) { + printf(","); + print_tree_structure_flat(node->rgt, level + 1); + } + + printf(")"); + } +} + +static void alloc_avltree_node_prepare(void) +{ + int i; + + for (i = 0; i < NODE_COUNT - 1; i++) { + avltree_nodes[i].par = &avltree_nodes[i + 1]; + } + + /* + * Node keys which will be used for insertion. Up to NODE_COUNT size of + * array. + */ + + /* First tree node and same key */ + avltree_nodes[0].key = 60; + avltree_nodes[1].key = 60; + avltree_nodes[2].key = 60; + /* LL rotation */ + avltree_nodes[3].key = 50; + avltree_nodes[4].key = 40; + avltree_nodes[5].key = 30; + /* LR rotation */ + avltree_nodes[6].key = 20; + avltree_nodes[7].key = 20; + avltree_nodes[8].key = 25; + avltree_nodes[9].key = 25; + /* LL rotation in lower floor */ + avltree_nodes[10].key = 35; + /* RR rotation */ + avltree_nodes[11].key = 70; + avltree_nodes[12].key = 80; + /* RL rotation */ + avltree_nodes[13].key = 90; + avltree_nodes[14].key = 85; + /* Insert 0 key */ + avltree_nodes[15].key = 0; + avltree_nodes[16].key = 0; + /* Insert reverse */ + avltree_nodes[17].key = 600; + avltree_nodes[18].key = 500; + avltree_nodes[19].key = 400; + avltree_nodes[20].key = 300; + + for (i = 21; i < NODE_COUNT; i++) + avltree_nodes[i].key = i * 3; + + avltree_nodes[i].par = NULL; + first_free_node = &avltree_nodes[0]; +} + +static avltree_node_t *alloc_avltree_node(void) +{ + avltree_node_t *node; + + node = first_free_node; + first_free_node = first_free_node->par; + + return node; +} + +static void test_tree_insert(avltree_t *tree, count_t node_count, bool quiet) +{ + unsigned int i; + avltree_node_t *newnode; + + avltree_create(tree); + + if (!quiet) + printf("Inserting %d nodes...", node_count); + + for (i = 0; i < node_count; i++) { + newnode = alloc_avltree_node(); + + avltree_insert(tree, newnode); + if (!quiet) { + test_tree_parents(tree->root); + test_tree_balance(tree->root); + } + } + + if (!quiet) + printf("done.\n"); +} + + +static void test_tree_delete(avltree_t *tree, count_t node_count, + int node_position, bool quiet) +{ + avltree_node_t *delnode; + unsigned int i; + + switch (node_position) { + case 0: + if (!quiet) + printf("Deleting root nodes..."); + while (tree->root != NULL) { + delnode = tree->root; + avltree_delete(tree, delnode); + if (!quiet) { + test_tree_parents(tree->root); + test_tree_balance(tree->root); + } + } + break; + case 1: + if (!quiet) + printf("Deleting nodes according to creation time..."); + for (i = 0; i < node_count; i++) { + avltree_delete(tree, &avltree_nodes[i]); + if (!quiet) { + test_tree_parents(tree->root); + test_tree_balance(tree->root); + } + } + break; + } + + if (!quiet) + printf("done.\n"); +} + +static void test_tree_delmin(avltree_t *tree, count_t node_count, bool quiet) +{ + int i = 0; + + if (!quiet) + printf("Deleting minimum nodes..."); + + while (tree->root != NULL) { + i++; + avltree_delete_min(tree); + if (!quiet) { + test_tree_parents(tree->root); + test_tree_balance(tree->root); + } + } + + if (!quiet && (i != node_count)) + printf("Bad node count. Some nodes have been lost!\n"); + + if (!quiet) + printf("done.\n"); +} + +char *test_avltree1(bool quiet) +{ + alloc_avltree_node_prepare(); + test_tree_insert(&avltree, NODE_COUNT, quiet); + test_tree_delete(&avltree, NODE_COUNT, 0, quiet); + + alloc_avltree_node_prepare(); + test_tree_insert(&avltree, NODE_COUNT, quiet); + test_tree_delete(&avltree, NODE_COUNT, 1, quiet); + + alloc_avltree_node_prepare(); + test_tree_insert(&avltree, NODE_COUNT, quiet); + test_tree_delmin(&avltree, NODE_COUNT, quiet); + + return NULL; +} + Index: kernel/test/avltree/avltree1.def =================================================================== --- kernel/test/avltree/avltree1.def (revision 358ec1390336e7c5e3015493822825c0d34dca53) +++ kernel/test/avltree/avltree1.def (revision 358ec1390336e7c5e3015493822825c0d34dca53) @@ -0,0 +1,6 @@ +{ + "avltree1", + "Test Avl tree operations", + &test_avltree1, + true +},