Open SCAP Library
|
00001 /* 00002 * Copyright 2009 Red Hat Inc., Durham, North Carolina. 00003 * All Rights Reserved. 00004 * 00005 * This library is free software; you can redistribute it and/or 00006 * modify it under the terms of the GNU Lesser General Public 00007 * License as published by the Free Software Foundation; either 00008 * version 2.1 of the License, or (at your option) any later version. 00009 * 00010 * This library is distributed in the hope that it will be useful, 00011 * but WITHOUT ANY WARRANTY; without even the implied warranty of 00012 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00013 * Lesser General Public License for more details. 00014 * 00015 * You should have received a copy of the GNU Lesser General Public 00016 * License along with this library; if not, write to the Free Software 00017 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA 00018 * 00019 * Authors: 00020 * "Daniel Kopecek" <dkopecek@redhat.com> 00021 */ 00022 00023 #pragma once 00024 #ifndef REDBLACK_H 00025 #define REDBLACK_H 00026 00027 #include <stdint.h> 00028 #include <stdlib.h> 00029 #include <assert.h> 00030 #include "../../../../common/util.h" 00031 00032 OSCAP_HIDDEN_START; 00033 00034 #ifndef NDEBUG 00035 # define _E(exp) exp 00036 #else 00037 # define _E(exp) while(0) 00038 #endif 00039 00040 #define XMALLOC malloc 00041 #define XREALLOC realloc 00042 #define XCALLOC calloc 00043 #define XFREE free 00044 00045 #define SIDE_LEFT ((side_t)0) 00046 #define SIDE_RGHT ((side_t)1) 00047 00048 #define COLOR_BLK 0 00049 #define COLOR_RED 1 00050 00051 #define PREORDER 0 00052 #define INORDER 1 00053 #define POSTORDER 2 00054 #define LRTDLAYER 3 00055 #define RLTDLAYER 4 00056 00057 #if !defined (E_OK) 00058 # define E_OK 0 00059 #endif 00060 #if !defined (E_FAIL) 00061 # define E_FAIL 1 00062 #endif 00063 #if !defined (E_COLL) 00064 # define E_COLL 2 00065 #endif 00066 00067 #define __NAME_PREFIX__ ___rb_ 00068 #define __TREETYPE_PREFIX rbtree_ 00069 #define __NODETYPE_PREFIX rbnode_ 00070 #define __NODETYPE_ATTRS__ __attribute__ ((packed)) 00071 #define __TREETYPE_ATTRS__ __attribute__ ((packed)) 00072 00073 typedef uint8_t side_t; 00074 typedef uint8_t color_t; 00075 00076 #define __MYCONCAT2(a, b) a ## b 00077 #define __MYCONCAT3(a, b, c) a ## b ## c 00078 #define CONCAT2(a, b) __MYCONCAT2(a, b) 00079 #define CONCAT3(a, b, c) __MYCONCAT3(a, b, c) 00080 #define EXPAND(a) a 00081 00082 #define TREETYPE(__t_name) struct CONCAT2(__TREETYPE_PREFIX, __t_name) 00083 #define NODETYPE(__t_name) struct CONCAT2(__NODETYPE_PREFIX, __t_name) 00084 00085 /* Definition templates */ 00086 #define DEF_RBN_INITST(__t_name) int CONCAT3(__NAME_PREFIX__, __t_name, _initst) (TREETYPE(__t_name) *tree) 00087 00088 #define RBN_CREATE_NAME(__t_name) CONCAT3(__NAME_PREFIX__, __t_name, _create) 00089 #define DEF_RBN_CREATE(__t_name) TREETYPE(__t_name) * RBN_CREATE_NAME(__t_name) (void) 00090 #define RB_CREATE RBN_CREATE_NAME 00091 00092 #define RBN_NEWNODE_NAME(__t_name) CONCAT3(__NAME_PREFIX__, __t_name, _newnode) 00093 #define DEF_RBN_NEWNODE(__t_name) NODETYPE(__t_name) * RBN_NEWNODE_NAME(__t_name) (void) 00094 #define RB_NEWNODE RBN_NEWNODE_NAME 00095 00096 #define RBN_INSERT_NAME(__t_name) CONCAT3(__NAME_PREFIX__, __t_name, _insert) 00097 #define DEF_RBN_INSERT(__t_name) int RBN_INSERT_NAME(__t_name) (TREETYPE(__t_name) *tree, NODETYPE(__t_name) *new_node) 00098 #define RB_INSERT RBN_INSERT_NAME 00099 00100 #define RBN_SEARCH_NAME(__t_name) CONCAT3(__NAME_PREFIX__, __t_name, _search) 00101 #define DEF_RBN_SEARCH(__t_name) NODETYPE(__t_name) * RBN_SEARCH_NAME(__t_name) (TREETYPE(__t_name) *tree, const NODETYPE(__t_name) *k_node) 00102 #define RB_SEARCH RBN_SEARCH_NAME 00103 00104 #define DEF_RBN_DELETE(__t_name) int CONCAT3(__NAME_PREFIX__, __t_name, _delete) (TREETYPE(__t_name) *tree, const NODETYPE(__t_name) *k_node) 00105 00106 #define DEF_RBN_REMOVE(__t_name) DEF_RBN_DELETE(__t_name) 00107 00108 #define DEF_RBN_NODE_LEFT(__t_name) NODETYPE(__t_name) * CONCAT3(__NAME_PREFIX__, __t_name, _getLeftNode) (NODETYPE(__t_name) *node) 00109 #define DEF_RBN_NODE_RGHT(__t_name) NODETYPE(__t_name) * CONCAT3(__NAME_PREFIX__, __t_name, _getRghtNode) (NODETYPE(__t_name) *node) 00110 #define DEF_RBN_NODE_RIGHT(__t_name) RBN_NODE_RGHT(__t_name) 00111 00112 #define DEF_RBN_NODE_COLOR(__t_name) color_t CONCAT3(__NAME_PREFIX__, __t_name, _getColor) (NODETYPE(__t_name) *node) 00113 #define DEF_RBN_NODE_SIDE(__t_name) side_t CONCAT3(__NAME_PREFIX__, __t_name, _getSide) (NODETYPE(__t_name) *node) 00114 00115 #define DEF_RBN_ROT_R(__t_name) NODETYPE(__t_name) * CONCAT3(__NAME_PREFIX__, __t_name, _rotR) (NODETYPE(__t_name) *r) 00116 #define DEF_RBN_ROT_L(__t_name) NODETYPE(__t_name) * CONCAT3(__NAME_PREFIX__, __t_name, _rotL) (NODETYPE(__t_name) *r) 00117 #define DEF_RBN_ROT_RL(__t_name) NODETYPE(__t_name) * CONCAT3(__NAME_PREFIX__, __t_name, _rotRL) (NODETYPE(__t_name) *r) 00118 #define DEF_RBN_ROT_LR(__t_name) NODETYPE(__t_name) * CONCAT3(__NAME_PREFIX__, __t_name, _rotLR) (NODETYPE(__t_name) *r) 00119 00120 #define ROTATE_ARR_NAME(__t_name) CONCAT3(__NAME_PREFIX__, __t_name, _rotate) 00121 00122 #define RBN_NODECMP_NAME(__t_name) CONCAT3(__NAME_PREFIX__, __t_name, _nodecmp) 00123 #define DEF_RBN_NODECMP(__t_name) int RBN_NODECMP_NAME(__t_name) (const NODETYPE(__t_name) *a, const NODETYPE(__t_name) *b) 00124 #define RBNODECMP DEF_RBN_NODECMP 00125 00126 #define RBN_NODEJOIN_NAME(__t_name) CONCAT3(__NAME_PREFIX__, __t_name, _nodejoin) 00127 #define DEF_RBN_NODEJOIN(__t_name) NODETYPE(__t_name) * RBN_NODEJOIN_NAME(__t_name) (NODETYPE(__t_name) *a, NODETYPE(__t_name) *b) 00128 #define RBNODEJOIN DEF_RBN_NODEJOIN 00129 00130 #define RBN_WALK_NAME(__t_name) CONCAT3(__NAME_PREFIX__, __t_name, _walk) 00131 #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) 00132 #define RB_WALK RBN_WALK_NAME 00133 00134 #define RBN_CALLBACK_NAME(__t_name, myname) CONCAT3(__t_name, _CB_, myname) 00135 #define DEF_RBN_CALLBACK(__t_name, myname) void RBN_CALLBACK_NAME(__t_name, myname) (NODETYPE(__t_name) *node, void *cbarg) 00136 #define RBCBNAME RBN_CALLBACK_NAME 00137 #define RBCALLBACK DEF_RBN_CALLBACK 00138 00139 #define NOARG 0 00140 00141 /* Main template */ 00142 #define DEFRBTREE(__t_name, __u_nitem) \ 00143 NODETYPE(__t_name) { \ 00144 /* META data */ \ 00145 NODETYPE(__t_name) *___child[2]; \ 00146 color_t ___c: 1; /* Node color */ \ 00147 side_t ___s: 1; /* Node side relative to parent */ \ 00148 /* USER data */ \ 00149 __u_nitem; \ 00150 } __NODETYPE_ATTRS__; \ 00151 \ 00152 TREETYPE(__t_name) { \ 00153 NODETYPE(__t_name) *root; \ 00154 size_t size; \ 00155 } __TREETYPE_ATTRS__; \ 00156 \ 00157 DEF_RBN_NODEJOIN(__t_name); \ 00158 DEF_RBN_NODECMP(__t_name); \ 00159 DEF_RBN_CREATE(__t_name); \ 00160 DEF_RBN_NEWNODE(__t_name); \ 00161 DEF_RBN_WALK(__t_name); \ 00162 DEF_RBN_INSERT(__t_name); \ 00163 DEF_RBN_SEARCH(__t_name) 00164 /* 00165 DEF_RBN_INITST(__t_name); \ 00166 DEF_RBN_SEARCH(__t_name, __keytype); \ 00167 DEF_RBN_DELETE(__t_name, __keytype); \ 00168 DEF_RBN_NODE_LEFT(__t_name); \ 00169 DEF_RBN_NODE_RGHT(__t_name); \ 00170 DEF_RBN_NODE_COLOR(__t_name); \ 00171 DEF_RBN_NODE_SIDE(__t_name) 00172 */ 00173 00174 #define __isRED(n) ((n)->___c == COLOR_RED) 00175 #define isRED(n) (((n) == NULL) ? 0 : __isRED(n)) 00176 #define PTRMOVE(next) { \ 00177 ggp = grp; \ 00178 grp = par; \ 00179 par = cur; \ 00180 cur = next; } 00181 00182 #define lch (cur->___child[SIDE_LEFT]) 00183 #define rch (cur->___child[SIDE_RGHT]) 00184 00185 /* Code templates */ 00186 //#define RBN_INITST() 00187 00188 #define RBN_NEWNODE_CODE(__t_name) \ 00189 DEF_RBN_NEWNODE(__t_name) { \ 00190 NODETYPE(__t_name) *new; \ 00191 new = XMALLOC(sizeof(NODETYPE(__t_name))); \ 00192 new->___s = 0; \ 00193 new->___c = 0; \ 00194 new->___child[0] = NULL; \ 00195 new->___child[1] = NULL; \ 00196 return (new); \ 00197 } 00198 00199 #define RBN_ROTATE_CODE(__t_name) \ 00200 static DEF_RBN_ROT_L(__t_name) { \ 00201 register NODETYPE(__t_name) *nr; \ 00202 \ 00203 nr = r->___child[SIDE_RGHT]; \ 00204 r->___child[SIDE_RGHT] = nr->___child[SIDE_LEFT]; \ 00205 nr->___child[SIDE_LEFT] = r; \ 00206 \ 00207 nr->___s = r->___s; \ 00208 r->___s = SIDE_LEFT; \ 00209 \ 00210 if (r->___child[SIDE_RGHT] != NULL) \ 00211 r->___child[SIDE_RGHT]->___s = SIDE_RGHT; \ 00212 \ 00213 if (nr->___child[SIDE_RGHT] != NULL) \ 00214 nr->___child[SIDE_RGHT]->___c = COLOR_BLK; \ 00215 \ 00216 return (nr); \ 00217 } \ 00218 \ 00219 static DEF_RBN_ROT_R(__t_name) { \ 00220 register NODETYPE(__t_name) *nr; \ 00221 \ 00222 nr = r->___child[SIDE_LEFT]; \ 00223 r->___child[SIDE_LEFT] = nr->___child[SIDE_RGHT]; \ 00224 nr->___child[SIDE_RGHT] = r; \ 00225 \ 00226 nr->___s = r->___s; \ 00227 r->___s = SIDE_RGHT; \ 00228 \ 00229 if (r->___child[SIDE_LEFT] != NULL) \ 00230 r->___child[SIDE_LEFT]->___s = SIDE_LEFT; \ 00231 \ 00232 if (nr->___child[SIDE_LEFT] != NULL) \ 00233 nr->___child[SIDE_LEFT]->___c = COLOR_BLK; \ 00234 \ 00235 return (nr); \ 00236 } \ 00237 \ 00238 static DEF_RBN_ROT_LR(__t_name) { \ 00239 register NODETYPE(__t_name) *nr; \ 00240 \ 00241 nr = r->___child[SIDE_RGHT]->___child[SIDE_LEFT]; \ 00242 nr->___s = r->___s; \ 00243 r->___s = SIDE_LEFT; \ 00244 r->___child[SIDE_RGHT]->___child[SIDE_LEFT] = nr->___child[SIDE_RGHT]; \ 00245 \ 00246 if (nr->___child[SIDE_RGHT] != NULL) \ 00247 nr->___child[SIDE_RGHT]->___s = SIDE_LEFT; \ 00248 \ 00249 nr->___child[SIDE_RGHT] = r->___child[SIDE_RGHT]; \ 00250 r->___child[SIDE_RGHT] = nr->___child[SIDE_LEFT]; \ 00251 \ 00252 if (nr->___child[SIDE_LEFT] != NULL) \ 00253 nr->___child[SIDE_LEFT]->___s = SIDE_RGHT; \ 00254 \ 00255 nr->___child[SIDE_LEFT] = r; \ 00256 nr->___child[SIDE_RGHT]->___c = COLOR_BLK; \ 00257 \ 00258 return (nr); \ 00259 } \ 00260 \ 00261 static DEF_RBN_ROT_RL(__t_name) { \ 00262 register NODETYPE(__t_name) *nr; \ 00263 \ 00264 nr = r->___child[SIDE_LEFT]->___child[SIDE_RGHT]; \ 00265 nr->___s = r->___s; \ 00266 r->___s = SIDE_RGHT; \ 00267 r->___child[SIDE_LEFT]->___child[SIDE_RGHT] = nr->___child[SIDE_LEFT]; \ 00268 \ 00269 if (nr->___child[SIDE_LEFT] != NULL) \ 00270 nr->___child[SIDE_LEFT]->___s = SIDE_RGHT; \ 00271 \ 00272 nr->___child[SIDE_LEFT] = r->___child[SIDE_LEFT]; \ 00273 r->___child[SIDE_LEFT] = nr->___child[SIDE_RGHT]; \ 00274 \ 00275 if (nr->___child[SIDE_RGHT] != NULL) \ 00276 nr->___child[SIDE_RGHT]->___s = SIDE_LEFT; \ 00277 \ 00278 nr->___child[SIDE_RGHT] = r; \ 00279 nr->___child[SIDE_LEFT]->___c = COLOR_BLK; \ 00280 \ 00281 return (nr); \ 00282 } \ 00283 \ 00284 static NODETYPE(__t_name) * (*ROTATE_ARR_NAME(__t_name)[4])(NODETYPE(__t_name) *) = { \ 00285 &CONCAT3(__NAME_PREFIX__, __t_name, _rotR), \ 00286 &CONCAT3(__NAME_PREFIX__, __t_name, _rotLR), \ 00287 &CONCAT3(__NAME_PREFIX__, __t_name, _rotRL), \ 00288 &CONCAT3(__NAME_PREFIX__, __t_name, _rotL) \ 00289 } 00290 00291 #define RBN_CREATE_CODE(__t_name) \ 00292 DEF_RBN_CREATE(__t_name) { \ 00293 TREETYPE(__t_name) *new = XMALLOC (sizeof (TREETYPE(__t_name))); \ 00294 new->root = NULL; \ 00295 new->size = 0; \ 00296 return (new); \ 00297 } 00298 00299 #define RBN_INSERT_CODE(__t_name) \ 00300 DEF_RBN_INSERT(__t_name) { \ 00301 NODETYPE(__t_name) *cur, *par, *grp, *ggp; \ 00302 side_t lastdir; \ 00303 int cmp; \ 00304 NODETYPE(__t_name) fake; \ 00305 \ 00306 fake.___c = COLOR_BLK; \ 00307 fake.___child[SIDE_RGHT] = tree->root; \ 00308 fake.___child[SIDE_LEFT] = NULL; \ 00309 ggp = grp = NULL; \ 00310 par = &fake; \ 00311 cur = tree->root; \ 00312 lastdir = SIDE_RGHT; \ 00313 \ 00314 for (;;) { \ 00315 /* Search loop BEGIN */ \ 00316 if (cur == NULL) { \ 00317 par->___child[lastdir] = cur = new_node; \ 00318 cur->___s = lastdir; \ 00319 cur->___c = COLOR_RED; \ 00320 cur->___child[SIDE_LEFT] = cur->___child[SIDE_RGHT]; \ 00321 \ 00322 if (__isRED(par)) /* red violation */ \ 00323 ggp->___child[grp->___s] = ROTATE_ARR_NAME(__t_name)[(lastdir << 1)|(par->___s)](grp); \ 00324 \ 00325 tree->root = fake.___child[SIDE_RGHT]; \ 00326 tree->root->___c = COLOR_BLK; \ 00327 ++(tree->size); \ 00328 \ 00329 return (E_OK); \ 00330 } else if (isRED(lch) && isRED(rch)) { \ 00331 /* color switch */ \ 00332 cur->___c = COLOR_RED; \ 00333 lch->___c = rch->___c = COLOR_BLK; \ 00334 \ 00335 if (__isRED(par)) /* red violation */ \ 00336 ggp->___child[grp->___s] = ROTATE_ARR_NAME(__t_name)[(cur->___s << 1)|(par->___s)](grp); \ 00337 } else if (__isRED(par) && __isRED(cur)) { \ 00338 /* red violation */ \ 00339 ggp->___child[grp->___s] = ROTATE_ARR_NAME(__t_name)[(cur->___s << 1)|(par->___s)](grp); \ 00340 } \ 00341 \ 00342 cmp = RBN_NODECMP_NAME(__t_name) (cur, new_node); \ 00343 \ 00344 if (cmp == 0) { \ 00345 lastdir = cur->___s; \ 00346 _E(color_t tmp_c = cur->___c;) \ 00347 _E(NODETYPE(__t_name) *tmp_l = cur->___child[SIDE_LEFT];) \ 00348 _E(NODETYPE(__t_name) *tmp_r = cur->___child[SIDE_RGHT];) \ 00349 tree->root = fake.___child[SIDE_RGHT]; \ 00350 tree->root->___c = COLOR_BLK; \ 00351 RBN_NODEJOIN_NAME(__t_name) (cur, new_node); \ 00352 \ 00353 assert(cur->___s == lastdir); \ 00354 assert(cur->___c == tmp_c); \ 00355 assert(cur->___child[SIDE_LEFT] == tmp_l); \ 00356 assert(cur->___child[SIDE_RGHT] == tmp_r); \ 00357 \ 00358 return (E_COLL); \ 00359 } else if (cmp < 0) { \ 00360 /* go right */ \ 00361 PTRMOVE(rch); \ 00362 lastdir = SIDE_RGHT; \ 00363 } else { \ 00364 /* go left */ \ 00365 PTRMOVE(lch); \ 00366 lastdir = SIDE_LEFT; \ 00367 } \ 00368 } /* Search loop END */ \ 00369 \ 00370 abort (); \ 00371 return (E_FAIL); \ 00372 } 00373 00374 #define RBN_SEARCH_CODE(__t_name) \ 00375 DEF_RBN_SEARCH(__t_name) { \ 00376 NODETYPE(__t_name) *node; \ 00377 int cmp; \ 00378 \ 00379 node = tree->root; \ 00380 \ 00381 while (node != NULL) { \ 00382 cmp = RBN_NODECMP_NAME(__t_name) (node, k_node); \ 00383 \ 00384 if (cmp == 0) \ 00385 break; \ 00386 else if (cmp < 0) \ 00387 node = node->___child[SIDE_RGHT]; \ 00388 else \ 00389 node = node->___child[SIDE_LEFT]; \ 00390 } \ 00391 \ 00392 return (node); \ 00393 } 00394 00395 #define __WALK_STACK_SIZE 32 00396 #define __WALK_STACK_GROW 16 00397 00398 #define PUSH(n) node_stack[node_stack_count] = (n), ++node_stack_count 00399 #define POP(n) (n) = node_stack[--node_stack_count] 00400 #define TOP (node_stack[node_stack_count-1]) 00401 #define CNT node_stack_count 00402 00403 #define RBN_WALK_CODE(__t_name) \ 00404 DEF_RBN_WALK(__t_name) { \ 00405 NODETYPE(__t_name) **node_stack; \ 00406 register uint16_t node_stack_size; \ 00407 register uint16_t node_stack_count; \ 00408 \ 00409 node_stack_count = 0; \ 00410 node_stack_size = __WALK_STACK_SIZE; \ 00411 node_stack = XCALLOC(sizeof (NODETYPE(__t_name) *), node_stack_size); \ 00412 \ 00413 PUSH(tree->root); \ 00414 \ 00415 switch (order) { \ 00416 case PREORDER: \ 00417 while (CNT > 0) { \ 00418 callback (TOP, cbarg); \ 00419 if (TOP->___child[SIDE_LEFT] != NULL) { \ 00420 PUSH(TOP->___child[SIDE_LEFT]); \ 00421 } else { \ 00422 __pre: \ 00423 if (TOP->___child[SIDE_RGHT] != NULL) { \ 00424 TOP = TOP->___child[SIDE_RGHT]; \ 00425 } else { \ 00426 if (--CNT > 0) \ 00427 goto __pre; \ 00428 else \ 00429 break; \ 00430 } \ 00431 } \ 00432 } \ 00433 break; \ 00434 case INORDER: \ 00435 while (CNT > 0) { \ 00436 if (TOP->___child[SIDE_LEFT] != NULL) { \ 00437 PUSH(TOP->___child[SIDE_LEFT]); \ 00438 } else { \ 00439 __in: \ 00440 callback (TOP, cbarg); \ 00441 if (TOP->___child[SIDE_RGHT] != NULL) { \ 00442 TOP = TOP->___child[SIDE_RGHT]; \ 00443 } else { \ 00444 if (--CNT > 0) \ 00445 goto __in; \ 00446 else \ 00447 break; \ 00448 } \ 00449 } \ 00450 } \ 00451 break; \ 00452 case POSTORDER: \ 00453 break; \ 00454 default: \ 00455 abort (); \ 00456 } \ 00457 XFREE(node_stack); \ 00458 return; \ 00459 } 00460 00461 /* 00462 #undef PUSH 00463 #undef POP 00464 #undef TOP 00465 #undef COUNT 00466 */ 00467 00468 /* 00469 #define RBN_DELETE() 00470 #define RBN_REMOVE() RBN_DELETE() 00471 */ 00472 00473 /* 00474 #define RBN_NODE_LEFT() 00475 #define RBN_NODE_RGHT() 00476 #define RBN_NODE_RIGHT() RBN_NODE_RGHT() 00477 #define RBN_NODE_COLOR() 00478 #define RBN_NODE_SIDE() 00479 */ 00480 00481 #define RBTREECODE(__t_name) \ 00482 RBN_CREATE_CODE(__t_name) \ 00483 RBN_ROTATE_CODE(__t_name); \ 00484 RBN_NEWNODE_CODE(__t_name) \ 00485 RBN_SEARCH_CODE(__t_name) \ 00486 RBN_INSERT_CODE(__t_name) \ 00487 RBN_WALK_CODE(__t_name) \ 00488 static const char CONCAT2(__t_name, dummy) = 0 00489 00490 OSCAP_HIDDEN_END; 00491 00492 #endif /* REDBLACK_H */