/src/openssl36/crypto/rbtree/rbtree.c

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

#include "internal/ossl_rbtree.h"

#ifndef NDEBUG
#include <assert.h>
#endif

#define OSSL_RBT_BLACK 0
#define OSSL_RBT_RED 1

static struct ossl_rbt_entry *
rbt_n2e(const struct ossl_rbt_type *t, void *node)
{
    uintptr_t addr = (uintptr_t)node;

    return (struct ossl_rbt_entry *)(addr + t->t_offset);
}

static void *
rbt_e2n(const struct ossl_rbt_type *t, struct ossl_rbt_entry *rbe)
{
    uintptr_t addr = (uintptr_t)rbe;

    return (void *)(addr - t->t_offset);
}

#define OSSL_RBE_LEFT(_rbe) (_rbe)->rb_left
#define OSSL_RBE_RIGHT(_rbe) (_rbe)->rb_right
#define OSSL_RBE_PARENT(_rbe) (_rbe)->rb_parent
#define OSSL_RBE_COLOR(_rbe) (_rbe)->rb_color

#define OSSL_RBH_ROOT(_rbt) (_rbt)->rb_root

static void
rbe_set(struct ossl_rbt_entry *rbe, struct ossl_rbt_entry *parent)
{
    OSSL_RBE_PARENT(rbe) = parent;
    OSSL_RBE_LEFT(rbe) = OSSL_RBE_RIGHT(rbe) = NULL;
    OSSL_RBE_COLOR(rbe) = OSSL_RBT_RED;
}

static void
rbe_set_blackred(struct ossl_rbt_entry *black, struct ossl_rbt_entry *red)
{
    OSSL_RBE_COLOR(black) = OSSL_RBT_BLACK;
    OSSL_RBE_COLOR(red) = OSSL_RBT_RED;
}

static void
rbe_rotate_left(struct ossl_rbt_tree *rbt, struct ossl_rbt_entry *rbe)
{
    struct ossl_rbt_entry *parent;
    struct ossl_rbt_entry *tmp;

    tmp = OSSL_RBE_RIGHT(rbe);
    OSSL_RBE_RIGHT(rbe) = OSSL_RBE_LEFT(tmp);
    if (OSSL_RBE_RIGHT(rbe) != NULL)
        OSSL_RBE_PARENT(OSSL_RBE_LEFT(tmp)) = rbe;

    parent = OSSL_RBE_PARENT(rbe);
    OSSL_RBE_PARENT(tmp) = parent;
    if (parent != NULL) {
        if (rbe == OSSL_RBE_LEFT(parent))
            OSSL_RBE_LEFT(parent) = tmp;
        else
            OSSL_RBE_RIGHT(parent) = tmp;
    } else
        OSSL_RBH_ROOT(rbt) = tmp;

    OSSL_RBE_LEFT(tmp) = rbe;
    OSSL_RBE_PARENT(rbe) = tmp;
}

static void
rbe_rotate_right(struct ossl_rbt_tree *rbt, struct ossl_rbt_entry *rbe)
{
    struct ossl_rbt_entry *parent;
    struct ossl_rbt_entry *tmp;

    tmp = OSSL_RBE_LEFT(rbe);
    OSSL_RBE_LEFT(rbe) = OSSL_RBE_RIGHT(tmp);
    if (OSSL_RBE_LEFT(rbe) != NULL)
        OSSL_RBE_PARENT(OSSL_RBE_RIGHT(tmp)) = rbe;

    parent = OSSL_RBE_PARENT(rbe);
    OSSL_RBE_PARENT(tmp) = parent;
    if (parent != NULL) {
        if (rbe == OSSL_RBE_LEFT(parent))
            OSSL_RBE_LEFT(parent) = tmp;
        else
            OSSL_RBE_RIGHT(parent) = tmp;
    } else
        OSSL_RBH_ROOT(rbt) = tmp;

    OSSL_RBE_RIGHT(tmp) = rbe;
    OSSL_RBE_PARENT(rbe) = tmp;
}

static void
rbe_insert_color(struct ossl_rbt_tree *rbt, struct ossl_rbt_entry *rbe)
{
    struct ossl_rbt_entry *parent, *gparent, *tmp;

    while ((parent = OSSL_RBE_PARENT(rbe)) != NULL && OSSL_RBE_COLOR(parent) == OSSL_RBT_RED) {
        gparent = OSSL_RBE_PARENT(parent);

        if (parent == OSSL_RBE_LEFT(gparent)) {
            tmp = OSSL_RBE_RIGHT(gparent);
            if (tmp != NULL && OSSL_RBE_COLOR(tmp) == OSSL_RBT_RED) {
                OSSL_RBE_COLOR(tmp) = OSSL_RBT_BLACK;
                rbe_set_blackred(parent, gparent);
                rbe = gparent;
                continue;
            }

            if (OSSL_RBE_RIGHT(parent) == rbe) {
                rbe_rotate_left(rbt, parent);
                tmp = parent;
                parent = rbe;
                rbe = tmp;
            }

            rbe_set_blackred(parent, gparent);
            rbe_rotate_right(rbt, gparent);
        } else {
            tmp = OSSL_RBE_LEFT(gparent);
            if (tmp != NULL && OSSL_RBE_COLOR(tmp) == OSSL_RBT_RED) {
                OSSL_RBE_COLOR(tmp) = OSSL_RBT_BLACK;
                rbe_set_blackred(parent, gparent);
                rbe = gparent;
                continue;
            }

            if (OSSL_RBE_LEFT(parent) == rbe) {
                rbe_rotate_right(rbt, parent);
                tmp = parent;
                parent = rbe;
                rbe = tmp;
            }

            rbe_set_blackred(parent, gparent);
            rbe_rotate_left(rbt, gparent);
        }
    }

    OSSL_RBE_COLOR(OSSL_RBH_ROOT(rbt)) = OSSL_RBT_BLACK;
}

static void
rbe_remove_color(struct ossl_rbt_tree *rbt,
    struct ossl_rbt_entry *parent, struct ossl_rbt_entry *rbe)
{
    struct ossl_rbt_entry *tmp;

