Open SCAP Library
|
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 #ifdef HAVE_CONFIG_H 00026 #include <config.h> 00027 #endif 00028 00029 #include <stdint.h> 00030 #include <stdbool.h> 00031 00032 #if defined(RBT_IMPLICIT_LOCKING) 00033 # include <pthread.h> 00034 #endif 00035 00036 #ifndef HAVE_POSIX_MEMALIGN 00037 # ifdef HAVE_MEMALIGN 00038 int posix_memalign(void **memptr, size_t alignment, size_t size); 00039 # endif /* HAVE_MEMALIGN */ 00040 #endif /* HAVE_POSIX_MEMALIGN */ 00041 00042 typedef enum { 00043 RBT_GENKEY, 00044 RBT_STRKEY, 00045 RBT_I32KEY, 00046 RBT_I64KEY 00047 } rbt_type_t; 00048 00049 typedef enum { 00050 RBT_WALK_PREORDER = 0x01, 00051 RBT_WALK_INORDER = 0x02, 00052 RBT_WALK_POSTORDER = 0x03, 00053 RBT_WALK_LEVELORDER = 0x04, 00054 RBT_WALK_RAWNODE = 0x10 00055 } rbt_walk_t; 00056 00057 #define RBT_WALK_TYPEMASK 0x0f 00058 #define RBT_WALK_FLAGMASK 0xf0 00059 00064 struct rbt_node { 00065 struct rbt_node *_chld[2]; 00066 uint8_t _node[]; 00067 }; 00068 00069 #define RBT_NODE_CB 0 00070 #define RBT_NODE_CR 1 00071 #define RBT_NODE_SL 0 00072 #define RBT_NODE_SR 1 00073 00074 #define rbt_node_ptr(np) ((struct rbt_node *)((uintptr_t)(np)&(UINTPTR_MAX << 1))) 00075 #define rbt_node_setptr(dst,src) (dst) = (struct rbt_node *)((uintptr_t)rbt_node_ptr(src)|((uintptr_t)(dst)&1)) 00076 00077 #define rbt_node_setcolor(np, cb) \ 00078 do { \ 00079 register struct rbt_node *__n = rbt_node_ptr(np); \ 00080 register uint8_t __c = (cb) & 1; \ 00081 \ 00082 if (__n != NULL) { \ 00083 if (__c) __n->_chld[0] = (struct rbt_node *)((uintptr_t)(__n->_chld[0]) | 1); \ 00084 else __n->_chld[0] = rbt_node_ptr(__n->_chld[0]); \ 00085 } \ 00086 } while(0) 00087 #define rbt_node_getcolor_raw(cp) ((uintptr_t)(cp) & 1) 00088 #define rbt_node_getcolor(np) (rbt_node_ptr(np) == NULL ? RBT_NODE_CB : rbt_node_getcolor_raw(rbt_node_ptr(np)->_chld[0])) 00089 #define rbt_node_cpycolor(dn, sn) rbt_node_setcolor((dn), rbt_node_getcolor(sn)) 00090 00091 #define rbt_hpush4(__a, __p) \ 00092 do { \ 00093 __a[3] = __a[2]; \ 00094 __a[2] = __a[1]; \ 00095 __a[1] = __a[0]; \ 00096 __a[0] = __p; \ 00097 } while(0) 00098 00099 #define rbt_hpush3(__a, __p) \ 00100 do { \ 00101 __a[2] = __a[1]; \ 00102 __a[1] = __a[0]; \ 00103 __a[0] = __p; \ 00104 } while(0) 00105 00106 #define rbt_redfix(__h, __d, v) \ 00107 do { \ 00108 if (((__d) & 3) < 2) { \ 00109 if (((__d) & 3) == 0) { \ 00110 rbt_node_setptr(v, rbt_node_rotate_R(__h[2])); \ 00111 } else { \ 00112 rbt_node_setptr(v, rbt_node_rotate_RL(__h[2])); \ 00113 } \ 00114 } else { \ 00115 if (((__d) & 3) == 2) { \ 00116 rbt_node_setptr(v, rbt_node_rotate_LR(__h[2])); \ 00117 } else { \ 00118 rbt_node_setptr(v, rbt_node_rotate_L(__h[2])); \ 00119 } \ 00120 } \ 00121 } while(0) 00122 00123 struct rbt { 00124 struct rbt_node *root; 00125 size_t size; 00126 rbt_type_t type; 00127 #if defined(RBT_IMPLICIT_LOCKING) 00128 pthread_rwlock_t lock; 00129 #endif 00130 }; 00131 00132 typedef struct rbt rbt_t; 00133 00138 rbt_t *rbt_new(rbt_type_t type); 00139 00146 void rbt_free(rbt_t *rbt, void (*callback)(void *)); 00147 void rbt_free2(rbt_t *rbt, void (*callback)(void *, void *), void *user); 00148 00153 int rbt_rlock(rbt_t *rbt); 00154 00159 void rbt_runlock(rbt_t *rbt); 00160 00165 int rbt_wlock(rbt_t *rbt); 00166 00171 void rbt_wunlock(rbt_t *rbt); 00172 00173 struct rbt_node *rbt_node_rotate_L(struct rbt_node *); 00174 struct rbt_node *rbt_node_rotate_R(struct rbt_node *); 00175 struct rbt_node *rbt_node_rotate_LR(struct rbt_node *); 00176 struct rbt_node *rbt_node_rotate_RL(struct rbt_node *); 00177 00178 size_t rbt_size(rbt_t *rbt); 00179 00180 #define rbt_walk_push(n) stack[depth++] = (n) 00181 #define rbt_walk_pop() stack[--depth] 00182 #define rbt_walk_top() stack[depth-1] 00183 00184 int rbt_walk_preorder(rbt_t *rbt, int (*callback)(void *), rbt_walk_t flags); 00185 int rbt_walk_inorder(rbt_t *rbt, int (*callback)(void *), rbt_walk_t flags); 00186 int rbt_walk_inorder2(rbt_t *rbt, int (*callback)(void *, void *), void *user, rbt_walk_t flags); 00187 int rbt_walk_postorder(rbt_t *rbt, int (*callback)(void *), rbt_walk_t flags); 00188 00189 #endif /* RBT_COMMON_H */