Subversion Repositories HelenOS

Rev

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
 
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
 */
2496 jermar 49
#define avltree_get_instance(link, type, member) \
50
    ((type *)(((uint8_t *)(link)) - ((uint8_t *) &(((type *) NULL)->member))))
2416 mencl 51
 
52
 
53
typedef struct avltree_node avltree_node_t;
54
typedef struct avltree avltree_t;
55
 
56
 
57
/** AVL tree node structure. */
58
struct avltree_node
59
{
60
    /**
2496 jermar 61
     * Pointer to the left descendant of this node.
2416 mencl 62
     *
2496 jermar 63
     * All keys of nodes in the left subtree are less than the key of this
64
     * node.
2416 mencl 65
     */
66
    struct avltree_node *lft;
67
 
68
    /**
2496 jermar 69
     * Pointer to the right descendant of this node.
2416 mencl 70
     *
2496 jermar 71
     * All keys of nodes in the right subtree are greater than the key of
72
     * this node.
2416 mencl 73
     */
74
    struct avltree_node *rgt;
75
 
2496 jermar 76
    /** Pointer to the parent node. Root node has NULL parent. */
2416 mencl 77
    struct avltree_node *par;
78
 
2496 jermar 79
    /** Node's key. */
2416 mencl 80
    uint64_t key;
81
 
2496 jermar 82
    /**
83
     * Difference between the heights of the left and the right subtree of
84
     * this node.
85
     */
2466 mencl 86
    int8_t balance;
2416 mencl 87
};
88
 
89
/** AVL tree structure. */
90
struct avltree
91
{
92
    /** AVL root node pointer */
93
    struct avltree_node *root;
94
 
95
    /**
2496 jermar 96
     * Base of the tree is a value that is smaller or equal than every value
97
     * in the tree (valid for positive keys otherwise ignore this atribute).
2416 mencl 98
     *  
2496 jermar 99
     * The base is added to the current key when a new node is inserted into
100
     * the tree. The base is changed to the key of the node which is deleted
101
     * with avltree_delete_min().
2416 mencl 102
     */
2466 mencl 103
    uint64_t base;
2416 mencl 104
};
105
 
106
 
107
/** Create empty AVL tree.
108
 *
109
 * @param t AVL tree.
110
 */
111
static inline void avltree_create (avltree_t *t)
112
{
113
    t->root = NULL;
114
    t->base = 0;
115
}
116
 
117
/** Initialize node.
118
 *
2496 jermar 119
 * @param node Node which is initialized.
2416 mencl 120
 */
121
static inline void avltree_node_initialize(avltree_node_t *node)
122
{
123
    node->key = 0;
124
    node->lft = NULL;
125
    node->rgt = NULL;
126
    node->par = NULL;
127
    node->balance = 0;
128
}
129
 
2496 jermar 130
extern avltree_node_t *avltree_find_min(avltree_t *t);
131
extern avltree_node_t *avltree_search(avltree_t *t, uint64_t key);
132
extern void avltree_insert(avltree_t *t, avltree_node_t *newnode);
133
extern void avltree_delete(avltree_t *t, avltree_node_t *node);
134
extern bool avltree_delete_min(avltree_t *t);
2416 mencl 135
 
136
#endif
137
 
138
/** @}
139
 */