Subversion Repositories HelenOS

Rev

Go to most recent revision | Blame | Compare with Previous | Last modification | View Log | Download | RSS feed

  1. /*
  2.  * Copyright (C) 2006 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. #ifdef AVLTREE_TEST
  98. struct extavlreltree
  99. {
  100.     /*
  101.      * ExtAvlrel root node pointer.
  102.      *
  103.      * Important only for recognition of non tree node.
  104.      */
  105.     extavlreltree_node_t *root;
  106.  
  107.     /** Head of doubly linked list of nodes. It is entrance point to the tree. */
  108.     extavlreltree_node_t head;
  109. };
  110.  
  111.  
  112.  
  113. /** Create empty Extended AVL tree.
  114.  *
  115.  * @param t Extended AVL tree structure.
  116.  */
  117. void extavlreltree_create (extavlreltree_t *t)
  118. {
  119.     t->root = NULL;
  120.  
  121.     t->head.next = &t->head;
  122.     t->head.prev = &t->head;
  123. }
  124.  
  125. /** Initialize node.
  126.  *
  127.  * @param node Node which is initialized.
  128.  */
  129. void extavlreltree_node_initialize(extavlreltree_node_t *node)
  130. {
  131.     node->lft = NULL;
  132.     node->rgt = NULL;
  133.     node->lft_height = 0;
  134.     node->rgt_height = 0;
  135.     node->par = NULL;
  136.     node->next = node;
  137.     node->prev = node;
  138.     node->rgt_sum = 0;
  139. }
  140.  
  141. extavlreltree_node_t *extavlreltree_search(extavlreltree_t *t, uint64_t key);
  142. void extavlreltree_insert(extavlreltree_t *t, extavlreltree_node_t *newnode);
  143. void extavlreltree_delete(extavlreltree_t *t, extavlreltree_node_t *node);
  144. bool extavlreltree_delete_min(extavlreltree_t *t);
  145.  
  146. #endif
  147.  
  148. /** @}
  149.  */
  150.