• Main Page
  • Related Pages
  • Modules
  • Data Structures
  • Files
  • File List
  • Globals

/home/pvrabec/project/openscap/openscap-0.6.3/src/OVAL/probes/SEAP/generic/rbt/rbt_common.h

00001 /*
00002  * Copyright 2010 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 #ifndef RBT_COMMON_H
00023 #define RBT_COMMON_H
00024 
00025 #include <stdint.h>
00026 #include <stdbool.h>
00027 
00028 #if defined(RBT_IMPLICIT_LOCKING)
00029 # include <pthread.h>
00030 #endif
00031 
00032 typedef enum {
00033         RBT_GENKEY,
00034         RBT_STRKEY,
00035         RBT_I32KEY,
00036         RBT_I64KEY
00037 } rbt_type_t;
00038 
00039 typedef enum {
00040         RBT_WALK_PREORDER   = 0x01,
00041         RBT_WALK_INORDER    = 0x02,
00042         RBT_WALK_POSTORDER  = 0x03,
00043         RBT_WALK_LEVELORDER = 0x04,
00044         RBT_WALK_RAWNODE    = 0x10
00045 } rbt_walk_t;
00046 
00047 #define RBT_WALK_TYPEMASK 0x0f
00048 #define RBT_WALK_FLAGMASK 0xf0
00049 
00054 struct rbt_node {
00055         struct rbt_node *_chld[2];
00056         uint8_t          _node[];
00057 };
00058 
00059 #define RBT_NODE_CB 0
00060 #define RBT_NODE_CR 1
00061 #define RBT_NODE_SL 0
00062 #define RBT_NODE_SR 1
00063 
00064 #define rbt_node_ptr(np) ((struct rbt_node *)((uintptr_t)(np)&(UINTPTR_MAX << 1)))
00065 #define rbt_node_setptr(dst,src) (dst) = (struct rbt_node *)((uintptr_t)rbt_node_ptr(src)|((uintptr_t)(dst)&1))
00066 
00067 #define rbt_node_setcolor(np, cb)                                       \
00068         do {                                                            \
00069                 register struct rbt_node *__n = rbt_node_ptr(np);       \
00070                 register uint8_t          __c = (cb) & 1;               \
00071                                                                         \
00072                 if (__n != NULL) {                                      \
00073                         if (__c) __n->_chld[0] = (struct rbt_node *)((uintptr_t)(__n->_chld[0]) | 1); \
00074                         else     __n->_chld[0] = rbt_node_ptr(__n->_chld[0]); \
00075                 }                                                       \
00076         } while(0)
00077 #define rbt_node_getcolor_raw(cp) ((uintptr_t)(cp) & 1)
00078 #define rbt_node_getcolor(np) (rbt_node_ptr(np) == NULL ? RBT_NODE_CB : rbt_node_getcolor_raw(rbt_node_ptr(np)->_chld[0]))
00079 #define rbt_node_cpycolor(dn, sn) rbt_node_setcolor((dn), rbt_node_getcolor(sn))
00080 
00081 #define rbt_hpush4(__a, __p)                    \
00082         do {                                    \
00083                 __a[3] = __a[2];                \
00084                 __a[2] = __a[1];                \
00085                 __a[1] = __a[0];                \
00086                 __a[0] = __p;                   \
00087         } while(0)
00088 
00089 #define rbt_hpush3(__a, __p)                    \
00090         do {                                    \
00091                 __a[2] = __a[1];                \
00092                 __a[1] = __a[0];                \
00093                 __a[0] = __p;                   \
00094         } while(0)
00095 
00096 #define rbt_redfix(__h, __d, v)                                         \
00097         do {                                                            \
00098                 if (((__d) & 3) < 2) {                                  \
00099                         if (((__d) & 3) == 0) {                         \
00100                                 rbt_node_setptr(v, rbt_node_rotate_R(__h[2])); \
00101                         } else {                                        \
00102                                 rbt_node_setptr(v, rbt_node_rotate_RL(__h[2])); \
00103                         }                                               \
00104                 } else {                                                \
00105                         if (((__d) & 3) == 2) {                         \
00106                                 rbt_node_setptr(v, rbt_node_rotate_LR(__h[2])); \
00107                         } else {                                        \
00108                                 rbt_node_setptr(v, rbt_node_rotate_L(__h[2])); \
00109                         }                                               \
00110                 }                                                       \
00111         } while(0)
00112 
00113 struct rbt {
00114         struct rbt_node *root;
00115         size_t           size;
00116         rbt_type_t       type;
00117 #if defined(RBT_IMPLICIT_LOCKING)
00118         pthread_rwlock_t lock;
00119 #endif
00120 };
00121 
00122 typedef struct rbt rbt_t;
00123 
00128 rbt_t *rbt_new(rbt_type_t type);
00129 
00136 void rbt_free(rbt_t *rbt, void (*callback)(void *));
00137 
00142 int rbt_rlock(rbt_t *rbt);
00143 
00148 void rbt_runlock(rbt_t *rbt);
00149 
00154 int rbt_wlock(rbt_t *rbt);
00155 
00160 void rbt_wunlock(rbt_t *rbt);
00161 
00162 struct rbt_node *rbt_node_rotate_L(struct rbt_node *);
00163 struct rbt_node *rbt_node_rotate_R(struct rbt_node *);
00164 struct rbt_node *rbt_node_rotate_LR(struct rbt_node *);
00165 struct rbt_node *rbt_node_rotate_RL(struct rbt_node *);
00166 
00167 size_t rbt_size(rbt_t *rbt);
00168 
00169 #define rbt_walk_push(n) stack[depth++] = (n)
00170 #define rbt_walk_pop()   stack[--depth]
00171 #define rbt_walk_top()   stack[depth-1]
00172 
00173 int rbt_walk_preorder(rbt_t *rbt, int (*callback)(void *), rbt_walk_t flags);
00174 int rbt_walk_inorder(rbt_t *rbt, int (*callback)(void *), rbt_walk_t flags);
00175 int rbt_walk_postorder(rbt_t *rbt, int (*callback)(void *), rbt_walk_t flags);
00176 
00177 #endif /* RBT_COMMON_H */

Generated on Tue Sep 14 2010 for Open SCAP Library by  doxygen 1.7.1