summaryrefslogtreecommitdiff
path: root/src/common
diff options
context:
space:
mode:
Diffstat (limited to 'src/common')
-rw-r--r--src/common/tree.h251
1 files changed, 2 insertions, 249 deletions
diff --git a/src/common/tree.h b/src/common/tree.h
index a6b636646..4a295f894 100644
--- a/src/common/tree.h
+++ b/src/common/tree.h
@@ -27,33 +27,10 @@
27 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28 */ 28 */
29 29
30#ifndef _SYS_TREE_H_ 30#pragma once
31#define _SYS_TREE_H_
32
33/* FreeBSD <sys/cdefs.h> has a lot of defines we don't really want. */
34/* tree.h only actually uses __inline and __unused, so we'll just define those. */
35
36/* #include <sys/cdefs.h> */
37
38#ifndef __inline
39#define __inline inline
40#endif
41 31
42/* 32/*
43 * This file defines data structures for different types of trees: 33 * This file defines data structures for red-black trees.
44 * splay trees and red-black trees.
45 *
46 * A splay tree is a self-organizing data structure. Every operation
47 * on the tree causes a splay to happen. The splay moves the requested
48 * node to the root of the tree and partly rebalances it.
49 *
50 * This has the benefit that request locality causes faster lookups as
51 * the requested nodes move to the top of the tree. On the other hand,
52 * every lookup causes memory writes.
53 *
54 * The Balance Theorem bounds the total access time for m operations
55 * and n inserts on an initially empty tree as O((m + n)lg n). The
56 * amortized cost for a sequence of m accesses to a splay tree is O(lg n);
57 * 34 *
58 * A red-black tree is a binary search tree with the node color as an 35 * A red-black tree is a binary search tree with the node color as an
59 * extra attribute. It fulfills a set of conditions: 36 * extra attribute. It fulfills a set of conditions:
@@ -66,228 +43,6 @@
66 * The maximum height of a red-black tree is 2lg (n+1). 43 * The maximum height of a red-black tree is 2lg (n+1).
67 */ 44 */
68 45
69#define SPLAY_HEAD(name, type) \
70 struct name { \
71 struct type* sph_root; /* root of the tree */ \
72 }
73
74#define SPLAY_INITIALIZER(root) \
75 { NULL }
76
77#define SPLAY_INIT(root) \
78 do { \
79 (root)->sph_root = NULL; \
80 } while (/*CONSTCOND*/ 0)
81
82#define SPLAY_ENTRY(type) \
83 struct { \
84 struct type* spe_left; /* left element */ \
85 struct type* spe_right; /* right element */ \
86 }
87
88#define SPLAY_LEFT(elm, field) (elm)->field.spe_left
89#define SPLAY_RIGHT(elm, field) (elm)->field.spe_right
90#define SPLAY_ROOT(head) (head)->sph_root
91#define SPLAY_EMPTY(head) (SPLAY_ROOT(head) == NULL)
92
93/* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */
94#define SPLAY_ROTATE_RIGHT(head, tmp, field) \
95 do { \
96 SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field); \
97 SPLAY_RIGHT(tmp, field) = (head)->sph_root; \
98 (head)->sph_root = tmp; \
99 } while (/*CONSTCOND*/ 0)
100
101#define SPLAY_ROTATE_LEFT(head, tmp, field) \
102 do { \
103 SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field); \
104 SPLAY_LEFT(tmp, field) = (head)->sph_root; \
105 (head)->sph_root = tmp; \
106 } while (/*CONSTCOND*/ 0)
107
108#define SPLAY_LINKLEFT(head, tmp, field) \
109 do { \
110 SPLAY_LEFT(tmp, field) = (head)->sph_root; \
111 tmp = (head)->sph_root; \
112 (head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \
113 } while (/*CONSTCOND*/ 0)
114
115#define SPLAY_LINKRIGHT(head, tmp, field) \
116 do { \
117 SPLAY_RIGHT(tmp, field) = (head)->sph_root; \
118 tmp = (head)->sph_root; \
119 (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \
120 } while (/*CONSTCOND*/ 0)
121
122#define SPLAY_ASSEMBLE(head, node, left, right, field) \
123 do { \
124 SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \
125 SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field); \
126 SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \
127 SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \
128 } while (/*CONSTCOND*/ 0)
129
130/* Generates prototypes and inline functions */
131
132#define SPLAY_PROTOTYPE(name, type, field, cmp) \
133 void name##_SPLAY(struct name*, struct type*); \
134 void name##_SPLAY_MINMAX(struct name*, int); \
135 struct type* name##_SPLAY_INSERT(struct name*, struct type*); \
136 struct type* name##_SPLAY_REMOVE(struct name*, struct type*); \
137 \
138 /* Finds the node with the same key as elm */ \
139 static __inline struct type* name##_SPLAY_FIND(struct name* head, struct type* elm) { \
140 if (SPLAY_EMPTY(head)) \
141 return (NULL); \
142 name##_SPLAY(head, elm); \
143 if ((cmp)(elm, (head)->sph_root) == 0) \
144 return (head->sph_root); \
145 return (NULL); \
146 } \
147 \
148 static __inline struct type* name##_SPLAY_NEXT(struct name* head, struct type* elm) { \
149 name##_SPLAY(head, elm); \
150 if (SPLAY_RIGHT(elm, field) != NULL) { \
151 elm = SPLAY_RIGHT(elm, field); \
152 while (SPLAY_LEFT(elm, field) != NULL) { \
153 elm = SPLAY_LEFT(elm, field); \
154 } \
155 } else \
156 elm = NULL; \
157 return (elm); \
158 } \
159 \
160 static __inline struct type* name##_SPLAY_MIN_MAX(struct name* head, int val) { \
161 name##_SPLAY_MINMAX(head, val); \
162 return (SPLAY_ROOT(head)); \
163 }
164
165/* Main splay operation.
166 * Moves node close to the key of elm to top
167 */
168#define SPLAY_GENERATE(name, type, field, cmp) \
169 struct type* name##_SPLAY_INSERT(struct name* head, struct type* elm) { \
170 if (SPLAY_EMPTY(head)) { \
171 SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL; \
172 } else { \
173 int __comp; \
174 name##_SPLAY(head, elm); \
175 __comp = (cmp)(elm, (head)->sph_root); \
176 if (__comp < 0) { \
177 SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field); \
178 SPLAY_RIGHT(elm, field) = (head)->sph_root; \
179 SPLAY_LEFT((head)->sph_root, field) = NULL; \
180 } else if (__comp > 0) { \
181 SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field); \
182 SPLAY_LEFT(elm, field) = (head)->sph_root; \
183 SPLAY_RIGHT((head)->sph_root, field) = NULL; \
184 } else \
185 return ((head)->sph_root); \
186 } \
187 (head)->sph_root = (elm); \
188 return (NULL); \
189 } \
190 \
191 struct type* name##_SPLAY_REMOVE(struct name* head, struct type* elm) { \
192 struct type* __tmp; \
193 if (SPLAY_EMPTY(head)) \
194 return (NULL); \
195 name##_SPLAY(head, elm); \
196 if ((cmp)(elm, (head)->sph_root) == 0) { \
197 if (SPLAY_LEFT((head)->sph_root, field) == NULL) { \
198 (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \
199 } else { \
200 __tmp = SPLAY_RIGHT((head)->sph_root, field); \
201 (head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \
202 name##_SPLAY(head, elm); \
203 SPLAY_RIGHT((head)->sph_root, field) = __tmp; \
204 } \
205 return (elm); \
206 } \
207 return (NULL); \
208 } \
209 \
210 void name##_SPLAY(struct name* head, struct type* elm) { \
211 struct type __node, *__left, *__right, *__tmp; \
212 int __comp; \
213 \
214 SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL; \
215 __left = __right = &__node; \
216 \
217 while ((__comp = (cmp)(elm, (head)->sph_root)) != 0) { \
218 if (__comp < 0) { \
219 __tmp = SPLAY_LEFT((head)->sph_root, field); \
220 if (__tmp == NULL) \
221 break; \
222 if ((cmp)(elm, __tmp) < 0) { \
223 SPLAY_ROTATE_RIGHT(head, __tmp, field); \
224 if (SPLAY_LEFT((head)->sph_root, field) == NULL) \
225 break; \
226 } \
227 SPLAY_LINKLEFT(head, __right, field); \
228 } else if (__comp > 0) { \
229 __tmp = SPLAY_RIGHT((head)->sph_root, field); \
230 if (__tmp == NULL) \
231 break; \
232 if ((cmp)(elm, __tmp) > 0) { \
233 SPLAY_ROTATE_LEFT(head, __tmp, field); \
234 if (SPLAY_RIGHT((head)->sph_root, field) == NULL) \
235 break; \
236 } \
237 SPLAY_LINKRIGHT(head, __left, field); \
238 } \
239 } \
240 SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \
241 } \
242 \
243 /* Splay with either the minimum or the maximum element \
244 * Used to find minimum or maximum element in tree. \
245 */ \
246 void name##_SPLAY_MINMAX(struct name* head, int __comp) { \
247 struct type __node, *__left, *__right, *__tmp; \
248 \
249 SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL; \
250 __left = __right = &__node; \
251 \
252 while (1) { \
253 if (__comp < 0) { \
254 __tmp = SPLAY_LEFT((head)->sph_root, field); \
255 if (__tmp == NULL) \
256 break; \
257 if (__comp < 0) { \
258 SPLAY_ROTATE_RIGHT(head, __tmp, field); \
259 if (SPLAY_LEFT((head)->sph_root, field) == NULL) \
260 break; \
261 } \
262 SPLAY_LINKLEFT(head, __right, field); \
263 } else if (__comp > 0) { \
264 __tmp = SPLAY_RIGHT((head)->sph_root, field); \
265 if (__tmp == NULL) \
266 break; \
267 if (__comp > 0) { \
268 SPLAY_ROTATE_LEFT(head, __tmp, field); \
269 if (SPLAY_RIGHT((head)->sph_root, field) == NULL) \
270 break; \
271 } \
272 SPLAY_LINKRIGHT(head, __left, field); \
273 } \
274 } \
275 SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \
276 }
277
278#define SPLAY_NEGINF -1
279#define SPLAY_INF 1
280
281#define SPLAY_INSERT(name, x, y) name##_SPLAY_INSERT(x, y)
282#define SPLAY_REMOVE(name, x, y) name##_SPLAY_REMOVE(x, y)
283#define SPLAY_FIND(name, x, y) name##_SPLAY_FIND(x, y)
284#define SPLAY_NEXT(name, x, y) name##_SPLAY_NEXT(x, y)
285#define SPLAY_MIN(name, x) (SPLAY_EMPTY(x) ? NULL : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF))
286#define SPLAY_MAX(name, x) (SPLAY_EMPTY(x) ? NULL : name##_SPLAY_MIN_MAX(x, SPLAY_INF))
287
288#define SPLAY_FOREACH(x, name, head) \
289 for ((x) = SPLAY_MIN(name, head); (x) != NULL; (x) = SPLAY_NEXT(name, head, x))
290
291/* Macros that define a red-black tree */ 46/* Macros that define a red-black tree */
292#define RB_HEAD(name, type) \ 47#define RB_HEAD(name, type) \
293 struct name { \ 48 struct name { \
@@ -818,5 +573,3 @@
818#define RB_FOREACH_REVERSE_SAFE(x, name, head, y) \ 573#define RB_FOREACH_REVERSE_SAFE(x, name, head, y) \
819 for ((x) = RB_MAX(name, head); ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL); \ 574 for ((x) = RB_MAX(name, head); ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL); \
820 (x) = (y)) 575 (x) = (y))
821
822#endif /* _SYS_TREE_H_ */
HIC SVNT DRACONES