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 
 */