    while ((rbe == NULL || OSSL_RBE_COLOR(rbe) == OSSL_RBT_BLACK) && rbe != OSSL_RBH_ROOT(rbt)) {
        if (OSSL_RBE_LEFT(parent) == rbe) {
            tmp = OSSL_RBE_RIGHT(parent);
            if (OSSL_RBE_COLOR(tmp) == OSSL_RBT_RED) {
                rbe_set_blackred(tmp, parent);
                rbe_rotate_left(rbt, parent);
                tmp = OSSL_RBE_RIGHT(parent);
            }
            if ((OSSL_RBE_LEFT(tmp) == NULL || OSSL_RBE_COLOR(OSSL_RBE_LEFT(tmp)) == OSSL_RBT_BLACK) && (OSSL_RBE_RIGHT(tmp) == NULL || OSSL_RBE_COLOR(OSSL_RBE_RIGHT(tmp)) == OSSL_RBT_BLACK)) {
                OSSL_RBE_COLOR(tmp) = OSSL_RBT_RED;
                rbe = parent;
                parent = OSSL_RBE_PARENT(rbe);
            } else {
                if (OSSL_RBE_RIGHT(tmp) == NULL || OSSL_RBE_COLOR(OSSL_RBE_RIGHT(tmp)) == OSSL_RBT_BLACK) {
                    struct ossl_rbt_entry *oleft;

                    oleft = OSSL_RBE_LEFT(tmp);
                    if (oleft != NULL)
                        OSSL_RBE_COLOR(oleft) = OSSL_RBT_BLACK;

                    OSSL_RBE_COLOR(tmp) = OSSL_RBT_RED;
                    rbe_rotate_right(rbt, tmp);
                    tmp = OSSL_RBE_RIGHT(parent);
                }

                OSSL_RBE_COLOR(tmp) = OSSL_RBE_COLOR(parent);
                OSSL_RBE_COLOR(parent) = OSSL_RBT_BLACK;
                if (OSSL_RBE_RIGHT(tmp))
                    OSSL_RBE_COLOR(OSSL_RBE_RIGHT(tmp)) = OSSL_RBT_BLACK;

                rbe_rotate_left(rbt, parent);
                rbe = OSSL_RBH_ROOT(rbt);
                break;
            }
        } else {
            tmp = OSSL_RBE_LEFT(parent);
            if (OSSL_RBE_COLOR(tmp) == OSSL_RBT_RED) {
                rbe_set_blackred(tmp, parent);
                rbe_rotate_right(rbt, parent);
                tmp = OSSL_RBE_LEFT(parent);
            }

            if ((OSSL_RBE_LEFT(tmp) == NULL || OSSL_RBE_COLOR(OSSL_RBE_LEFT(tmp)) == OSSL_RBT_BLACK) && (OSSL_RBE_RIGHT(tmp) == NULL || OSSL_RBE_COLOR(OSSL_RBE_RIGHT(tmp)) == OSSL_RBT_BLACK)) {
                OSSL_RBE_COLOR(tmp) = OSSL_RBT_RED;
                rbe = parent;
                parent = OSSL_RBE_PARENT(rbe);
            } else {
                if (OSSL_RBE_LEFT(tmp) == NULL || OSSL_RBE_COLOR(OSSL_RBE_LEFT(tmp)) == OSSL_RBT_BLACK) {
                    struct ossl_rbt_entry *oright;

                    oright = OSSL_RBE_RIGHT(tmp);
                    if (oright != NULL)
                        OSSL_RBE_COLOR(oright) = OSSL_RBT_BLACK;

                    OSSL_RBE_COLOR(tmp) = OSSL_RBT_RED;
                    rbe_rotate_left(rbt, tmp);
                    tmp = OSSL_RBE_LEFT(parent);
                }

                OSSL_RBE_COLOR(tmp) = OSSL_RBE_COLOR(parent);
                OSSL_RBE_COLOR(parent) = OSSL_RBT_BLACK;
                if (OSSL_RBE_LEFT(tmp) != NULL)
                    OSSL_RBE_COLOR(OSSL_RBE_LEFT(tmp)) = OSSL_RBT_BLACK;

                rbe_rotate_right(rbt, parent);
                rbe = OSSL_RBH_ROOT(rbt);
                break;
            }
        }
    }

    if (rbe != NULL)
        OSSL_RBE_COLOR(rbe) = OSSL_RBT_BLACK;
}

static struct ossl_rbt_entry *
rbe_remove(struct ossl_rbt_tree *rbt, struct ossl_rbt_entry *rbe)
{
    struct ossl_rbt_entry *child, *parent, *old = rbe;
    unsigned int color;

    if (OSSL_RBE_LEFT(rbe) == NULL)
        child = OSSL_RBE_RIGHT(rbe);
    else if (OSSL_RBE_RIGHT(rbe) == NULL)
        child = OSSL_RBE_LEFT(rbe);
    else {
        struct ossl_rbt_entry *tmp;

        rbe = OSSL_RBE_RIGHT(rbe);
        while ((tmp = OSSL_RBE_LEFT(rbe)) != NULL)
            rbe = tmp;

        child = OSSL_RBE_RIGHT(rbe);
        parent = OSSL_RBE_PARENT(rbe);
        color = OSSL_RBE_COLOR(rbe);
        if (child != NULL)
            OSSL_RBE_PARENT(child) = parent;
        if (parent != NULL) {
            if (OSSL_RBE_LEFT(parent) == rbe)
                OSSL_RBE_LEFT(parent) = child;
            else
                OSSL_RBE_RIGHT(parent) = child;
        } else
            OSSL_RBH_ROOT(rbt) = child;
        if (OSSL_RBE_PARENT(rbe) == old)
            parent = rbe;
        *rbe = *old;

        tmp = OSSL_RBE_PARENT(old);
        if (tmp != NULL) {
            if (OSSL_RBE_LEFT(tmp) == old)
                OSSL_RBE_LEFT(tmp) = rbe;
            else
                OSSL_RBE_RIGHT(tmp) = rbe;
        } else
            OSSL_RBH_ROOT(rbt) = rbe;

        OSSL_RBE_PARENT(OSSL_RBE_LEFT(old)) = rbe;
        if (OSSL_RBE_RIGHT(old))
            OSSL_RBE_PARENT(OSSL_RBE_RIGHT(old)) = rbe;
        goto color;
    }

    parent = OSSL_RBE_PARENT(rbe);
    color = OSSL_RBE_COLOR(rbe);

    if (child != NULL)
        OSSL_RBE_PARENT(child) = parent;
    if (parent != NULL) {
        if (OSSL_RBE_LEFT(parent) == rbe)
            OSSL_RBE_LEFT(parent) = child;
        else
            OSSL_RBE_RIGHT(parent) = child;
    } else
        OSSL_RBH_ROOT(rbt) = child;
color:
    if (color == OSSL_RBT_BLACK)
        rbe_remove_color(rbt, parent, child);

#ifndef NDEBUG
    if (old != NULL) {
        OSSL_RBE_PARENT(old) = NULL;
        OSSL_RBE_LEFT(old) = NULL;
        OSSL_RBE_RIGHT(old) = NULL;
    }
#endif

    return old;
}

