Open SCAP Library
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 
70 typedef uint8_t side_t;
71 typedef 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 */