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., 59 Temple Place, Suite 330, Boston, MA 02111-1307 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 #define __NODETYPE_ATTRS__ __attribute__ ((packed))
70 #define __TREETYPE_ATTRS__ __attribute__ ((packed))
71 
72 typedef uint8_t side_t;
73 typedef uint8_t color_t;
74 
75 #define __MYCONCAT2(a, b) a ## b
76 #define __MYCONCAT3(a, b, c) a ## b ## c
77 #define CONCAT2(a, b) __MYCONCAT2(a, b)
78 #define CONCAT3(a, b, c) __MYCONCAT3(a, b, c)
79 #define EXPAND(a) a
80 
81 #define TREETYPE(__t_name) struct CONCAT2(__TREETYPE_PREFIX, __t_name)
82 #define NODETYPE(__t_name) struct CONCAT2(__NODETYPE_PREFIX, __t_name)
83 
84 /* Definition templates */
85 #define DEF_RBN_INITST(__t_name) int CONCAT3(__NAME_PREFIX__, __t_name, _initst) (TREETYPE(__t_name) *tree)
86 
87 #define RBN_CREATE_NAME(__t_name) CONCAT3(__NAME_PREFIX__, __t_name, _create)
88 #define DEF_RBN_CREATE(__t_name) TREETYPE(__t_name) * RBN_CREATE_NAME(__t_name) (void)
89 #define RB_CREATE RBN_CREATE_NAME
90 
91 #define RBN_NEWNODE_NAME(__t_name) CONCAT3(__NAME_PREFIX__, __t_name, _newnode)
92 #define DEF_RBN_NEWNODE(__t_name) NODETYPE(__t_name) * RBN_NEWNODE_NAME(__t_name) (void)
93 #define RB_NEWNODE RBN_NEWNODE_NAME
94 
95 #define RBN_INSERT_NAME(__t_name) CONCAT3(__NAME_PREFIX__, __t_name, _insert)
96 #define DEF_RBN_INSERT(__t_name) int RBN_INSERT_NAME(__t_name) (TREETYPE(__t_name) *tree, NODETYPE(__t_name) *new_node)
97 #define RB_INSERT RBN_INSERT_NAME
98 
99 #define RBN_SEARCH_NAME(__t_name) CONCAT3(__NAME_PREFIX__, __t_name, _search)
100 #define DEF_RBN_SEARCH(__t_name) NODETYPE(__t_name) * RBN_SEARCH_NAME(__t_name) (TREETYPE(__t_name) *tree, const NODETYPE(__t_name) *k_node)
101 #define RB_SEARCH RBN_SEARCH_NAME
102 
103 #define DEF_RBN_DELETE(__t_name) int CONCAT3(__NAME_PREFIX__, __t_name, _delete) (TREETYPE(__t_name) *tree, const NODETYPE(__t_name) *k_node)
104 
105 #define DEF_RBN_REMOVE(__t_name) DEF_RBN_DELETE(__t_name)
106 
107 #define DEF_RBN_NODE_LEFT(__t_name) NODETYPE(__t_name) * CONCAT3(__NAME_PREFIX__, __t_name, _getLeftNode) (NODETYPE(__t_name) *node)
108 #define DEF_RBN_NODE_RGHT(__t_name) NODETYPE(__t_name) * CONCAT3(__NAME_PREFIX__, __t_name, _getRghtNode) (NODETYPE(__t_name) *node)
109 #define DEF_RBN_NODE_RIGHT(__t_name) RBN_NODE_RGHT(__t_name)
110 
111 #define DEF_RBN_NODE_COLOR(__t_name) color_t CONCAT3(__NAME_PREFIX__, __t_name, _getColor) (NODETYPE(__t_name) *node)
112 #define DEF_RBN_NODE_SIDE(__t_name) side_t CONCAT3(__NAME_PREFIX__, __t_name, _getSide) (NODETYPE(__t_name) *node)
113 
114 #define DEF_RBN_ROT_R(__t_name) NODETYPE(__t_name) * CONCAT3(__NAME_PREFIX__, __t_name, _rotR) (NODETYPE(__t_name) *r)
115 #define DEF_RBN_ROT_L(__t_name) NODETYPE(__t_name) * CONCAT3(__NAME_PREFIX__, __t_name, _rotL) (NODETYPE(__t_name) *r)
116 #define DEF_RBN_ROT_RL(__t_name) NODETYPE(__t_name) * CONCAT3(__NAME_PREFIX__, __t_name, _rotRL) (NODETYPE(__t_name) *r)
117 #define DEF_RBN_ROT_LR(__t_name) NODETYPE(__t_name) * CONCAT3(__NAME_PREFIX__, __t_name, _rotLR) (NODETYPE(__t_name) *r)
118 
119 #define ROTATE_ARR_NAME(__t_name) CONCAT3(__NAME_PREFIX__, __t_name, _rotate)
120 
121 #define RBN_NODECMP_NAME(__t_name) CONCAT3(__NAME_PREFIX__, __t_name, _nodecmp)
122 #define DEF_RBN_NODECMP(__t_name) int RBN_NODECMP_NAME(__t_name) (const NODETYPE(__t_name) *a, const NODETYPE(__t_name) *b)
123 #define RBNODECMP DEF_RBN_NODECMP
124 
125 #define RBN_NODEJOIN_NAME(__t_name) CONCAT3(__NAME_PREFIX__, __t_name, _nodejoin)
126 #define DEF_RBN_NODEJOIN(__t_name) NODETYPE(__t_name) * RBN_NODEJOIN_NAME(__t_name) (NODETYPE(__t_name) *a, NODETYPE(__t_name) *b)
127 #define RBNODEJOIN DEF_RBN_NODEJOIN
128 
129 #define RBN_WALK_NAME(__t_name) CONCAT3(__NAME_PREFIX__, __t_name, _walk)
130 #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)
131 #define RB_WALK RBN_WALK_NAME
132 
133 #define RBN_CALLBACK_NAME(__t_name, myname) CONCAT3(__t_name, _CB_, myname)
134 #define DEF_RBN_CALLBACK(__t_name, myname) void RBN_CALLBACK_NAME(__t_name, myname) (NODETYPE(__t_name) *node, void *cbarg)
135 #define RBCBNAME RBN_CALLBACK_NAME
136 #define RBCALLBACK DEF_RBN_CALLBACK
137 
138 #define NOARG 0
139 
140 /* Main template */
141 #define DEFRBTREE(__t_name, __u_nitem) \
142  NODETYPE(__t_name) { \
143  /* META data */ \
144  NODETYPE(__t_name) *___child[2]; \
145  color_t ___c: 1; /* Node color */ \
146  side_t ___s: 1; /* Node side relative to parent */ \
147  /* USER data */ \
148  __u_nitem; \
149  } __NODETYPE_ATTRS__; \
150  \
151  TREETYPE(__t_name) { \
152  NODETYPE(__t_name) *root; \
153  size_t size; \
154  } __TREETYPE_ATTRS__; \
155  \
156  DEF_RBN_NODEJOIN(__t_name); \
157  DEF_RBN_NODECMP(__t_name); \
158  DEF_RBN_CREATE(__t_name); \
159  DEF_RBN_NEWNODE(__t_name); \
160  DEF_RBN_WALK(__t_name); \
161  DEF_RBN_INSERT(__t_name); \
162  DEF_RBN_SEARCH(__t_name)
163 /*
164  DEF_RBN_INITST(__t_name); \
165  DEF_RBN_SEARCH(__t_name, __keytype); \
166  DEF_RBN_DELETE(__t_name, __keytype); \
167  DEF_RBN_NODE_LEFT(__t_name); \
168  DEF_RBN_NODE_RGHT(__t_name); \
169  DEF_RBN_NODE_COLOR(__t_name); \
170  DEF_RBN_NODE_SIDE(__t_name)
171 */
172 
173 #define __isRED(n) ((n)->___c == COLOR_RED)
174 #define isRED(n) (((n) == NULL) ? 0 : __isRED(n))
175 #define PTRMOVE(next) { \
176  ggp = grp; \
177  grp = par; \
178  par = cur; \
179  cur = next; }
180 
181 #define lch (cur->___child[SIDE_LEFT])
182 #define rch (cur->___child[SIDE_RGHT])
183 
184 /* Code templates */
185 //#define RBN_INITST()
186 
187 #define RBN_NEWNODE_CODE(__t_name) \
188  DEF_RBN_NEWNODE(__t_name) { \
189  NODETYPE(__t_name) *new; \
190  new = XMALLOC(sizeof(NODETYPE(__t_name))); \
191  new->___s = 0; \
192  new->___c = 0; \
193  new->___child[0] = NULL; \
194  new->___child[1] = NULL; \
195  return (new); \
196  }
197 
198 #define RBN_ROTATE_CODE(__t_name) \
199  static DEF_RBN_ROT_L(__t_name) { \
200  register NODETYPE(__t_name) *nr; \
201  \
202  nr = r->___child[SIDE_RGHT]; \
203  r->___child[SIDE_RGHT] = nr->___child[SIDE_LEFT]; \
204  nr->___child[SIDE_LEFT] = r; \
205  \
206  nr->___s = r->___s; \
207  r->___s = SIDE_LEFT; \
208  \
209  if (r->___child[SIDE_RGHT] != NULL) \
210  r->___child[SIDE_RGHT]->___s = SIDE_RGHT; \
211  \
212  if (nr->___child[SIDE_RGHT] != NULL) \
213  nr->___child[SIDE_RGHT]->___c = COLOR_BLK; \
214  \
215  return (nr); \
216  } \
217  \
218  static DEF_RBN_ROT_R(__t_name) { \
219  register NODETYPE(__t_name) *nr; \
220  \
221  nr = r->___child[SIDE_LEFT]; \
222  r->___child[SIDE_LEFT] = nr->___child[SIDE_RGHT]; \
223  nr->___child[SIDE_RGHT] = r; \
224  \
225  nr->___s = r->___s; \
226  r->___s = SIDE_RGHT; \
227  \
228  if (r->___child[SIDE_LEFT] != NULL) \
229  r->___child[SIDE_LEFT]->___s = SIDE_LEFT; \
230  \
231  if (nr->___child[SIDE_LEFT] != NULL) \
232  nr->___child[SIDE_LEFT]->___c = COLOR_BLK; \
233  \
234  return (nr); \
235  } \
236  \
237  static DEF_RBN_ROT_LR(__t_name) { \
238  register NODETYPE(__t_name) *nr; \
239  \
240  nr = r->___child[SIDE_RGHT]->___child[SIDE_LEFT]; \
241  nr->___s = r->___s; \
242  r->___s = SIDE_LEFT; \
243  r->___child[SIDE_RGHT]->___child[SIDE_LEFT] = nr->___child[SIDE_RGHT]; \
244  \
245  if (nr->___child[SIDE_RGHT] != NULL) \
246  nr->___child[SIDE_RGHT]->___s = SIDE_LEFT; \
247  \
248  nr->___child[SIDE_RGHT] = r->___child[SIDE_RGHT]; \
249  r->___child[SIDE_RGHT] = nr->___child[SIDE_LEFT]; \
250  \
251  if (nr->___child[SIDE_LEFT] != NULL) \
252  nr->___child[SIDE_LEFT]->___s = SIDE_RGHT; \
253  \
254  nr->___child[SIDE_LEFT] = r; \
255  nr->___child[SIDE_RGHT]->___c = COLOR_BLK; \
256  \
257  return (nr); \
258  } \
259  \
260  static DEF_RBN_ROT_RL(__t_name) { \
261  register NODETYPE(__t_name) *nr; \
262  \
263  nr = r->___child[SIDE_LEFT]->___child[SIDE_RGHT]; \
264  nr->___s = r->___s; \
265  r->___s = SIDE_RGHT; \
266  r->___child[SIDE_LEFT]->___child[SIDE_RGHT] = nr->___child[SIDE_LEFT]; \
267  \
268  if (nr->___child[SIDE_LEFT] != NULL) \
269  nr->___child[SIDE_LEFT]->___s = SIDE_RGHT; \
270  \
271  nr->___child[SIDE_LEFT] = r->___child[SIDE_LEFT]; \
272  r->___child[SIDE_LEFT] = nr->___child[SIDE_RGHT]; \
273  \
274  if (nr->___child[SIDE_RGHT] != NULL) \
275  nr->___child[SIDE_RGHT]->___s = SIDE_LEFT; \
276  \
277  nr->___child[SIDE_RGHT] = r; \
278  nr->___child[SIDE_LEFT]->___c = COLOR_BLK; \
279  \
280  return (nr); \
281  } \
282  \
283  static NODETYPE(__t_name) * (*ROTATE_ARR_NAME(__t_name)[4])(NODETYPE(__t_name) *) = { \
284  &CONCAT3(__NAME_PREFIX__, __t_name, _rotR), \
285  &CONCAT3(__NAME_PREFIX__, __t_name, _rotLR), \
286  &CONCAT3(__NAME_PREFIX__, __t_name, _rotRL), \
287  &CONCAT3(__NAME_PREFIX__, __t_name, _rotL) \
288  }
289 
290 #define RBN_CREATE_CODE(__t_name) \
291  DEF_RBN_CREATE(__t_name) { \
292  TREETYPE(__t_name) *new = XMALLOC (sizeof (TREETYPE(__t_name))); \
293  new->root = NULL; \
294  new->size = 0; \
295  return (new); \
296  }
297 
298 #define RBN_INSERT_CODE(__t_name) \
299  DEF_RBN_INSERT(__t_name) { \
300  NODETYPE(__t_name) *cur, *par, *grp, *ggp; \
301  side_t lastdir; \
302  int cmp; \
303  NODETYPE(__t_name) fake; \
304  \
305  fake.___c = COLOR_BLK; \
306  fake.___child[SIDE_RGHT] = tree->root; \
307  fake.___child[SIDE_LEFT] = NULL; \
308  ggp = grp = NULL; \
309  par = &fake; \
310  cur = tree->root; \
311  lastdir = SIDE_RGHT; \
312  \
313  for (;;) { \
314  /* Search loop BEGIN */ \
315  if (cur == NULL) { \
316  par->___child[lastdir] = cur = new_node; \
317  cur->___s = lastdir; \
318  cur->___c = COLOR_RED; \
319  cur->___child[SIDE_LEFT] = cur->___child[SIDE_RGHT]; \
320  \
321  if (__isRED(par)) /* red violation */ \
322  ggp->___child[grp->___s] = ROTATE_ARR_NAME(__t_name)[(lastdir << 1)|(par->___s)](grp); \
323  \
324  tree->root = fake.___child[SIDE_RGHT]; \
325  tree->root->___c = COLOR_BLK; \
326  ++(tree->size); \
327  \
328  return (E_OK); \
329  } else if (isRED(lch) && isRED(rch)) { \
330  /* color switch */ \
331  cur->___c = COLOR_RED; \
332  lch->___c = rch->___c = COLOR_BLK; \
333  \
334  if (__isRED(par)) /* red violation */ \
335  ggp->___child[grp->___s] = ROTATE_ARR_NAME(__t_name)[(cur->___s << 1)|(par->___s)](grp); \
336  } else if (__isRED(par) && __isRED(cur)) { \
337  /* red violation */ \
338  ggp->___child[grp->___s] = ROTATE_ARR_NAME(__t_name)[(cur->___s << 1)|(par->___s)](grp); \
339  } \
340  \
341  cmp = RBN_NODECMP_NAME(__t_name) (cur, new_node); \
342  \
343  if (cmp == 0) { \
344  lastdir = cur->___s; \
345  _E(color_t tmp_c = cur->___c;) \
346  _E(NODETYPE(__t_name) *tmp_l = cur->___child[SIDE_LEFT];) \
347  _E(NODETYPE(__t_name) *tmp_r = cur->___child[SIDE_RGHT];) \
348  tree->root = fake.___child[SIDE_RGHT]; \
349  tree->root->___c = COLOR_BLK; \
350  RBN_NODEJOIN_NAME(__t_name) (cur, new_node); \
351  \
352  assert(cur->___s == lastdir); \
353  assert(cur->___c == tmp_c); \
354  assert(cur->___child[SIDE_LEFT] == tmp_l); \
355  assert(cur->___child[SIDE_RGHT] == tmp_r); \
356  \
357  return (E_COLL); \
358  } else if (cmp < 0) { \
359  /* go right */ \
360  PTRMOVE(rch); \
361  lastdir = SIDE_RGHT; \
362  } else { \
363  /* go left */ \
364  PTRMOVE(lch); \
365  lastdir = SIDE_LEFT; \
366  } \
367  } /* Search loop END */ \
368  \
369  abort (); \
370  return (E_FAIL); \
371  }
372 
373 #define RBN_SEARCH_CODE(__t_name) \
374  DEF_RBN_SEARCH(__t_name) { \
375  NODETYPE(__t_name) *node; \
376  int cmp; \
377  \
378  node = tree->root; \
379  \
380  while (node != NULL) { \
381  cmp = RBN_NODECMP_NAME(__t_name) (node, k_node); \
382  \
383  if (cmp == 0) \
384  break; \
385  else if (cmp < 0) \
386  node = node->___child[SIDE_RGHT]; \
387  else \
388  node = node->___child[SIDE_LEFT]; \
389  } \
390  \
391  return (node); \
392  }
393 
394 #define __WALK_STACK_SIZE 32
395 #define __WALK_STACK_GROW 16
396 
397 #define PUSH(n) node_stack[node_stack_count] = (n), ++node_stack_count
398 #define POP(n) (n) = node_stack[--node_stack_count]
399 #define TOP (node_stack[node_stack_count-1])
400 #define CNT node_stack_count
401 
402 #define RBN_WALK_CODE(__t_name) \
403  DEF_RBN_WALK(__t_name) { \
404  NODETYPE(__t_name) **node_stack; \
405  register uint16_t node_stack_size; \
406  register uint16_t node_stack_count; \
407  \
408  node_stack_count = 0; \
409  node_stack_size = __WALK_STACK_SIZE; \
410  node_stack = XCALLOC(sizeof (NODETYPE(__t_name) *), node_stack_size); \
411  \
412  PUSH(tree->root); \
413  \
414  switch (order) { \
415  case PREORDER: \
416  while (CNT > 0) { \
417  callback (TOP, cbarg); \
418  if (TOP->___child[SIDE_LEFT] != NULL) { \
419  PUSH(TOP->___child[SIDE_LEFT]); \
420  } else { \
421  __pre: \
422  if (TOP->___child[SIDE_RGHT] != NULL) { \
423  TOP = TOP->___child[SIDE_RGHT]; \
424  } else { \
425  if (--CNT > 0) \
426  goto __pre; \
427  else \
428  break; \
429  } \
430  } \
431  } \
432  break; \
433  case INORDER: \
434  while (CNT > 0) { \
435  if (TOP->___child[SIDE_LEFT] != NULL) { \
436  PUSH(TOP->___child[SIDE_LEFT]); \
437  } else { \
438  __in: \
439  callback (TOP, cbarg); \
440  if (TOP->___child[SIDE_RGHT] != NULL) { \
441  TOP = TOP->___child[SIDE_RGHT]; \
442  } else { \
443  if (--CNT > 0) \
444  goto __in; \
445  else \
446  break; \
447  } \
448  } \
449  } \
450  break; \
451  case POSTORDER: \
452  break; \
453  default: \
454  abort (); \
455  } \
456  XFREE(node_stack); \
457  return; \
458  }
459 
460 /*
461  #undef PUSH
462  #undef POP
463  #undef TOP
464  #undef COUNT
465 */
466 
467 /*
468  #define RBN_DELETE()
469  #define RBN_REMOVE() RBN_DELETE()
470 */
471 
472 /*
473  #define RBN_NODE_LEFT()
474  #define RBN_NODE_RGHT()
475  #define RBN_NODE_RIGHT() RBN_NODE_RGHT()
476  #define RBN_NODE_COLOR()
477  #define RBN_NODE_SIDE()
478 */
479 
480 #define RBTREECODE(__t_name) \
481  RBN_CREATE_CODE(__t_name) \
482  RBN_ROTATE_CODE(__t_name); \
483  RBN_NEWNODE_CODE(__t_name) \
484  RBN_SEARCH_CODE(__t_name) \
485  RBN_INSERT_CODE(__t_name) \
486  RBN_WALK_CODE(__t_name) \
487  static const char CONCAT2(__t_name, dummy) = 0
488 
489 
490 #endif /* REDBLACK_H */