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_EXTAVLTREE_H_
37
#define KERN_EXTAVLTREE_H_
38
 
39
#include <arch/types.h>
40
 
41
/*
42
 * Makro for getting pointer to structure which enclosure extavltree structure.
43
 *
44
 * @param link Pointer to extavltree structure.
45
 * @param type Name of outer structure.
46
 * @param member Name of extavltree atribute in outer structure.
47
 */
48
#define extavltree_get_instance(link,type,member) \
49
    ((type *)(((uint8_t *)(link)) - ((uint8_t *)&(((type *)NULL)->member))))
50
 
51
 
52
typedef struct extavltree_node extavltree_node_t;
53
typedef struct extavltree extavltree_t;
54
 
55
/** Extended AVL tree node structure. */
56
struct extavltree_node
57
{
58
    /**
59
     * Pointer to left descendand of this node.
60
     *
61
     * All keys of nodes in the left subtree are less then key of this node.
62
     */
63
    extavltree_node_t *lft;
64
 
65
    /**
66
     * Pointer to right descendand of this node.
67
     *
68
     * All keys of nodes in the right subtree are greater then key of this node.
69
     */
70
    extavltree_node_t *rgt;  
71
 
72
    /** Pointer to parent node. Root node has NULL parent. */
73
    extavltree_node_t *par;  
74
 
75
    /** Pointer to next node which has equal or the closest greater key or head. */
76
    extavltree_node_t *next;
77
 
78
    /** Pointer to previous node which has equal or the closest lesser key or head. */
79
    extavltree_node_t *prev;
80
 
81
    /** Height of left subtree. */
82
    int16_t lft_height;
83
 
84
    /** Height of right subtree. */
85
    int16_t rgt_height;    
86
 
87
    /** Nodes key. */
88
    uint64_t key;              
89
};
90
 
91
/** Extended AVL tree structure. */
92
struct extavltree
93
{
94
    /** Extended AVL root node pointer. */
95
    extavltree_node_t *root;
96
 
97
    /** Head of doubly linked list of nodes. */
98
    extavltree_node_t head;
99
 
100
    /**
101
     * Base of tree is value that is smaller or equal then every value in tree.
102
     *  
103
     * Base is added to current key when new node is inserted into tree.
104
     * Base is changed to the key of node which is deleted with function
105
     *      extavltree_delete_min.
106
     */
107
    uint64_t base;
108
};
109
 
110
/** Initialize node.
111
 *
112
 * @param node Node which is initialized.
113
 */
114
static inline void extavltree_node_initialize(extavltree_node_t *node)
115
{
116
    node->lft = NULL;
117
    node->rgt = NULL;
118
    node->lft_height = 0;
119
    node->rgt_height = 0;
120
    node->par = NULL;
121
    node->next = node;
122
    node->prev = node;
123
    node->key = 0;
124
};
125
 
126
/** Create empty Extended AVL tree.
127
 *
128
 * @param t Extended AVL tree structure.
129
 */
130
static inline void extavltree_create (extavltree_t *t) //jen inicializace
131
{
132
    t->root = NULL;
133
    t->base = 0;
134
    extavltree_node_initialize(&t->head);
135
};
136
 
137
extavltree_node_t *extavltree_search(extavltree_t *t, uint64_t key);
138
void extavltree_insert(extavltree_t *t, extavltree_node_t *newnode);
139
void extavltree_delete(extavltree_t *t, extavltree_node_t *node);
140
bool extavltree_delete_min(extavltree_t *t);
141
 
142
#endif
143
 
144
/** @}
145
 */