void *
ossl_rbt_remove(const struct ossl_rbt_type *t, struct ossl_rbt_tree *rbt, void *elm)
{
    struct ossl_rbt_entry *rbe = rbt_n2e(t, elm);
    struct ossl_rbt_entry *old;

    old = rbe_remove(rbt, rbe);

    return old == NULL ? NULL : rbt_e2n(t, old);
}

void *
ossl_rbt_insert(const struct ossl_rbt_type *t, struct ossl_rbt_tree *rbt, void *elm)
{
    struct ossl_rbt_entry *rbe = rbt_n2e(t, elm);
    struct ossl_rbt_entry *tmp;
    struct ossl_rbt_entry *parent = NULL;
    void *node;
    int comp = 0;

#ifndef NDEBUG
    assert(rbe->rb_parent == NULL);
    assert(rbe->rb_left == NULL);
    assert(rbe->rb_right == NULL);
#endif

    tmp = OSSL_RBH_ROOT(rbt);
    while (tmp != NULL) {
        parent = tmp;

        node = rbt_e2n(t, tmp);
        comp = (*t->t_compare)(elm, node);
        if (comp < 0)
            tmp = OSSL_RBE_LEFT(tmp);
        else if (comp > 0)
            tmp = OSSL_RBE_RIGHT(tmp);
        else
            return node;
    }

    rbe_set(rbe, parent);

    if (parent != NULL) {
        if (comp < 0)
            OSSL_RBE_LEFT(parent) = rbe;
        else
            OSSL_RBE_RIGHT(parent) = rbe;
    } else
        OSSL_RBH_ROOT(rbt) = rbe;

    rbe_insert_color(rbt, rbe);

    return NULL;
}

/* Finds the node with the same key as elm */
void *
ossl_rbt_find(const struct ossl_rbt_type *t, struct ossl_rbt_tree *rbt, const void *key)
{
    struct ossl_rbt_entry *tmp = OSSL_RBH_ROOT(rbt);
    void *node;
    int comp;

    while (tmp != NULL) {
        node = rbt_e2n(t, tmp);
        comp = (*t->t_compare)(key, node);
        if (comp < 0)
            tmp = OSSL_RBE_LEFT(tmp);
        else if (comp > 0)
            tmp = OSSL_RBE_RIGHT(tmp);
        else
            return node;
    }

    return NULL;
}

/* Finds the first node greater than or equal to the search key */
void *
ossl_rbt_nfind(const struct ossl_rbt_type *t, struct ossl_rbt_tree *rbt, const void *key)
{
    struct ossl_rbt_entry *tmp = OSSL_RBH_ROOT(rbt);
    void *node;
    void *res = NULL;
    int comp;

    while (tmp != NULL) {
        node = rbt_e2n(t, tmp);
        comp = (*t->t_compare)(key, node);
        if (comp < 0) {
            res = node;
            tmp = OSSL_RBE_LEFT(tmp);
        } else if (comp > 0)
            tmp = OSSL_RBE_RIGHT(tmp);
        else
            return node;
    }

    return res;
}

void *
ossl_rbt_next(const struct ossl_rbt_type *t, void *elm)
{
    struct ossl_rbt_entry *rbe = rbt_n2e(t, elm);

    if (OSSL_RBE_RIGHT(rbe) != NULL) {
        rbe = OSSL_RBE_RIGHT(rbe);
        while (OSSL_RBE_LEFT(rbe) != NULL)
            rbe = OSSL_RBE_LEFT(rbe);
    } else {
        if (OSSL_RBE_PARENT(rbe) && (rbe == OSSL_RBE_LEFT(OSSL_RBE_PARENT(rbe))))
            rbe = OSSL_RBE_PARENT(rbe);
        else {
            while (OSSL_RBE_PARENT(rbe) && (rbe == OSSL_RBE_RIGHT(OSSL_RBE_PARENT(rbe))))
                rbe = OSSL_RBE_PARENT(rbe);
            rbe = OSSL_RBE_PARENT(rbe);
        }
    }

    return rbe == NULL ? NULL : rbt_e2n(t, rbe);
}

void *
ossl_rbt_prev(const struct ossl_rbt_type *t, void *elm)
{
    struct ossl_rbt_entry *rbe = rbt_n2e(t, elm);

    if (OSSL_RBE_LEFT(rbe)) {
        rbe = OSSL_RBE_LEFT(rbe);
        while (OSSL_RBE_RIGHT(rbe))
            rbe = OSSL_RBE_RIGHT(rbe);
    } else {
        if (OSSL_RBE_PARENT(rbe) && (rbe == OSSL_RBE_RIGHT(OSSL_RBE_PARENT(rbe))))
            rbe = OSSL_RBE_PARENT(rbe);
        else {
            while (OSSL_RBE_PARENT(rbe) && (rbe == OSSL_RBE_LEFT(OSSL_RBE_PARENT(rbe))))
                rbe = OSSL_RBE_PARENT(rbe);
            rbe = OSSL_RBE_PARENT(rbe);
        }
    }

    return rbe == NULL ? NULL : rbt_e2n(t, rbe);
}

