/src/openssl/include/internal/ossl_rbtree.h

Source
/*
 * Copyright 2026 The OpenSSL Project Authors. All Rights Reserved.
 * Copyright (c) 2016 David Gwynne <david@gwynne.id.au>
 *
 * Licensed under the Apache License 2.0 (the "License").  You may not use
 * this file except in compliance with the License.  You can obtain a copy
 * in the file LICENSE in the source distribution or at
 * https://www.openssl.org/source/license.html
 */

/*
 * The code here comes from David Gwynne <david@gwynne.id.au>. The original
 * version can be found:
 *    https://github.com/dgwynne/data-structures/
 * file bst.h. The same code is also part of OpenBSD OS where it is shipped
 * under BSD license.
 *
 * David Gwynne agrees to include modified version to OpenSSL and ship it
 * under OpenSSL Apache 2.0 license.
 */
#ifndef _OSSL_INTERNAL_RBTREE_H_
#define _OSSL_INTERNAL_RBTREE_H_

#include "internal/e_os.h"

/*
 * List of changes against upstream version:
 *   augmentation mechanism is removed in OpenSSL as there is no demand for it
 *
 *   prefix changed from rb/rbt to ossl_rbt
 *
 *   debug version of OSSL_RBT_REMOVE() sets parent, left, right members
 *   to NULL
 *
 *   cstyle is changed to match OpenSSL.
 */
struct ossl_rbt_type {
    int (*t_compare)(const void *, const void *);
    uintptr_t t_offset; /* offset of ossl_rbt_entry in type */
};

struct ossl_rbt_tree {
    struct ossl_rbt_entry *rb_root;
};

struct ossl_rbt_entry {
    struct ossl_rbt_entry *rb_parent;
    struct ossl_rbt_entry *rb_left;
    struct ossl_rbt_entry *rb_right;
    unsigned int rb_color;
};

#define OSSL_RBT_HEAD(_name, _type)    \
    struct _name {                     \
        struct ossl_rbt_tree rbh_root; \
    }

#define OSSL_RBT_ENTRY(_type) struct ossl_rbt_entry

static ossl_inline void
ossl_rbt_init(struct ossl_rbt_tree *rb)
{
    rb->rb_root = NULL;
}

static ossl_inline int
ossl_rbt_empty(struct ossl_rbt_tree *rb)
{
    return rb->rb_root == NULL;
}

void *ossl_rbt_insert(const struct ossl_rbt_type *, struct ossl_rbt_tree *, void *);
void *ossl_rbt_remove(const struct ossl_rbt_type *, struct ossl_rbt_tree *, void *);
void *ossl_rbt_find(const struct ossl_rbt_type *, struct ossl_rbt_tree *, const void *);
void *ossl_rbt_nfind(const struct ossl_rbt_type *, struct ossl_rbt_tree *, const void *);
void *ossl_rbt_root(const struct ossl_rbt_type *, struct ossl_rbt_tree *);
void *ossl_rbt_min(const struct ossl_rbt_type *, struct ossl_rbt_tree *);
void *ossl_rbt_max(const struct ossl_rbt_type *, struct ossl_rbt_tree *);
void *ossl_rbt_next(const struct ossl_rbt_type *, void *);
void *ossl_rbt_prev(const struct ossl_rbt_type *, void *);
void *ossl_rbt_left(const struct ossl_rbt_type *, void *);
void *ossl_rbt_right(const struct ossl_rbt_type *, void *);
void *ossl_rbt_parent(const struct ossl_rbt_type *, void *);
void ossl_rbt_set_left(const struct ossl_rbt_type *, void *, void *);
void ossl_rbt_set_right(const struct ossl_rbt_type *, void *, void *);
void ossl_rbt_set_parent(const struct ossl_rbt_type *, void *, void *);
void ossl_rbt_init_rbe(const struct ossl_rbt_type *, void *);

#define OSSL_RBT_INITIALIZER(_head) \
    {                               \
        {                           \
            NULL                    \
        }                           \
    }

