Subversion Repositories HelenOS

Rev

Rev 2421 | Rev 2466 | Go to most recent revision | Details | Compare with Previous | Last modification | View Log | RSS feed

Rev Author Line No. Line
2416 mencl 1
/*
2461 mencl 2
 * Copyright (C) 2007 Vojtech Mencl
2416 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_AVLTREE_H_
37
#define KERN_AVLTREE_H_ 
38
 
39
#include <arch/types.h>
40
 
41
/*
42
 * Makro for getting pointer to structure which enclosure avltree structure.
43
 *
44
 * @param link Pointer to avltree structure.
45
 * @param type Name of outer structure.
46
 * @param member Name of avltree atribute in outer structure.
47
 */
48
#define avltree_get_instance(link,type,member) \
49
    ((type *)(((uint8_t *)(link)) - ((uint8_t *)&(((type *)NULL)->member))))
50
 
51
 
52
typedef struct avltree_node avltree_node_t;
53
typedef struct avltree avltree_t;
54
 
55
 
56
/** AVL tree node structure. */
57
struct avltree_node
58
{
59
    /**
60
     * Pointer to left descendand of this node.
61
     *
62
     * All keys of nodes in the left subtree are less then key of this node.
63
     */
64
    struct avltree_node *lft;
65
 
66
    /**
67
     * Pointer to right descendand of this node.
68
     *
69
     * All keys of nodes in the right subtree are greater then key of this node.
70
     */
71
    struct avltree_node *rgt;
72
 
73
    /** Pointer to parent node. Root node has NULL parent. */
74
    struct avltree_node *par;
75
 
76
    /** Nodes key. */
77
    uint64_t key;
78
 
79
    /** Difference between heights of left and right subtree of this node.*/
80
    short balance;
81
};
82
 
83
/** AVL tree structure. */
84
struct avltree
85
{
86
    /** AVL root node pointer */
87
    struct avltree_node *root;
88
 
89
    /**
2461 mencl 90
     * Base of tree is value that is smaller or equal then every value in tree
91
     * (valid for positive keys otherwise ignore this atribute).
2416 mencl 92
     *  
93
     * Base is added to current key when new node is inserted into tree.
94
     * Base is changed to the key of node which is deleted with function
95
     *      avltree_delete_min.
96
     */
97
    uint64_t base;             /**< POZOR: Base time for inserting new nodes */
98
};
99
 
100
 
101
/** Create empty AVL tree.
102
 *
103
 * @param t AVL tree.
104
 */
105
static inline void avltree_create (avltree_t *t)
106
{
107
    t->root = NULL;
108
    t->base = 0;
109
}
110
 
111
/** Initialize node.
112
 *
113
 * @param Node which is initialized.
114
 */
115
static inline void avltree_node_initialize(avltree_node_t *node)
116
{
117
    node->key = 0;
118
    node->lft = NULL;
119
    node->rgt = NULL;
120
    node->par = NULL;
121
    node->balance = 0;
122
}
123
 
2421 mencl 124
avltree_node_t *avltree_find_min(avltree_t *t);
2416 mencl 125
avltree_node_t *avltree_search(avltree_t *t, uint64_t key);
126
void avltree_insert(avltree_t *t, avltree_node_t *newnode);
127
void avltree_delete(avltree_t *t, avltree_node_t *node);
2421 mencl 128
bool avltree_delete_min(avltree_t *t);
2416 mencl 129
 
130
#endif
131
 
132
/** @}
133
 */