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 */
rb_left(rb_tree_t * tree,rb_idx_t n_idx)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 */
rb_right(rb_tree_t * tree,rb_idx_t n_idx)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 */
rb_parent(rb_tree_t * tree,rb_idx_t n_idx)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 */
rb_root(rb_tree_t * tree)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 */
rb_cache(rb_tree_t * tree)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 */
rb_null(rb_tree_t * tree)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 */
rb_node_data(rb_tree_t * tree,rb_idx_t n_idx)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 */
rb_set_left(rb_tree_t * tree,rb_idx_t n_idx,rb_node_t * child)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 */
rb_set_right(rb_tree_t * tree,rb_idx_t n_idx,rb_node_t * child)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 */
rb_set_cache(rb_tree_t * tree,rb_idx_t c_idx)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 */
rb_set_node_data(rb_tree_t * tree,rb_idx_t n_idx,u32 data)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