Open SCAP Library
Loading...
Searching...
No Matches
redblack.h
1/*
2 * Copyright 2009 Red Hat Inc., Durham, North Carolina.
3 * All Rights Reserved.
4 *
5 * This library is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU Lesser General Public
7 * License as published by the Free Software Foundation; either
8 * version 2.1 of the License, or (at your option) any later version.
9 *
10 * This library is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 * Lesser General Public License for more details.
14 *
15 * You should have received a copy of the GNU Lesser General Public
16 * License along with this library; if not, write to the Free Software
17 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
18 *
19 * Authors:
20 * "Daniel Kopecek" <dkopecek@redhat.com>
21 */
22
23#pragma once
24#ifndef REDBLACK_H
25#define REDBLACK_H
26
27#include <stdint.h>
28#include <stdlib.h>
29#include <assert.h>
30#include "../../../../common/util.h"
31
32
33#ifndef NDEBUG
34# define _E(exp) exp
35#else
36# define _E(exp) while(0)
37#endif
38
39#define XMALLOC malloc
40#define XREALLOC realloc
41#define XCALLOC calloc
42#define XFREE free
43
44#define SIDE_LEFT ((side_t)0)
45#define SIDE_RGHT ((side_t)1)
46
47#define COLOR_BLK 0
48#define COLOR_RED 1
49
50#define PREORDER 0
51#define INORDER 1
52#define POSTORDER 2
53#define LRTDLAYER 3
54#define RLTDLAYER 4
55
56#if !defined (E_OK)
57# define E_OK 0
58#endif
59#if !defined (E_FAIL)
60# define E_FAIL 1
61#endif
62#if !defined (E_COLL)
63# define E_COLL 2
64#endif
65
66#define __NAME_PREFIX__ ___rb_
67#define __TREETYPE_PREFIX rbtree_
68#define __NODETYPE_PREFIX rbnode_
69
70typedef uint8_t side_t;
71typedef uint8_t color_t;
72
73#define __MYCONCAT2(a, b) a ## b
74#define __MYCONCAT3(a, b, c) a ## b ## c
75#define CONCAT2(a, b) __MYCONCAT2(a, b)
76#define CONCAT3(a, b, c) __MYCONCAT3(a, b, c)
77#define EXPAND(a) a
78
79#define TREETYPE(__t_name) struct CONCAT2(__TREETYPE_PREFIX, __t_name)
80#define NODETYPE(__t_name) struct CONCAT2(__NODETYPE_PREFIX, __t_name)
81
82/* Definition templates */
83#define DEF_RBN_INITST(__t_name) int CONCAT3(__NAME_PREFIX__, __t_name, _initst) (TREETYPE(__t_name) *tree)
84
85#define RBN_CREATE_NAME(__t_name) CONCAT3(__NAME_PREFIX__, __t_name, _create)
86#define DEF_RBN_CREATE(__t_name) TREETYPE(__t_name) * RBN_CREATE_NAME(__t_name) (void)
87#define RB_CREATE RBN_CREATE_NAME
88
89#define RBN_NEWNODE_NAME(__t_name) CONCAT3(__NAME_PREFIX__, __t_name, _newnode)
90#define DEF_RBN_NEWNODE(__t_name) NODETYPE(__t_name) * RBN_NEWNODE_NAME(__t_name) (void)
91#define RB_NEWNODE RBN_NEWNODE_NAME
92
93#define RBN_INSERT_NAME(__t_name) CONCAT3(__NAME_PREFIX__, __t_name, _insert)
94#define DEF_RBN_INSERT(__t_name) int RBN_INSERT_NAME(__t_name) (TREETYPE(__t_name) *tree, NODETYPE(__t_name) *new_node)
95#define RB_INSERT RBN_INSERT_NAME
96
97#define RBN_SEARCH_NAME(__t_name) CONCAT3(__NAME_PREFIX__, __t_name, _search)
98#define DEF_RBN_SEARCH(__t_name) NODETYPE(__t_name) * RBN_SEARCH_NAME(__t_name) (TREETYPE(__t_name) *tree, const NODETYPE(__t_name) *k_node)
99#define RB_SEARCH RBN_SEARCH_NAME
100
101#define DEF_RBN_DELETE(__t_name) int CONCAT3(__NAME_PREFIX__, __t_name, _delete) (TREETYPE(__t_name) *tree, const NODETYPE(__t_name) *k_node)
102
103#define DEF_RBN_REMOVE(__t_name) DEF_RBN_DELETE(__t_name)
104
105#define DEF_RBN_NODE_LEFT(__t_name) NODETYPE(__t_name) * CONCAT3(__NAME_PREFIX__, __t_name, _getLeftNode) (NODETYPE(__t_name) *node)
106#define DEF_RBN_NODE_RGHT(__t_name) NODETYPE(__t_name) * CONCAT3(__NAME_PREFIX__, __t_name, _getRghtNode) (NODETYPE(__t_name) *node)
107#define DEF_RBN_NODE_RIGHT(__t_name) RBN_NODE_RGHT(__t_name)
108
109#define DEF_RBN_NODE_COLOR(__t_name) color_t CONCAT3(__NAME_PREFIX__, __t_name, _getColor) (NODETYPE(__t_name) *node)
110#define DEF_RBN_NODE_SIDE(__t_name) side_t CONCAT3(__NAME_PREFIX__, __t_name, _getSide) (NODETYPE(__t_name) *node)
111
112#define DEF_RBN_ROT_R(__t_name) NODETYPE(__t_name) * CONCAT3(__NAME_PREFIX__, __t_name, _rotR) (NODETYPE(__t_name) *r)
113#define DEF_RBN_ROT_L(__t_name) NODETYPE(__t_name) * CONCAT3(__NAME_PREFIX__, __t_name, _rotL) (NODETYPE(__t_name) *r)
114#define DEF_RBN_ROT_RL(__t_name) NODETYPE(__t_name) * CONCAT3(__NAME_PREFIX__, __t_name, _rotRL) (NODETYPE(__t_name) *r)
115#define DEF_RBN_ROT_LR(__t_name) NODETYPE(__t_name) * CONCAT3(__NAME_PREFIX__, __t_name, _rotLR) (NODETYPE(__t_name) *r)
116
117#define ROTATE_ARR_NAME(__t_name) CONCAT3(__NAME_PREFIX__, __t_name, _rotate)
118
119#define RBN_NODECMP_NAME(__t_name) CONCAT3(__NAME_PREFIX__, __t_name, _nodecmp)
120#define DEF_RBN_NODECMP(__t_name) int RBN_NODECMP_NAME(__t_name) (const NODETYPE(__t_name) *a, const NODETYPE(__t_name) *b)
121#define RBNODECMP DEF_RBN_NODECMP
122
123#define RBN_NODEJOIN_NAME(__t_name) CONCAT3(__NAME_PREFIX__, __t_name, _nodejoin)
124#define DEF_RBN_NODEJOIN(__t_name) NODETYPE(__t_name) * RBN_NODEJOIN_NAME(__t_name) (NODETYPE(__t_name) *a, NODETYPE(__t_name) *b)
125#define RBNODEJOIN DEF_RBN_NODEJOIN
126
127#define RBN_WALK_NAME(__t_name) CONCAT3(__NAME_PREFIX__, __t_name, _walk)
128#define DEF_RBN_WALK(__t_name) void RBN_WALK_NAME(__t_name) (TREETYPE(__t_name) *tree, uint8_t order, void (*callback)(NODETYPE(__t_name) *, void *), void *cbarg)
129#define RB_WALK RBN_WALK_NAME
130
131#define RBN_CALLBACK_NAME(__t_name, myname) CONCAT3(__t_name, _CB_, myname)
132#define DEF_RBN_CALLBACK(__t_name, myname) void RBN_CALLBACK_NAME(__t_name, myname) (NODETYPE(__t_name) *node, void *cbarg)
133#define RBCBNAME RBN_CALLBACK_NAME
134#define RBCALLBACK DEF_RBN_CALLBACK
135
136#define NOARG 0
137
138/* Main template */
139#define DEFRBTREE(__t_name, __u_nitem) \
140 NODETYPE(__t_name) { \
141 /* META data */ \
142 NODETYPE(__t_name) *___child[2]; \
143 color_t ___c: 1; /* Node color */ \
144 side_t ___s: 1; /* Node side relative to parent */ \
145 /* USER data */ \
146 __u_nitem; \
147 }; \
148 \
149 TREETYPE(__t_name) { \
150 NODETYPE(__t_name) *root; \
151 size_t size; \
152 }; \
153 \
154 DEF_RBN_NODEJOIN(__t_name); \
155 DEF_RBN_NODECMP(__t_name); \
156 DEF_RBN_CREATE(__t_name); \
157 DEF_RBN_NEWNODE(__t_name); \
158 DEF_RBN_WALK(__t_name); \
159 DEF_RBN_INSERT(__t_name); \
160 DEF_RBN_SEARCH(__t_name)
161/*
162 DEF_RBN_INITST(__t_name); \
163 DEF_RBN_SEARCH(__t_name, __keytype); \
164 DEF_RBN_DELETE(__t_name, __keytype); \
165 DEF_RBN_NODE_LEFT(__t_name); \
166 DEF_RBN_NODE_RGHT(__t_name); \
167 DEF_RBN_NODE_COLOR(__t_name); \
168 DEF_RBN_NODE_SIDE(__t_name)
169*/
170
171#define __isRED(n) ((n)->___c == COLOR_RED)
172#define isRED(n) (((n) == NULL) ? 0 : __isRED(n))
173#define PTRMOVE(next) { \
174 ggp = grp; \
175 grp = par; \
176 par = cur; \
177 cur = next; }
178
179#define lch (cur->___child[SIDE_LEFT])
180#define rch (cur->___child[SIDE_RGHT])
181
182/* Code templates */
183//#define RBN_INITST()
184
185#define RBN_NEWNODE_CODE(__t_name) \
186 DEF_RBN_NEWNODE(__t_name) { \
187 NODETYPE(__t_name) *new; \
188 new = XMALLOC(sizeof(NODETYPE(__t_name))); \
189 new->___s = 0; \
190 new->___c = 0; \
191 new->___child[0] = NULL; \
192 new->___child[1] = NULL; \
193 return (new); \
194 }
195
196#define RBN_ROTATE_CODE(__t_name) \
197 static DEF_RBN_ROT_L(__t_name) { \
198 register NODETYPE(__t_name) *nr; \
199 \
200 nr = r->___child[SIDE_RGHT]; \
201 r->___child[SIDE_RGHT] = nr->___child[SIDE_LEFT]; \
202 nr->___child[SIDE_LEFT] = r; \
203 \
204 nr->___s = r->___s; \
205 r->___s = SIDE_LEFT; \
206 \
207 if (r->___child[SIDE_RGHT] != NULL) \
208 r->___child[SIDE_RGHT]->___s = SIDE_RGHT; \
209 \
210 if (nr->___child[SIDE_RGHT] != NULL) \
211 nr->___child[SIDE_RGHT]->___c = COLOR_BLK; \
212 \
213 return (nr); \
214 } \
215 \
216 static DEF_RBN_ROT_R(__t_name) { \
217 register NODETYPE(__t_name) *nr; \
218 \
219 nr = r->___child[SIDE_LEFT]; \
220 r->___child[SIDE_LEFT] = nr->___child[SIDE_RGHT]; \
221 nr->___child[SIDE_RGHT] = r; \
222 \
223 nr->___s = r->___s; \
224 r->___s = SIDE_RGHT; \
225 \
226 if (r->___child[SIDE_LEFT] != NULL) \
227 r->___child[SIDE_LEFT]->___s = SIDE_LEFT; \
228 \
229 if (nr->___child[SIDE_LEFT] != NULL) \
230 nr->___child[SIDE_LEFT]->___c = COLOR_BLK; \
231 \
232 return (nr); \
233 } \
234 \
235 static DEF_RBN_ROT_LR(__t_name) { \
236 register NODETYPE(__t_name) *nr; \
237 \
238 nr = r->___child[SIDE_RGHT]->___child[SIDE_LEFT]; \
239 nr->___s = r->___s; \
240 r->___s = SIDE_LEFT; \
241 r->___child[SIDE_RGHT]->___child[SIDE_LEFT] = nr->___child[SIDE_RGHT]; \
242 \
243 if (nr->___child[SIDE_RGHT] != NULL) \
244 nr->___child[SIDE_RGHT]->___s = SIDE_LEFT; \
245 \
246 nr->___child[SIDE_RGHT] = r->___child[SIDE_RGHT]; \
247 r->___child[SIDE_RGHT] = nr->___child[SIDE_LEFT]; \
248 \
249 if (nr->___child[SIDE_LEFT] != NULL) \
250 nr->___child[SIDE_LEFT]->___s = SIDE_RGHT; \
251 \
252 nr->___child[SIDE_LEFT] = r; \
253 nr->___child[SIDE_RGHT]->___c = COLOR_BLK; \
254 \
255 return (nr); \
256 } \
257 \
258 static DEF_RBN_ROT_RL(__t_name) { \
259 register NODETYPE(__t_name) *nr; \
260 \
261 nr = r->___child[SIDE_LEFT]->___child[SIDE_RGHT]; \
262 nr->___s = r->___s; \
263 r->___s = SIDE_RGHT; \
264 r->___child[SIDE_LEFT]->___child[SIDE_RGHT] = nr->___child[SIDE_LEFT]; \
265 \
266 if (nr->___child[SIDE_LEFT] != NULL) \
267 nr->___child[SIDE_LEFT]->___s = SIDE_RGHT; \
268 \
269 nr->___child[SIDE_LEFT] = r->___child[SIDE_LEFT]; \
270 r->___child[SIDE_LEFT] = nr->___child[SIDE_RGHT]; \
271 \
272 if (nr->___child[SIDE_RGHT] != NULL) \
273 nr->___child[SIDE_RGHT]->___s = SIDE_LEFT; \
274 \
275 nr->___child[SIDE_RGHT] = r; \
276 nr->___child[SIDE_LEFT]->___c = COLOR_BLK; \
277 \
278 return (nr); \
279 } \
280 \
281 static NODETYPE(__t_name) * (*ROTATE_ARR_NAME(__t_name)[4])(NODETYPE(__t_name) *) = { \
282 &CONCAT3(__NAME_PREFIX__, __t_name, _rotR), \
283 &CONCAT3(__NAME_PREFIX__, __t_name, _rotLR), \
284 &CONCAT3(__NAME_PREFIX__, __t_name, _rotRL), \
285 &CONCAT3(__NAME_PREFIX__, __t_name, _rotL) \
286 }
287
288#define RBN_CREATE_CODE(__t_name) \
289 DEF_RBN_CREATE(__t_name) { \
290 TREETYPE(__t_name) *new = XMALLOC (sizeof (TREETYPE(__t_name))); \
291 new->root = NULL; \
292 new->size = 0; \
293 return (new); \
294 }
295
296#define RBN_INSERT_CODE(__t_name) \
297 DEF_RBN_INSERT(__t_name) { \
298 NODETYPE(__t_name) *cur, *par, *grp, *ggp; \
299 side_t lastdir; \
300 int cmp; \
301 NODETYPE(__t_name) fake; \
302 \
303 fake.___c = COLOR_BLK; \
304 fake.___child[SIDE_RGHT] = tree->root; \
305 fake.___child[SIDE_LEFT] = NULL; \
306 ggp = grp = NULL; \
307 par = &fake; \
308 cur = tree->root; \
309 lastdir = SIDE_RGHT; \
310 \
311 for (;;) { \
312 /* Search loop BEGIN */ \
313 if (cur == NULL) { \
314 par->___child[lastdir] = cur = new_node; \
315 cur->___s = lastdir; \
316 cur->___c = COLOR_RED; \
317 cur->___child[SIDE_LEFT] = cur->___child[SIDE_RGHT]; \
318 \
319 if (__isRED(par)) /* red violation */ \
320 ggp->___child[grp->___s] = ROTATE_ARR_NAME(__t_name)[(lastdir << 1)|(par->___s)](grp); \
321 \
322 tree->root = fake.___child[SIDE_RGHT]; \
323 tree->root->___c = COLOR_BLK; \
324 ++(tree->size); \
325 \
326 return (E_OK); \
327 } else if (isRED(lch) && isRED(rch)) { \
328 /* color switch */ \
329 cur->___c = COLOR_RED; \
330 lch->___c = rch->___c = COLOR_BLK; \
331 \
332 if (__isRED(par)) /* red violation */ \
333 ggp->___child[grp->___s] = ROTATE_ARR_NAME(__t_name)[(cur->___s << 1)|(par->___s)](grp); \
334 } else if (__isRED(par) && __isRED(cur)) { \
335 /* red violation */ \
336 ggp->___child[grp->___s] = ROTATE_ARR_NAME(__t_name)[(cur->___s << 1)|(par->___s)](grp); \
337 } \
338 \
339 cmp = RBN_NODECMP_NAME(__t_name) (cur, new_node); \
340 \
341 if (cmp == 0) { \
342 lastdir = cur->___s; \
343 _E(color_t tmp_c = cur->___c;) \
344 _E(NODETYPE(__t_name) *tmp_l = cur->___child[SIDE_LEFT];) \
345 _E(NODETYPE(__t_name) *tmp_r = cur->___child[SIDE_RGHT];) \
346 tree->root = fake.___child[SIDE_RGHT]; \
347 tree->root->___c = COLOR_BLK; \
348 RBN_NODEJOIN_NAME(__t_name) (cur, new_node); \
349 \
350 assert(cur->___s == lastdir); \
351 assert(cur->___c == tmp_c); \
352 assert(cur->___child[SIDE_LEFT] == tmp_l); \
353 assert(cur->___child[SIDE_RGHT] == tmp_r); \
354 \
355 return (E_COLL); \
356 } else if (cmp < 0) { \
357 /* go right */ \
358 PTRMOVE(rch); \
359 lastdir = SIDE_RGHT; \
360 } else { \
361 /* go left */ \
362 PTRMOVE(lch); \
363 lastdir = SIDE_LEFT; \
364 } \
365 } /* Search loop END */ \
366 \
367 abort (); \
368 return (E_FAIL); \
369 }
370
371#define RBN_SEARCH_CODE(__t_name) \
372 DEF_RBN_SEARCH(__t_name) { \
373 NODETYPE(__t_name) *node; \
374 int cmp; \
375 \
376 node = tree->root; \
377 \
378 while (node != NULL) { \
379 cmp = RBN_NODECMP_NAME(__t_name) (node, k_node); \
380 \
381 if (cmp == 0) \
382 break; \
383 else if (cmp < 0) \
384 node = node->___child[SIDE_RGHT]; \
385 else \
386 node = node->___child[SIDE_LEFT]; \
387 } \
388 \
389 return (node); \
390 }
391
392#define __WALK_STACK_SIZE 32
393#define __WALK_STACK_GROW 16
394
395#define PUSH(n) node_stack[node_stack_count] = (n), ++node_stack_count
396#define POP(n) (n) = node_stack[--node_stack_count]
397#define TOP (node_stack[node_stack_count-1])
398#define CNT node_stack_count
399
400#define RBN_WALK_CODE(__t_name) \
401 DEF_RBN_WALK(__t_name) { \
402 NODETYPE(__t_name) **node_stack; \
403 register uint16_t node_stack_size; \
404 register uint16_t node_stack_count; \
405 \
406 node_stack_count = 0; \
407 node_stack_size = __WALK_STACK_SIZE; \
408 node_stack = XCALLOC(sizeof (NODETYPE(__t_name) *), node_stack_size); \
409 \
410 PUSH(tree->root); \
411 \
412 switch (order) { \
413 case PREORDER: \
414 while (CNT > 0) { \
415 callback (TOP, cbarg); \
416 if (TOP->___child[SIDE_LEFT] != NULL) { \
417 PUSH(TOP->___child[SIDE_LEFT]); \
418 } else { \
419 __pre: \
420 if (TOP->___child[SIDE_RGHT] != NULL) { \
421 TOP = TOP->___child[SIDE_RGHT]; \
422 } else { \
423 if (--CNT > 0) \
424 goto __pre; \
425 else \
426 break; \
427 } \
428 } \
429 } \
430 break; \
431 case INORDER: \
432 while (CNT > 0) { \
433 if (TOP->___child[SIDE_LEFT] != NULL) { \
434 PUSH(TOP->___child[SIDE_LEFT]); \
435 } else { \
436 __in: \
437 callback (TOP, cbarg); \
438 if (TOP->___child[SIDE_RGHT] != NULL) { \
439 TOP = TOP->___child[SIDE_RGHT]; \
440 } else { \
441 if (--CNT > 0) \
442 goto __in; \
443 else \
444 break; \
445 } \
446 } \
447 } \
448 break; \
449 case POSTORDER: \
450 break; \
451 default: \
452 abort (); \
453 } \
454 XFREE(node_stack); \
455 return; \
456 }
457
458/*
459 #undef PUSH
460 #undef POP
461 #undef TOP
462 #undef COUNT
463*/
464
465/*
466 #define RBN_DELETE()
467 #define RBN_REMOVE() RBN_DELETE()
468*/
469
470/*
471 #define RBN_NODE_LEFT()
472 #define RBN_NODE_RGHT()
473 #define RBN_NODE_RIGHT() RBN_NODE_RGHT()
474 #define RBN_NODE_COLOR()
475 #define RBN_NODE_SIDE()
476*/
477
478#define RBTREECODE(__t_name) \
479 RBN_CREATE_CODE(__t_name) \
480 RBN_ROTATE_CODE(__t_name); \
481 RBN_NEWNODE_CODE(__t_name) \
482 RBN_SEARCH_CODE(__t_name) \
483 RBN_INSERT_CODE(__t_name) \
484 RBN_WALK_CODE(__t_name) \
485 static const char CONCAT2(__t_name, dummy) = 0
486
487
488#endif /* REDBLACK_H */
Generated by doxygen 1.9.5