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