summaryrefslogtreecommitdiff
path: root/kern/rbtree.h
blob: 1eafebbe50b120669b52a100306b6a33f5fe999d (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
/*
 * Copyright (c) 2010-2015 Richard Braun.
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 *
 * Upstream site with license notes :
 * http://git.sceen.net/rbraun/librbraun.git/
 *
 *
 * Red-black tree.
 */

#ifndef KERN_RBTREE_H
#define KERN_RBTREE_H

#include <assert.h>
#include <stddef.h>
#include <stdint.h>

#include <kern/macros.h>

/*
 * Indexes of the left and right nodes in the children array of a node.
 */
#define RBTREE_LEFT     0
#define RBTREE_RIGHT    1

/*
 * Red-black node.
 */
struct rbtree_node;

/*
 * Red-black tree.
 */
struct rbtree;

/*
 * Insertion point identifier.
 */
typedef uintptr_t rbtree_slot_t;

/*
 * Static tree initializer.
 */
#define RBTREE_INITIALIZER { NULL }

#include <kern/rbtree_i.h>

/*
 * Initialize a tree.
 */
static inline void
rbtree_init(struct rbtree *tree)
{
    tree->root = NULL;
}

/*
 * Initialize a node.
 *
 * A node is in no tree when its parent points to itself.
 */
static inline void
rbtree_node_init(struct rbtree_node *node)
{
    assert(rbtree_node_check_alignment(node));

    node->parent = (uintptr_t)node | RBTREE_COLOR_RED;
    node->children[RBTREE_LEFT] = NULL;
    node->children[RBTREE_RIGHT] = NULL;
}

/*
 * Return true if node is in no tree.
 */
static inline int
rbtree_node_unlinked(const struct rbtree_node *node)
{
    return rbtree_node_parent(node) == node;
}

/*
 * Macro that evaluates to the address of the structure containing the
 * given node based on the given type and member.
 */
#define rbtree_entry(node, type, member) structof(node, type, member)

/*
 * Return true if tree is empty.
 */
static inline int
rbtree_empty(const struct rbtree *tree)
{
    return tree->root == NULL;
}

/*
 * Look up a node in a tree.
 *
 * Note that implementing the lookup algorithm as a macro gives two benefits:
 * First, it avoids the overhead of a callback function. Next, the type of the
 * cmp_fn parameter isn't rigid. The only guarantee offered by this
 * implementation is that the key parameter is the first parameter given to
 * cmp_fn. This way, users can pass only the value they need for comparison
 * instead of e.g. allocating a full structure on the stack.
 *
 * See rbtree_insert().
 */
#define rbtree_lookup(tree, key, cmp_fn)                \
MACRO_BEGIN                                             \
    struct rbtree_node *cur_;                           \
    int diff_;                                          \
                                                        \
    cur_ = (tree)->root;                                \
                                                        \
    while (cur_ != NULL) {                              \
        diff_ = cmp_fn(key, cur_);                      \
                                                        \
        if (diff_ == 0) {                               \
            break;                                      \
        }                                               \
                                                        \
        cur_ = cur_->children[rbtree_d2i(diff_)];       \
    }                                                   \
                                                        \
    cur_;                                               \
MACRO_END

/*
 * Look up a node or one of its nearest nodes in a tree.
 *
 * This macro essentially acts as rbtree_lookup() but if no entry matched
 * the key, an additional step is performed to obtain the next or previous
 * node, depending on the direction (left or right).
 *
 * The constraints that apply to the key parameter are the same as for
 * rbtree_lookup().
 */
#define rbtree_lookup_nearest(tree, key, cmp_fn, dir)       \
MACRO_BEGIN                                                 \
    struct rbtree_node *cur_, *prev_;                       \
    int diff_, index_;                                      \
                                                            \
    prev_ = NULL;                                           \
    index_ = -1;                                            \
    cur_ = (tree)->root;                                    \
                                                            \
    while (cur_ != NULL) {                                  \
        diff_ = cmp_fn(key, cur_);                          \
                                                            \
        if (diff_ == 0) {                                   \
            break;                                          \
        }                                                   \
                                                            \
        prev_ = cur_;                                       \
        index_ = rbtree_d2i(diff_);                         \
        cur_ = cur_->children[index_];                      \
    }                                                       \
                                                            \
    if (cur_ == NULL) {                                     \
        cur_ = rbtree_nearest(prev_, index_, dir);          \
    }                                                       \
                                                            \
    cur_;                                                   \
MACRO_END

/*
 * Insert a node in a tree.
 *
 * This macro performs a standard lookup to obtain the insertion point of
 * the given node in the tree (it is assumed that the inserted node never
 * compares equal to any other entry in the tree) and links the node. It
 * then checks red-black rules violations, and rebalances the tree if
 * necessary.
 *
 * Unlike rbtree_lookup(), the cmp_fn parameter must compare two complete
 * entries, so it is suggested to use two different comparison inline
 * functions, such as myobj_cmp_lookup() and myobj_cmp_insert(). There is no
 * guarantee about the order of the nodes given to the comparison function.
 *
 * See rbtree_lookup().
 */
#define rbtree_insert(tree, node, cmp_fn)                   \
MACRO_BEGIN                                                 \
    struct rbtree_node *cur_, *prev_;                       \
    int diff_, index_;                                      \
                                                            \
    prev_ = NULL;                                           \
    index_ = -1;                                            \
    cur_ = (tree)->root;                                    \
                                                            \
    while (cur_ != NULL) {                                  \
        diff_ = cmp_fn(node, cur_);                         \
        assert(diff_ != 0);                                 \
        prev_ = cur_;                                       \
        index_ = rbtree_d2i(diff_);                         \
        cur_ = cur_->children[index_];                      \
    }                                                       \
                                                            \
    rbtree_insert_rebalance(tree, prev_, index_, node);     \
MACRO_END

/*
 * Look up a node/slot pair in a tree.
 *
 * This macro essentially acts as rbtree_lookup() but in addition to a node,
 * it also returns a slot, which identifies an insertion point in the tree.
 * If the returned node is NULL, the slot can be used by rbtree_insert_slot()
 * to insert without the overhead of an additional lookup.
 *
 * The constraints that apply to the key parameter are the same as for
 * rbtree_lookup().
 */
#define rbtree_lookup_slot(tree, key, cmp_fn, slot) \
MACRO_BEGIN                                         \
    struct rbtree_node *cur_, *prev_;               \
    int diff_, index_;                              \
                                                    \
    prev_ = NULL;                                   \
    index_ = 0;                                     \
    cur_ = (tree)->root;                            \
                                                    \
    while (cur_ != NULL) {                          \
        diff_ = cmp_fn(key, cur_);                  \
                                                    \
        if (diff_ == 0) {                           \
            break;                                  \
        }                                           \
                                                    \
        prev_ = cur_;                               \
        index_ = rbtree_d2i(diff_);                 \
        cur_ = cur_->children[index_];              \
    }                                               \
                                                    \
    (slot) = rbtree_slot(prev_, index_);            \
    cur_;                                           \
MACRO_END

/*
 * Insert a node at an insertion point in a tree.
 *
 * This macro essentially acts as rbtree_insert() except that it doesn't
 * obtain the insertion point with a standard lookup. The insertion point
 * is obtained by calling rbtree_lookup_slot(). In addition, the new node
 * must not compare equal to an existing node in the tree (i.e. the slot
 * must denote a NULL node).
 */
static inline void
rbtree_insert_slot(struct rbtree *tree, rbtree_slot_t slot,
                   struct rbtree_node *node)
{
    struct rbtree_node *parent;
    int index;

    parent = rbtree_slot_parent(slot);
    index = rbtree_slot_index(slot);
    rbtree_insert_rebalance(tree, parent, index, node);
}

/*
 * Replace a node at an insertion point in a tree.
 *
 * The given node must compare strictly equal to the previous node,
 * which is returned on completion.
 */
void * rbtree_replace_slot(struct rbtree *tree, rbtree_slot_t slot,
                           struct rbtree_node *node);

/*
 * Remove a node from a tree.
 *
 * After completion, the node is stale.
 */
void rbtree_remove(struct rbtree *tree, struct rbtree_node *node);

/*
 * Return the first node of a tree.
 */
#define rbtree_first(tree) rbtree_firstlast(tree, RBTREE_LEFT)

/*
 * Return the last node of a tree.
 */
#define rbtree_last(tree) rbtree_firstlast(tree, RBTREE_RIGHT)

/*
 * Return the node previous to the given node.
 */
#define rbtree_prev(node) rbtree_walk(node, RBTREE_LEFT)

/*
 * Return the node next to the given node.
 */
#define rbtree_next(node) rbtree_walk(node, RBTREE_RIGHT)

/*
 * Forge a loop to process all nodes of a tree, removing them when visited.
 *
 * This macro can only be used to destroy a tree, so that the resources used
 * by the entries can be released by the user. It basically removes all nodes
 * without doing any color checking.
 *
 * After completion, all nodes and the tree root member are stale.
 */
#define rbtree_for_each_remove(tree, node, tmp)         \
for (node = rbtree_postwalk_deepest(tree),              \
     tmp = rbtree_postwalk_unlink(node);                \
     node != NULL;                                      \
     node = tmp, tmp = rbtree_postwalk_unlink(node))

#endif /* KERN_RBTREE_H */