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