Line data    Source code

       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     1147195 : rb_node_index (rb_tree_t * rt, rb_node_t * n)
      71             : {
      72     1147195 :   return n - rt->nodes;
      73             : }
      74             : 
      75             : static inline u8
      76     1085399 : rb_node_is_tnil (rb_tree_t * rt, rb_node_t * n)
      77             : {
      78     1085399 :   return rb_node_index (rt, n) == RBTREE_TNIL_INDEX;
      79             : }
      80             : 
      81             : static inline rb_node_t *
      82      573124 : rb_node (rb_tree_t * rt, rb_node_index_t ri)
      83             : {
      84      573124 :   return pool_elt_at_index (rt->nodes, ri);
      85             : }
      86             : 
      87             : static inline rb_node_t *
      88     1062884 : rb_node_right (rb_tree_t * rt, rb_node_t * n)
      89             : {
      90     1062884 :   return pool_elt_at_index (rt->nodes, n->right);
      91             : }
      92             : 
      93             : static inline rb_node_t *
      94        8226 : rb_node_left (rb_tree_t * rt, rb_node_t * n)
      95             : {
      96        8226 :   return pool_elt_at_index (rt->nodes, n->left);
      97             : }
      98             : 
      99             : static inline rb_node_t *
     100       19371 : rb_node_parent (rb_tree_t * rt, rb_node_t * n)
     101             : {
     102       19371 :   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             :  */