Gitiles
Code Review Sign In
gerrit.devboardsforandroid.linaro.org / device / linaro / hikey960 / 4dce66122cb339f55492e908176d5ee8257bf9a7 / . / hifi / xaf / hifi-dpf / include / lib / rbtree.h
blob: 7f02cdf3f88a475d622a0a418d8daa053097147c [file] [log] [blame]
Steve Muckle0a9c0872022-02-16 05:58:07 +0000[diff] [blame]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 */
38typedef struct rb_node *rb_idx_t;
39
40/* ...rb-tree node */
41typedef 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 */
52typedef 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 */
64static 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 */
70static 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 */
76static 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 */
82static 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 */
88static inline rb_idx_t rb_cache(rb_tree_t *tree)
89{
90 return rb_right(tree, &tree->root);
91}
92
93/* ...tree null node */
94static 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 */
100static 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 */
106static 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 */
112static 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 */
118static 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 */
124static 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 */
134extern void rb_init(rb_tree_t *tree);
135
136/* ...insert node into tree as a child of p */
137extern 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 */
140extern 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 */
143extern rb_idx_t rb_delete(rb_tree_t *tree, rb_idx_t n_idx);
144
145/* ...first in-order item in the tree */
146extern rb_idx_t rb_first(rb_tree_t *tree);
147
148/* ...last in-order item in the tree */
149extern rb_idx_t rb_last(rb_tree_t *tree);
150
151/* ...forward tree iterator */
152extern rb_idx_t rb_next(rb_tree_t *tree, rb_idx_t n_idx);
153
154/* ...backward tree iterator */
155extern rb_idx_t rb_prev(rb_tree_t *tree, rb_idx_t n_idx);
156
157#endif /* __RBTREE_H */