aboutsummaryrefslogtreecommitdiffstats
path: root/VPP_STABLE_VER_CENTOS
AgeCommit message (Expand)AuthorFilesLines
2020-09-16Update of VPP_STABLE_VER filesJan Gelety1-1/+1
2020-10-12Update of VPP_STABLE_VER filesJan Gelety1-1/+1
2020-09-14Update of VPP_STABLE_VER filesJan Gelety1-1/+1
2020-09-12Downgrade vpp build to version 21.01-rc0~112-g2c714a0ceJan Gelety1-1/+1
2020-09-29Update of VPP_STABLE_VER filesJan Gelety1-1/+1
2020-09-22Framework: Heapsize configurationpmikus1-1/+1
2020-09-21Update of VPP_STABLE_VER filesJan Gelety1-1/+1
2020-09-04Update of VPP_STABLE_VER filesJan Gelety1-1/+1
2020-08-09Update of VPP_STABLE_VER filesJan Gelety1-1/+1
2020-08-17Update of VPP_STABLE_VER filesJan Gelety1-1/+1
2020-08-05Update of VPP_STABLE_VER filesJan Gelety1-1/+1
2020-07-23Update of VPP_STABLE_VER filesJan Gelety1-1/+1
2020-07-21Update of VPP_STABLE_VER filesJan Gelety1-1/+1
2020-07-20Update of VPP_STABLE_VER filesJan Gelety1-1/+1
2020-07-13Update of VPP_STABLE_VER filesJan Gelety1-1/+1
2020-06-15Update of VPP_STABLE_VER filesJan Gelety1-1/+1
2020-05-27Update of VPP_STABLE_VER filesJan Gelety1-1/+1
2020-05-28Update of VPP_STABLE_VER filesJan Gelety1-1/+1
2020-05-25Update of VPP_STABLE_VER filesJan Gelety1-1/+1
2020-05-19Update of VPP_STABLE_VER filesJan Gelety1-1/+1
2020-05-11CSIT-1597 API cleanup: ipsecJan Gelety1-1/+1
2020-04-28CSIT-1597 API cleanup: lispJan Gelety1-1/+1
2020-04-02CSIT-1597 API cleanup: virtioJan Gelety1-1/+1
2020-04-02Update of VPP_STABLE_VER filesJan Gelety1-1/+1
2020-04-20Update of VPP_STABLE_VER filesJan Gelety1-1/+1
2020-03-29Update of VPP_STABLE_VER filesJan Gelety1-1/+1
2020-04-06Update of VPP_STABLE_VER filesJan Gelety1-1/+1
2020-03-27CSIT-1597 API cleanup: aclJan Gelety1-1/+1
2020-03-24CSIT-1597 API cleanup: srv6Jan Gelety1-1/+1
2020-03-17CSIT-1597 API cleanup: vpeJan Gelety1-1/+1
2020-03-16CSIT-1597 API cleanup: vxlanJan Gelety1-1/+1
2020-03-10CSIT-1597 API cleanup: policerJan Gelety1-1/+1
2020-03-10CSIT-1597 API cleanup: ipsecJan Gelety1-1/+1
2020-03-09CSIT-1597 API cleanup: l2Jan Gelety1-1/+1
2020-03-09Update of VPP_STABLE_VER filesJan Gelety1-1/+1
2020-03-03Update of VPP_STABLE_VER filesJan Gelety1-1/+1
2020-02-25Update of VPP_STABLE_VER filesJan Gelety1-1/+1
2020-02-11Update of VPP_STABLE_VER filesJan Gelety1-1/+1
2020-01-19Update of VPP_STABLE_VER filesJan Gelety1-1/+1
2020-01-19Update of VPP_STABLE_VER filesJan Gelety1-1/+1
2020-01-20Update of VPP_STABLE_VER filesJan Gelety1-1/+1
2020-01-13CSIT-1597 API cleanup: rdmaJan Gelety1-1/+1
2020-01-07Update of VPP_STABLE_VER filesJan Gelety1-1/+1
2019-12-12CSIT-1597, CSIT-1647 API cleanup: gbpJan Gelety1-1/+1
2019-12-12API: Add collection for 23835/1Jan Gelety1-1/+1
2019-12-01API: Add collection for 23830/1Jan Gelety1-1/+1
2019-12-01CSIT-1597 API cleanup: vhostJan Gelety1-1/+1
2019-12-11CSIT-1597 API cleanup: tapJan Gelety1-1/+1
2019-12-10CSIT-1597 API cleanup: classifyJan Gelety1-1/+1
2019-11-14Update of VPP_STABLE_VER filesJan Gelety1-1/+1
n>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: */