src/vppinfra/rbtree.h

   1 /*
   2  * Copyright (c) 2019 Cisco and/or its affiliates.
   3  * Licensed under the Apache License, Version 2.0 (the "License");
   4  * you may not use this file except in compliance with the License.
   5  * You may obtain a copy of the License at:
   6  *
   7  *     http://www.apache.org/licenses/LICENSE-2.0
   8  *
   9  * Unless required by applicable law or agreed to in writing, software
  10  * distributed under the License is distributed on an "AS IS" BASIS,
  11  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12  * See the License for the specific language governing permissions and
  13  * limitations under the License.
  14  */
  15
  16 #ifndef SRC_VPPINFRA_RBTREE_H_
  17 #define SRC_VPPINFRA_RBTREE_H_
  18
  19 #include <vppinfra/types.h>
  20 #include <vppinfra/pool.h>
  21
  22 #define RBTREE_TNIL_INDEX 0
  23
  24 typedef u32 rb_node_index_t;
  25
  26 typedef enum rb_tree_color_
  27 {
  28   RBTREE_RED,
  29   RBTREE_BLACK
  30 } rb_node_color_t;
  31
  32 typedef struct rb_node_
  33 {
  34   u8 color;                     /**< node color */
  35   rb_node_index_t parent;       /**< parent index */
  36   rb_node_index_t left;         /**< left child index */
  37   rb_node_index_t right;        /**< right child index */
  38   u32 key;                      /**< node key */
  39   uword opaque;                 /**< value stored by node */
  40 } rb_node_t;
  41
  42 typedef struct rb_tree_
  43 {
  44   rb_node_t *nodes;             /**< pool of nodes */
  45   rb_node_index_t root;         /**< root index */
  46 } rb_tree_t;
  47
  48 typedef int (*rb_tree_lt_fn) (u32 a, u32 b);
  49
  50 void rb_tree_init (rb_tree_t * rt);
  51 rb_node_index_t rb_tree_add (rb_tree_t * rt, u32 key);
  52 rb_node_index_t rb_tree_add2 (rb_tree_t * rt, u32 key, uword opaque);
  53 rb_node_index_t rb_tree_add_custom (rb_tree_t * rt, u32 key, uword opaque,
  54                                     rb_tree_lt_fn ltfn);
  55 void rb_tree_del (rb_tree_t * rt, u32 key);
  56 void rb_tree_del_node (rb_tree_t * rt, rb_node_t * z);
  57 void rb_tree_del_custom (rb_tree_t * rt, u32 key, rb_tree_lt_fn ltfn);
  58 void rb_tree_free_nodes (rb_tree_t * rt);
  59 u32 rb_tree_n_nodes (rb_tree_t * rt);
  60 rb_node_t *rb_tree_min_subtree (rb_tree_t * rt, rb_node_t * x);
  61 rb_node_t *rb_tree_max_subtree (rb_tree_t * rt, rb_node_t * x);
  62 rb_node_t *rb_tree_search_subtree (rb_tree_t * rt, rb_node_t * x, u32 key);
  63 rb_node_t *rb_tree_search_subtree_custom (rb_tree_t * rt, rb_node_t * x,
  64                                           u32 key, rb_tree_lt_fn ltfn);
  65 rb_node_t *rb_tree_successor (rb_tree_t * rt, rb_node_t * x);
  66 rb_node_t *rb_tree_predecessor (rb_tree_t * rt, rb_node_t * x);
  67 int rb_tree_is_init (rb_tree_t * rt);
  68
  69 static inline rb_node_index_t
  70 rb_node_index (rb_tree_t * rt, rb_node_t * n)
  71 {
  72   return n - rt->nodes;
  73 }
  74
  75 static inline u8
  76 rb_node_is_tnil (rb_tree_t * rt, rb_node_t * n)
  77 {
  78   return rb_node_index (rt, n) == RBTREE_TNIL_INDEX;
  79 }
  80
  81 static inline rb_node_t *
  82 rb_node (rb_tree_t * rt, rb_node_index_t ri)
  83 {
  84   return pool_elt_at_index (rt->nodes, ri);
  85 }
  86
  87 static inline rb_node_t *
  88 rb_node_right (rb_tree_t * rt, rb_node_t * n)
  89 {
  90   return pool_elt_at_index (rt->nodes, n->right);
  91 }
  92
  93 static inline rb_node_t *
  94 rb_node_left (rb_tree_t * rt, rb_node_t * n)
  95 {
  96   return pool_elt_at_index (rt->nodes, n->left);
  97 }
  98
  99 static inline rb_node_t *
 100 rb_node_parent (rb_tree_t * rt, rb_node_t * n)
 101 {
 102   return pool_elt_at_index (rt->nodes, n->parent);
 103 }
 104
 105 #endif /* SRC_VPPINFRA_RBTREE_H_ */
 106
 107 /*
 108  * fd.io coding-style-patch-verification: ON
 109  *
 110  * Local Variables:
 111  * eval: (c-set-style "gnu")
 112  * End:
 113  */