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 #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 void rbt_free2(rbt_t *rbt, void (*callback)(void *, void *), void *user); 00138 00143 int rbt_rlock(rbt_t *rbt); 00144 00149 void rbt_runlock(rbt_t *rbt); 00150 00155 int rbt_wlock(rbt_t *rbt); 00156 00161 void rbt_wunlock(rbt_t *rbt); 00162 00163 struct rbt_node *rbt_node_rotate_L(struct rbt_node *); 00164 struct rbt_node *rbt_node_rotate_R(struct rbt_node *); 00165 struct rbt_node *rbt_node_rotate_LR(struct rbt_node *); 00166 struct rbt_node *rbt_node_rotate_RL(struct rbt_node *); 00167 00168 size_t rbt_size(rbt_t *rbt); 00169 00170 #define rbt_walk_push(n) stack[depth++] = (n) 00171 #define rbt_walk_pop() stack[--depth] 00172 #define rbt_walk_top() stack[depth-1] 00173 00174 int rbt_walk_preorder(rbt_t *rbt, int (*callback)(void *), rbt_walk_t flags); 00175 int rbt_walk_inorder(rbt_t *rbt, int (*callback)(void *), rbt_walk_t flags); 00176 int rbt_walk_inorder2(rbt_t *rbt, int (*callback)(void *, void *), void *user, rbt_walk_t flags); 00177 int rbt_walk_postorder(rbt_t *rbt, int (*callback)(void *), rbt_walk_t flags); 00178 00179 #endif /* RBT_COMMON_H */