Subversion Repositories HelenOS

Rev

Rev 2466 | Only display areas with differences | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed

Rev 2466 Rev 2496
1 
/*
 1 
/*
2 
 * Copyright (C) 2007 Vojtech Mencl
 2 
 * Copyright (C) 2007 Vojtech Mencl
3 
 * All rights reserved.
 3 
 * All rights reserved.
4 
 *
 4 
 *
5 
 * Redistribution and use in source and binary forms, with or without
 5 
 * Redistribution and use in source and binary forms, with or without
6 
 * modification, are permitted provided that the following conditions
 6 
 * modification, are permitted provided that the following conditions
7 
 * are met:
 7 
 * are met:
8 
 *
 8 
 *
9 
 * - Redistributions of source code must retain the above copyright
 9 
 * - Redistributions of source code must retain the above copyright
10 
 *   notice, this list of conditions and the following disclaimer.
 10 
 *   notice, this list of conditions and the following disclaimer.
11 
 * - Redistributions in binary form must reproduce the above copyright
 11 
 * - Redistributions in binary form must reproduce the above copyright
12 
 *   notice, this list of conditions and the following disclaimer in the
 12 
 *   notice, this list of conditions and the following disclaimer in the
13 
 *   documentation and/or other materials provided with the distribution.
 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
 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.
 15 
 *   derived from this software without specific prior written permission.
16 
 *
 16 
 *
17 
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
 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
 18 
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
19 
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 19 
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
20 
 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
 20 
 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
21 
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 21 
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
22 
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 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
 23 
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 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
 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.
 26 
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 
 */
 27 
 */
28 
 
 28 
 
29 
/** @addtogroup genericadt
 29 
/** @addtogroup genericadt
30 
 * @{
 30 
 * @{
31 
 */
 31 
 */
32 
/** @file
 32 
/** @file
33 
 */
 33 
 */
34 
 
 34 
 
35 
 
 35 
 
36 
#ifndef KERN_AVLTREE_H_
 36 
#ifndef KERN_AVLTREE_H_
37 
#define KERN_AVLTREE_H_
37 
#define KERN_AVLTREE_H_
38 
 
 38 
 
39 
#include <arch/types.h>
 39 
#include <arch/types.h>
40 
 
 40 
 
41 
/*
 41 
/**
42 
 * Makro for getting pointer to structure which enclosure avltree structure.
 42 
 * Macro for getting a pointer to the structure which contains the avltree
- 
 
 43 
 * structure.
43 
 *
 44 
 *
44 
 * @param link Pointer to avltree structure.
 45 
 * @param link Pointer to the avltree structure.
45 
 * @param type Name of outer structure.
 46 
 * @param type Name of the outer structure.
46 
 * @param member Name of avltree atribute in outer structure.
 47 
 * @param member Name of avltree attribute in the outer structure.
47 
 */
 48 
 */
48 
#define avltree_get_instance(link,type,member) \
 49 
#define avltree_get_instance(link, type, member) \
49 
    ((type *)(((uint8_t *)(link)) - ((uint8_t *)&(((type *)NULL)->member))))
 50 
    ((type *)(((uint8_t *)(link)) - ((uint8_t *) &(((type *) NULL)->member))))
50 
 
 51 
 
51 
 
 52 
 
52 
typedef struct avltree_node avltree_node_t;
 53 
typedef struct avltree_node avltree_node_t;
53 
typedef struct avltree avltree_t;
 54 
typedef struct avltree avltree_t;
54 
 
 55 
 
55 
 
 56 
 
56 
/** AVL tree node structure. */
 57 
/** AVL tree node structure. */
57 
struct avltree_node
 58 
