Subversion Repositories HelenOS

Rev

Rev 2466 | Go to most recent revision | Show entire file | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed

Rev 2466 Rev 2496
Line 36... Line 36...
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
 
Line 108... Line 114...
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
 */