/*
 * l2_bvi.h : layer 2 Bridged Virtual Interface
 *
 * Copyright (c) 2013 Cisco and/or its affiliates.
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at:
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#ifndef included_l2bvi_h
#define included_l2bvi_h

#include <vlib/vlib.h>
#include <vnet/ethernet/ethernet.h>
#include <vppinfra/sparse_vec.h>

#include <vnet/l2/l2_input.h>

#define TO_BVI_ERR_OK        0
#define TO_BVI_ERR_BAD_MAC   1
#define TO_BVI_ERR_ETHERTYPE 2

/**
 * Send a packet from L2 processing to L3 via the BVI interface.
 * Set next0 to the proper L3 input node.
 * Return an error if the packet isn't what we expect.
 */

static_always_inline u32
l2_to_bvi (vlib_main_t * vlib_main,
	   vnet_main_t * vnet_main,
	   vlib_buffer_t * b0,
	   u32 bvi_sw_if_index, next_by_ethertype_t * l3_next, u16 * next0)
{
  /* Perform L3 my-mac filter */
  ethernet_header_t *e0 = vlib_buffer_get_current (b0);
  if (!ethernet_address_cast (e0->dst_address))
    {
      vnet_hw_interface_t *hi =
	vnet_get_sup_hw_interface (vnet_main, bvi_sw_if_index);
      if (!ethernet_mac_address_equal (e0->dst_address, hi->
@media only all and (prefers-color-scheme: dark) {
.highlight .hll { background-color: #49483e }
.highlight .c { color: #75715e } /* Comment */
.highlight .err { color: #960050; background-color: #1e0010 } /* Error */
.highlight .k { color: #66d9ef } /* Keyword */
.highlight .l { color: #ae81ff } /* Literal */
.highlight .n { color: #f8f8f2 } /* Name */
.highlight .o { color: #f92672 } /* Operator */
.highlight .p { color: #f8f8f2 } /* Punctuation */
.highlight .ch { color: #75715e } /* Comment.Hashbang */
.highlight .cm { color: #75715e } /* Comment.Multiline */
.highlight .cp { color: #75715e } /* Comment.Preproc */
.highlight .cpf { color: #75715e } /* Comment.PreprocFile */
.highlight .c1 { color: #75715e } /* Comment.Single */
.highlight .cs { color: #75715e } /* Comment.Special */
.highlight .gd { color: #f92672 } /* Generic.Deleted */
.highlight .ge { font-style: italic } /* Generic.Emph */
.highlight .gi { color: #a6e22e } /* Generic.Inserted */
.highlight .gs { font-weight: bold } /* Generic.Strong */
.highlight .gu { color: #75715e } /* Generic.Subheading */
.highlight .kc { color: #66d9ef } /* Keyword.Constant */
.highlight .kd { color: #66d9ef } /* Keyword.Declaration */
.highlight .kn { color: #f92672 } /* Keyword.Namespace */
.highlight .kp { color: #66d9ef } /* Keyword.Pseudo */
.highlight .kr { color: #66d9ef } /* Keyword.Reserved */
.highlight .kt { color: #66d9ef } /* Keyword.Type */
.highlight .ld { color: #e6db74 } /* Literal.Date */
.highlight .m { color: #ae81ff } /* Literal.Number */
.highlight .s { color: #e6db74 } /* Literal.String */
.highlight .na { color: #a6e22e } /* Name.Attribute */
.highlight .nb { color: #f8f8f2 } /* Name.Builtin */
.highlight .nc { color: #a6e22e } /* Name.Class */
.highlight .no { color: #66d9ef } /* Name.Constant */
.highlight .nd { color: #a6e22e } /* Name.Decorator */
.highlight .ni { color: #f8f8f2 } /* Name.Entity */
.highlight .ne { color: #a6e22e } /* Name.Exception */
.highlight .nf { color: #a6e22e } /* Name.Function */
.highlight .nl { color: #f8f8f2 } /* Name.Label */
.highlight .nn { color: #f8f8f2 } /* Name.Namespace */
.highlight .nx { color: #a6e22e } /* Name.Other */
.highlight .py { color: #f8f8f2 } /* Name.Property */
.highlight .nt { color: #f92672 } /* Name.Tag */
.highlight .nv { color: #f8f8f2 } /* Name.Variable */
.highlight .ow { color: #f92672 } /* Operator.Word */
.highlight .w { color: #f8f8f2 } /* Text.Whitespace */
.highlight .mb { color: #ae81ff } /* Literal.Number.Bin */
.highlight .mf { color: #ae81ff } /* Literal.Number.Float */
.highlight .mh { color: #ae81ff } /* Literal.Number.Hex */
.highlight .mi { color: #ae81ff } /* Literal.Number.Integer */
.highlight .mo { color: #ae81ff } /* Literal.Number.Oct */
.highlight .sa { color: #e6db74 } /* Literal.String.Affix */
.highlight .sb { color: #e6db74 } /* Literal.String.Backtick */
.highlight .sc { color: #e6db74 } /* Literal.String.Char */
.highlight .dl { color: #e6db74 } /* Literal.String.Delimiter */
.highlight .sd { color: #e6db74 } /* Literal.String.Doc */
.highlight .s2 { color: #e6db74 } /* Literal.String.Double */
.highlight .se { color: #ae81ff } /* Literal.String.Escape */
.highlight .sh { color: #e6db74 } /* Literal.String.Heredoc */
.highlight .si { color: #e6db74 } /* Literal.String.Interpol */
.highlight .sx { color: #e6db74 } /* Literal.String.Other */
.highlight .sr { color: #e6db74 } /* Literal.String.Regex */
.highlight .s1 { color: #e6db74 } /* Literal.String.Single */
.highlight .ss { color: #e6db74 } /* Literal.String.Symbol */
.highlight .bp { color: #f8f8f2 } /* Name.Builtin.Pseudo */
.highlight .fm { color: #a6e22e } /* Name.Function.Magic */
.highlight .vc { color: #f8f8f2 } /* Name.Variable.Class */
.highlight .vg { color: #f8f8f2 } /* Name.Variable.Global */
.highlight .vi { color: #f8f8f2 } /* Name.Variable.Instance */
.highlight .vm { color: #f8f8f2 } /* Name.Variable.Magic */
.highlight .il { color: #ae81ff } /* Literal.Number.Integer.Long */
}
@media (prefers-color-scheme: light) {
.highlight .hll { background-color: #ffffcc }
.highlight .c { color: #888888 } /* Comment */
.highlight .err { color: #a61717; background-color: #e3d2d2 } /* Error */
.highlight .k { color: #008800; font-weight: bold } /* Keyword */
.highlight .ch { color: #888888 } /* Comment.Hashbang */
.highlight .cm { color: #888888 } /* Comment.Multiline */
.highlight .cp { color: #cc0000; font-weight: bold } /* Comment.Preproc */
.highlight .cpf { color: #888888 } /* Comment.PreprocFile */
.highlight .c1 { color: #888888 } /* Comment.Single */
.highlight .cs { color: #cc0000; font-weight: bold; background-color: #fff0f0 } /* Comment.Special */
.highlight .gd { color: #000000; background-color: #ffdddd } /* Generic.Deleted */
.highlight .ge { font-style: italic } /* Generic.Emph */
.highlight .gr { color: #aa0000 } /* Generic.Error */
.highlight .gh { color: #333333 } /* Generic.Heading */
.highlight .gi { color: #000000; background-color: #ddffdd } /* Generic.Inserted */
.highlight .go { color: #888888 } /* Generic.Output */
.highlight .gp { color: #555555 } /* Generic.Prompt */
.highlight .gs { font-weight: bold } /* Generic.Strong */
.highlight .gu { color: #666666 } /* Generic.Subheading */
.highlight .gt { color: #aa0000 } /* Generic.Traceback */
.highlight .kc { color: #008800; font-weight: bold } /* Keyword.Constant */
.highlight .kd { color: #008800; font-weight: bold } /* Keyword.Declaration */
.highlight .kn { color: #008800; font-weight: bold } /* Keyword.Namespace */
.highlight .kp { color: #008800 } /* Keyword.Pseudo */
.highlight .kr { color: #008800; font-weight: bold } /* Keyword.Reserved */
.highlight .kt { color: #888888; font-weight: bold } /* Keyword.Type */
.highlight .m { color: #0000DD; font-weight: bold } /* Literal.Number */
.highlight .s { color: #dd2200; background-color: #fff0f0 } /* Literal.String */
.highlight .na { color: #336699 } /* Name.Attribute */
.highlight .nb { color: #003388 } /* Name.Builtin */
.highlight .nc { color: #bb0066; font-weight: bold } /* Name.Class */
.highlight .no { color: #003366; font-weight: bold } /* Name.Constant */
.highlight .nd { color: #555555 } /* Name.Decorator */
.highlight .ne { color: #bb0066; font-weight: bold } /* Name.Exception */
.highlight .nf { color: #0066bb; font-weight: bold } /* Name.Function */
.highlight .nl { color: #336699; font-style: italic } /* Name.Label */
.highlight .nn { color: #bb0066; font-weight: bold } /* Name.Namespace */
.highlight .py { color: #336699; font-weight: bold } /* Name.Property */
.highlight .nt { color: #bb0066; font-weight: bold } /* Name.Tag */
.highlight .nv { color: #336699 } /* Name.Variable */
.highlight .ow { color: #008800 } /* Operator.Word */
.highlight .w { color: #bbbbbb } /* Text.Whitespace */
.highlight .mb { color: #0000DD; font-weight: bold } /* Literal.Number.Bin */
.highlight .mf { color: #0000DD; font-weight: bold } /* Literal.Number.Float */
.highlight .mh { color: #0000DD; font-weight: bold } /* Literal.Number.Hex */
.highlight .mi { color: #0000DD; font-weight: bold } /* Literal.Number.Integer */
.highlight .mo { color: #0000DD; font-weight: bold } /* Literal.Number.Oct */
.highlight .sa { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Affix */
.highlight .sb { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Backtick */
.highlight .sc { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Char */
.highlight .dl { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Delimiter */
.highlight .sd { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Doc */
.highlight .s2 { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Double */
.highlight .se { color: #0044dd; background-color: #fff0f0 } /* Literal.String.Escape */
.highlight .sh { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Heredoc */
.highlight .si { color: #3333bb; background-color: #fff0f0 } /* Literal.String.Interpol */
.highlight .sx { color: #22bb22; background-color: #f0fff0 } /* Literal.String.Other */
.highlight .sr { color: #008800; background-color: #fff0ff } /* Literal.String.Regex */
.highlight .s1 { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Single */
.highlight .ss { color: #aa6600; background-color: #fff0f0 } /* Literal.String.Symbol */
.highlight .bp { color: #003388 } /* Name.Builtin.Pseudo */
.highlight .fm { color: #0066bb; font-weight: bold } /* Name.Function.Magic */
.highlight .vc { color: #336699 } /* Name.Variable.Class */
.highlight .vg { color: #dd7700 } /* Name.Variable.Global */
.highlight .vi { color: #3333bb } /* Name.Variable.Instance */
.highlight .vm { color: #336699 } /* Name.Variable.Magic */
.highlight .il { color: #0000DD; font-weight: bold } /* Literal.Number.Integer.Long */
}
/*
 * Copyright (c) 2019 Cisco and/or its affiliates.
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at:
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
/*
 * Algorithm from:
 * Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009).
 * Introduction to algorithms. MIT press, 3rd Edition, Ch. 13
 */

#include <vppinfra/rbtree.h>

static inline void
rb_tree_rotate_left (rb_tree_t * rt, rb_node_t * x)
{
  rb_node_t *y, *tmp, *xp;
  rb_node_index_t xi, yi;

  xi = rb_node_index (rt, x);
  yi = x->right;
  y = rb_node_right (rt, x);
  x->right = y->left;
  if (y->left != RBTREE_TNIL_INDEX)
    {
      tmp = rb_node_left (rt, y);
      tmp->parent = xi;
    }
  xp = rb_node_parent (rt, x);
  y->parent = x->parent;
  if (x->parent == RBTREE_TNIL_INDEX)
    rt->root = rb_node_index (rt, y);
  else if (xp->left == xi)
    xp->left = yi;
  else
    xp->right = yi;
  y->left = xi;
  x->parent = yi;
}

static inline void
rb_tree_rotate_right (rb_tree_t * rt, rb_node_t * y)
{
  rb_node_index_t yi, xi;
  rb_node_t *x, *yp;

  yi = rb_node_index (rt, y);
  xi = y->left;
  x = rb_node_left (rt, y);
  y->left = x->right;
  if (x->right != RBTREE_TNIL_INDEX)
    {
      rb_node_t *tmp = rb_node_right (rt, x);
      tmp->parent = yi;
    }
  yp = rb_node_parent (rt, y);
  x->parent = y->parent;
  if (y->parent == RBTREE_TNIL_INDEX)
    rt->root = rb_node_index (rt, x);
  else if (yp->right == yi)
    yp->right = xi;
  else
    yp->left = xi;
  x->right = yi;
  y->parent = xi;
}

static inline void
rb_tree_fixup_inline (rb_tree_t * rt, rb_node_t * y, rb_node_t * z)
{
  rb_node_t *zpp, *zp;
  rb_node_index_t zi;

  while (y->color == RBTREE_RED)
    {
      zi = rb_node_index (rt, z);
      zp = rb_node_parent (rt, z);
      zpp = rb_node_parent (rt, zp);
      if (z->parent == zpp->left)
	{
	  y = rb_node_right (rt, zpp);
	  if (y->color == RBTREE_RED)
	    {
	      zp->color = RBTREE_BLACK;
	      y->color = RBTREE_BLACK;
	      zpp->color = RBTREE_RED;
	      z = zpp;
	    }
	  else
	    {
	      if (zi == zp->right)
		{
		  z = zp;
		  rb_tree_rotate_left (rt, z);
		  zp = rb_node (rt, z->parent);
		  zpp = rb_node (rt, zp->parent);
		}
	      zp->color = RBTREE_BLACK;
	      zpp->color = RBTREE_RED;
	      rb_tree_rotate_right (rt, zpp);
	    }
	}
      else
	{
	  y = rb_node (rt, zpp->left);
	  if (y->color == RBTREE_RED)
	    {
	      zp->color = RBTREE_BLACK;
	      y->color = RBTREE_BLACK;
	      zpp->color = RBTREE_RED;
	      z = zpp;
	    }
	  else
	    {
	      if (zi == zp->left)
		{
		  z = zp;
		  rb_tree_rotate_right (rt, z);
		  zp = rb_node (rt, z->parent);
		  zpp = rb_node (rt, zp->parent);
		}
	      zp->color = RBTREE_BLACK;
	      zpp->color = RBTREE_RED;
	      rb_tree_rotate_left (rt, zpp);
	    }
	}
    }
  rb_node (rt, rt->root)->color = RBTREE_BLACK;
}

static void
rb_tree_insert (rb_tree_t * rt, rb_node_t * z)
{
  rb_node_index_t yi = 0, xi = rt->root;
  rb_node_t *y, *x;

  y = rb_node (rt, RBTREE_TNIL_INDEX);
  while (xi != RBTREE_TNIL_INDEX)
    {
      x = rb_node (rt, xi);
      y = x;
      if (z->key < x->key)
	xi = x->left;
      else
	xi = x->right;
    }
  yi = rb_node_index (rt, y);
  z->parent = yi;
  if (yi == RBTREE_TNIL_INDEX)
    rt->root = rb_node_index (rt, z);
  else if (z->key < y->key)
    y->left = rb_node_index (rt, z);
  else
    y->right = rb_node_index (rt, z);

  /* Tree fixup stage */
  rb_tree_fixup_inline (rt, y, z);
}

rb_node_index_t
rb_tree_add (rb_tree_t * rt, u32 key)
{
  rb_node_t *n;

  pool_get_zero (rt->nodes, n);
  n->key = key;
  n->color = RBTREE_RED;
  rb_tree_insert (rt, n);
  return rb_node_index (rt, n);
}

rb_node_index_t
rb_tree_add2 (rb_tree_t * rt, u32 key, uword opaque)
{
  rb_node_t *n;

  pool_get_zero (rt->nodes, n);
  n->key = key;
  n->color = RBTREE_RED;
  n->opaque = opaque;
  rb_tree_insert (rt, n);
  return rb_node_index (rt, n);
}

rb_node_index_t
rb_tree_add_custom (rb_tree_t * rt, u32 key, uword opaque, rb_tree_lt_fn ltfn)
{
  rb_node_index_t yi = 0, xi = rt->root;
  rb_node_t *z, *y, *x;

  pool_get_zero (rt->nodes, z);
  z->key = key;
  z->color = RBTREE_RED;
  z->opaque = opaque;

  y = rb_node (rt, RBTREE_TNIL_INDEX);
  while (xi != RBTREE_TNIL_INDEX)
    {
      x = rb_node (rt, xi);
      y = x;
      if (ltfn (z->key, x->key))
	xi = x->left;
      else
	xi = x->right;
    }
  yi = rb_node_index (rt, y);
  z->parent = yi;
  if (yi == RBTREE_TNIL_INDEX)
    rt->root = rb_node_index (rt, z);
  else if (ltfn (z->key, y->key))
    y->left = rb_node_index (rt, z);
  else
    y->right = rb_node_index (rt, z);

  rb_tree_fixup_inline (rt, y, z);

  return rb_node_index (rt, z);
}

rb_node_t *
rb_tree_search_subtree (rb_tree_t * rt, rb_node_t * x, u32 key)
{
  while (rb_node_index (rt, x) != RBTREE_TNIL_INDEX && key != x->key)
    if (key < x->key)
      x = rb_node_left (rt, x);
    else
      x = rb_node_right (rt, x);
  return x;
}

rb_node_t *
rb_tree_search_subtree_custom (rb_tree_t * rt, rb_node_t * x, u32 key,
			       rb_tree_lt_fn ltfn)
{
  while (rb_node_index (rt, x) != RBTREE_TNIL_INDEX && key != x->key)
    if (ltfn (key, x->key))
      x = rb_node_left (rt, x);
    else
      x = rb_node_right (rt, x);
  return x;
}

rb_node_t *
rb_tree_min_subtree (rb_tree_t * rt, rb_node_t * x)
{
  while (x->left != RBTREE_TNIL_INDEX)
    x = rb_node_left (rt, x);
  return x;
}

rb_node_t *
rb_tree_max_subtree (rb_tree_t * rt, rb_node_t * x)
{
  while (x->right != RBTREE_TNIL_INDEX)
    x = rb_node_right (rt, x);
  return x;
}

rb_node_t *
rb_tree_successor (rb_tree_t * rt, rb_node_t * x)
{
  rb_node_t *y;

  if (x->right != RBTREE_TNIL_INDEX)
    return rb_tree_min_subtree (rt, rb_node_right (rt, x));

  y = rb_node_parent (rt, x);
  while (!rb_node_is_tnil (rt, y) && y->right == rb_node_index (rt, x))
    {
      x = y;
      y = rb_node_parent (rt, y);
    }
  return y;
}

rb_node_t *
rb_tree_predecessor (rb_tree_t * rt, rb_node_t * x)
{
  rb_node_t *y;

  if (x->left != RBTREE_TNIL_INDEX)
    return rb_tree_max_subtree (rt, rb_node_left (rt, x));

  y = rb_node_parent (rt, x);
  while (!rb_node_is_tnil (rt, y) && y->left == rb_node_index (rt, x))
    {
      x = y;
      y = rb_node_parent (rt, y);
    }
  return y;
}

static inline void
rb_tree_transplant (rb_tree_t * rt, rb_node_t * u, rb_node_t * v)
{
  rb_node_t *up;

  up = rb_node_parent (rt, u);
  if (u->parent == RBTREE_TNIL_INDEX)
    rt->root = rb_node_index (rt, v);
  else if (rb_node_index (rt, u) == up->left)
    up->left = rb_node_index (rt, v);
  else
    up->right = rb_node_index (rt, v);
  v->parent = u->parent;
}

void
rb_tree_del_node (rb_tree_t * rt, rb_node_t * z)
{
  rb_node_color_t y_original_color;
  rb_node_t *x, *y, *yr, *yl, *xp, *w, *wl, *wr;
  rb_node_index_t xi, yi;

  y = z;
  y_original_color = y->color;

  if (z->left == RBTREE_TNIL_INDEX)
    {
      x = rb_node_right (rt, z);
      rb_tree_transplant (rt, z, x);
    }
  else if (z->right == RBTREE_TNIL_INDEX)
    {
      x = rb_node_left (rt, z);
      rb_tree_transplant (rt, z, x);
    }
  else
    {
      y = rb_tree_min_subtree (rt, rb_node_right (rt, z));
      y_original_color = y->color;
      x = rb_node_right (rt, y);
      yi = rb_node_index (rt, y);
      if (y->parent == rb_node_index (rt, z))
	x->parent = yi;
      else
	{
	  rb_tree_transplant (rt, y, x);
	  y->right = z->right;
	  yr = rb_node_right (rt, y);
	  yr->parent = yi;
	}
      rb_tree_transplant (rt, z, y);
      y->left = z->left;
      yl = rb_node_left (rt, y);
      yl->parent = yi;
      y->color = z->color;
    }

  if (y_original_color == RBTREE_RED)
    return;

  /* Tree fixup needed */

  xi = rb_node_index (rt, x);
  while (xi != rt->root && x->color == RBTREE_BLACK)
    {
      xp = rb_node_parent (rt, x);
      if (xi == xp->left)
	{
	  w = rb_node_right (rt, xp);
	  if (w->color == RBTREE_RED)
	    {
	      w->color = RBTREE_BLACK;
	      xp->color = RBTREE_RED;
	      rb_tree_rotate_left (rt, xp);
	      w = rb_node_right (rt, xp);
	    }
	  wl = rb_node_left (rt, w);
	  wr = rb_node_right (rt, w);
	  if (wl->color == RBTREE_BLACK && wr->color == RBTREE_BLACK)
	    {
	      if (!rb_node_is_tnil (rt, w))
		w->color = RBTREE_RED;
	      x = xp;
	    }
	  else
	    {
	      if (wr->color == RBTREE_BLACK)
		{
		  wl->color = RBTREE_BLACK;
		  w->color = RBTREE_RED;
		  rb_tree_rotate_right (rt, w);
		  w = rb_node_right (rt, xp);
		  wr = rb_node_right (rt, w);
		}
	      w->color = xp->color;
	      xp->color = RBTREE_BLACK;
	      wr->color = RBTREE_BLACK;
	      rb_tree_rotate_left (rt, xp);
	      x = rb_node (rt, rt->root);
	    }
	}
      else
	{
	  w = rb_node_left (rt, xp);
	  if (w->color == RBTREE_RED)
	    {
	      w->color = RBTREE_BLACK;
	      xp->color = RBTREE_RED;
	      rb_tree_rotate_right (rt, xp);
	      w = rb_node_left (rt, xp);
	    }
	  wl = rb_node_left (rt, w);
	  wr = rb_node_right (rt, w);
	  if (wl->color == RBTREE_BLACK && wr->color == RBTREE_BLACK)
	    {
	      if (!rb_node_is_tnil (rt, w))
		w->color = RBTREE_RED;
	      x = xp;
	    }
	  else
	    {
	      if (wl->color == RBTREE_BLACK)
		{
		  wr->color = RBTREE_BLACK;
		  w->color = RBTREE_RED;
		  rb_tree_rotate_left (rt, w);
		  w = rb_node_left (rt, xp);
		  wl = rb_node_left (rt, w);
		}
	      w->color = xp->color;
	      xp->color = RBTREE_BLACK;
	      wl->color = RBTREE_BLACK;
	      rb_tree_rotate_right (rt, xp);
	      x = rb_node (rt, rt->root);
	    }
	}
      xi = rb_node_index (rt, x);
    }
  x->color = RBTREE_BLACK;
}

void
rb_tree_del (rb_tree_t * rt, u32 key)
{
  rb_node_t *n;
  n = rb_tree_search_subtree (rt, rb_node (rt, rt->root), key);
  if (rb_node_index (rt, n) != RBTREE_TNIL_INDEX)
    {
      rb_tree_del_node (rt, n);
      pool_put (rt->nodes, n);
    }
}

void
rb_tree_del_custom (rb_tree_t * rt, u32 key, rb_tree_lt_fn ltfn)
{
  rb_node_t *n;
  n = rb_tree_search_subtree_custom (rt, rb_node (rt, rt->root), key, ltfn);
  if (rb_node_index (rt, n) != RBTREE_TNIL_INDEX)
    {
      rb_tree_del_node (rt, n);
      pool_put (rt->nodes, n);
    }
}

u32
rb_tree_n_nodes (rb_tree_t * rt)
{
  return pool_elts (rt->nodes);
}

void
rb_tree_free_nodes (rb_tree_t * rt)
{
  pool_free (rt->nodes);
  rt->root = RBTREE_TNIL_INDEX;
}

void
rb_tree_init (rb_tree_t * rt)
{
  rb_node_t *tnil;

  rt->nodes = 0;
  rt->root = RBTREE_TNIL_INDEX;

  /* By convention first node, index 0, is the T.nil sentinel */
  pool_get_zero (rt->nodes, tnil);
  tnil->color = RBTREE_BLACK;
}

/*
 * fd.io coding-style-patch-verification: ON
 *
 * Local Variables:
 * eval: (c-set-style "gnu")
 * End:
 */