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

Source
// 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: 2026-02-21 06:33

Line	Count	Source
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	328k	{
22	328k	unsigned long addr = (unsigned long)node;
23
24	328k	return ((struct rb_entry *)(addr + t->t_offset));
25	328k	}
26
27		static inline void rb_e2n(const struct rb_type t, struct rb_entry *rbe)
28	3.38M	{
29	3.38M	unsigned long addr = (unsigned long)rbe;
30
31	3.38M	return ((void *)(addr - t->t_offset));
32	3.38M	}
33
34	2.38M	#define RBE_LEFT(_rbe) (_rbe)->rbt_left
35	2.43M	#define RBE_RIGHT(_rbe) (_rbe)->rbt_right
36	1.42M	#define RBE_PARENT(_rbe) (_rbe)->rbt_parent
37	553k	#define RBE_COLOR(_rbe) (_rbe)->rbt_color
38
39	590k	#define RBH_ROOT(_rbt) (_rbt)->rbt_root
40
41		static inline void rbe_set(struct rb_entry rbe, struct rb_entry parent)
42	43.2k	{
43	43.2k	RBE_PARENT(rbe) = parent;
44	43.2k	RBE_LEFT(rbe) = RBE_RIGHT(rbe) = NULL;
45	43.2k	RBE_COLOR(rbe) = RB_RED;
46	43.2k	}
47
48		static inline void rbe_set_blackred(struct rb_entry *black,
49		struct rb_entry *red)
50	49.0k	{
51	49.0k	RBE_COLOR(black) = RB_BLACK;
52	49.0k	RBE_COLOR(red) = RB_RED;
53	49.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	104k	{
62	104k	if (t->t_augment != NULL)
63	0	rbe_augment(t, rbe);
64	104k	}
65
66		static inline void rbe_rotate_left(const struct rb_type *t,
67		struct rbt_tree rbt, struct rb_entry rbe)
68	31.2k	{
69	31.2k	struct rb_entry *parent;
70	31.2k	struct rb_entry *tmp;
71
72	31.2k	tmp = RBE_RIGHT(rbe);
73	31.2k	RBE_RIGHT(rbe) = RBE_LEFT(tmp);
74	31.2k	if (RBE_RIGHT(rbe) != NULL)
75	13.0k	RBE_PARENT(RBE_LEFT(tmp)) = rbe;
76
77	31.2k	parent = RBE_PARENT(rbe);
78	31.2k	RBE_PARENT(tmp) = parent;
79	31.2k	if (parent != NULL) {
80	31.2k	if (rbe == RBE_LEFT(parent))
81	18.3k	RBE_LEFT(parent) = tmp;
82	12.9k	else
83	12.9k	RBE_RIGHT(parent) = tmp;
84	31.2k	} else
85	5	RBH_ROOT(rbt) = tmp;
86
87	31.2k	RBE_LEFT(tmp) = rbe;
88	31.2k	RBE_PARENT(rbe) = tmp;
89
90	31.2k	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.2k	}
98
99		static inline void rbe_rotate_right(const struct rb_type *t,
100		struct rbt_tree rbt, struct rb_entry rbe)
101	18.0k	{
102	18.0k	struct rb_entry *parent;
103	18.0k	struct rb_entry *tmp;
104
105	18.0k	tmp = RBE_LEFT(rbe);
106	18.0k	RBE_LEFT(rbe) = RBE_RIGHT(tmp);
107	18.0k	if (RBE_LEFT(rbe) != NULL)
108	5.84k	RBE_PARENT(RBE_RIGHT(tmp)) = rbe;
109
110	18.0k	parent = RBE_PARENT(rbe);
111	18.0k	RBE_PARENT(tmp) = parent;
112	18.0k	if (parent != NULL) {
113	18.0k	if (rbe == RBE_LEFT(parent))
114	5.86k	RBE_LEFT(parent) = tmp;
115	12.1k	else
116	12.1k	RBE_RIGHT(parent) = tmp;
117	18.0k	} else
118	1	RBH_ROOT(rbt) = tmp;
119
120	18.0k	RBE_RIGHT(tmp) = rbe;
121	18.0k	RBE_PARENT(rbe) = tmp;
122
123	18.0k	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	18.0k	}
131
132		static inline void rbe_insert_color(const struct rb_type *t,
133		struct rbt_tree rbt, struct rb_entry rbe)
134	43.2k	{
135	43.2k	struct rb_entry parent, gparent, *tmp;
136
137	87.4k	while ((parent = RBE_PARENT(rbe)) != NULL
138	87.4k	&& RBE_COLOR(parent) == RB_RED) {
139	44.2k	gparent = RBE_PARENT(parent);
140
141	44.2k	if (parent == RBE_LEFT(gparent)) {
142	14.8k	tmp = RBE_RIGHT(gparent);
143	14.8k	if (tmp != NULL && RBE_COLOR(tmp) == RB_RED) {
144	5.07k	RBE_COLOR(tmp) = RB_BLACK;
145	5.07k	rbe_set_blackred(parent, gparent);
146	5.07k	rbe = gparent;
147	5.07k	continue;
148	5.07k	}
149
150	9.77k	if (RBE_RIGHT(parent) == rbe) {
151	7.67k	rbe_rotate_left(t, rbt, parent);
152	7.67k	tmp = parent;
153	7.67k	parent = rbe;
154	7.67k	rbe = tmp;
155	7.67k	}
156
157	9.77k	rbe_set_blackred(parent, gparent);
158	9.77k	rbe_rotate_right(t, rbt, gparent);
159	29.3k	} else {
160	29.3k	tmp = RBE_LEFT(gparent);
161	29.3k	if (tmp != NULL && RBE_COLOR(tmp) == RB_RED) {
162	16.1k	RBE_COLOR(tmp) = RB_BLACK;
163	16.1k	rbe_set_blackred(parent, gparent);
164	16.1k	rbe = gparent;
165	16.1k	continue;
166	16.1k	}
167
168	13.2k	if (RBE_LEFT(parent) == rbe) {
169	2.90k	rbe_rotate_right(t, rbt, parent);
170	2.90k	tmp = parent;
171	2.90k	parent = rbe;
172	2.90k	rbe = tmp;
173	2.90k	}
174
175	13.2k	rbe_set_blackred(parent, gparent);
176	13.2k	rbe_rotate_left(t, rbt, gparent);
177	13.2k	}
178	44.2k	}
179
180	43.2k	RBE_COLOR(RBH_ROOT(rbt)) = RB_BLACK;
181	43.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	36.8k	{
188	36.8k	struct rb_entry *tmp;
189
190	57.6k	while ((rbe == NULL \|\| RBE_COLOR(rbe) == RB_BLACK)
191	29.6k	&& rbe != RBH_ROOT(rbt) && parent) {
192	29.6k	if (RBE_LEFT(parent) == rbe) {
193	18.7k	tmp = RBE_RIGHT(parent);
194	18.7k	if (RBE_COLOR(tmp) == RB_RED) {
195	3.22k	rbe_set_blackred(tmp, parent);
196	3.22k	rbe_rotate_left(t, rbt, parent);
197	3.22k	tmp = RBE_RIGHT(parent);
198	3.22k	}
199	18.7k	if ((RBE_LEFT(tmp) == NULL
200	7.19k	\|\| RBE_COLOR(RBE_LEFT(tmp)) == RB_BLACK)
201	16.2k	&& (RBE_RIGHT(tmp) == NULL
202	13.1k	\|\| RBE_COLOR(RBE_RIGHT(tmp)) == RB_BLACK)) {
203	13.1k	RBE_COLOR(tmp) = RB_RED;
204	13.1k	rbe = parent;
205	13.1k	parent = RBE_PARENT(rbe);
206	13.1k	} else {
207	5.59k	if (RBE_RIGHT(tmp) == NULL
208	5.23k	\|\| RBE_COLOR(RBE_RIGHT(tmp)) == RB_BLACK) {
209	532	struct rb_entry *oleft;
210
211	532	oleft = RBE_LEFT(tmp);
212	532	if (oleft != NULL)
213	532	RBE_COLOR(oleft) = RB_BLACK;
214
215	532	RBE_COLOR(tmp) = RB_RED;
216	532	rbe_rotate_right(t, rbt, tmp);
217	532	tmp = RBE_RIGHT(parent);
218	532	}
219
220	5.59k	RBE_COLOR(tmp) = RBE_COLOR(parent);
221	5.59k	RBE_COLOR(parent) = RB_BLACK;
222	5.59k	if (RBE_RIGHT(tmp))
223	5.59k	RBE_COLOR(RBE_RIGHT(tmp)) = RB_BLACK;
224
225	5.59k	rbe_rotate_left(t, rbt, parent);
226	5.59k	rbe = RBH_ROOT(rbt);
227	5.59k	break;
228	5.59k	}
229	18.7k	} else {
230	10.8k	tmp = RBE_LEFT(parent);
231	10.8k	if (RBE_COLOR(tmp) == RB_RED) {
232	1.62k	rbe_set_blackred(tmp, parent);
233	1.62k	rbe_rotate_right(t, rbt, parent);
234	1.62k	tmp = RBE_LEFT(parent);
235	1.62k	}
236
237	10.8k	if ((RBE_LEFT(tmp) == NULL
238	4.06k	\|\| RBE_COLOR(RBE_LEFT(tmp)) == RB_BLACK)
239	9.13k	&& (RBE_RIGHT(tmp) == NULL
240	7.64k	\|\| RBE_COLOR(RBE_RIGHT(tmp)) == RB_BLACK)) {
241	7.64k	RBE_COLOR(tmp) = RB_RED;
242	7.64k	rbe = parent;
243	7.64k	parent = RBE_PARENT(rbe);
244	7.64k	} else {
245	3.23k	if (RBE_LEFT(tmp) == NULL
246	1.75k	\|\| RBE_COLOR(RBE_LEFT(tmp)) == RB_BLACK) {
247	1.49k	struct rb_entry *oright;
248
249	1.49k	oright = RBE_RIGHT(tmp);
250	1.49k	if (oright != NULL)
251	1.49k	RBE_COLOR(oright) = RB_BLACK;
252
253	1.49k	RBE_COLOR(tmp) = RB_RED;
254	1.49k	rbe_rotate_left(t, rbt, tmp);
255	1.49k	tmp = RBE_LEFT(parent);
256	1.49k	}
257
258	3.23k	RBE_COLOR(tmp) = RBE_COLOR(parent);
259	3.23k	RBE_COLOR(parent) = RB_BLACK;
260	3.23k	if (RBE_LEFT(tmp) != NULL)
261	3.23k	RBE_COLOR(RBE_LEFT(tmp)) = RB_BLACK;
262
263	3.23k	rbe_rotate_right(t, rbt, parent);
264	3.23k	rbe = RBH_ROOT(rbt);
265	3.23k	break;
266	3.23k	}
267	10.8k	}
268	29.6k	}
269
270	36.8k	if (rbe != NULL)
271	36.8k	RBE_COLOR(rbe) = RB_BLACK;
272	36.8k	}
273
274		static inline struct rb_entry *
275		rbe_remove(const struct rb_type t, struct rbt_tree rbt, struct rb_entry *rbe)
276	42.5k	{
277	42.5k	struct rb_entry child, parent, *old = rbe;
278	42.5k	unsigned int color;
279
280	42.5k	if (RBE_LEFT(rbe) == NULL)
281	19.6k	child = RBE_RIGHT(rbe);
282	22.9k	else if (RBE_RIGHT(rbe) == NULL)
283	3.84k	child = RBE_LEFT(rbe);
284	19.0k	else {
285	19.0k	struct rb_entry *tmp;
286
287	19.0k	rbe = RBE_RIGHT(rbe);
288	39.6k	while ((tmp = RBE_LEFT(rbe)) != NULL)
289	20.5k	rbe = tmp;
290
291	19.0k	child = RBE_RIGHT(rbe);
292	19.0k	parent = RBE_PARENT(rbe);
293	19.0k	color = RBE_COLOR(rbe);
294	19.0k	if (child != NULL)
295	6.16k	RBE_PARENT(child) = parent;
296	19.0k	if (parent != NULL) {
297	19.0k	if (RBE_LEFT(parent) == rbe)
298	12.8k	RBE_LEFT(parent) = child;
299	6.23k	else
300	6.23k	RBE_RIGHT(parent) = child;
301
302	19.0k	rbe_if_augment(t, parent);
303	19.0k	} else
304	0	RBH_ROOT(rbt) = child;
305	19.0k	if (RBE_PARENT(rbe) == old)
306	6.23k	parent = rbe;
307	19.0k	rbe = old;
308
309	19.0k	tmp = RBE_PARENT(old);
310	19.0k	if (tmp != NULL) {
311	19.0k	if (RBE_LEFT(tmp) == old)
312	13.1k	RBE_LEFT(tmp) = rbe;
313	5.93k	else
314	5.93k	RBE_RIGHT(tmp) = rbe;
315
316	19.0k	rbe_if_augment(t, tmp);
317	19.0k	} else
318	0	RBH_ROOT(rbt) = rbe;
319
320	19.0k	RBE_PARENT(RBE_LEFT(old)) = rbe;
321	19.0k	if (RBE_RIGHT(old))
322	14.5k	RBE_PARENT(RBE_RIGHT(old)) = rbe;
323
324	19.0k	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	19.0k	goto color;
333	19.0k	}
334
335	23.4k	parent = RBE_PARENT(rbe);
336	23.4k	color = RBE_COLOR(rbe);
337
338	23.4k	if (child != NULL)
339	8.36k	RBE_PARENT(child) = parent;
340	23.4k	if (parent != NULL) {
341	23.4k	if (RBE_LEFT(parent) == rbe)
342	13.9k	RBE_LEFT(parent) = child;
343	9.49k	else
344	9.49k	RBE_RIGHT(parent) = child;
345
346	23.4k	rbe_if_augment(t, parent);
347	23.4k	} else
348	0	RBH_ROOT(rbt) = child;
349	42.5k	color:
350	42.5k	if (color == RB_BLACK)
351	36.8k	rbe_remove_color(t, rbt, parent, child);
352
353	42.5k	return (old);
354	23.4k	}
355
356		void _rb_remove(const struct rb_type t, struct rbt_tree rbt, void elm)
357	42.5k	{
358	42.5k	struct rb_entry *rbe = rb_n2e(t, elm);
359	42.5k	struct rb_entry *old;
360
361	42.5k	old = rbe_remove(t, rbt, rbe);
362
363	42.5k	return (old == NULL ? NULL : rb_e2n(t, old));
364	42.5k	}
365
366		void _rb_insert(const struct rb_type t, struct rbt_tree rbt, void elm)
367	43.2k	{
368	43.2k	struct rb_entry *rbe = rb_n2e(t, elm);
369	43.2k	struct rb_entry *tmp;
370	43.2k	struct rb_entry *parent = NULL;
371	43.2k	void *node;
372	43.2k	int comp = 0;
373
374	43.2k	tmp = RBH_ROOT(rbt);
375	458k	while (tmp != NULL) {
376	415k	parent = tmp;
377
378	415k	node = rb_e2n(t, tmp);
379	415k	comp = (*t->t_compare)(elm, node);
380	415k	if (comp < 0)
381	190k	tmp = RBE_LEFT(tmp);
382	224k	else if (comp > 0)
383	224k	tmp = RBE_RIGHT(tmp);
384	0	else
385	0	return (node);
386	415k	}
387
388	43.2k	rbe_set(rbe, parent);
389
390	43.2k	if (parent != NULL) {
391	43.2k	if (comp < 0)
392	15.4k	RBE_LEFT(parent) = rbe;
393	27.8k	else
394	27.8k	RBE_RIGHT(parent) = rbe;
395
396	43.2k	rbe_if_augment(t, parent);
397	43.2k	} else
398	13	RBH_ROOT(rbt) = rbe;
399
400	43.2k	rbe_insert_color(t, rbt, rbe);
401
402	43.2k	return NULL;
403	43.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	352k	{
409	352k	struct rb_entry *tmp = RBH_ROOT(rbt);
410	352k	void *node;
411	352k	int comp;
412
413	2.81M	while (tmp != NULL) {
414	2.67M	node = rb_e2n(t, tmp);
415	2.67M	comp = (*t->t_compare)(key, node);
416	2.67M	if (comp < 0)
417	1.18M	tmp = RBE_LEFT(tmp);
418	1.48M	else if (comp > 0)
419	1.27M	tmp = RBE_RIGHT(tmp);
420	213k	else
421	213k	return (node);
422	2.67M	}
423
424	139k	return NULL;
425	352k	}
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	242k	{
453	242k	struct rb_entry *rbe = rb_n2e(t, elm);
454
455	242k	if (RBE_RIGHT(rbe) != NULL) {
456	118k	rbe = RBE_RIGHT(rbe);
457	155k	while (RBE_LEFT(rbe) != NULL)
458	36.2k	rbe = RBE_LEFT(rbe);
459	123k	} else {
460	123k	if (RBE_PARENT(rbe) && (rbe == RBE_LEFT(RBE_PARENT(rbe))))
461	19.0k	rbe = RBE_PARENT(rbe);
462	104k	else {
463	223k	while (RBE_PARENT(rbe)
464	137k	&& (rbe == RBE_RIGHT(RBE_PARENT(rbe))))
465	118k	rbe = RBE_PARENT(rbe);
466	104k	rbe = RBE_PARENT(rbe);
467	104k	}
468	123k	}
469
470	242k	return (rbe == NULL ? NULL : rb_e2n(t, rbe));
471	242k	}
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	97.6k	{
504	97.6k	struct rb_entry *rbe = RBH_ROOT(rbt);
505	97.6k	struct rb_entry *parent = NULL;
506
507	196k	while (rbe != NULL) {
508	98.8k	parent = rbe;
509	98.8k	rbe = RBE_LEFT(rbe);
510	98.8k	}
511
512	97.6k	return (parent == NULL ? NULL : rb_e2n(t, parent));
513	97.6k	}
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	}