struct avltree_node
58 
{
 59 
{
59 
    /**
 60 
    /**
60 
     * Pointer to left descendand of this node.
 61 
     * Pointer to the left descendant of this node.
61 
     *
 62 
     *
62 
     * All keys of nodes in the left subtree are less then key of this node.
 63 
     * All keys of nodes in the left subtree are less than the key of this
- 
 
 64 
     * node.
63 
     */
 65 
     */
64 
    struct avltree_node *lft;
 66 
    struct avltree_node *lft;
65 
   
 67 
   
66 
    /**
 68 
    /**
67 
     * Pointer to right descendand of this node.
 69 
     * Pointer to the right descendant of this node.
68 
     *
 70 
     *
69 
     * All keys of nodes in the right subtree are greater then key of this node.
 71 
     * All keys of nodes in the right subtree are greater than the key of
- 
 
 72 
     * this node.
70 
     */
 73 
     */
71 
    struct avltree_node *rgt;
 74 
    struct avltree_node *rgt;
72 
   
 75 
   
73 
    /** Pointer to parent node. Root node has NULL parent. */
 76 
    /** Pointer to the parent node. Root node has NULL parent. */
74 
    struct avltree_node *par;
 77 
    struct avltree_node *par;
75 
   
 78 
   
76 
    /** Nodes key. */
 79 
    /** Node's key. */
77 
    uint64_t key;
 80 
    uint64_t key;
78 
   
 81 
   
- 
 
 82 
    /**
79 
    /** Difference between heights of left and right subtree of this node.*/
 83 
     * Difference between the heights of the left and the right subtree of
- 
 
 84 
     * this node.
- 
 
 85 
     */
80 
    int8_t balance;
 86 
    int8_t balance;
81 
};
 87 
};
82 
 
 88 
 
83 
/** AVL tree structure. */
 89 
/** AVL tree structure. */
84 
struct avltree
 90 
struct avltree
85 
{
 91 
{
86 
    /** AVL root node pointer */
 92 
    /** AVL root node pointer */
87 
    struct avltree_node *root;
 93 
    struct avltree_node *root;
88 
 
 94 
 
89 
    /**
 95 
    /**
90 
     * Base of tree is value that is smaller or equal then every value in tree
 96 
     * Base of the tree is a value that is smaller or equal than every value
91 
     * (valid for positive keys otherwise ignore this atribute).
 97 
     * in the tree (valid for positive keys otherwise ignore this atribute).
92 
     *  
 98 
     *  
93 
     * Base is added to current key when new node is inserted into tree.
 99 
     * The base is added to the current key when a new node is inserted into
94 
     * Base is changed to the key of node which is deleted with function
 100 
     * the tree. The base is changed to the key of the node which is deleted
95 
     *      avltree_delete_min.
 101 
     * with avltree_delete_min().
96 
     */
 102 
     */
97 
    uint64_t base;
 103 
    uint64_t base;
98 
};
 104 
};
99 
 
 105 
 
100 
 
 106 
 
101 
/** Create empty AVL tree.
 107 
/** Create empty AVL tree.
102 
 *
 108 
 *
103 
 * @param t AVL tree.
 109 
 * @param t AVL tree.
104 
 */
 110 
 */
105 
static inline void avltree_create (avltree_t *t)
 111 
static inline void avltree_create (avltree_t *t)
106 
{
 112 
{
107 
    t->root = NULL;
 113 
    t->root = NULL;
108 
    t->base = 0;
 114 
    t->base = 0;
109 
}
 115 
}
110 
 
 116 
 
111 
/** Initialize node.
 117 
/** Initialize node.
112 
 *
 118 
 *
113 
 * @param Node which is initialized.
 119 
 * @param node Node which is initialized.
114 
 */
 120 
 */
115 
static inline void avltree_node_initialize(avltree_node_t *node)
 121 
static inline void avltree_node_initialize(avltree_node_t *node)
116 
{
 122 
{
117 
    node->key = 0;
 123 
    node->key = 0;
118 
    node->lft = NULL;
 124 
    node->lft = NULL;
119 
    node->rgt = NULL;
 125 
    node->rgt = NULL;
120 
    node->par = NULL;
 126 
    node->par = NULL;
121 
    node->balance = 0;
 127 
    node->balance = 0;
122 
}
 128 
}
123 
 
 129 
 
124 
avltree_node_t *avltree_find_min(avltree_t *t);
 130 
extern avltree_node_t *avltree_find_min(avltree_t *t);
125 
avltree_node_t *avltree_search(avltree_t *t, uint64_t key);
 131 
extern avltree_node_t *avltree_search(avltree_t *t, uint64_t key);
126 
void avltree_insert(avltree_t *t, avltree_node_t *newnode);
 132 
extern void avltree_insert(avltree_t *t, avltree_node_t *newnode);
127 
void avltree_delete(avltree_t *t, avltree_node_t *node);
 133 
extern void avltree_delete(avltree_t *t, avltree_node_t *node);
128 
bool avltree_delete_min(avltree_t *t);
 134 
extern bool avltree_delete_min(avltree_t *t);
129 
 
 135 
 
130 
#endif
 136 
#endif
131 
 
 137 
 
132 
/** @}
 138 
/** @}
133 
 */
 139 
 */
134 
 
 140