Home | History | Annotate | Download | only in lib 
      1 /*******************************************************************************
      2 * Copyright (C) 2018 Cadence Design Systems, Inc.
      3 *
      4 * Permission is hereby granted, free of charge, to any person obtaining
      5 * a copy of this software and associated documentation files (the
      6 * "Software"), to use this Software with Cadence processor cores only and
      7 * not with any other processors and platforms, subject to
      8 * the following conditions:
      9 *
     10 * The above copyright notice and this permission notice shall be included
     11 * in all copies or substantial portions of the Software.
     12 *
     13 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
     14 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
     15 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
     16 * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
     17 * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
     18 * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
     19 * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
     20 
     21 ******************************************************************************/
     22 
     23 /*******************************************************************************
     24  * rbtree.h
     25  *
     26  * Generic implmentation of red-black trees
     27  *
     28  *******************************************************************************/
     29 
     30 #ifndef __RBTREE_H
     31 #define __RBTREE_H
     32 
     33 /*******************************************************************************
     34  * Red-black tree node definition
     35  ******************************************************************************/
     36 
     37 /* ...reference to rb-tree node */
     38 typedef struct rb_node  *rb_idx_t;
     39 
     40 /* ...rb-tree node */
     41 typedef struct rb_node
     42 {
     43     /* ...pointers to parent and two children */
     44     rb_idx_t            parent, left, right;
     45 
     46     /* ...node color (least-significant-bit only) */
     47     u32                 color;
     48 
     49 }   rb_node_t;
     50 
     51 /* ...rb-tree data */
     52 typedef struct rb_tree_t
     53 {
     54     /* ...tree sentinel node */
     55     rb_node_t           root;
     56 
     57 }   rb_tree_t;
     58 
     59 /*******************************************************************************
     60  * Helpers
     61  ******************************************************************************/
     62 
     63 /* ...left child accessor */
     64 static inline rb_idx_t rb_left(rb_tree_t *tree, rb_idx_t n_idx)
     65 {
     66     return n_idx->left;
     67 }
     68 
     69 /* ...right child accessor */
     70 static inline rb_idx_t rb_right(rb_tree_t *tree, rb_idx_t n_idx)
     71 {
     72     return n_idx->right;
     73 }
     74 
     75 /* ...parent node accessor */
     76 static inline rb_idx_t rb_parent(rb_tree_t *tree, rb_idx_t n_idx)
     77 {
     78     return n_idx->parent;
     79 }
     80 
     81 /* ...tree root node accessor */
     82 static inline rb_idx_t rb_root(rb_tree_t *tree)
     83 {
     84     return rb_left(tree, &tree->root);
     85 }
     86 
     87 /* ...tree data pointer accessor */
     88 static inline rb_idx_t rb_cache(rb_tree_t *tree)
     89 {
     90     return rb_right(tree, &tree->root);
     91 }
     92 
     93 /* ...tree null node */
     94 static inline rb_idx_t rb_null(rb_tree_t *tree)
     95 {
     96     return &tree->root;
     97 }
     98 
     99 /* ...get user-bits stored in node color */
    100 static inline u32 rb_node_data(rb_tree_t *tree, rb_idx_t n_idx)
    101 {
    102     return (n_idx->color >> 1);
    103 }
    104 
    105 /* ...left child assignment */
    106 static inline void rb_set_left(rb_tree_t *tree, rb_idx_t n_idx, rb_node_t *child)
    107 {
    108     n_idx->left = child;
    109 }
    110 
    111 /* ...right child assignment */
    112 static inline void rb_set_right(rb_tree_t *tree, rb_idx_t n_idx, rb_node_t *child)
    113 {
    114     n_idx->right = child;
    115 }
    116 
    117 /* ...cache tree client index */
    118 static inline void rb_set_cache(rb_tree_t *tree, rb_idx_t c_idx)
    119 {
    120     tree->root.right = c_idx;
    121 }
    122 
    123 /* ...get user-bits stored in node color */
    124 static inline void rb_set_node_data(rb_tree_t *tree, rb_idx_t n_idx, u32 data)
    125 {
    126     n_idx->color = (n_idx->color & 0x1) | (data << 1);
    127 }
    128 
    129 /*******************************************************************************
    130  * API functions
    131  ******************************************************************************/
    132 
    133 /* ...initialize rb-tree */
    134 extern void     rb_init(rb_tree_t *tree);
    135 
    136 /* ...insert node into tree as a child of p */
    137 extern void     rb_insert(rb_tree_t *tree, rb_idx_t n_idx, rb_idx_t p_idx);
    138 
    139 /* ...replace the node with same-key value and fixup tree pointers */
    140 extern void     rb_replace(rb_tree_t *tree, rb_idx_t n_idx, rb_idx_t t_idx);
    141 
    142 /* ...delete node from the tree and return its in-order predecessor/successor */
    143 extern rb_idx_t rb_delete(rb_tree_t *tree, rb_idx_t n_idx);
    144 
    145 /* ...first in-order item in the tree */
    146 extern rb_idx_t rb_first(rb_tree_t *tree);
    147 
    148 /* ...last in-order item in the tree */
    149 extern rb_idx_t rb_last(rb_tree_t *tree);
    150 
    151 /* ...forward tree iterator */
    152 extern rb_idx_t rb_next(rb_tree_t *tree, rb_idx_t n_idx);
    153 
    154 /* ...backward tree iterator */
    155 extern rb_idx_t rb_prev(rb_tree_t *tree, rb_idx_t n_idx);
    156 
    157 #endif  /* __RBTREE_H */
    158