projects / darkstat-debian / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
history | raw | HEAD
Imported Upstream version 3.0.715
[darkstat-debian] / tree.h
1 /* This is a cut down version of FreeBSD's
2 * src/sys/sys/tree.h,v 1.5
3 *
4 * Also tagged
5 * $NetBSD: tree.h,v 1.8 2004/03/28 19:38:30 provos Exp $
6 * $OpenBSD: tree.h,v 1.7 2002/10/17 21:51:54 art Exp $
7 *
8 * The original file's license:
9 *
10 * Copyright 2002 Niels Provos <provos@citi.umich.edu>
11 * All rights reserved.
12 *
13 * Redistribution and use in source and binary forms, with or without
14 * modification, are permitted provided that the following conditions
15 * are met:
16 * 1. Redistributions of source code must retain the above copyright
17 * notice, this list of conditions and the following disclaimer.
18 * 2. Redistributions in binary form must reproduce the above copyright
19 * notice, this list of conditions and the following disclaimer in the
20 * documentation and/or other materials provided with the distribution.
21 *
22 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
23 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
24 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
25 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
26 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
27 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
28 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
29 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
30 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
31 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
32 */
33
34 #define RB_HEAD(name, type) \
35 struct name { \
36 struct type *rbh_root; /* root of the tree */ \
37 }
38
39 #define RB_INITIALIZER(root) { NULL }
40
41 #define RB_BLACK 0
42 #define RB_RED 1
43 #define RB_ENTRY(type) \
44 struct { \
45 struct type *rbe_left; /* left element */ \
46 struct type *rbe_right; /* right element */ \
47 struct type *rbe_parent; /* parent element */ \
48 int rbe_color; /* node color */ \
49 }
50
51 #define RB_LEFT(elm, field) (elm)->field.rbe_left
52 #define RB_RIGHT(elm, field) (elm)->field.rbe_right
53 #define RB_PARENT(elm, field) (elm)->field.rbe_parent
54 #define RB_COLOR(elm, field) (elm)->field.rbe_color
55 #define RB_ROOT(head) (head)->rbh_root
56
57 #define RB_SET(elm, parent, field) do { \
58 RB_PARENT(elm, field) = parent; \
59 RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \
60 RB_COLOR(elm, field) = RB_RED; \
61 } while (/*CONSTCOND*/ 0)
62
63 #define RB_SET_BLACKRED(black, red, field) do { \
64 RB_COLOR(black, field) = RB_BLACK; \
65 RB_COLOR(red, field) = RB_RED; \
66 } while (/*CONSTCOND*/ 0)
67
68 #define RB_AUGMENT(x) do {} while (0)
69
70 #define RB_ROTATE_LEFT(head, elm, tmp, field) do { \
71 (tmp) = RB_RIGHT(elm, field); \
72 if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field)) != NULL) { \
73 RB_PARENT(RB_LEFT(tmp, field), field) = (elm); \
74 } \
75 RB_AUGMENT(elm); \
76 if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) { \
77 if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \
78 RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \
79 else \
80 RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
81 } else \
82 (head)->rbh_root = (tmp); \
83 RB_LEFT(tmp, field) = (elm); \
84 RB_PARENT(elm, field) = (tmp); \
85 RB_AUGMENT(tmp); \
86 if ((RB_PARENT(tmp, field))) \
87 RB_AUGMENT(RB_PARENT(tmp, field)); \
88 } while (/*CONSTCOND*/ 0)
89
90 #define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \
91 (tmp) = RB_LEFT(elm, field); \
92 if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field)) != NULL) { \
93 RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \
94 } \
95 RB_AUGMENT(elm); \
96 if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) { \
97 if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \
98 RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \
99 else \
100 RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
101 } else \
102 (head)->rbh_root = (tmp); \
103 RB_RIGHT(tmp, field) = (elm); \
104 RB_PARENT(elm, field) = (tmp); \
105 RB_AUGMENT(tmp); \
106 if ((RB_PARENT(tmp, field))) \
107 RB_AUGMENT(RB_PARENT(tmp, field)); \
108 } while (/*CONSTCOND*/ 0)
109
110 #define RB_GENERATE(name, type, field, cmp) \
111 RB_GENERATE_INTERNAL(name, type, field, cmp, static)
112 #define RB_GENERATE_INTERNAL(name, type, field, cmp, attr) \
113 attr void \
114 name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \
115 { \
116 struct type *parent, *gparent, *tmp; \
117 while ((parent = RB_PARENT(elm, field)) != NULL && \
118 RB_COLOR(parent, field) == RB_RED) { \
119 gparent = RB_PARENT(parent, field); \
120 if (parent == RB_LEFT(gparent, field)) { \
121 tmp = RB_RIGHT(gparent, field); \
122 if (tmp && RB_COLOR(tmp, field) == RB_RED) { \
123 RB_COLOR(tmp, field) = RB_BLACK; \
124 RB_SET_BLACKRED(parent, gparent, field);\
125 elm = gparent; \
126 continue; \
127 } \
128 if (RB_RIGHT(parent, field) == elm) { \
129 RB_ROTATE_LEFT(head, parent, tmp, field);\
130 tmp = parent; \
131 parent = elm; \
132 elm = tmp; \
133 } \
134 RB_SET_BLACKRED(parent, gparent, field); \
135 RB_ROTATE_RIGHT(head, gparent, tmp, field); \
136 } else { \
137 tmp = RB_LEFT(gparent, field); \
138 if (tmp && RB_COLOR(tmp, field) == RB_RED) { \
139 RB_COLOR(tmp, field) = RB_BLACK; \
140 RB_SET_BLACKRED(parent, gparent, field);\
141 elm = gparent; \
142 continue; \
143 } \
144 if (RB_LEFT(parent, field) == elm) { \
145 RB_ROTATE_RIGHT(head, parent, tmp, field);\
146 tmp = parent; \
147 parent = elm; \
148 elm = tmp; \
149 } \
150 RB_SET_BLACKRED(parent, gparent, field); \
151 RB_ROTATE_LEFT(head, gparent, tmp, field); \
152 } \
153 } \
154 RB_COLOR(head->rbh_root, field) = RB_BLACK; \
155 } \
156 \
157 attr void \
158 name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \
159 { \
160 struct type *tmp; \
161 while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) && \
162 elm != RB_ROOT(head)) { \
163 if (RB_LEFT(parent, field) == elm) { \
164 tmp = RB_RIGHT(parent, field); \
165 if (RB_COLOR(tmp, field) == RB_RED) { \
166 RB_SET_BLACKRED(tmp, parent, field); \
167 RB_ROTATE_LEFT(head, parent, tmp, field);\
168 tmp = RB_RIGHT(parent, field); \
169 } \
170 if ((RB_LEFT(tmp, field) == NULL || \
171 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
172 (RB_RIGHT(tmp, field) == NULL || \
173 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
174 RB_COLOR(tmp, field) = RB_RED; \
175 elm = parent; \
176 parent = RB_PARENT(elm, field); \
177 } else { \
178 if (RB_RIGHT(tmp, field) == NULL || \
179 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) {\
180 struct type *oleft; \
181 if ((oleft = RB_LEFT(tmp, field)) \
182 != NULL) \
183 RB_COLOR(oleft, field) = RB_BLACK;\
184 RB_COLOR(tmp, field) = RB_RED; \
185 RB_ROTATE_RIGHT(head, tmp, oleft, field);\
186 tmp = RB_RIGHT(parent, field); \
187 } \
188 RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
189 RB_COLOR(parent, field) = RB_BLACK; \
190 if (RB_RIGHT(tmp, field)) \
191 RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\
192 RB_ROTATE_LEFT(head, parent, tmp, field);\
193 elm = RB_ROOT(head); \
194 break; \
195 } \
196 } else { \
197 tmp = RB_LEFT(parent, field); \
198 if (RB_COLOR(tmp, field) == RB_RED) { \
199 RB_SET_BLACKRED(tmp, parent, field); \
200 RB_ROTATE_RIGHT(head, parent, tmp, field);\
201 tmp = RB_LEFT(parent, field); \
202 } \
203 if ((RB_LEFT(tmp, field) == NULL || \
204 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
205 (RB_RIGHT(tmp, field) == NULL || \
206 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
207 RB_COLOR(tmp, field) = RB_RED; \
208 elm = parent; \
209 parent = RB_PARENT(elm, field); \
210 } else { \
211 if (RB_LEFT(tmp, field) == NULL || \
212 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {\
213 struct type *oright; \
214 if ((oright = RB_RIGHT(tmp, field)) \
215 != NULL) \
216 RB_COLOR(oright, field) = RB_BLACK;\
217 RB_COLOR(tmp, field) = RB_RED; \
218 RB_ROTATE_LEFT(head, tmp, oright, field);\
219 tmp = RB_LEFT(parent, field); \
220 } \
221 RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
222 RB_COLOR(parent, field) = RB_BLACK; \
223 if (RB_LEFT(tmp, field)) \
224 RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\
225 RB_ROTATE_RIGHT(head, parent, tmp, field);\
226 elm = RB_ROOT(head); \
227 break; \
228 } \
229 } \
230 } \
231 if (elm) \
232 RB_COLOR(elm, field) = RB_BLACK; \
233 } \
234 \
235 attr struct type * \
236 name##_RB_REMOVE(struct name *head, struct type *elm) \
237 { \
238 struct type *child, *parent, *old = elm; \
239 int color; \
240 if (RB_LEFT(elm, field) == NULL) \
241 child = RB_RIGHT(elm, field); \
242 else if (RB_RIGHT(elm, field) == NULL) \
243 child = RB_LEFT(elm, field); \
244 else { \
245 struct type *left; \
246 elm = RB_RIGHT(elm, field); \
247 while ((left = RB_LEFT(elm, field)) != NULL) \
248 elm = left; \
249 child = RB_RIGHT(elm, field); \
250 parent = RB_PARENT(elm, field); \
251 color = RB_COLOR(elm, field); \
252 if (child) \
253 RB_PARENT(child, field) = parent; \
254 if (parent) { \
255 if (RB_LEFT(parent, field) == elm) \
256 RB_LEFT(parent, field) = child; \
257 else \
258 RB_RIGHT(parent, field) = child; \
259 RB_AUGMENT(parent); \
260 } else \
261 RB_ROOT(head) = child; \
262 if (RB_PARENT(elm, field) == old) \
263 parent = elm; \
264 (elm)->field = (old)->field; \
265 if (RB_PARENT(old, field)) { \
266 if (RB_LEFT(RB_PARENT(old, field), field) == old)\
267 RB_LEFT(RB_PARENT(old, field), field) = elm;\
268 else \
269 RB_RIGHT(RB_PARENT(old, field), field) = elm;\
270 RB_AUGMENT(RB_PARENT(old, field)); \
271 } else \
272 RB_ROOT(head) = elm; \
273 RB_PARENT(RB_LEFT(old, field), field) = elm; \
274 if (RB_RIGHT(old, field)) \
275 RB_PARENT(RB_RIGHT(old, field), field) = elm; \
276 if (parent) { \
277 left = parent; \
278 do { \
279 RB_AUGMENT(left); \
280 } while ((left = RB_PARENT(left, field)) != NULL); \
281 } \
282 goto color; \
283 } \
284 parent = RB_PARENT(elm, field); \
285 color = RB_COLOR(elm, field); \
286 if (child) \
287 RB_PARENT(child, field) = parent; \
288 if (parent) { \
289 if (RB_LEFT(parent, field) == elm) \
290 RB_LEFT(parent, field) = child; \
291 else \
292 RB_RIGHT(parent, field) = child; \
293 RB_AUGMENT(parent); \
294 } else \
295 RB_ROOT(head) = child; \
296 color: \
297 if (color == RB_BLACK) \
298 name##_RB_REMOVE_COLOR(head, parent, child); \
299 return (old); \
300 } \
301 \
302 /* Inserts a node into the RB tree */ \
303 attr struct type * \
304 name##_RB_INSERT(struct name *head, struct type *elm) \
305 { \
306 struct type *tmp; \
307 struct type *parent = NULL; \
308 int comp = 0; \
309 tmp = RB_ROOT(head); \
310 while (tmp) { \
311 parent = tmp; \
312 comp = (cmp)(elm, parent); \
313 if (comp < 0) \
314 tmp = RB_LEFT(tmp, field); \
315 else if (comp > 0) \
316 tmp = RB_RIGHT(tmp, field); \
317 else \
318 return (tmp); \
319 } \
320 RB_SET(elm, parent, field); \
321 if (parent != NULL) { \
322 if (comp < 0) \
323 RB_LEFT(parent, field) = elm; \
324 else \
325 RB_RIGHT(parent, field) = elm; \
326 RB_AUGMENT(parent); \
327 } else \
328 RB_ROOT(head) = elm; \
329 name##_RB_INSERT_COLOR(head, elm); \
330 return (NULL); \
331 } \
332 \
333 /* Finds the node with the same key as elm */ \
334 attr struct type * \
335 name##_RB_FIND(struct name *head, struct type *elm) \
336 { \
337 struct type *tmp = RB_ROOT(head); \
338 int comp; \
339 while (tmp) { \
340 comp = cmp(elm, tmp); \
341 if (comp < 0) \
342 tmp = RB_LEFT(tmp, field); \
343 else if (comp > 0) \
344 tmp = RB_RIGHT(tmp, field); \
345 else \
346 return (tmp); \
347 } \
348 return (NULL); \
349 } \
350 \
351 /* ARGSUSED */ \
352 attr struct type * \
353 name##_RB_NEXT(struct type *elm) \
354 { \
355 if (RB_RIGHT(elm, field)) { \
356 elm = RB_RIGHT(elm, field); \
357 while (RB_LEFT(elm, field)) \
358 elm = RB_LEFT(elm, field); \
359 } else { \
360 if (RB_PARENT(elm, field) && \
361 (elm == RB_LEFT(RB_PARENT(elm, field), field))) \
362 elm = RB_PARENT(elm, field); \
363 else { \
364 while (RB_PARENT(elm, field) && \
365 (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\
366 elm = RB_PARENT(elm, field); \
367 elm = RB_PARENT(elm, field); \
368 } \
369 } \
370 return (elm); \
371 } \
372 \
373 attr struct type * \
374 name##_RB_MINMAX(struct name *head, int val) \
375 { \
376 struct type *tmp = RB_ROOT(head); \
377 struct type *parent = NULL; \
378 while (tmp) { \
379 parent = tmp; \
380 if (val < 0) \
381 tmp = RB_LEFT(tmp, field); \
382 else \
383 tmp = RB_RIGHT(tmp, field); \
384 } \
385 return (parent); \
386 }
387
388 #define RB_NEGINF -1
389
390 #define RB_INSERT(name, x, y) name##_RB_INSERT(x, y)
391 #define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y)
392 #define RB_FIND(name, x, y) name##_RB_FIND(x, y)
393 #define RB_NEXT(name, x, y) name##_RB_NEXT(y)
394 #define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF)
Debian package for darkstat