Add a red-black tree implementation

The code comes from David Gwynne <[email protected]>.
The same implmentation can be found in OpenBSD.

Several minor adjustments have been done to include the code
into OpenSSL:
 * the prefix has been changed to OSSL_RBT_,
 * the support augment is removed,
 * _RBT_CHECK()/_RBT_POISON() got removed too,
 * _RB_REMOVE() resets link pointer to NULL in debug build,

The documentation is based on tree(3) from OpenBSD, originally authored
by Niels Provos <[email protected]>.

Co-Authoerd-by: David Gwynne <[email protected]>
Co-Authored-by: Niels Provos <[email protected]>
Co-Authored-by: Andrew Dinh <[email protected]>

Reviewed-by: Eugene Syromiatnikov <[email protected]>
Reviewed-by: Bob Beck <[email protected]>
Reviewed-by: Norbert Pocs <[email protected]>
MergeDate: Tue Aug 11 19:15:59 2026
(Merged from https://github.com/openssl/openssl/pull/32033)

1 files changed, 265 insertions, 0 deletions

diff --git a/include/internal/ossl_rbtree.h b/include/internal/ossl_rbtree.h
new file mode 100644
index 00000000000..053ed99478b
--- /dev/null
+++ b/include/internal/ossl_rbtree.h
@@ -0,0 +1,265 @@
+/*
+ * Copyright 2026 The OpenSSL Project Authors. All Rights Reserved.
+ * Copyright (c) 2016 David Gwynne <[email protected]>
+ *
+ * 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 <[email protected]>. 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_ */