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