summaryrefslogtreecommitdiffstats
path: root/src/fluent-bit/lib/rbtree/rbtree.h
blob: ef2f61e7d40dbfadd105a057188dc0b8332c81c1 (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
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
#ifndef __INCLUDED_RBTREE_H__
#define __INCLUDED_RBTREE_H__

/** \file rbtree.h
 * Declaration of associated structures and functions for a simple, intrusive
 * red-black tree implementation.
 */

#ifdef __cplusplus
extern "C" {
#endif /* __cplusplus */

#include <stdlib.h>
#include <assert.h>

/** \defgroup rb_tree_compiler_prims Compiler Abstractions
 * Primitives used to abstract compiler-specific syntax for common details used in
 * providing hints to the compiler for optimization or linker details.
 * @{
 */

/**
 * Macro to check if a given assertion about an argument is true
 */
#define RB_ASSERT_ARG(x) \
    do {                                \
        if (RB_UNLIKELY(!(x))) {        \
            assert(#x && 0);            \
            return RB_BAD_ARG;          \
        }                               \
    } while (0)

/**
 * The tagged branch is unlikely to be taken
 */
#ifdef _MSC_VER
#define RB_UNLIKELY(x) (!!(x))
#else
#define RB_UNLIKELY(x) __builtin_expect(!!(x), 0)
#endif
/**@}*/

/** \defgroup rb_tree_state State Structures
 * Structures that are used to represent state of a red-black tree, including the
 * state of the tree itself, comparison functions used to determine how the tree
 * is to be traversed, and representations of red-black tree nodes themselves.
 * @{
 */

/**
 * Structure that represents a node in a red-black tree. Embed this in your own
 * structure in order to add your structure to the given red-black tree.
 * Users of the rb_tree_node would embed it something like
 * \code{.c}
    struct my_sample_struct {
        char *name;
        int data;
        struct rb_tree_node rnode;
    };
 * \endcode
 *
 * \note No user of `struct rb_tree_node` should ever modify or inspect any
 *       members of the structure.
 */
struct rb_tree_node {
    /**
     * The left child (`NULL` if empty)
     */
    struct rb_tree_node *left;

    /** 
     * The right child (`NULL` if empty)
     */
    struct rb_tree_node *right;

    /**
     * The parent of this node (`NULL` if at root)
     */
    struct rb_tree_node *parent;

    /**
     * The key for this node
     */
    const void *key;

    /**
     * The color of the node
     */
    int color;
};

/**
 * Pointer to a function to compare two keys, and returns as follows:
 *  - (0, +inf] if lhs > rhs
 *  - 0 if lhs == rhs
 *  - [-inf, 0) if lhs < rhs
 */
typedef int (*rb_cmp_func_t)(const void *lhs, const void *rhs);

/**
 * Pointer to a comparison function that allows passing along state.
 * Return values are interpreted as follows:
 *  (0, +inf] if lhs > rhs
 *  0 if lhs == rhs
 *  [-inf, 0) if lhs < rhs
 */
typedef int (*rb_cmp_func_ex_t)(void *state, const void *lhs, const void *rhs);

/**
 * Structure representing an RB tree's associated state. Contains all
 * the information needed to manage the lifecycle of a RB tree.
 * \note Typically users should not directly manipulate the structure,
 *       but rather use the provided accessor functions.
 */
struct rb_tree {
    /**
     * The root of the tree
     */
    struct rb_tree_node *root;

    /**
     * Predicate used for traversing the tree
     */
    rb_cmp_func_ex_t compare;

    /**
     * The right-most node of the rb-tree
     */
    struct rb_tree_node *rightmost;

    /**
     * Private state that can be used by the rb-tree owner
     */
    void *state;
};

/**@} rb_tree_state */

/** \defgroup rb_result Function Results and Error Handling
 * @{
 */
/** \typedef rb_result_t
 * Value of a returned result code from a red-black tree function.
 */
typedef int rb_result_t;

/** \defgroup rb_result_code Result Codes
 * Error codes that can be returned from any function that returns an rb_result_t.
 * @{
 */

/**
 * Function was successful
 */
#define RB_OK           0x0
/**
 * Element was not found
 */
#define RB_NOT_FOUND    0x1
/**
 * Bad argument provided to function (typically unexpected NULL)
 */
#define RB_BAD_ARG      0x2
/**
 * Node is a duplicate of an existing node
 */
#define RB_DUPLICATE    0x3

/**@} rb_result_code */
/**@} rb_result */

/** \brief Helper to get a pointer to a containing structure.
 * Given a pointer to an rb_tree_node, a target type and a member name,
 * return a pointer to the structure containing the `struct rb_tree_node`.
 * \code{.c}
    struct sample {
        const char *name;
        struct rb_tree_node node;
    };

    void test(void)
    {
        struct sample samp = { .name = "Test 123" };
        struct rb_tree_node *samp_node = &(samp.node);
        struct sample *samp2 = RB_CONTAINER_OF(samp_node, struct sample, node);

        assert(&samp == samp2);
    }
 * \endcode
 * \param x The pointer to the node
 * \param type The type of the containing structure
 * \param memb The name of the `struct rb_tree_node` in the containing structure
 * \return Pointer to the containing structure of the specified type
 */
#define RB_CONTAINER_OF(x, type, memb) \
    ({                                                              \
        const __typeof__( ((type *)0)->memb ) *__member = (x);      \
        (type *)( (char *)__member - __offsetof__(type, memb) );    \
    })


/** \defgroup rb_functions Functions for Manipulating Red-Black Trees
 * All functions associated with manipulating Red-Black trees using `struct rb_tree`,
 * inluding lifecycle functions and member manipulation and state checking functions.
 * @{
 */

/**
 * \brief Construct a new, empty red-black tree, with extended state
 * Given a region of memory at least the size of a struct rb_tree to
 * store the red-black tree metadata, update it to contain an initialized, empty
 * red-black tree, with given private state.
 * \param tree Pointer to the new tree.
 * \param compare Function used to traverse the tree.
 * \param state The private state to be passed to the compare function
 * \return RB_OK on success, an error code otherwise
 */
rb_result_t rb_tree_new_ex(struct rb_tree *tree, rb_cmp_func_ex_t compare, void *state);

/**
 * \brief Construct a new, empty red-black tree.
 * Given a region of memory at least the size of a struct rb_tree to
 * store the red-black tree metadata, update it to contain an initialized, empty
 * red-black tree.
 * \param tree Pointer to the new tree.
 * \param compare Function used to traverse the tree.
 * \return RB_OK on success, an error code otherwise
 */
rb_result_t rb_tree_new(struct rb_tree *tree,
                        rb_cmp_func_t compare);

/**
 * \brief Destroy a Red-Black tree.
 * Clean up the state structure, clearing out the state of the tree
 * so that it no longer can be used.
 * \note Assumes that external callers will deallocate all nodes through
 *       some application-specific mechanism.
 * \param tree The reference to the pointer to the tree itself.
 * \return RB_OK on success, an error code otherwise
 */
rb_result_t rb_tree_destroy(struct rb_tree *tree);

/**
 * \brief Check if an red-black tree is empty (has no nodes).
 * If no nodes are present, returns a non-zero value in `is_empty` -- returns
 * 0 if there are nodes present.
 * \param tree The tree to check
 * \param is_empty nonzero on true, 0 otherwise
 * \return RB_OK on success, an error code otherwise
 */
rb_result_t rb_tree_empty(struct rb_tree *tree, int *is_empty);

/**
 * \brief Find a node in the Red-Black tree given the specified key.
 * Given a key, search the RB-tree iteratively until the specified key is found.
 * This traversal is in O(log n) time, per the properties of a binary search tree.
 * \param tree The RB-tree to search
 * \param key The key to search for
 * \param value a reference to a pointer to receive the pointer to the rb_tree_node if key is found
 * \return RB_OK on success, an error code otherwise
 */
rb_result_t rb_tree_find(struct rb_tree *tree,
                         const void *key,
                         struct rb_tree_node **value);

/**
 * \brief Insert a node into the tree.
 * Given a node and key, insert the node into the red-black tree and rebalance
 * the tree if appropriate. Insertion is O(log n) time, with two tree traversals
 * possible -- one for insertion (guaranteed) and one for rebalancing.
 * \param tree the RB tree to insert the node into
 * \param key The key for the node (must live as long as the node itself is in the tree)
 * \param node the node to be inserted into the tree
 * \return RB_OK on sucess, an error code otherwise
 */
rb_result_t rb_tree_insert(struct rb_tree *tree,
                           const void *key,
                           struct rb_tree_node *node);

/**
 * \brief Remove the specified node from the Red-Black tree.
 * Given a pointer to the node, splice the node out of the tree, then, if applicable
 * rebalance the tree so the Red-Black properties are maintained.
 * \param tree The tree we want to remove the node from
 * \param node The the node we want to remove
 * \return RB_OK on success, an error code otherwise
 */
rb_result_t rb_tree_remove(struct rb_tree *tree,
                           struct rb_tree_node *node);

/**
 * \brief Find a node. If not found, insert the candidate.
 * Find a node with the given key. If the node is found, return it by
 * reference, without modifying the tree. If the node is not found,
 * insert the provided candidate node.
 * \note This function always will return in *value the node inserted
 *       or the existing node. If you want to check if the candidate
 *       node was inserted, check if `*value == new_candidate`
 *
 * \param tree The tree in question
 * \param key The key to search for
 * \param new_candidate The candidate node to insert
 * \param value The value at the given location
 * \return RB_OK on success, an error code otherwise
 */
rb_result_t rb_tree_find_or_insert(struct rb_tree *tree,
                                   void *key,
                                   struct rb_tree_node *new_candidate,
                                   struct rb_tree_node **value);

/**
 * \brief Find a node. If not found, insert the candidate.
 * Find a node with the given key. If the node is found, return it by
 * reference, without modifying the tree. If the node is not found,
 * insert the provided candidate node.
 * \note This function always will return in *value the node inserted
 *       or the existing node. If you want to check if the candidate
 *       node was inserted, check if `*value == new_candidate`
 *
 * \param tree The tree in question
 * \param key The key to search for
 * \param new_candidate The candidate node to insert
 * \param value The value at the given location
 *
 * \return RB_OK on success, an error code otherwise
 */
rb_result_t rb_tree_find_or_insert(struct rb_tree *tree,
                                   void *key,
                                   struct rb_tree_node *new_candidate,
                                   struct rb_tree_node **value);
/**
 * \brief Get the rightmost (greatest relative to predicate) node.
 * Return the rightmost (i.e. greatest relative to predicate) node of the Red-Black tree.
 */
static inline
rb_result_t rb_tree_get_rightmost(struct rb_tree *tree,
                                  struct rb_tree_node **rightmost)
{
    if ( (NULL == tree) || (NULL == rightmost) ) {
        return RB_BAD_ARG;
    }

    *rightmost = tree->rightmost;

    return RB_OK;
}


/**
 * Find the minimum of the given tree/subtree rooted at the given node.
 */
static inline
rb_result_t __rb_tree_find_minimum(struct rb_tree_node *root,
                                   struct rb_tree_node **min)
{
    struct rb_tree_node *x = root;

    while (x->left != NULL) {
        x = x->left;
    }

    *min = x;

    return RB_OK;
}

/**
 * Find the maximum of the given tree/subtree rooted at the given node.
 */
static inline
rb_result_t __rb_tree_find_maximum(struct rb_tree_node *root,
                                   struct rb_tree_node **max)
{
    struct rb_tree_node *x = root;

    while (x->right != NULL) {
        x = x->right;
    }

    *max = x;

    return RB_OK;
}

/**
 * Find the successor (greater than, relative to predicate) node of the given node.
 */
static inline
rb_result_t rb_tree_find_successor(struct rb_tree *tree,
                                   struct rb_tree_node *node,
                                   struct rb_tree_node **successor)
{
    rb_result_t ret = RB_OK;

    RB_ASSERT_ARG(tree != NULL);
    RB_ASSERT_ARG(node != NULL);
    RB_ASSERT_ARG(successor != NULL);

    struct rb_tree_node *x = node;

    if (x->right != NULL) {
        __rb_tree_find_minimum(x->right, successor);
        goto done;
    }

    struct rb_tree_node *y = x->parent;

    while (y != NULL && (x == y->right)) {
        x = y;
        y = y->parent;
    }

    *successor = y;

done:
    return ret;
}

/**
 * Find the predecessor (less than, relative to predicate) node of the given node.
 */
static inline
rb_result_t rb_tree_find_predecessor(struct rb_tree *tree,
                                     struct rb_tree_node *node,
                                     struct rb_tree_node **pred)
{
    rb_result_t ret = RB_OK;
    struct rb_tree_node *x = node;

    RB_ASSERT_ARG(tree != NULL);
    RB_ASSERT_ARG(node != NULL);
    RB_ASSERT_ARG(pred != NULL);

    if (x->left != NULL) {
        __rb_tree_find_maximum(x->left, pred);
        goto done;
    }

    struct rb_tree_node *y = x->parent;

    while (y != NULL && (x == y->left)) {
        x = y;
        y = y->parent;
    }

    *pred = y;

done:
    return ret;
}

/**@} rb_functions */

#ifdef __cplusplus
} // extern "C"
#endif /* __cplusplus */

#endif /* __INCLUDED_RBTREE_H__ */