Subversion Repositories HelenOS

Rev

Rev 2787 | Blame | Compare with Previous | Last modification | View Log | Download | RSS feed

  1. /*
  2.  * Copyright (C) 2007 Vojtech Mencl
  3.  * All rights reserved.
  4.  *
  5.  * Redistribution and use in source and binary forms, with or without
  6.  * modification, are permitted provided that the following conditions
  7.  * are met:
  8.  *
  9.  * - Redistributions of source code must retain the above copyright
  10.  *   notice, this list of conditions and the following disclaimer.
  11.  * - Redistributions in binary form must reproduce the above copyright
  12.  *   notice, this list of conditions and the following disclaimer in the
  13.  *   documentation and/or other materials provided with the distribution.
  14.  * - The name of the author may not be used to endorse or promote products
  15.  *   derived from this software without specific prior written permission.
  16.  *
  17.  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  18.  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  19.  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  20.  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  21.  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  22.  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  23.  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  24.  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  25.  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  26.  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  27.  */
  28.  
  29. /** @addtogroup genericadt
  30.  * @{
  31.  */
  32. /** @file
  33.  */
  34.  
  35. #ifndef KERN_AVLTREE_H_
  36. #define KERN_AVLTREE_H_
  37.  
  38. #include <arch/types.h>
  39. #include <typedefs.h>
  40.  
  41. /**
  42.  * Macro for getting a pointer to the structure which contains the avltree
  43.  * structure.
  44.  *
  45.  * @param link Pointer to the avltree structure.
  46.  * @param type Name of the outer structure.
  47.  * @param member Name of avltree attribute in the outer structure.
  48.  */
  49. #define avltree_get_instance(node, type, member) \
  50.     ((type *)(((uint8_t *)(node)) - ((uint8_t *) &(((type *) NULL)->member))))
  51.  
  52. typedef struct avltree_node avltree_node_t;
  53. typedef struct avltree avltree_t;
  54.  
  55. typedef uint64_t avltree_key_t;
  56.  
  57. typedef bool (* avltree_walker_t)(avltree_node_t *, void *);
  58.  
  59. /** AVL tree node structure. */
  60. struct avltree_node
  61. {
  62.     /**
  63.      * Pointer to the left descendant of this node.
  64.      *
  65.      * All keys of nodes in the left subtree are less than the key of this
  66.      * node.
  67.      */
  68.     struct avltree_node *lft;
  69.    
  70.     /**
  71.      * Pointer to the right descendant of this node.
  72.      *
  73.      * All keys of nodes in the right subtree are greater than the key of
  74.      * this node.
  75.      */
  76.     struct avltree_node *rgt;
  77.    
  78.     /** Pointer to the parent node. Root node has NULL parent. */
  79.     struct avltree_node *par;
  80.    
  81.     /** Node's key. */
  82.     avltree_key_t key;
  83.    
  84.     /**
  85.      * Difference between the heights of the left and the right subtree of
  86.      * this node.
  87.      */
  88.     int8_t balance;
  89. };
  90.  
  91. /** AVL tree structure. */
  92. struct avltree
  93. {
  94.     /** AVL root node pointer */
  95.     struct avltree_node *root;
  96.  
  97.     /**
  98.      * Base of the tree is a value that is smaller or equal than every value
  99.      * in the tree (valid for positive keys otherwise ignore this atribute).
  100.      *  
  101.      * The base is added to the current key when a new node is inserted into
  102.      * the tree. The base is changed to the key of the node which is deleted
  103.      * with avltree_delete_min().
  104.      */
  105.     avltree_key_t base;
  106. };
  107.  
  108.  
  109. /** Create empty AVL tree.
  110.  *
  111.  * @param t AVL tree.
  112.  */
  113. static inline void avltree_create(avltree_t *t)
  114. {
  115.     t->root = NULL;
  116.     t->base = 0;
  117. }
  118.  
  119. /** Initialize node.
  120.  *
  121.  * @param node Node which is initialized.
  122.  */
  123. static inline void avltree_node_initialize(avltree_node_t *node)
  124. {
  125.     node->key = 0;
  126.     node->lft = NULL;
  127.     node->rgt = NULL;
  128.     node->par = NULL;
  129.     node->balance = 0;
  130. }
  131.  
  132. extern avltree_node_t *avltree_find_min(avltree_t *t);
  133. extern avltree_node_t *avltree_search(avltree_t *t, avltree_key_t key);
  134. extern void avltree_insert(avltree_t *t, avltree_node_t *newnode);
  135. extern void avltree_delete(avltree_t *t, avltree_node_t *node);
  136. extern bool avltree_delete_min(avltree_t *t);
  137. extern void avltree_walk(avltree_t *t, avltree_walker_t walker, void *arg);
  138.  
  139. #endif
  140.  
  141. /** @}
  142.  */
  143.