Subversion Repositories HelenOS

Rev

Go to most recent revision | Details | Last modification | View Log | RSS feed

Rev Author Line No. Line
2416 mencl 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 
 */