aboutsummaryrefslogtreecommitdiffstats
path: root/test/vpp_neighbor.py
AgeCommit message (Expand)AuthorFilesLines
2022-05-10tests: replace pycodestyle with blackKlement Sekera1-23/+23
2021-03-25stats: python vpp_stats rewrite to access stat segment directlyOle Troan1-1/+1
2020-10-08ip-neighbor: Grat ARPs from different subnet are droppedNeale Ranns1-1/+2
2020-04-28tests: implement ipaddress convenience methodsPaul Vinciguerra1-5/+2
2019-12-17ip: Protocol Independent IP NeighborsNeale Ranns1-2/+5
2019-11-05ip: Fragmentation fixesNeale Ranns1-0/+1
2019-03-29tests: refactor vpp_object.pyPaul Vinciguerra1-3/+0
2019-03-01Tests: Trivial fox use of 'is'.Paul Vinciguerra1-1/+1
2019-03-01Tests: Remove all wildcard imports.Paul Vinciguerra1-1/+1
2019-02-26VPP-1508 python tests: unicodePaul Vinciguerra1-1/+5
2019-01-30Use IP and MAC API types for neighborsNeale Ranns1-27/+27
2018-12-18PAPI: Add MACAddress object wrapper for vl_api_mac_address_tOle Troan1-3/+3
2018-12-10Test framework: StringIO fixes for Python3Ole Troan1-1/+1
2018-10-01Add adjacency counters to the stats segmentNeale Ranns1-1/+6
2018-06-08Gratuitous ARP packet handlingNeale Ranns1-2/+6
2018-03-28test: fix VppNeighbor.query_vpp_configNeale Ranns1-14/+10
2017-04-19Learn IP6 link-local ND entries from NSs sourced from link-local addressNeale Ranns1-1/+1
2017-03-09IMplementation for option to not create a FIB table entry when adding a neigh...Neale Ranns1-2/+4
2017-03-03IPv6 RA improvementsNeale Ranns1-1/+1
2017-02-27[Proxy] ARP testsNeale Ranns1-0/+77
href='#n402'>402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509
/*
 * 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);
}

__clib_export 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);
}

__clib_export 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);
}

__clib_export 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;
      ASSERT (z->key != x->key);
      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);
}

__clib_export 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;
}

__clib_export 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;
}

__clib_export 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;
}

__clib_export 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;
}

__clib_export 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;
}

__clib_export 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;
}

static void
rb_tree_del_node_internal (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;
}

__clib_export void
rb_tree_del_node (rb_tree_t * rt, rb_node_t * z)
{
  rb_tree_del_node_internal (rt, z);
  pool_put (rt->nodes, z);
}

__clib_export 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);
}

__clib_export 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);
}

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

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

__clib_export 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;
}

__clib_export int
rb_tree_is_init (rb_tree_t * rt)
{
  if (pool_elts (rt->nodes) == 0)
    return 0;
  return 1;
}

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