void *
ossl_rbt_root(const struct ossl_rbt_type *t, struct ossl_rbt_tree *rbt)
{
    struct ossl_rbt_entry *rbe = OSSL_RBH_ROOT(rbt);

    return rbe == NULL ? rbe : rbt_e2n(t, rbe);
}

void *
ossl_rbt_min(const struct ossl_rbt_type *t, struct ossl_rbt_tree *rbt)
{
    struct ossl_rbt_entry *rbe = OSSL_RBH_ROOT(rbt);
    struct ossl_rbt_entry *parent = NULL;

    while (rbe != NULL) {
        parent = rbe;
        rbe = OSSL_RBE_LEFT(rbe);
    }

    return parent == NULL ? NULL : rbt_e2n(t, parent);
}

void *
ossl_rbt_max(const struct ossl_rbt_type *t, struct ossl_rbt_tree *rbt)
{
    struct ossl_rbt_entry *rbe = OSSL_RBH_ROOT(rbt);
    struct ossl_rbt_entry *parent = NULL;

    while (rbe != NULL) {
        parent = rbe;
        rbe = OSSL_RBE_RIGHT(rbe);
    }

    return parent == NULL ? NULL : rbt_e2n(t, parent);
}

void *
ossl_rbt_left(const struct ossl_rbt_type *t, void *node)
{
    struct ossl_rbt_entry *rbe = rbt_n2e(t, node);
    rbe = OSSL_RBE_LEFT(rbe);
    return rbe == NULL ? NULL : rbt_e2n(t, rbe);
}

void *
ossl_rbt_right(const struct ossl_rbt_type *t, void *node)
{
    struct ossl_rbt_entry *rbe = rbt_n2e(t, node);
    rbe = OSSL_RBE_RIGHT(rbe);
    return rbe == NULL ? NULL : rbt_e2n(t, rbe);
}

void *
ossl_rbt_parent(const struct ossl_rbt_type *t, void *node)
{
    struct ossl_rbt_entry *rbe = rbt_n2e(t, node);
    rbe = OSSL_RBE_PARENT(rbe);
    return rbe == NULL ? NULL : rbt_e2n(t, rbe);
}

void ossl_rbt_set_left(const struct ossl_rbt_type *t, void *node, void *left)
{
    struct ossl_rbt_entry *rbe = rbt_n2e(t, node);
    struct ossl_rbt_entry *rbl = (left == NULL) ? NULL : rbt_n2e(t, left);

    OSSL_RBE_LEFT(rbe) = rbl;
}

void ossl_rbt_set_right(const struct ossl_rbt_type *t, void *node, void *right)
{
    struct ossl_rbt_entry *rbe = rbt_n2e(t, node);
    struct ossl_rbt_entry *rbr = (right == NULL) ? NULL : rbt_n2e(t, right);

    OSSL_RBE_RIGHT(rbe) = rbr;
}

void ossl_rbt_set_parent(const struct ossl_rbt_type *t, void *node, void *parent)
{
    struct ossl_rbt_entry *rbe = rbt_n2e(t, node);
    struct ossl_rbt_entry *rbp = (parent == NULL) ? NULL : rbt_n2e(t, parent);

    OSSL_RBE_PARENT(rbe) = rbp;
}

void ossl_rbt_init_rbe(const struct ossl_rbt_type *t, void *node)
{
    struct ossl_rbt_entry *rbe = rbt_n2e(t, node);

    OSSL_RBE_PARENT(rbe) = NULL;
    OSSL_RBE_LEFT(rbe) = NULL;
    OSSL_RBE_RIGHT(rbe) = NULL;
}

Coverage Report

