Subversion Repositories HelenOS

Rev

Rev 2787 | 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
#ifndef KERN_AVLTREE_H_
36
#define KERN_AVLTREE_H_ 
37
 
38
#include <arch/types.h>
3424 svoboda 39
#include <typedefs.h>
2416 mencl 40
 
2496 jermar 41
/**
42
 * Macro for getting a pointer to the structure which contains the avltree
43
 * structure.
2416 mencl 44
 *
2496 jermar 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.
2416 mencl 48
 */
2501 jermar 49
#define avltree_get_instance(node, type, member) \
50
    ((type *)(((uint8_t *)(node)) - ((uint8_t *) &(((type *) NULL)->member))))
2416 mencl 51
 
52
typedef struct avltree_node avltree_node_t;
53
typedef struct avltree avltree_t;
54
 
2501 jermar 55
typedef uint64_t avltree_key_t;
2416 mencl 56
 
2504 jermar 57
typedef bool (* avltree_walker_t)(avltree_node_t *, void *);
2501 jermar 58
 
2416 mencl 59
/** AVL tree node structure. */
60
struct avltree_node
61
{
62
    /**
2496 jermar 63
     * Pointer to the left descendant of this node.
2416 mencl 64
     *
2496 jermar 65
     * All keys of nodes in the left subtree are less than the key of this
66
     * node.
2416 mencl 67
     */
68
    struct avltree_node *lft;
69
 
70
    /**
2496 jermar 71
     * Pointer to the right descendant of this node.
2416 mencl 72
     *
2496 jermar 73
     * All keys of nodes in the right subtree are greater than the key of
74
     * this node.
2416 mencl 75
     */
76
    struct avltree_node *rgt;
77
 
2496 jermar 78
    /** Pointer to the parent node. Root node has NULL parent. */
2416 mencl 79
    struct avltree_node *par;
80
 
2496 jermar 81
    /** Node's key. */
2501 jermar 82
    avltree_key_t key;
2416 mencl 83
 
2496 jermar 84
    /**
85
     * Difference between the heights of the left and the right subtree of
86
     * this node.
87
     */
2466 mencl 88
    int8_t balance;
2416 mencl 89
};
90
 
91
/** AVL tree structure. */
92
struct avltree
93
{
94
    /** AVL root node pointer */
95
    struct avltree_node *root;
96
 
97
    /**
2496 jermar 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).
2416 mencl 100
     *  
2496 jermar 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().
2416 mencl 104
     */
2501 jermar 105
    avltree_key_t base;
2416 mencl 106
};
107
 
108
 
109
/** Create empty AVL tree.
110
 *
111
 * @param t AVL tree.
112
 */
2501 jermar 113
static inline void avltree_create(avltree_t *t)
2416 mencl 114
{
115
    t->root = NULL;
116
    t->base = 0;
117
}
118
 
119
/** Initialize node.
120
 *
2496 jermar 121
 * @param node Node which is initialized.
2416 mencl 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
 
2496 jermar 132
extern avltree_node_t *avltree_find_min(avltree_t *t);
2501 jermar 133
extern avltree_node_t *avltree_search(avltree_t *t, avltree_key_t key);
2496 jermar 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);
2504 jermar 137
extern void avltree_walk(avltree_t *t, avltree_walker_t walker, void *arg);
2416 mencl 138
 
139
#endif
140
 
141
/** @}
142
 */