Subversion Repositories HelenOS

Rev

Rev 2416 | 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.  
  36. #ifndef KERN_EXTAVLRELTREE_H_
  37. #define KERN_EXTAVLRELTREE_H_
  38.  
  39. #include <arch/types.h>
  40.  
  41. typedef struct extavlreltree_node extavlreltree_node_t;
  42. typedef struct extavlreltree extavlreltree_t;
  43.  
  44.  
  45. /*
  46.  * Makro for getting pointer to structure which enclosure extavlreltree structure.
  47.  *
  48.  * @param link Pointer to extavlreltree structure.
  49.  * @param type Name of outer structure.
  50.  * @param member Name of extavlreltree atribute in outer structure.
  51.  */
  52. #define extavlreltree_get_instance(link,type,member) \
  53.     ((type *)(((uint8_t *)(link)) - ((uint8_t *)&(((type *)NULL)->member))))
  54.  
  55.  
  56.  
  57. /** Relative key Extended AVL tree node structure. */
  58. struct extavlreltree_node
  59. {
  60.     /**
  61.      * Pointer to left descendand of this node.
  62.      *
  63.      * All keys of nodes in the left subtree are less then key of this node.
  64.      */
  65.     extavlreltree_node_t *lft;
  66.  
  67.     /**
  68.      * Pointer to right descendand of this node.
  69.      *
  70.      * All keys of nodes in the right subtree are greater then key of this node.
  71.      */
  72.     extavlreltree_node_t *rgt;  
  73.    
  74.     /** Pointer to parent node. Root node has NULL parent. */
  75.     extavlreltree_node_t *par;  
  76.  
  77.     /** Pointer to next node which has equal or the closest greater key or head. */
  78.     extavlreltree_node_t *next;
  79.    
  80.     /** Pointer to previous node which has equal or the closest lesser key or head. */
  81.     extavlreltree_node_t *prev;
  82.    
  83.     /** Height of left subtree. */
  84.     int16_t lft_height;
  85.  
  86.     /** Height of right subtree. */
  87.     int16_t rgt_height;    
  88.  
  89.     /** Nodes key. */
  90.     uint64_t key;
  91.  
  92.     /** Sum of all keys in the right subtree. */
  93.     uint64_t rgt_sum;
  94. };
  95.  
  96. /** Relative key Extended AVL tree structure (ExtAvlrel). */
  97. struct extavlreltree
  98. {
  99.     /*
  100.      * ExtAvlrel root node pointer.
  101.      *
  102.      * Important only for recognition of non tree node.
  103.      */
  104.     extavlreltree_node_t *root;
  105.  
  106.     /** Head of doubly linked list of nodes. It is entrance point to the tree. */
  107.     extavlreltree_node_t head;
  108. };
  109.  
  110.  
  111.  
  112. /** Create empty Extended AVL tree.
  113.  *
  114.  * @param t Extended AVL tree structure.
  115.  */
  116. static inline void extavlreltree_create (extavlreltree_t *t)
  117. {
  118.     t->root = NULL;
  119.  
  120.     t->head.next = &t->head;
  121.     t->head.prev = &t->head;
  122. }
  123.  
  124. /** Initialize node.
  125.  *
  126.  * @param node Node which is initialized.
  127.  */
  128. static inline void extavlreltree_node_initialize(extavlreltree_node_t *node)
  129. {
  130.     node->lft = NULL;
  131.     node->rgt = NULL;
  132.     node->lft_height = 0;
  133.     node->rgt_height = 0;
  134.     node->par = NULL;
  135.     node->next = node;
  136.     node->prev = node;
  137.     node->rgt_sum = 0;
  138. }
  139.  
  140. extavlreltree_node_t *extavlreltree_search(extavlreltree_t *t, uint64_t key);
  141. void extavlreltree_insert(extavlreltree_t *t, extavlreltree_node_t *newnode);
  142. void extavlreltree_delete(extavlreltree_t *t, extavlreltree_node_t *node);
  143. bool extavlreltree_delete_min(extavlreltree_t *t);
  144.  
  145. #endif
  146.  
  147. /** @}
  148.  */
  149.