Created: 2026-10-28 06:28

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
22		#include "internal/ossl_rbtree.h"
23
24		#ifndef NDEBUG
25		#include <assert.h>
26		#endif
27
28	240k	#define OSSL_RBT_BLACK 0
29	137k	#define OSSL_RBT_RED 1
30
31		static struct ossl_rbt_entry *
32		rbt_n2e(const struct ossl_rbt_type t, void node)
33	227k	{
34	227k	uintptr_t addr = (uintptr_t)node;
35
36	227k	return (struct ossl_rbt_entry *)(addr + t->t_offset);
37	227k	}
38
39		static void *
40		rbt_e2n(const struct ossl_rbt_type t, struct ossl_rbt_entry rbe)
41	29.9M	{
42	29.9M	uintptr_t addr = (uintptr_t)rbe;
43
44	29.9M	return (void *)(addr - t->t_offset);
45	29.9M	}
46
47	34.5M	#define OSSL_RBE_LEFT(_rbe) (_rbe)->rb_left
48	418k	#define OSSL_RBE_RIGHT(_rbe) (_rbe)->rb_right
49	543k	#define OSSL_RBE_PARENT(_rbe) (_rbe)->rb_parent
50	381k	#define OSSL_RBE_COLOR(_rbe) (_rbe)->rb_color
51
52	133M	#define OSSL_RBH_ROOT(_rbt) (_rbt)->rb_root
53
54		static void
55		rbe_set(struct ossl_rbt_entry rbe, struct ossl_rbt_entry parent)
56	103k	{
57	103k	OSSL_RBE_PARENT(rbe) = parent;
58	103k	OSSL_RBE_LEFT(rbe) = OSSL_RBE_RIGHT(rbe) = NULL;
59	103k	OSSL_RBE_COLOR(rbe) = OSSL_RBT_RED;
60	103k	}
61
62		static void
63		rbe_set_blackred(struct ossl_rbt_entry black, struct ossl_rbt_entry red)
64	6.25k	{
65	6.25k	OSSL_RBE_COLOR(black) = OSSL_RBT_BLACK;
66	6.25k	OSSL_RBE_COLOR(red) = OSSL_RBT_RED;
67	6.25k	}
68
69		static void
70		rbe_rotate_left(struct ossl_rbt_tree rbt, struct ossl_rbt_entry rbe)
71	4.97k	{
72	4.97k	struct ossl_rbt_entry *parent;
73	4.97k	struct ossl_rbt_entry *tmp;
74
75	4.97k	tmp = OSSL_RBE_RIGHT(rbe);
76	4.97k	OSSL_RBE_RIGHT(rbe) = OSSL_RBE_LEFT(tmp);
77	4.97k	if (OSSL_RBE_RIGHT(rbe) != NULL)
78	1.30k	OSSL_RBE_PARENT(OSSL_RBE_LEFT(tmp)) = rbe;
79
80	4.97k	parent = OSSL_RBE_PARENT(rbe);
81	4.97k	OSSL_RBE_PARENT(tmp) = parent;
82	4.97k	if (parent != NULL) {
83	3.31k	if (rbe == OSSL_RBE_LEFT(parent))
84	2.60k	OSSL_RBE_LEFT(parent) = tmp;
85	709	else
86	709	OSSL_RBE_RIGHT(parent) = tmp;
87	3.31k	} else
88	1.65k	OSSL_RBH_ROOT(rbt) = tmp;
89
90	4.97k	OSSL_RBE_LEFT(tmp) = rbe;
91	4.97k	OSSL_RBE_PARENT(rbe) = tmp;
92	4.97k	}
93
94		static void
95		rbe_rotate_right(struct ossl_rbt_tree rbt, struct ossl_rbt_entry rbe)
96	3.53k	{
97	3.53k	struct ossl_rbt_entry *parent;
98	3.53k	struct ossl_rbt_entry *tmp;
99
100	3.53k	tmp = OSSL_RBE_LEFT(rbe);
101	3.53k	OSSL_RBE_LEFT(rbe) = OSSL_RBE_RIGHT(tmp);
102	3.53k	if (OSSL_RBE_LEFT(rbe) != NULL)
103	540	OSSL_RBE_PARENT(OSSL_RBE_RIGHT(tmp)) = rbe;
104
105	3.53k	parent = OSSL_RBE_PARENT(rbe);
106	3.53k	OSSL_RBE_PARENT(tmp) = parent;
107	3.53k	if (parent != NULL) {
108	2.31k	if (rbe == OSSL_RBE_LEFT(parent))
109	646	OSSL_RBE_LEFT(parent) = tmp;
110	1.66k	else
111	1.66k	OSSL_RBE_RIGHT(parent) = tmp;
112	2.31k	} else
113	1.22k	OSSL_RBH_ROOT(rbt) = tmp;
114
115	3.53k	OSSL_RBE_RIGHT(tmp) = rbe;
116	3.53k	OSSL_RBE_PARENT(rbe) = tmp;
117	3.53k	}
118
119		static void
120		rbe_insert_color(struct ossl_rbt_tree rbt, struct ossl_rbt_entry rbe)
121	103k	{
122	103k	struct ossl_rbt_entry parent, gparent, *tmp;
123
124	109k	while ((parent = OSSL_RBE_PARENT(rbe)) != NULL && OSSL_RBE_COLOR(parent) == OSSL_RBT_RED) {
125	5.59k	gparent = OSSL_RBE_PARENT(parent);
126
127	5.59k	if (parent == OSSL_RBE_LEFT(gparent)) {
128	2.76k	tmp = OSSL_RBE_RIGHT(gparent);
129	2.76k	if (tmp != NULL && OSSL_RBE_COLOR(tmp) == OSSL_RBT_RED) {
130	1.00k	OSSL_RBE_COLOR(tmp) = OSSL_RBT_BLACK;
131	1.00k	rbe_set_blackred(parent, gparent);
132	1.00k	rbe = gparent;
133	1.00k	continue;
134	1.00k	}
135
136	1.75k	if (OSSL_RBE_RIGHT(parent) == rbe) {
137	1.31k	rbe_rotate_left(rbt, parent);
138	1.31k	tmp = parent;
139	1.31k	parent = rbe;
140	1.31k	rbe = tmp;
141	1.31k	}
142
143	1.75k	rbe_set_blackred(parent, gparent);
144	1.75k	rbe_rotate_right(rbt, gparent);
145	2.83k	} else {
146	2.83k	tmp = OSSL_RBE_LEFT(gparent);
147	2.83k	if (tmp != NULL && OSSL_RBE_COLOR(tmp) == OSSL_RBT_RED) {
148	1.41k	OSSL_RBE_COLOR(tmp) = OSSL_RBT_BLACK;
149	1.41k	rbe_set_blackred(parent, gparent);
150	1.41k	rbe = gparent;
151	1.41k	continue;
152	1.41k	}
153
154	1.41k	if (OSSL_RBE_LEFT(parent) == rbe) {
155	494	rbe_rotate_right(rbt, parent);
156	494	tmp = parent;
157	494	parent = rbe;
158	494	rbe = tmp;
159	494	}
160
161	1.41k	rbe_set_blackred(parent, gparent);
162	1.41k	rbe_rotate_left(rbt, gparent);
163	1.41k	}
164	5.59k	}
165
166	103k	OSSL_RBE_COLOR(OSSL_RBH_ROOT(rbt)) = OSSL_RBT_BLACK;
167	103k	}
168
169		static void
170		rbe_remove_color(struct ossl_rbt_tree *rbt,
171		struct ossl_rbt_entry parent, struct ossl_rbt_entry rbe)
172	99.8k	{
173	99.8k	struct ossl_rbt_entry *tmp;
174
175	102k	while ((rbe == NULL \|\| OSSL_RBE_COLOR(rbe) == OSSL_RBT_BLACK) && rbe != OSSL_RBH_ROOT(rbt)) {
176	4.56k	if (OSSL_RBE_LEFT(parent) == rbe) {
177	3.38k	tmp = OSSL_RBE_RIGHT(parent);
178	3.38k	if (OSSL_RBE_COLOR(tmp) == OSSL_RBT_RED) {
179	531	rbe_set_blackred(tmp, parent);
180	531	rbe_rotate_left(rbt, parent);
181	531	tmp = OSSL_RBE_RIGHT(parent);
182	531	}
183	3.38k	if ((OSSL_RBE_LEFT(tmp) == NULL \|\| OSSL_RBE_COLOR(OSSL_RBE_LEFT(tmp)) == OSSL_RBT_BLACK) && (OSSL_RBE_RIGHT(tmp) == NULL \|\| OSSL_RBE_COLOR(OSSL_RBE_RIGHT(tmp)) == OSSL_RBT_BLACK)) {
184	1.94k	OSSL_RBE_COLOR(tmp) = OSSL_RBT_RED;
185	1.94k	rbe = parent;
186	1.94k	parent = OSSL_RBE_PARENT(rbe);
187	1.94k	} else {
188	1.43k	if (OSSL_RBE_RIGHT(tmp) == NULL \|\| OSSL_RBE_COLOR(OSSL_RBE_RIGHT(tmp)) == OSSL_RBT_BLACK) {
189	461	struct ossl_rbt_entry *oleft;
190
191	461	oleft = OSSL_RBE_LEFT(tmp);
192	461	if (oleft != NULL)
193	461	OSSL_RBE_COLOR(oleft) = OSSL_RBT_BLACK;
194
195	461	OSSL_RBE_COLOR(tmp) = OSSL_RBT_RED;
196	461	rbe_rotate_right(rbt, tmp);
197	461	tmp = OSSL_RBE_RIGHT(parent);
198	461	}
199
200	1.43k	OSSL_RBE_COLOR(tmp) = OSSL_RBE_COLOR(parent);
201	1.43k	OSSL_RBE_COLOR(parent) = OSSL_RBT_BLACK;
202	1.43k	if (OSSL_RBE_RIGHT(tmp))
203	1.43k	OSSL_RBE_COLOR(OSSL_RBE_RIGHT(tmp)) = OSSL_RBT_BLACK;
204
205	1.43k	rbe_rotate_left(rbt, parent);
206	1.43k	rbe = OSSL_RBH_ROOT(rbt);
207	1.43k	break;
208	1.43k	}
209	3.38k	} else {
210	1.18k	tmp = OSSL_RBE_LEFT(parent);
211	1.18k	if (OSSL_RBE_COLOR(tmp) == OSSL_RBT_RED) {
212	122	rbe_set_blackred(tmp, parent);
213	122	rbe_rotate_right(rbt, parent);
214	122	tmp = OSSL_RBE_LEFT(parent);
215	122	}
216
217	1.18k	if ((OSSL_RBE_LEFT(tmp) == NULL \|\| OSSL_RBE_COLOR(OSSL_RBE_LEFT(tmp)) == OSSL_RBT_BLACK) && (OSSL_RBE_RIGHT(tmp) == NULL \|\| OSSL_RBE_COLOR(OSSL_RBE_RIGHT(tmp)) == OSSL_RBT_BLACK)) {
218	483	OSSL_RBE_COLOR(tmp) = OSSL_RBT_RED;
219	483	rbe = parent;
220	483	parent = OSSL_RBE_PARENT(rbe);
221	704	} else {
222	704	if (OSSL_RBE_LEFT(tmp) == NULL \|\| OSSL_RBE_COLOR(OSSL_RBE_LEFT(tmp)) == OSSL_RBT_BLACK) {
223	274	struct ossl_rbt_entry *oright;
224
225	274	oright = OSSL_RBE_RIGHT(tmp);
226	274	if (oright != NULL)
227	274	OSSL_RBE_COLOR(oright) = OSSL_RBT_BLACK;
228
229	274	OSSL_RBE_COLOR(tmp) = OSSL_RBT_RED;
230	274	rbe_rotate_left(rbt, tmp);
231	274	tmp = OSSL_RBE_LEFT(parent);
232	274	}
233
234	704	OSSL_RBE_COLOR(tmp) = OSSL_RBE_COLOR(parent);
235	704	OSSL_RBE_COLOR(parent) = OSSL_RBT_BLACK;
236	704	if (OSSL_RBE_LEFT(tmp) != NULL)
237	704	OSSL_RBE_COLOR(OSSL_RBE_LEFT(tmp)) = OSSL_RBT_BLACK;
238
239	704	rbe_rotate_right(rbt, parent);
240	704	rbe = OSSL_RBH_ROOT(rbt);
241	704	break;
242	704	}
243	1.18k	}
244	4.56k	}
245
246	99.8k	if (rbe != NULL)
247	8.48k	OSSL_RBE_COLOR(rbe) = OSSL_RBT_BLACK;
248	99.8k	}
249
250		static struct ossl_rbt_entry *
251		rbe_remove(struct ossl_rbt_tree rbt, struct ossl_rbt_entry rbe)
252	103k	{
253	103k	struct ossl_rbt_entry child, parent, *old = rbe;
254	103k	unsigned int color;
255
256	103k	if (OSSL_RBE_LEFT(rbe) == NULL)
257	100k	child = OSSL_RBE_RIGHT(rbe);
258	3.35k	else if (OSSL_RBE_RIGHT(rbe) == NULL)
259	611	child = OSSL_RBE_LEFT(rbe);
260	2.74k	else {
261	2.74k	struct ossl_rbt_entry *tmp;
262
263	2.74k	rbe = OSSL_RBE_RIGHT(rbe);
264	3.79k	while ((tmp = OSSL_RBE_LEFT(rbe)) != NULL)
265	1.05k	rbe = tmp;
266
267	2.74k	child = OSSL_RBE_RIGHT(rbe);
268	2.74k	parent = OSSL_RBE_PARENT(rbe);
269	2.74k	color = OSSL_RBE_COLOR(rbe);
270	2.74k	if (child != NULL)
271	460	OSSL_RBE_PARENT(child) = parent;
272	2.74k	if (parent != NULL) {
273	2.74k	if (OSSL_RBE_LEFT(parent) == rbe)
274	883	OSSL_RBE_LEFT(parent) = child;
275	1.86k	else
276	1.86k	OSSL_RBE_RIGHT(parent) = child;
277	2.74k	} else
278	0	OSSL_RBH_ROOT(rbt) = child;
279	2.74k	if (OSSL_RBE_PARENT(rbe) == old)
280	1.86k	parent = rbe;
281	2.74k	rbe = old;
282
283	2.74k	tmp = OSSL_RBE_PARENT(old);
284	2.74k	if (tmp != NULL) {
285	1.23k	if (OSSL_RBE_LEFT(tmp) == old)
286	962	OSSL_RBE_LEFT(tmp) = rbe;
287	273	else
288	273	OSSL_RBE_RIGHT(tmp) = rbe;
289	1.23k	} else
290	1.50k	OSSL_RBH_ROOT(rbt) = rbe;
291
292	2.74k	OSSL_RBE_PARENT(OSSL_RBE_LEFT(old)) = rbe;
293	2.74k	if (OSSL_RBE_RIGHT(old))
294	1.23k	OSSL_RBE_PARENT(OSSL_RBE_RIGHT(old)) = rbe;
295	2.74k	goto color;
296	2.74k	}
297
298	100k	parent = OSSL_RBE_PARENT(rbe);
299	100k	color = OSSL_RBE_COLOR(rbe);
300
301	100k	if (child != NULL)
302	3.79k	OSSL_RBE_PARENT(child) = parent;
303	100k	if (parent != NULL) {
304	7.61k	if (OSSL_RBE_LEFT(parent) == rbe)
305	6.82k	OSSL_RBE_LEFT(parent) = child;
306	790	else
307	790	OSSL_RBE_RIGHT(parent) = child;
308	7.61k	} else
309	93.3k	OSSL_RBH_ROOT(rbt) = child;
310	103k	color:
311	103k	if (color == OSSL_RBT_BLACK)
312	99.8k	rbe_remove_color(rbt, parent, child);
313
314	103k	#ifndef NDEBUG
315	103k	if (old != NULL) {
316	103k	OSSL_RBE_PARENT(old) = NULL;
317	103k	OSSL_RBE_LEFT(old) = NULL;
318	103k	OSSL_RBE_RIGHT(old) = NULL;
319	103k	}
320	103k	#endif
321
322	103k	return old;
323	100k	}
324
325		void *
326		ossl_rbt_remove(const struct ossl_rbt_type t, struct ossl_rbt_tree rbt, void *elm)
327	103k	{
328	103k	struct ossl_rbt_entry *rbe = rbt_n2e(t, elm);
329	103k	struct ossl_rbt_entry *old;
330
331	103k	old = rbe_remove(rbt, rbe);
332
333	103k	return old == NULL ? NULL : rbt_e2n(t, old);
334	103k	}
335
336		void *
337		ossl_rbt_insert(const struct ossl_rbt_type t, struct ossl_rbt_tree rbt, void *elm)
338	105k	{
339	105k	struct ossl_rbt_entry *rbe = rbt_n2e(t, elm);
340	105k	struct ossl_rbt_entry *tmp;
341	105k	struct ossl_rbt_entry *parent = NULL;
342	105k	void *node;
343	105k	int comp = 0;
344
345	105k	#ifndef NDEBUG
346	105k	assert(rbe->rb_parent == NULL);
347	105k	assert(rbe->rb_left == NULL);
348	105k	assert(rbe->rb_right == NULL);
349	105k	#endif
350
351	105k	tmp = OSSL_RBH_ROOT(rbt);
352	134k	while (tmp != NULL) {
353	31.0k	parent = tmp;
354
355	31.0k	node = rbt_e2n(t, tmp);
356	31.0k	comp = (*t->t_compare)(elm, node);
357	31.0k	if (comp < 0)
358	14.8k	tmp = OSSL_RBE_LEFT(tmp);
359	16.1k	else if (comp > 0)
360	14.1k	tmp = OSSL_RBE_RIGHT(tmp);
361	1.99k	else
362	1.99k	return node;
363	31.0k	}
364
365	103k	rbe_set(rbe, parent);
366
367	103k	if (parent != NULL) {
368	12.3k	if (comp < 0)
369	5.92k	OSSL_RBE_LEFT(parent) = rbe;
370	6.42k	else
371	6.42k	OSSL_RBE_RIGHT(parent) = rbe;
372	12.3k	} else
373	91.3k	OSSL_RBH_ROOT(rbt) = rbe;
374
375	103k	rbe_insert_color(rbt, rbe);
376
377	103k	return NULL;
378	105k	}
379
380		/* Finds the node with the same key as elm */
381		void *
382		ossl_rbt_find(const struct ossl_rbt_type t, struct ossl_rbt_tree rbt, const void *key)
383	101k	{
384	101k	struct ossl_rbt_entry *tmp = OSSL_RBH_ROOT(rbt);
385	101k	void *node;
386	101k	int comp;
387
388	167k	while (tmp != NULL) {
389	159k	node = rbt_e2n(t, tmp);
390	159k	comp = (*t->t_compare)(key, node);
391	159k	if (comp < 0)
392	51.1k	tmp = OSSL_RBE_LEFT(tmp);
393	108k	else if (comp > 0)
394	14.9k	tmp = OSSL_RBE_RIGHT(tmp);
395	93.2k	else
396	93.2k	return node;
397	159k	}
398
399	8.10k	return NULL;
400	101k	}
401
402		/* Finds the first node greater than or equal to the search key */
403		void *
404		ossl_rbt_nfind(const struct ossl_rbt_type t, struct ossl_rbt_tree rbt, const void *key)
405	0	{
406	0	struct ossl_rbt_entry *tmp = OSSL_RBH_ROOT(rbt);
407	0	void *node;
408	0	void *res = NULL;
409	0	int comp;
410
411	0	while (tmp != NULL) {
412	0	node = rbt_e2n(t, tmp);
413	0	comp = (*t->t_compare)(key, node);
414	0	if (comp < 0) {
415	0	res = node;
416	0	tmp = OSSL_RBE_LEFT(tmp);
417	0	} else if (comp > 0)
418	0	tmp = OSSL_RBE_RIGHT(tmp);
419	0	else
420	0	return node;
421	0	}
422
423	0	return res;
424	0	}
425
426		void *
427		ossl_rbt_next(const struct ossl_rbt_type t, void elm)
428	18.4k	{
429	18.4k	struct ossl_rbt_entry *rbe = rbt_n2e(t, elm);
430
431	18.4k	if (OSSL_RBE_RIGHT(rbe) != NULL) {
432	2.32k	rbe = OSSL_RBE_RIGHT(rbe);
433	2.32k	while (OSSL_RBE_LEFT(rbe) != NULL)
434	0	rbe = OSSL_RBE_LEFT(rbe);
435	16.0k	} else {
436	16.0k	if (OSSL_RBE_PARENT(rbe) && (rbe == OSSL_RBE_LEFT(OSSL_RBE_PARENT(rbe))))
437	3.19k	rbe = OSSL_RBE_PARENT(rbe);
438	12.9k	else {
439	12.9k	while (OSSL_RBE_PARENT(rbe) && (rbe == OSSL_RBE_RIGHT(OSSL_RBE_PARENT(rbe))))
440	0	rbe = OSSL_RBE_PARENT(rbe);
441	12.9k	rbe = OSSL_RBE_PARENT(rbe);
442	12.9k	}
443	16.0k	}
444
445	18.4k	return rbe == NULL ? NULL : rbt_e2n(t, rbe);
446	18.4k	}
447
448		void *
449		ossl_rbt_prev(const struct ossl_rbt_type t, void elm)
450	0	{
451	0	struct ossl_rbt_entry *rbe = rbt_n2e(t, elm);
452
453	0	if (OSSL_RBE_LEFT(rbe)) {
454	0	rbe = OSSL_RBE_LEFT(rbe);
455	0	while (OSSL_RBE_RIGHT(rbe))
456	0	rbe = OSSL_RBE_RIGHT(rbe);
457	0	} else {
458	0	if (OSSL_RBE_PARENT(rbe) && (rbe == OSSL_RBE_RIGHT(OSSL_RBE_PARENT(rbe))))
459	0	rbe = OSSL_RBE_PARENT(rbe);
460	0	else {
461	0	while (OSSL_RBE_PARENT(rbe) && (rbe == OSSL_RBE_LEFT(OSSL_RBE_PARENT(rbe))))
462	0	rbe = OSSL_RBE_PARENT(rbe);
463	0	rbe = OSSL_RBE_PARENT(rbe);
464	0	}
465	0	}
466
467	0	return rbe == NULL ? NULL : rbt_e2n(t, rbe);
468	0	}
469
470		void *
471		ossl_rbt_root(const struct ossl_rbt_type t, struct ossl_rbt_tree rbt)
472	0	{
473	0	struct ossl_rbt_entry *rbe = OSSL_RBH_ROOT(rbt);
474
475	0	return rbe == NULL ? rbe : rbt_e2n(t, rbe);
476	0	}
477
478		void *
479		ossl_rbt_min(const struct ossl_rbt_type t, struct ossl_rbt_tree rbt)
480	133M	{
481	133M	struct ossl_rbt_entry *rbe = OSSL_RBH_ROOT(rbt);
482	133M	struct ossl_rbt_entry *parent = NULL;
483
484	167M	while (rbe != NULL) {
485	34.1M	parent = rbe;
486	34.1M	rbe = OSSL_RBE_LEFT(rbe);
487	34.1M	}
488
489	133M	return parent == NULL ? NULL : rbt_e2n(t, parent);
490	133M	}
491
492		void *
493		ossl_rbt_max(const struct ossl_rbt_type t, struct ossl_rbt_tree rbt)
494	7.40k	{
495	7.40k	struct ossl_rbt_entry *rbe = OSSL_RBH_ROOT(rbt);
496	7.40k	struct ossl_rbt_entry *parent = NULL;
497
498	7.47k	while (rbe != NULL) {
499	70	parent = rbe;
500	70	rbe = OSSL_RBE_RIGHT(rbe);
501	70	}
502
503	7.40k	return parent == NULL ? NULL : rbt_e2n(t, parent);
504	7.40k	}
505
506		void *
507		ossl_rbt_left(const struct ossl_rbt_type t, void node)
508	0	{
509	0	struct ossl_rbt_entry *rbe = rbt_n2e(t, node);
510	0	rbe = OSSL_RBE_LEFT(rbe);
511	0	return rbe == NULL ? NULL : rbt_e2n(t, rbe);
512	0	}
513
514		void *
515		ossl_rbt_right(const struct ossl_rbt_type t, void node)
516	0	{
517	0	struct ossl_rbt_entry *rbe = rbt_n2e(t, node);
518	0	rbe = OSSL_RBE_RIGHT(rbe);
519	0	return rbe == NULL ? NULL : rbt_e2n(t, rbe);
520	0	}
521
522		void *
523		ossl_rbt_parent(const struct ossl_rbt_type t, void node)
524	0	{
525	0	struct ossl_rbt_entry *rbe = rbt_n2e(t, node);
526	0	rbe = OSSL_RBE_PARENT(rbe);
527	0	return rbe == NULL ? NULL : rbt_e2n(t, rbe);
528	0	}
529
530		void ossl_rbt_set_left(const struct ossl_rbt_type t, void node, void *left)
531	0	{
532	0	struct ossl_rbt_entry *rbe = rbt_n2e(t, node);
533	0	struct ossl_rbt_entry *rbl = (left == NULL) ? NULL : rbt_n2e(t, left);
534
535	0	OSSL_RBE_LEFT(rbe) = rbl;
536	0	}
537
538		void ossl_rbt_set_right(const struct ossl_rbt_type t, void node, void *right)
539	0	{
540	0	struct ossl_rbt_entry *rbe = rbt_n2e(t, node);
541	0	struct ossl_rbt_entry *rbr = (right == NULL) ? NULL : rbt_n2e(t, right);
542
543	0	OSSL_RBE_RIGHT(rbe) = rbr;
544	0	}
545
546		void ossl_rbt_set_parent(const struct ossl_rbt_type t, void node, void *parent)
547	0	{
548	0	struct ossl_rbt_entry *rbe = rbt_n2e(t, node);
549	0	struct ossl_rbt_entry *rbp = (parent == NULL) ? NULL : rbt_n2e(t, parent);
550
551	0	OSSL_RBE_PARENT(rbe) = rbp;
552	0	}
553
554		void ossl_rbt_init_rbe(const struct ossl_rbt_type t, void node)
555	0	{
556	0	struct ossl_rbt_entry *rbe = rbt_n2e(t, node);
557
558	0	OSSL_RBE_PARENT(rbe) = NULL;
559	0	OSSL_RBE_LEFT(rbe) = NULL;
560	0	OSSL_RBE_RIGHT(rbe) = NULL;
561	0	}