#define OSSL_RBT_PROTOTYPE(_name, _type, _field, _cmp)                       \
    extern const struct ossl_rbt_type *const _name##_OSSL_RBT_TYPE;          \
                                                                             \
    ossl_unused static ossl_inline void                                      \
    _name##_OSSL_RBT_INIT(struct _name *head)                                \
    {                                                                        \
        ossl_rbt_init(&head->rbh_root);                                      \
    }                                                                        \
                                                                             \
    ossl_unused static ossl_inline struct _type *                            \
    _name##_OSSL_RBT_INSERT(struct _name *head, struct _type *elm)           \
    {                                                                        \
        return ossl_rbt_insert(_name##_OSSL_RBT_TYPE, &head->rbh_root, elm); \
    }                                                                        \
                                                                             \
    ossl_unused static ossl_inline struct _type *                            \
    _name##_OSSL_RBT_REMOVE(struct _name *head, struct _type *elm)           \
    {                                                                        \
        return ossl_rbt_remove(_name##_OSSL_RBT_TYPE, &head->rbh_root, elm); \
    }                                                                        \
                                                                             \
    ossl_unused static ossl_inline struct _type *                            \
    _name##_OSSL_RBT_FIND(struct _name *head, const struct _type *key)       \
    {                                                                        \
        return ossl_rbt_find(_name##_OSSL_RBT_TYPE, &head->rbh_root, key);   \
    }                                                                        \
                                                                             \
    ossl_unused static ossl_inline struct _type *                            \
    _name##_OSSL_RBT_NFIND(struct _name *head, const struct _type *key)      \
    {                                                                        \
        return ossl_rbt_nfind(_name##_OSSL_RBT_TYPE, &head->rbh_root, key);  \
    }                                                                        \
                                                                             \
    ossl_unused static ossl_inline struct _type *                            \
    _name##_OSSL_RBT_ROOT(struct _name *head)                                \
    {                                                                        \
        return ossl_rbt_root(_name##_OSSL_RBT_TYPE, &head->rbh_root);        \
    }                                                                        \
                                                                             \
    ossl_unused static ossl_inline int                                       \
    _name##_OSSL_RBT_EMPTY(struct _name *head)                               \
    {                                                                        \
        return ossl_rbt_empty(&head->rbh_root);                              \
    }                                                                        \
                                                                             \
    ossl_unused static ossl_inline struct _type *                            \
    _name##_OSSL_RBT_MIN(struct _name *head)                                 \
    {                                                                        \
        return ossl_rbt_min(_name##_OSSL_RBT_TYPE, &head->rbh_root);         \
    }                                                                        \
                                                                             \
    ossl_unused static ossl_inline struct _type *                            \
    _name##_OSSL_RBT_MAX(struct _name *head)                                 \
    {                                                                        \
        return ossl_rbt_max(_name##_OSSL_RBT_TYPE, &head->rbh_root);         \
    }                                                                        \
                                                                             \
    ossl_unused static ossl_inline struct _type *                            \
    _name##_OSSL_RBT_NEXT(struct _type *elm)                                 \
    {                                                                        \
        return ossl_rbt_next(_name##_OSSL_RBT_TYPE, elm);                    \
    }                                                                        \
                                                                             \
    ossl_unused static ossl_inline struct _type *                            \
    _name##_OSSL_RBT_PREV(struct _type *elm)                                 \
    {                                                                        \
        return ossl_rbt_prev(_name##_OSSL_RBT_TYPE, elm);                    \
    }                                                                        \
                                                                             \
    ossl_unused static ossl_inline struct _type *                            \
    _name##_OSSL_RBT_LEFT(struct _type *elm)                                 \
    {                                                                        \
        return ossl_rbt_left(_name##_OSSL_RBT_TYPE, elm);                    \
    }                                                                        \
                                                                             \
    ossl_unused static ossl_inline struct _type *                            \
    _name##_OSSL_RBT_RIGHT(struct _type *elm)                                \
    {                                                                        \
        return ossl_rbt_right(_name##_OSSL_RBT_TYPE, elm);                   \
    }                                                                        \
                                                                             \
    ossl_unused static ossl_inline struct _type *                            \
    _name##_OSSL_RBT_PARENT(struct _type *elm)                               \
    {                                                                        \
        return ossl_rbt_parent(_name##_OSSL_RBT_TYPE, elm);                  \
    }                                                                        \
                                                                             \
    ossl_unused static ossl_inline void                                      \
    _name##_OSSL_RBT_SET_LEFT(struct _type *elm, struct _type *left)         \
    {                                                                        \
        ossl_rbt_set_left(_name##_OSSL_RBT_TYPE, elm, left);                 \
    }                                                                        \
                                                                             \
    ossl_unused static ossl_inline void                                      \
    _name##_OSSL_RBT_SET_RIGHT(struct _type *elm, struct _type *right)       \
    {                                                                        \
        ossl_rbt_set_right(_name##_OSSL_RBT_TYPE, elm, right);               \
    }                                                                        \
                                                                             \
    ossl_unused static ossl_inline void                                      \
    _name##_OSSL_RBT_SET_PARENT(struct _type *elm, struct _type *parent)     \
    {                                                                        \
        ossl_rbt_set_parent(_name##_OSSL_RBT_TYPE, elm, parent);             \
    }                                                                        \
    ossl_unused static ossl_inline void                                      \
    _name##_OSSL_RBT_INIT_RBE(struct _type *elm)                             \
    {                                                                        \
        ossl_rbt_init_rbe(_name##_OSSL_RBT_TYPE, elm);                       \
    }

#define OSSL_RBT_GENERATE_INTERNAL(_name, _type, _field, _cmp)   \
    static int                                                   \
    _name##_OSSL_RBT_COMPARE(const void *lptr, const void *rptr) \
    {                                                            \
        const struct _type *l = lptr, *r = rptr;                 \
        return _cmp(l, r);                                       \
    }                                                            \
    static const struct ossl_rbt_type _name##_OSSL_RBT_INFO = {  \
        _name##_OSSL_RBT_COMPARE,                                \
        offsetof(struct _type, _field),                          \
    };                                                           \
    const struct ossl_rbt_type *const _name##_OSSL_RBT_TYPE = &_name##_OSSL_RBT_INFO

#define OSSL_RBT_GENERATE(_name, _type, _field, _cmp) \
    OSSL_RBT_GENERATE_INTERNAL(_name, _type, _field, _cmp)

#define OSSL_RBT_INIT(_name, _head) _name##_OSSL_RBT_INIT(_head)
#define OSSL_RBT_INSERT(_name, _head, _elm) _name##_OSSL_RBT_INSERT(_head, _elm)
#define OSSL_RBT_REMOVE(_name, _head, _elm) _name##_OSSL_RBT_REMOVE(_head, _elm)
#define OSSL_RBT_FIND(_name, _head, _key) _name##_OSSL_RBT_FIND(_head, _key)
#define OSSL_RBT_NFIND(_name, _head, _key) _name##_OSSL_RBT_NFIND(_head, _key)
#define OSSL_RBT_ROOT(_name, _head) _name##_OSSL_RBT_ROOT(_head)
#define OSSL_RBT_EMPTY(_name, _head) _name##_OSSL_RBT_EMPTY(_head)
#define OSSL_RBT_MIN(_name, _head) _name##_OSSL_RBT_MIN(_head)
#define OSSL_RBT_MAX(_name, _head) _name##_OSSL_RBT_MAX(_head)
#define OSSL_RBT_NEXT(_name, _elm) _name##_OSSL_RBT_NEXT(_elm)
#define OSSL_RBT_PREV(_name, _elm) _name##_OSSL_RBT_PREV(_elm)
#define OSSL_RBT_LEFT(_name, _elm) _name##_OSSL_RBT_LEFT(_elm)
#define OSSL_RBT_RIGHT(_name, _elm) _name##_OSSL_RBT_RIGHT(_elm)
#define OSSL_RBT_PARENT(_name, _elm) _name##_OSSL_RBT_PARENT(_elm)
#define OSSL_RBT_SET_LEFT(_name, _elm, _l) _name##_OSSL_RBT_SET_LEFT(_elm, _l)
#define OSSL_RBT_SET_RIGHT(_name, _elm, _r) _name##_OSSL_RBT_SET_RIGHT(_elm, _r)
#define OSSL_RBT_SET_PARENT(_name, _elm, _p) _name##_OSSL_RBT_SET_PARENT(_elm, _p)
#ifndef NDEBUG
#define OSSL_RBT_INIT_RBE(_name, _elm) _name##_OSSL_RBT_INIT_RBE(_elm)
#else
#define OSSL_RBT_INIT_RBE(_name, _elm) (void)(0)
#endif

#define OSSL_RBT_FOREACH(_e, _name, _head)    \
    for ((_e) = OSSL_RBT_MIN(_name, (_head)); \
        (_e) != NULL;                         \
        (_e) = OSSL_RBT_NEXT(_name, (_e)))

#define OSSL_RBT_FOREACH_SAFE(_e, _name, _head, _n)             \
    for ((_e) = OSSL_RBT_MIN(_name, (_head));                   \
        (_e) != NULL && ((_n) = OSSL_RBT_NEXT(_name, (_e)), 1); \
        (_e) = (_n))

#define OSSL_RBT_FOREACH_REVERSE(_e, _name, _head) \
    for ((_e) = OSSL_RBT_MAX(_name, (_head));      \
        (_e) != NULL;                              \
        (_e) = OSSL_RBT_PREV(_name, (_e)))

#define OSSL_RBT_FOREACH_REVERSE_SAFE(_e, _name, _head, _n)     \
    for ((_e) = OSSL_RBT_MAX(_name, (_head));                   \
        (_e) != NULL && ((_n) = OSSL_RBT_PREV(_name, (_e)), 1); \
        (_e) = (_n))

#endif /* _OSSL_INTERNAL_RBTREE_H_ */

Coverage Report

Created: 2026-10-16 07:31

Line	Count	Source
1		/*
2		* Copyright 2026 The OpenSSL Project Authors. All Rights Reserved.
3		* Copyright (c) 2016 David Gwynne <david@gwynne.id.au>
4		*
5		* Licensed under the Apache License 2.0 (the "License"). You may not use
6		* this file except in compliance with the License. You can obtain a copy
7		* in the file LICENSE in the source distribution or at
8		* https://www.openssl.org/source/license.html
9		*/
10
11		/*
12		* The code here comes from David Gwynne <david@gwynne.id.au>. The original
13		* version can be found:
14		* https://github.com/dgwynne/data-structures/
15		* file bst.h. The same code is also part of OpenBSD OS where it is shipped
16		* under BSD license.
17		*
18		* David Gwynne agrees to include modified version to OpenSSL and ship it
19		* under OpenSSL Apache 2.0 license.
20		*/
21		#ifndef _OSSL_INTERNAL_RBTREE_H_
22		#define _OSSL_INTERNAL_RBTREE_H_
23
24		#include "internal/e_os.h"
25
26		/*
27		* List of changes against upstream version:
28		* augmentation mechanism is removed in OpenSSL as there is no demand for it
29		*
30		* prefix changed from rb/rbt to ossl_rbt
31		*
32		* debug version of OSSL_RBT_REMOVE() sets parent, left, right members
33		* to NULL
34		*
35		* cstyle is changed to match OpenSSL.
36		*/
37		struct ossl_rbt_type {
38		int (t_compare)(const void , const void *);
39		uintptr_t t_offset; /* offset of ossl_rbt_entry in type */
40		};
41
42		struct ossl_rbt_tree {
43		struct ossl_rbt_entry *rb_root;
44		};
45
46		struct ossl_rbt_entry {
47		struct ossl_rbt_entry *rb_parent;
48		struct ossl_rbt_entry *rb_left;
49		struct ossl_rbt_entry *rb_right;
50		unsigned int rb_color;
51		};
52
53		#define OSSL_RBT_HEAD(_name, _type) \
54		struct _name { \
55		struct ossl_rbt_tree rbh_root; \
56		}
57
58		#define OSSL_RBT_ENTRY(_type) struct ossl_rbt_entry
59
60		static ossl_inline void
61		ossl_rbt_init(struct ossl_rbt_tree *rb)
62	0	{
63	0	rb->rb_root = NULL;
64	0	} Unexecuted instantiation: quic_rstream.c:ossl_rbt_init Unexecuted instantiation: quic_strm_reas.c:ossl_rbt_init Unexecuted instantiation: rbtree.c:ossl_rbt_init
65
66		static ossl_inline int
67		ossl_rbt_empty(struct ossl_rbt_tree *rb)
68	0	{
69	0	return rb->rb_root == NULL;
70	0	} Unexecuted instantiation: quic_rstream.c:ossl_rbt_empty Unexecuted instantiation: quic_strm_reas.c:ossl_rbt_empty Unexecuted instantiation: rbtree.c:ossl_rbt_empty
71
72		void ossl_rbt_insert(const struct ossl_rbt_type , struct ossl_rbt_tree , void );
73		void ossl_rbt_remove(const struct ossl_rbt_type , struct ossl_rbt_tree , void );
74		void ossl_rbt_find(const struct ossl_rbt_type , struct ossl_rbt_tree , const void );
75		void ossl_rbt_nfind(const struct ossl_rbt_type , struct ossl_rbt_tree , const void );
76		void ossl_rbt_root(const struct ossl_rbt_type , struct ossl_rbt_tree *);
77		void ossl_rbt_min(const struct ossl_rbt_type , struct ossl_rbt_tree *);
78		void ossl_rbt_max(const struct ossl_rbt_type , struct ossl_rbt_tree *);
79		void ossl_rbt_next(const struct ossl_rbt_type , void *);
80		void ossl_rbt_prev(const struct ossl_rbt_type , void *);
81		void ossl_rbt_left(const struct ossl_rbt_type , void *);
82		void ossl_rbt_right(const struct ossl_rbt_type , void *);
83		void ossl_rbt_parent(const struct ossl_rbt_type , void *);
84		void ossl_rbt_set_left(const struct ossl_rbt_type , void , void *);
85		void ossl_rbt_set_right(const struct ossl_rbt_type , void , void *);
86		void ossl_rbt_set_parent(const struct ossl_rbt_type , void , void *);
87		void ossl_rbt_init_rbe(const struct ossl_rbt_type , void );
88
89		#define OSSL_RBT_INITIALIZER(_head) \
90		{ \
91		{ \
92		NULL \
93		} \
94		}
95
96		#define OSSL_RBT_PROTOTYPE(_name, _type, _field, _cmp) \
97		extern const struct ossl_rbt_type *const _name##_OSSL_RBT_TYPE; \
98		\
99		ossl_unused static ossl_inline void \
100		_name##_OSSL_RBT_INIT(struct _name *head) \
101	0	{ \
102	0	ossl_rbt_init(&head->rbh_root); \
103	0	} \
104		\
105		ossl_unused static ossl_inline struct _type * \
106		_name##_OSSL_RBT_INSERT(struct _name head, struct _type elm) \
107	0	{ \
108	0	return ossl_rbt_insert(_name##_OSSL_RBT_TYPE, &head->rbh_root, elm); \
109	0	} \
110		\
111		ossl_unused static ossl_inline struct _type * \
112		_name##_OSSL_RBT_REMOVE(struct _name head, struct _type elm) \
113	0	{ \
114	0	return ossl_rbt_remove(_name##_OSSL_RBT_TYPE, &head->rbh_root, elm); \
115	0	} \
116		\
117		ossl_unused static ossl_inline struct _type * \
118		_name##_OSSL_RBT_FIND(struct _name head, const struct _type key) \
119	0	{ \
120	0	return ossl_rbt_find(_name##_OSSL_RBT_TYPE, &head->rbh_root, key); \
121	0	} \
122		\
123		ossl_unused static ossl_inline struct _type * \
124		_name##_OSSL_RBT_NFIND(struct _name head, const struct _type key) \
125	0	{ \
126	0	return ossl_rbt_nfind(_name##_OSSL_RBT_TYPE, &head->rbh_root, key); \
127	0	} \
128		\
129		ossl_unused static ossl_inline struct _type * \
130		_name##_OSSL_RBT_ROOT(struct _name *head) \
131	0	{ \
132	0	return ossl_rbt_root(_name##_OSSL_RBT_TYPE, &head->rbh_root); \
133	0	} \
134		\
135		ossl_unused static ossl_inline int \
136		_name##_OSSL_RBT_EMPTY(struct _name *head) \
137	0	{ \
138	0	return ossl_rbt_empty(&head->rbh_root); \
139	0	} \
140		\
141		ossl_unused static ossl_inline struct _type * \
142		_name##_OSSL_RBT_MIN(struct _name *head) \
143	0	{ \
144	0	return ossl_rbt_min(_name##_OSSL_RBT_TYPE, &head->rbh_root); \
145	0	} \
146		\
147		ossl_unused static ossl_inline struct _type * \
148		_name##_OSSL_RBT_MAX(struct _name *head) \
149	0	{ \
150	0	return ossl_rbt_max(_name##_OSSL_RBT_TYPE, &head->rbh_root); \
151	0	} \
152		\
153		ossl_unused static ossl_inline struct _type * \
154		_name##_OSSL_RBT_NEXT(struct _type *elm) \
155	0	{ \
156	0	return ossl_rbt_next(_name##_OSSL_RBT_TYPE, elm); \
157	0	} \
158		\
159		ossl_unused static ossl_inline struct _type * \
160		_name##_OSSL_RBT_PREV(struct _type *elm) \
161	0	{ \
162	0	return ossl_rbt_prev(_name##_OSSL_RBT_TYPE, elm); \
163	0	} \
164		\
165		ossl_unused static ossl_inline struct _type * \
166		_name##_OSSL_RBT_LEFT(struct _type *elm) \
167	0	{ \
168	0	return ossl_rbt_left(_name##_OSSL_RBT_TYPE, elm); \
169	0	} \
170		\
171		ossl_unused static ossl_inline struct _type * \
172		_name##_OSSL_RBT_RIGHT(struct _type *elm) \
173	0	{ \
174	0	return ossl_rbt_right(_name##_OSSL_RBT_TYPE, elm); \
175	0	} \
176		\
177		ossl_unused static ossl_inline struct _type * \
178		_name##_OSSL_RBT_PARENT(struct _type *elm) \
179	0	{ \
180	0	return ossl_rbt_parent(_name##_OSSL_RBT_TYPE, elm); \
181	0	} \
182		\
183		ossl_unused static ossl_inline void \
184		_name##_OSSL_RBT_SET_LEFT(struct _type elm, struct _type left) \
185	0	{ \
186	0	ossl_rbt_set_left(_name##_OSSL_RBT_TYPE, elm, left); \
187	0	} \
188		\
189		ossl_unused static ossl_inline void \
190		_name##_OSSL_RBT_SET_RIGHT(struct _type elm, struct _type right) \
191	0	{ \
192	0	ossl_rbt_set_right(_name##_OSSL_RBT_TYPE, elm, right); \
193	0	} \
194		\
195		ossl_unused static ossl_inline void \
196		_name##_OSSL_RBT_SET_PARENT(struct _type elm, struct _type parent) \
197	0	{ \
198	0	ossl_rbt_set_parent(_name##_OSSL_RBT_TYPE, elm, parent); \
199	0	} \
200		ossl_unused static ossl_inline void \
201		_name##_OSSL_RBT_INIT_RBE(struct _type *elm) \
202	0	{ \
203	0	ossl_rbt_init_rbe(_name##_OSSL_RBT_TYPE, elm); \
204	0	}
205
206		#define OSSL_RBT_GENERATE_INTERNAL(_name, _type, _field, _cmp) \
207		static int \
208		_name##_OSSL_RBT_COMPARE(const void lptr, const void rptr) \
209	0	{ \
210	0	const struct _type l = lptr, r = rptr; \
211	0	return _cmp(l, r); \
212	0	} \
213		static const struct ossl_rbt_type _name##_OSSL_RBT_INFO = { \
214		_name##_OSSL_RBT_COMPARE, \
215		offsetof(struct _type, _field), \
216		}; \
217		const struct ossl_rbt_type *const _name##_OSSL_RBT_TYPE = &_name##_OSSL_RBT_INFO
218
219		#define OSSL_RBT_GENERATE(_name, _type, _field, _cmp) \
220		OSSL_RBT_GENERATE_INTERNAL(_name, _type, _field, _cmp)
221
222	0	#define OSSL_RBT_INIT(_name, _head) _name##_OSSL_RBT_INIT(_head)
223	0	#define OSSL_RBT_INSERT(_name, _head, _elm) _name##_OSSL_RBT_INSERT(_head, _elm)
224	0	#define OSSL_RBT_REMOVE(_name, _head, _elm) _name##_OSSL_RBT_REMOVE(_head, _elm)
225	0	#define OSSL_RBT_FIND(_name, _head, _key) _name##_OSSL_RBT_FIND(_head, _key)
226		#define OSSL_RBT_NFIND(_name, _head, _key) _name##_OSSL_RBT_NFIND(_head, _key)
227		#define OSSL_RBT_ROOT(_name, _head) _name##_OSSL_RBT_ROOT(_head)
228	0	#define OSSL_RBT_EMPTY(_name, _head) _name##_OSSL_RBT_EMPTY(_head)
229	0	#define OSSL_RBT_MIN(_name, _head) _name##_OSSL_RBT_MIN(_head)
230	0	#define OSSL_RBT_MAX(_name, _head) _name##_OSSL_RBT_MAX(_head)
231	0	#define OSSL_RBT_NEXT(_name, _elm) _name##_OSSL_RBT_NEXT(_elm)
232		#define OSSL_RBT_PREV(_name, _elm) _name##_OSSL_RBT_PREV(_elm)
233		#define OSSL_RBT_LEFT(_name, _elm) _name##_OSSL_RBT_LEFT(_elm)
234		#define OSSL_RBT_RIGHT(_name, _elm) _name##_OSSL_RBT_RIGHT(_elm)
235		#define OSSL_RBT_PARENT(_name, _elm) _name##_OSSL_RBT_PARENT(_elm)
236		#define OSSL_RBT_SET_LEFT(_name, _elm, _l) _name##_OSSL_RBT_SET_LEFT(_elm, _l)
237		#define OSSL_RBT_SET_RIGHT(_name, _elm, _r) _name##_OSSL_RBT_SET_RIGHT(_elm, _r)
238		#define OSSL_RBT_SET_PARENT(_name, _elm, _p) _name##_OSSL_RBT_SET_PARENT(_elm, _p)
239		#ifndef NDEBUG
240		#define OSSL_RBT_INIT_RBE(_name, _elm) _name##_OSSL_RBT_INIT_RBE(_elm)
241		#else
242		#define OSSL_RBT_INIT_RBE(_name, _elm) (void)(0)
243		#endif
244
245		#define OSSL_RBT_FOREACH(_e, _name, _head) \
246		for ((_e) = OSSL_RBT_MIN(_name, (_head)); \
247		(_e) != NULL; \
248		(_e) = OSSL_RBT_NEXT(_name, (_e)))
249
250		#define OSSL_RBT_FOREACH_SAFE(_e, _name, _head, _n) \
251	0	for ((_e) = OSSL_RBT_MIN(_name, (_head)); \
252	0	(_e) != NULL && ((_n) = OSSL_RBT_NEXT(_name, (_e)), 1); \
253	0	(_e) = (_n))
254
255		#define OSSL_RBT_FOREACH_REVERSE(_e, _name, _head) \
256		for ((_e) = OSSL_RBT_MAX(_name, (_head)); \
257		(_e) != NULL; \
258		(_e) = OSSL_RBT_PREV(_name, (_e)))
259
260		#define OSSL_RBT_FOREACH_REVERSE_SAFE(_e, _name, _head, _n) \
261		for ((_e) = OSSL_RBT_MAX(_name, (_head)); \
262		(_e) != NULL && ((_n) = OSSL_RBT_PREV(_name, (_e)), 1); \
263		(_e) = (_n))
264
265		#endif /* _OSSL_INTERNAL_RBTREE_H_ */