/src/frr/lib/openbsd-tree.c

Source (jump to first uncovered line)
// SPDX-License-Identifier: ISC AND BSD-2-Clause
/*  $OpenBSD: subr_tree.c,v 1.9 2017/06/08 03:30:52 dlg Exp $ */

/*
 * Copyright 2002 Niels Provos <provos@citi.umich.edu>
 */

/*
 * Copyright (c) 2016 David Gwynne <dlg@openbsd.org>
 */

#ifdef HAVE_CONFIG_H
#include "config.h"
#endif

#include <stdlib.h>

#include <lib/openbsd-tree.h>

static inline struct rb_entry *rb_n2e(const struct rb_type *t, void *node)
{
  unsigned long addr = (unsigned long)node;

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

static inline void *rb_e2n(const struct rb_type *t, struct rb_entry *rbe)
{
  unsigned long addr = (unsigned long)rbe;

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

#define RBE_LEFT(_rbe)    (_rbe)->rbt_left
#define RBE_RIGHT(_rbe)   (_rbe)->rbt_right
#define RBE_PARENT(_rbe)  (_rbe)->rbt_parent
#define RBE_COLOR(_rbe)   (_rbe)->rbt_color

#define RBH_ROOT(_rbt)    (_rbt)->rbt_root

static inline void rbe_set(struct rb_entry *rbe, struct rb_entry *parent)
{
  RBE_PARENT(rbe) = parent;
  RBE_LEFT(rbe) = RBE_RIGHT(rbe) = NULL;
  RBE_COLOR(rbe) = RB_RED;
}

static inline void rbe_set_blackred(struct rb_entry *black,
            struct rb_entry *red)
{
  RBE_COLOR(black) = RB_BLACK;
  RBE_COLOR(red) = RB_RED;
}

static inline void rbe_augment(const struct rb_type *t, struct rb_entry *rbe)
{
  (*t->t_augment)(rb_e2n(t, rbe));
}

static inline void rbe_if_augment(const struct rb_type *t, struct rb_entry *rbe)
{
  if (t->t_augment != NULL)
    rbe_augment(t, rbe);
}

static inline void rbe_rotate_left(const struct rb_type *t,
           struct rbt_tree *rbt, struct rb_entry *rbe)
{
  struct rb_entry *parent;
  struct rb_entry *tmp;

  tmp = RBE_RIGHT(rbe);
  RBE_RIGHT(rbe) = RBE_LEFT(tmp);
  if (RBE_RIGHT(rbe) != NULL)
    RBE_PARENT(RBE_LEFT(tmp)) = rbe;

  parent = RBE_PARENT(rbe);
  RBE_PARENT(tmp) = parent;
  if (parent != NULL) {
    if (rbe == RBE_LEFT(parent))
      RBE_LEFT(parent) = tmp;
    else
      RBE_RIGHT(parent) = tmp;
  } else
    RBH_ROOT(rbt) = tmp;

  RBE_LEFT(tmp) = rbe;
  RBE_PARENT(rbe) = tmp;

  if (t->t_augment != NULL) {
    rbe_augment(t, rbe);
    rbe_augment(t, tmp);
    parent = RBE_PARENT(tmp);
    if (parent != NULL)
      rbe_augment(t, parent);
  }
}

static inline void rbe_rotate_right(const struct rb_type *t,
            struct rbt_tree *rbt, struct rb_entry *rbe)
{
  struct rb_entry *parent;
  struct rb_entry *tmp;

  tmp = RBE_LEFT(rbe);
  RBE_LEFT(rbe) = RBE_RIGHT(tmp);
  if (RBE_LEFT(rbe) != NULL)
    RBE_PARENT(RBE_RIGHT(tmp)) = rbe;

  parent = RBE_PARENT(rbe);
  RBE_PARENT(tmp) = parent;
  if (parent != NULL) {
    if (rbe == RBE_LEFT(parent))
      RBE_LEFT(parent) = tmp;
    else
      RBE_RIGHT(parent) = tmp;
  } else
    RBH_ROOT(rbt) = tmp;

  RBE_RIGHT(tmp) = rbe;
  RBE_PARENT(rbe) = tmp;

  if (t->t_augment != NULL) {
    rbe_augment(t, rbe);
    rbe_augment(t, tmp);
    parent = RBE_PARENT(tmp);
    if (parent != NULL)
      rbe_augment(t, parent);
  }
}

static inline void rbe_insert_color(const struct rb_type *t,
            struct rbt_tree *rbt, struct rb_entry *rbe)
{
  struct rb_entry *parent, *gparent, *tmp;

  while ((parent = RBE_PARENT(rbe)) != NULL
         && RBE_COLOR(parent) == RB_RED) {
    gparent = RBE_PARENT(parent);

    if (parent == RBE_LEFT(gparent)) {
      tmp = RBE_RIGHT(gparent);
      if (tmp != NULL && RBE_COLOR(tmp) == RB_RED) {
        RBE_COLOR(tmp) = RB_BLACK;
        rbe_set_blackred(parent, gparent);
        rbe = gparent;
        continue;
      }

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

      rbe_set_blackred(parent, gparent);
      rbe_rotate_right(t, rbt, gparent);
    } else {
      tmp = RBE_LEFT(gparent);
      if (tmp != NULL && RBE_COLOR(tmp) == RB_RED) {
        RBE_COLOR(tmp) = RB_BLACK;
        rbe_set_blackred(parent, gparent);
        rbe = gparent;
        continue;
      }

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

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

  RBE_COLOR(RBH_ROOT(rbt)) = RB_BLACK;
}

static inline void rbe_remove_color(const struct rb_type *t,
            struct rbt_tree *rbt,
            struct rb_entry *parent,
            struct rb_entry *rbe)
{
  struct rb_entry *tmp;

  while ((rbe == NULL || RBE_COLOR(rbe) == RB_BLACK)
         && rbe != RBH_ROOT(rbt) && parent) {
    if (RBE_LEFT(parent) == rbe) {
      tmp = RBE_RIGHT(parent);
      if (RBE_COLOR(tmp) == RB_RED) {
        rbe_set_blackred(tmp, parent);
        rbe_rotate_left(t, rbt, parent);
        tmp = RBE_RIGHT(parent);
      }
      if ((RBE_LEFT(tmp) == NULL
           || RBE_COLOR(RBE_LEFT(tmp)) == RB_BLACK)
          && (RBE_RIGHT(tmp) == NULL
        || RBE_COLOR(RBE_RIGHT(tmp)) == RB_BLACK)) {
        RBE_COLOR(tmp) = RB_RED;
        rbe = parent;
        parent = RBE_PARENT(rbe);
      } else {
        if (RBE_RIGHT(tmp) == NULL
            || RBE_COLOR(RBE_RIGHT(tmp)) == RB_BLACK) {
          struct rb_entry *oleft;

          oleft = RBE_LEFT(tmp);
          if (oleft != NULL)
            RBE_COLOR(oleft) = RB_BLACK;

          RBE_COLOR(tmp) = RB_RED;
          rbe_rotate_right(t, rbt, tmp);
          tmp = RBE_RIGHT(parent);
        }

        RBE_COLOR(tmp) = RBE_COLOR(parent);
        RBE_COLOR(parent) = RB_BLACK;
        if (RBE_RIGHT(tmp))
          RBE_COLOR(RBE_RIGHT(tmp)) = RB_BLACK;

        rbe_rotate_left(t, rbt, parent);
        rbe = RBH_ROOT(rbt);
        break;
      }
    } else {
      tmp = RBE_LEFT(parent);
      if (RBE_COLOR(tmp) == RB_RED) {
        rbe_set_blackred(tmp, parent);
        rbe_rotate_right(t, rbt, parent);
        tmp = RBE_LEFT(parent);
      }

      if ((RBE_LEFT(tmp) == NULL
           || RBE_COLOR(RBE_LEFT(tmp)) == RB_BLACK)
          && (RBE_RIGHT(tmp) == NULL
        || RBE_COLOR(RBE_RIGHT(tmp)) == RB_BLACK)) {
        RBE_COLOR(tmp) = RB_RED;
        rbe = parent;
        parent = RBE_PARENT(rbe);
      } else {
        if (RBE_LEFT(tmp) == NULL
            || RBE_COLOR(RBE_LEFT(tmp)) == RB_BLACK) {
          struct rb_entry *oright;

          oright = RBE_RIGHT(tmp);
          if (oright != NULL)
            RBE_COLOR(oright) = RB_BLACK;

          RBE_COLOR(tmp) = RB_RED;
          rbe_rotate_left(t, rbt, tmp);
          tmp = RBE_LEFT(parent);
        }

        RBE_COLOR(tmp) = RBE_COLOR(parent);
        RBE_COLOR(parent) = RB_BLACK;
        if (RBE_LEFT(tmp) != NULL)
          RBE_COLOR(RBE_LEFT(tmp)) = RB_BLACK;

        rbe_rotate_right(t, rbt, parent);
        rbe = RBH_ROOT(rbt);
        break;
      }
    }
  }

  if (rbe != NULL)
    RBE_COLOR(rbe) = RB_BLACK;
}

static inline struct rb_entry *
rbe_remove(const struct rb_type *t, struct rbt_tree *rbt, struct rb_entry *rbe)
{
  struct rb_entry *child, *parent, *old = rbe;
  unsigned int color;

  if (RBE_LEFT(rbe) == NULL)
    child = RBE_RIGHT(rbe);
  else if (RBE_RIGHT(rbe) == NULL)
    child = RBE_LEFT(rbe);
  else {
    struct rb_entry *tmp;

    rbe = RBE_RIGHT(rbe);
    while ((tmp = RBE_LEFT(rbe)) != NULL)
      rbe = tmp;

    child = RBE_RIGHT(rbe);
    parent = RBE_PARENT(rbe);
    color = RBE_COLOR(rbe);
    if (child != NULL)
      RBE_PARENT(child) = parent;
    if (parent != NULL) {
      if (RBE_LEFT(parent) == rbe)
        RBE_LEFT(parent) = child;
      else
        RBE_RIGHT(parent) = child;

      rbe_if_augment(t, parent);
    } else
      RBH_ROOT(rbt) = child;
    if (RBE_PARENT(rbe) == old)
      parent = rbe;
    *rbe = *old;

    tmp = RBE_PARENT(old);
    if (tmp != NULL) {
      if (RBE_LEFT(tmp) == old)
        RBE_LEFT(tmp) = rbe;
      else
        RBE_RIGHT(tmp) = rbe;

      rbe_if_augment(t, tmp);
    } else
      RBH_ROOT(rbt) = rbe;

    RBE_PARENT(RBE_LEFT(old)) = rbe;
    if (RBE_RIGHT(old))
      RBE_PARENT(RBE_RIGHT(old)) = rbe;

    if (t->t_augment != NULL && parent != NULL) {
      tmp = parent;
      do {
        rbe_augment(t, tmp);
        tmp = RBE_PARENT(tmp);
      } while (tmp != NULL);
    }

    goto color;
  }

  parent = RBE_PARENT(rbe);
  color = RBE_COLOR(rbe);

  if (child != NULL)
    RBE_PARENT(child) = parent;
  if (parent != NULL) {
    if (RBE_LEFT(parent) == rbe)
      RBE_LEFT(parent) = child;
    else
      RBE_RIGHT(parent) = child;

    rbe_if_augment(t, parent);
  } else
    RBH_ROOT(rbt) = child;
color:
  if (color == RB_BLACK)
    rbe_remove_color(t, rbt, parent, child);

  return (old);
}

void *_rb_remove(const struct rb_type *t, struct rbt_tree *rbt, void *elm)
{
  struct rb_entry *rbe = rb_n2e(t, elm);
  struct rb_entry *old;

  old = rbe_remove(t, rbt, rbe);

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

void *_rb_insert(const struct rb_type *t, struct rbt_tree *rbt, void *elm)
{
  struct rb_entry *rbe = rb_n2e(t, elm);
  struct rb_entry *tmp;
  struct rb_entry *parent = NULL;
  void *node;
  int comp = 0;

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

    node = rb_e2n(t, tmp);
    comp = (*t->t_compare)(elm, node);
    if (comp < 0)
      tmp = RBE_LEFT(tmp);
    else if (comp > 0)
      tmp = RBE_RIGHT(tmp);
    else
      return (node);
  }

  rbe_set(rbe, parent);

  if (parent != NULL) {
    if (comp < 0)
      RBE_LEFT(parent) = rbe;
    else
      RBE_RIGHT(parent) = rbe;

    rbe_if_augment(t, parent);
  } else
    RBH_ROOT(rbt) = rbe;

  rbe_insert_color(t, rbt, rbe);

  return NULL;
}

/* Finds the node with the same key as elm */
void *_rb_find(const struct rb_type *t, const struct rbt_tree *rbt,
         const void *key)
{
  struct rb_entry *tmp = RBH_ROOT(rbt);
  void *node;
  int comp;

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

  return NULL;
}

/* Finds the first node greater than or equal to the search key */
void *_rb_nfind(const struct rb_type *t, const struct rbt_tree *rbt,
    const void *key)
{
  struct rb_entry *tmp = RBH_ROOT(rbt);
  void *node;
  void *res = NULL;
  int comp;

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

  return (res);
}

void *_rb_next(const struct rb_type *t, void *elm)
{
  struct rb_entry *rbe = rb_n2e(t, elm);

  if (RBE_RIGHT(rbe) != NULL) {
    rbe = RBE_RIGHT(rbe);
    while (RBE_LEFT(rbe) != NULL)
      rbe = RBE_LEFT(rbe);
  } else {
    if (RBE_PARENT(rbe) && (rbe == RBE_LEFT(RBE_PARENT(rbe))))
      rbe = RBE_PARENT(rbe);
    else {
      while (RBE_PARENT(rbe)
             && (rbe == RBE_RIGHT(RBE_PARENT(rbe))))
        rbe = RBE_PARENT(rbe);
      rbe = RBE_PARENT(rbe);
    }
  }

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

void *_rb_prev(const struct rb_type *t, void *elm)
{
  struct rb_entry *rbe = rb_n2e(t, elm);

  if (RBE_LEFT(rbe)) {
    rbe = RBE_LEFT(rbe);
    while (RBE_RIGHT(rbe))
      rbe = RBE_RIGHT(rbe);
  } else {
    if (RBE_PARENT(rbe) && (rbe == RBE_RIGHT(RBE_PARENT(rbe))))
      rbe = RBE_PARENT(rbe);
    else {
      while (RBE_PARENT(rbe)
             && (rbe == RBE_LEFT(RBE_PARENT(rbe))))
        rbe = RBE_PARENT(rbe);
      rbe = RBE_PARENT(rbe);
    }
  }

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

void *_rb_root(const struct rb_type *t, const struct rbt_tree *rbt)
{
  struct rb_entry *rbe = RBH_ROOT(rbt);

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

void *_rb_min(const struct rb_type *t, const struct rbt_tree *rbt)
{
  struct rb_entry *rbe = RBH_ROOT(rbt);
  struct rb_entry *parent = NULL;

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

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

void *_rb_max(const struct rb_type *t, const struct rbt_tree *rbt)
{
  struct rb_entry *rbe = RBH_ROOT(rbt);
  struct rb_entry *parent = NULL;

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

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

void *_rb_left(const struct rb_type *t, void *node)
{
  struct rb_entry *rbe = rb_n2e(t, node);
  rbe = RBE_LEFT(rbe);
  return (rbe == NULL ? NULL : rb_e2n(t, rbe));
}

void *_rb_right(const struct rb_type *t, void *node)
{
  struct rb_entry *rbe = rb_n2e(t, node);
  rbe = RBE_RIGHT(rbe);
  return (rbe == NULL ? NULL : rb_e2n(t, rbe));
}

void *_rb_parent(const struct rb_type *t, void *node)
{
  struct rb_entry *rbe = rb_n2e(t, node);
  rbe = RBE_PARENT(rbe);
  return (rbe == NULL ? NULL : rb_e2n(t, rbe));
}

void _rb_set_left(const struct rb_type *t, void *node, void *left)
{
  struct rb_entry *rbe = rb_n2e(t, node);
  struct rb_entry *rbl = (left == NULL) ? NULL : rb_n2e(t, left);

  RBE_LEFT(rbe) = rbl;
}

void _rb_set_right(const struct rb_type *t, void *node, void *right)
{
  struct rb_entry *rbe = rb_n2e(t, node);
  struct rb_entry *rbr = (right == NULL) ? NULL : rb_n2e(t, right);

  RBE_RIGHT(rbe) = rbr;
}

void _rb_set_parent(const struct rb_type *t, void *node, void *parent)
{
  struct rb_entry *rbe = rb_n2e(t, node);
  struct rb_entry *rbp = (parent == NULL) ? NULL : rb_n2e(t, parent);

  RBE_PARENT(rbe) = rbp;
}

void _rb_poison(const struct rb_type *t, void *node, unsigned long poison)
{
  struct rb_entry *rbe = rb_n2e(t, node);

  RBE_PARENT(rbe) = RBE_LEFT(rbe) = RBE_RIGHT(rbe) =
    (struct rb_entry *)poison;
}

int _rb_check(const struct rb_type *t, void *node, unsigned long poison)
{
  struct rb_entry *rbe = rb_n2e(t, node);

  return ((unsigned long)RBE_PARENT(rbe) == poison
    && (unsigned long)RBE_LEFT(rbe) == poison
    && (unsigned long)RBE_RIGHT(rbe) == poison);
}

Coverage Report

Created: 2025-08-26 06:20

Line	Count	Source (jump to first uncovered line)
1		// SPDX-License-Identifier: ISC AND BSD-2-Clause
2		/* $OpenBSD: subr_tree.c,v 1.9 2017/06/08 03:30:52 dlg Exp $ */
3
4		/*
5		* Copyright 2002 Niels Provos <provos@citi.umich.edu>
6		*/
7
8		/*
9		* Copyright (c) 2016 David Gwynne <dlg@openbsd.org>
10		*/
11
12		#ifdef HAVE_CONFIG_H
13		#include "config.h"
14		#endif
15
16		#include <stdlib.h>
17
18		#include <lib/openbsd-tree.h>
19
20		static inline struct rb_entry rb_n2e(const struct rb_type t, void *node)
21	403k	{
22	403k	unsigned long addr = (unsigned long)node;
23
24	403k	return ((struct rb_entry *)(addr + t->t_offset));
25	403k	}
26
27		static inline void rb_e2n(const struct rb_type t, struct rb_entry *rbe)
28	3.83M	{
29	3.83M	unsigned long addr = (unsigned long)rbe;
30
31	3.83M	return ((void *)(addr - t->t_offset));
32	3.83M	}
33
34	2.78M	#define RBE_LEFT(_rbe) (_rbe)->rbt_left
35	2.79M	#define RBE_RIGHT(_rbe) (_rbe)->rbt_right
36	1.69M	#define RBE_PARENT(_rbe) (_rbe)->rbt_parent
37	631k	#define RBE_COLOR(_rbe) (_rbe)->rbt_color
38
39	619k	#define RBH_ROOT(_rbt) (_rbt)->rbt_root
40
41		static inline void rbe_set(struct rb_entry rbe, struct rb_entry parent)
42	52.2k	{
43	52.2k	RBE_PARENT(rbe) = parent;
44	52.2k	RBE_LEFT(rbe) = RBE_RIGHT(rbe) = NULL;
45	52.2k	RBE_COLOR(rbe) = RB_RED;
46	52.2k	}
47
48		static inline void rbe_set_blackred(struct rb_entry *black,
49		struct rb_entry *red)
50	55.0k	{
51	55.0k	RBE_COLOR(black) = RB_BLACK;
52	55.0k	RBE_COLOR(red) = RB_RED;
53	55.0k	}
54
55		static inline void rbe_augment(const struct rb_type t, struct rb_entry rbe)
56	0	{
57	0	(*t->t_augment)(rb_e2n(t, rbe));
58	0	}
59
60		static inline void rbe_if_augment(const struct rb_type t, struct rb_entry rbe)
61	121k	{
62	121k	if (t->t_augment != NULL)
63	0	rbe_augment(t, rbe);
64	121k	}
65
66		static inline void rbe_rotate_left(const struct rb_type *t,
67		struct rbt_tree rbt, struct rb_entry rbe)
68	31.7k	{
69	31.7k	struct rb_entry *parent;
70	31.7k	struct rb_entry *tmp;
71
72	31.7k	tmp = RBE_RIGHT(rbe);
73	31.7k	RBE_RIGHT(rbe) = RBE_LEFT(tmp);
74	31.7k	if (RBE_RIGHT(rbe) != NULL)
75	9.85k	RBE_PARENT(RBE_LEFT(tmp)) = rbe;
76
77	31.7k	parent = RBE_PARENT(rbe);
78	31.7k	RBE_PARENT(tmp) = parent;
79	31.7k	if (parent != NULL) {
80	31.7k	if (rbe == RBE_LEFT(parent))
81	20.2k	RBE_LEFT(parent) = tmp;
82	11.4k	else
83	11.4k	RBE_RIGHT(parent) = tmp;
84	31.7k	} else
85	1	RBH_ROOT(rbt) = tmp;
86
87	31.7k	RBE_LEFT(tmp) = rbe;
88	31.7k	RBE_PARENT(rbe) = tmp;
89
90	31.7k	if (t->t_augment != NULL) {
91	0	rbe_augment(t, rbe);
92	0	rbe_augment(t, tmp);
93	0	parent = RBE_PARENT(tmp);
94	0	if (parent != NULL)
95	0	rbe_augment(t, parent);
96	0	}
97	31.7k	}
98
99		static inline void rbe_rotate_right(const struct rb_type *t,
100		struct rbt_tree rbt, struct rb_entry rbe)
101	25.3k	{
102	25.3k	struct rb_entry *parent;
103	25.3k	struct rb_entry *tmp;
104
105	25.3k	tmp = RBE_LEFT(rbe);
106	25.3k	RBE_LEFT(rbe) = RBE_RIGHT(tmp);
107	25.3k	if (RBE_LEFT(rbe) != NULL)
108	8.83k	RBE_PARENT(RBE_RIGHT(tmp)) = rbe;
109
110	25.3k	parent = RBE_PARENT(rbe);
111	25.3k	RBE_PARENT(tmp) = parent;
112	25.3k	if (parent != NULL) {
113	25.3k	if (rbe == RBE_LEFT(parent))
114	9.66k	RBE_LEFT(parent) = tmp;
115	15.6k	else
116	15.6k	RBE_RIGHT(parent) = tmp;
117	25.3k	} else
118	2	RBH_ROOT(rbt) = tmp;
119
120	25.3k	RBE_RIGHT(tmp) = rbe;
121	25.3k	RBE_PARENT(rbe) = tmp;
122
123	25.3k	if (t->t_augment != NULL) {
124	0	rbe_augment(t, rbe);
125	0	rbe_augment(t, tmp);
126	0	parent = RBE_PARENT(tmp);
127	0	if (parent != NULL)
128	0	rbe_augment(t, parent);
129	0	}
130	25.3k	}
131
132		static inline void rbe_insert_color(const struct rb_type *t,
133		struct rbt_tree rbt, struct rb_entry rbe)
134	52.2k	{
135	52.2k	struct rb_entry parent, gparent, *tmp;
136
137	102k	while ((parent = RBE_PARENT(rbe)) != NULL
138	102k	&& RBE_COLOR(parent) == RB_RED) {
139	50.4k	gparent = RBE_PARENT(parent);
140
141	50.4k	if (parent == RBE_LEFT(gparent)) {
142	20.3k	tmp = RBE_RIGHT(gparent);
143	20.3k	if (tmp != NULL && RBE_COLOR(tmp) == RB_RED) {
144	11.7k	RBE_COLOR(tmp) = RB_BLACK;
145	11.7k	rbe_set_blackred(parent, gparent);
146	11.7k	rbe = gparent;
147	11.7k	continue;
148	11.7k	}
149
150	8.66k	if (RBE_RIGHT(parent) == rbe) {
151	6.91k	rbe_rotate_left(t, rbt, parent);
152	6.91k	tmp = parent;
153	6.91k	parent = rbe;
154	6.91k	rbe = tmp;
155	6.91k	}
156
157	8.66k	rbe_set_blackred(parent, gparent);
158	8.66k	rbe_rotate_right(t, rbt, gparent);
159	30.0k	} else {
160	30.0k	tmp = RBE_LEFT(gparent);
161	30.0k	if (tmp != NULL && RBE_COLOR(tmp) == RB_RED) {
162	11.2k	RBE_COLOR(tmp) = RB_BLACK;
163	11.2k	rbe_set_blackred(parent, gparent);
164	11.2k	rbe = gparent;
165	11.2k	continue;
166	11.2k	}
167
168	18.7k	if (RBE_LEFT(parent) == rbe) {
169	7.03k	rbe_rotate_right(t, rbt, parent);
170	7.03k	tmp = parent;
171	7.03k	parent = rbe;
172	7.03k	rbe = tmp;
173	7.03k	}
174
175	18.7k	rbe_set_blackred(parent, gparent);
176	18.7k	rbe_rotate_left(t, rbt, gparent);
177	18.7k	}
178	50.4k	}
179
180	52.2k	RBE_COLOR(RBH_ROOT(rbt)) = RB_BLACK;
181	52.2k	}
182
183		static inline void rbe_remove_color(const struct rb_type *t,
184		struct rbt_tree *rbt,
185		struct rb_entry *parent,
186		struct rb_entry *rbe)
187	43.5k	{
188	43.5k	struct rb_entry *tmp;
189
190	66.0k	while ((rbe == NULL \|\| RBE_COLOR(rbe) == RB_BLACK)
191	66.0k	&& rbe != RBH_ROOT(rbt) && parent) {
192	31.9k	if (RBE_LEFT(parent) == rbe) {
193	13.9k	tmp = RBE_RIGHT(parent);
194	13.9k	if (RBE_COLOR(tmp) == RB_RED) {
195	2.05k	rbe_set_blackred(tmp, parent);
196	2.05k	rbe_rotate_left(t, rbt, parent);
197	2.05k	tmp = RBE_RIGHT(parent);
198	2.05k	}
199	13.9k	if ((RBE_LEFT(tmp) == NULL
200	13.9k	\|\| RBE_COLOR(RBE_LEFT(tmp)) == RB_BLACK)
201	13.9k	&& (RBE_RIGHT(tmp) == NULL
202	12.1k	\|\| RBE_COLOR(RBE_RIGHT(tmp)) == RB_BLACK)) {
203	10.8k	RBE_COLOR(tmp) = RB_RED;
204	10.8k	rbe = parent;
205	10.8k	parent = RBE_PARENT(rbe);
206	10.8k	} else {
207	3.05k	if (RBE_RIGHT(tmp) == NULL
208	3.05k	\|\| RBE_COLOR(RBE_RIGHT(tmp)) == RB_BLACK) {
209	560	struct rb_entry *oleft;
210
211	560	oleft = RBE_LEFT(tmp);
212	560	if (oleft != NULL)
213	560	RBE_COLOR(oleft) = RB_BLACK;
214
215	560	RBE_COLOR(tmp) = RB_RED;
216	560	rbe_rotate_right(t, rbt, tmp);
217	560	tmp = RBE_RIGHT(parent);
218	560	}
219
220	3.05k	RBE_COLOR(tmp) = RBE_COLOR(parent);
221	3.05k	RBE_COLOR(parent) = RB_BLACK;
222	3.05k	if (RBE_RIGHT(tmp))
223	3.05k	RBE_COLOR(RBE_RIGHT(tmp)) = RB_BLACK;
224
225	3.05k	rbe_rotate_left(t, rbt, parent);
226	3.05k	rbe = RBH_ROOT(rbt);
227	3.05k	break;
228	3.05k	}
229	18.0k	} else {
230	18.0k	tmp = RBE_LEFT(parent);
231	18.0k	if (RBE_COLOR(tmp) == RB_RED) {
232	2.62k	rbe_set_blackred(tmp, parent);
233	2.62k	rbe_rotate_right(t, rbt, parent);
234	2.62k	tmp = RBE_LEFT(parent);
235	2.62k	}
236
237	18.0k	if ((RBE_LEFT(tmp) == NULL
238	18.0k	\|\| RBE_COLOR(RBE_LEFT(tmp)) == RB_BLACK)
239	18.0k	&& (RBE_RIGHT(tmp) == NULL
240	12.5k	\|\| RBE_COLOR(RBE_RIGHT(tmp)) == RB_BLACK)) {
241	11.5k	RBE_COLOR(tmp) = RB_RED;
242	11.5k	rbe = parent;
243	11.5k	parent = RBE_PARENT(rbe);
244	11.5k	} else {
245	6.46k	if (RBE_LEFT(tmp) == NULL
246	6.46k	\|\| RBE_COLOR(RBE_LEFT(tmp)) == RB_BLACK) {
247	944	struct rb_entry *oright;
248
249	944	oright = RBE_RIGHT(tmp);
250	944	if (oright != NULL)
251	944	RBE_COLOR(oright) = RB_BLACK;
252
253	944	RBE_COLOR(tmp) = RB_RED;
254	944	rbe_rotate_left(t, rbt, tmp);
255	944	tmp = RBE_LEFT(parent);
256	944	}
257
258	6.46k	RBE_COLOR(tmp) = RBE_COLOR(parent);
259	6.46k	RBE_COLOR(parent) = RB_BLACK;
260	6.46k	if (RBE_LEFT(tmp) != NULL)
261	6.46k	RBE_COLOR(RBE_LEFT(tmp)) = RB_BLACK;
262
263	6.46k	rbe_rotate_right(t, rbt, parent);
264	6.46k	rbe = RBH_ROOT(rbt);
265	6.46k	break;
266	6.46k	}
267	18.0k	}
268	31.9k	}
269
270	43.5k	if (rbe != NULL)
271	43.5k	RBE_COLOR(rbe) = RB_BLACK;
272	43.5k	}
273
274		static inline struct rb_entry *
275		rbe_remove(const struct rb_type t, struct rbt_tree rbt, struct rb_entry *rbe)
276	51.4k	{
277	51.4k	struct rb_entry child, parent, *old = rbe;
278	51.4k	unsigned int color;
279
280	51.4k	if (RBE_LEFT(rbe) == NULL)
281	24.3k	child = RBE_RIGHT(rbe);
282	27.0k	else if (RBE_RIGHT(rbe) == NULL)
283	8.89k	child = RBE_LEFT(rbe);
284	18.1k	else {
285	18.1k	struct rb_entry *tmp;
286
287	18.1k	rbe = RBE_RIGHT(rbe);
288	32.4k	while ((tmp = RBE_LEFT(rbe)) != NULL)
289	14.3k	rbe = tmp;
290
291	18.1k	child = RBE_RIGHT(rbe);
292	18.1k	parent = RBE_PARENT(rbe);
293	18.1k	color = RBE_COLOR(rbe);
294	18.1k	if (child != NULL)
295	4.27k	RBE_PARENT(child) = parent;
296	18.1k	if (parent != NULL) {
297	18.1k	if (RBE_LEFT(parent) == rbe)
298	9.62k	RBE_LEFT(parent) = child;
299	8.54k	else
300	8.54k	RBE_RIGHT(parent) = child;
301
302	18.1k	rbe_if_augment(t, parent);
303	18.1k	} else
304	0	RBH_ROOT(rbt) = child;
305	18.1k	if (RBE_PARENT(rbe) == old)
306	8.54k	parent = rbe;
307	18.1k	rbe = old;
308
309	18.1k	tmp = RBE_PARENT(old);
310	18.1k	if (tmp != NULL) {
311	18.1k	if (RBE_LEFT(tmp) == old)
312	7.96k	RBE_LEFT(tmp) = rbe;
313	10.2k	else
314	10.2k	RBE_RIGHT(tmp) = rbe;
315
316	18.1k	rbe_if_augment(t, tmp);
317	18.1k	} else
318	0	RBH_ROOT(rbt) = rbe;
319
320	18.1k	RBE_PARENT(RBE_LEFT(old)) = rbe;
321	18.1k	if (RBE_RIGHT(old))
322	11.1k	RBE_PARENT(RBE_RIGHT(old)) = rbe;
323
324	18.1k	if (t->t_augment != NULL && parent != NULL) {
325	0	tmp = parent;
326	0	do {
327	0	rbe_augment(t, tmp);
328	0	tmp = RBE_PARENT(tmp);
329	0	} while (tmp != NULL);
330	0	}
331
332	18.1k	goto color;
333	18.1k	}
334
335	33.2k	parent = RBE_PARENT(rbe);
336	33.2k	color = RBE_COLOR(rbe);
337
338	33.2k	if (child != NULL)
339	14.6k	RBE_PARENT(child) = parent;
340	33.2k	if (parent != NULL) {
341	33.2k	if (RBE_LEFT(parent) == rbe)
342	16.7k	RBE_LEFT(parent) = child;
343	16.4k	else
344	16.4k	RBE_RIGHT(parent) = child;
345
346	33.2k	rbe_if_augment(t, parent);
347	33.2k	} else
348	0	RBH_ROOT(rbt) = child;
349	51.4k	color:
350	51.4k	if (color == RB_BLACK)
351	43.5k	rbe_remove_color(t, rbt, parent, child);
352
353	51.4k	return (old);
354	33.2k	}
355
356		void _rb_remove(const struct rb_type t, struct rbt_tree rbt, void elm)
357	51.4k	{
358	51.4k	struct rb_entry *rbe = rb_n2e(t, elm);
359	51.4k	struct rb_entry *old;
360
361	51.4k	old = rbe_remove(t, rbt, rbe);
362
363	51.4k	return (old == NULL ? NULL : rb_e2n(t, old));
364	51.4k	}
365
366		void _rb_insert(const struct rb_type t, struct rbt_tree rbt, void elm)
367	52.2k	{
368	52.2k	struct rb_entry *rbe = rb_n2e(t, elm);
369	52.2k	struct rb_entry *tmp;
370	52.2k	struct rb_entry *parent = NULL;
371	52.2k	void *node;
372	52.2k	int comp = 0;
373
374	52.2k	tmp = RBH_ROOT(rbt);
375	570k	while (tmp != NULL) {
376	518k	parent = tmp;
377
378	518k	node = rb_e2n(t, tmp);
379	518k	comp = (*t->t_compare)(elm, node);
380	518k	if (comp < 0)
381	240k	tmp = RBE_LEFT(tmp);
382	277k	else if (comp > 0)
383	277k	tmp = RBE_RIGHT(tmp);
384	0	else
385	0	return (node);
386	518k	}
387
388	52.2k	rbe_set(rbe, parent);
389
390	52.2k	if (parent != NULL) {
391	52.2k	if (comp < 0)
392	20.4k	RBE_LEFT(parent) = rbe;
393	31.8k	else
394	31.8k	RBE_RIGHT(parent) = rbe;
395
396	52.2k	rbe_if_augment(t, parent);
397	52.2k	} else
398	8	RBH_ROOT(rbt) = rbe;
399
400	52.2k	rbe_insert_color(t, rbt, rbe);
401
402	52.2k	return NULL;
403	52.2k	}
404
405		/* Finds the node with the same key as elm */
406		void _rb_find(const struct rb_type t, const struct rbt_tree *rbt,
407		const void *key)
408	366k	{
409	366k	struct rb_entry *tmp = RBH_ROOT(rbt);
410	366k	void *node;
411	366k	int comp;
412
413	3.12M	while (tmp != NULL) {
414	2.95M	node = rb_e2n(t, tmp);
415	2.95M	comp = (*t->t_compare)(key, node);
416	2.95M	if (comp < 0)
417	1.33M	tmp = RBE_LEFT(tmp);
418	1.62M	else if (comp > 0)
419	1.41M	tmp = RBE_RIGHT(tmp);
420	205k	else
421	205k	return (node);
422	2.95M	}
423
424	161k	return NULL;
425	366k	}
426
427		/* Finds the first node greater than or equal to the search key */
428		void _rb_nfind(const struct rb_type t, const struct rbt_tree *rbt,
429		const void *key)
430	0	{
431	0	struct rb_entry *tmp = RBH_ROOT(rbt);
432	0	void *node;
433	0	void *res = NULL;
434	0	int comp;
435
436	0	while (tmp != NULL) {
437	0	node = rb_e2n(t, tmp);
438	0	comp = (*t->t_compare)(key, node);
439	0	if (comp < 0) {
440	0	res = node;
441	0	tmp = RBE_LEFT(tmp);
442	0	} else if (comp > 0)
443	0	tmp = RBE_RIGHT(tmp);
444	0	else
445	0	return (node);
446	0	}
447
448	0	return (res);
449	0	}
450
451		void _rb_next(const struct rb_type t, void *elm)
452	299k	{
453	299k	struct rb_entry *rbe = rb_n2e(t, elm);
454
455	299k	if (RBE_RIGHT(rbe) != NULL) {
456	150k	rbe = RBE_RIGHT(rbe);
457	206k	while (RBE_LEFT(rbe) != NULL)
458	56.4k	rbe = RBE_LEFT(rbe);
459	150k	} else {
460	149k	if (RBE_PARENT(rbe) && (rbe == RBE_LEFT(RBE_PARENT(rbe))))
461	28.8k	rbe = RBE_PARENT(rbe);
462	120k	else {
463	270k	while (RBE_PARENT(rbe)
464	270k	&& (rbe == RBE_RIGHT(RBE_PARENT(rbe))))
465	150k	rbe = RBE_PARENT(rbe);
466	120k	rbe = RBE_PARENT(rbe);
467	120k	}
468	149k	}
469
470	299k	return (rbe == NULL ? NULL : rb_e2n(t, rbe));
471	299k	}
472
473		void _rb_prev(const struct rb_type t, void *elm)
474	0	{
475	0	struct rb_entry *rbe = rb_n2e(t, elm);
476
477	0	if (RBE_LEFT(rbe)) {
478	0	rbe = RBE_LEFT(rbe);
479	0	while (RBE_RIGHT(rbe))
480	0	rbe = RBE_RIGHT(rbe);
481	0	} else {
482	0	if (RBE_PARENT(rbe) && (rbe == RBE_RIGHT(RBE_PARENT(rbe))))
483	0	rbe = RBE_PARENT(rbe);
484	0	else {
485	0	while (RBE_PARENT(rbe)
486	0	&& (rbe == RBE_LEFT(RBE_PARENT(rbe))))
487	0	rbe = RBE_PARENT(rbe);
488	0	rbe = RBE_PARENT(rbe);
489	0	}
490	0	}
491
492	0	return (rbe == NULL ? NULL : rb_e2n(t, rbe));
493	0	}
494
495		void _rb_root(const struct rb_type t, const struct rbt_tree *rbt)
496	0	{
497	0	struct rb_entry *rbe = RBH_ROOT(rbt);
498
499	0	return (rbe == NULL ? rbe : rb_e2n(t, rbe));
500	0	}
501
502		void _rb_min(const struct rb_type t, const struct rbt_tree *rbt)
503	93.3k	{
504	93.3k	struct rb_entry *rbe = RBH_ROOT(rbt);
505	93.3k	struct rb_entry *parent = NULL;
506
507	188k	while (rbe != NULL) {
508	95.6k	parent = rbe;
509	95.6k	rbe = RBE_LEFT(rbe);
510	95.6k	}
511
512	93.3k	return (parent == NULL ? NULL : rb_e2n(t, parent));
513	93.3k	}
514
515		void _rb_max(const struct rb_type t, const struct rbt_tree *rbt)
516	0	{
517	0	struct rb_entry *rbe = RBH_ROOT(rbt);
518	0	struct rb_entry *parent = NULL;
519
520	0	while (rbe != NULL) {
521	0	parent = rbe;
522	0	rbe = RBE_RIGHT(rbe);
523	0	}
524
525	0	return (parent == NULL ? NULL : rb_e2n(t, parent));
526	0	}
527
528		void _rb_left(const struct rb_type t, void *node)
529	0	{
530	0	struct rb_entry *rbe = rb_n2e(t, node);
531	0	rbe = RBE_LEFT(rbe);
532	0	return (rbe == NULL ? NULL : rb_e2n(t, rbe));
533	0	}
534
535		void _rb_right(const struct rb_type t, void *node)
536	0	{
537	0	struct rb_entry *rbe = rb_n2e(t, node);
538	0	rbe = RBE_RIGHT(rbe);
539	0	return (rbe == NULL ? NULL : rb_e2n(t, rbe));
540	0	}
541
542		void _rb_parent(const struct rb_type t, void *node)
543	0	{
544	0	struct rb_entry *rbe = rb_n2e(t, node);
545	0	rbe = RBE_PARENT(rbe);
546	0	return (rbe == NULL ? NULL : rb_e2n(t, rbe));
547	0	}
548
549		void _rb_set_left(const struct rb_type t, void node, void *left)
550	0	{
551	0	struct rb_entry *rbe = rb_n2e(t, node);
552	0	struct rb_entry *rbl = (left == NULL) ? NULL : rb_n2e(t, left);
553
554	0	RBE_LEFT(rbe) = rbl;
555	0	}
556
557		void _rb_set_right(const struct rb_type t, void node, void *right)
558	0	{
559	0	struct rb_entry *rbe = rb_n2e(t, node);
560	0	struct rb_entry *rbr = (right == NULL) ? NULL : rb_n2e(t, right);
561
562	0	RBE_RIGHT(rbe) = rbr;
563	0	}
564
565		void _rb_set_parent(const struct rb_type t, void node, void *parent)
566	0	{
567	0	struct rb_entry *rbe = rb_n2e(t, node);
568	0	struct rb_entry *rbp = (parent == NULL) ? NULL : rb_n2e(t, parent);
569
570	0	RBE_PARENT(rbe) = rbp;
571	0	}
572
573		void _rb_poison(const struct rb_type t, void node, unsigned long poison)
574	0	{
575	0	struct rb_entry *rbe = rb_n2e(t, node);
576
577	0	RBE_PARENT(rbe) = RBE_LEFT(rbe) = RBE_RIGHT(rbe) =
578	0	(struct rb_entry *)poison;
579	0	}
580
581		int _rb_check(const struct rb_type t, void node, unsigned long poison)
582	0	{
583	0	struct rb_entry *rbe = rb_n2e(t, node);
584
585	0	return ((unsigned long)RBE_PARENT(rbe) == poison
586	0	&& (unsigned long)RBE_LEFT(rbe) == poison
587	0	&& (unsigned long)RBE_RIGHT(rbe) == poison);
588	0	}