1 /* 2 * librd - Rapid Development C library 3 * 4 * Copyright (c) 2012-2016, Magnus Edenhill 5 * All rights reserved. 6 * 7 * Redistribution and use in source and binary forms, with or without 8 * modification, are permitted provided that the following conditions are met: 9 * 10 * 1. Redistributions of source code must retain the above copyright notice, 11 * this list of conditions and the following disclaimer. 12 * 2. Redistributions in binary form must reproduce the above copyright notice, 13 * this list of conditions and the following disclaimer in the documentation 14 * and/or other materials provided with the distribution. 15 * 16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 17 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 19 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE 20 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 21 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 22 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 23 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 26 * POSSIBILITY OF SUCH DAMAGE. 27 */ 28 29 30 /* 31 * AVL tree. 32 * Inspired by Ian Piumarta's tree.h implementation. 33 */ 34 35 #ifndef _RDAVL_H_ 36 #define _RDAVL_H_ 37 38 #include "tinycthread.h" 39 40 41 typedef enum { 42 RD_AVL_LEFT, 43 RD_AVL_RIGHT, 44 } rd_avl_dir_t; 45 46 /** 47 * AVL tree node. 48 * Add 'rd_avl_node_t ..' as field to your element's struct and 49 * provide it as the 'field' argument in the API below. 50 */ 51 typedef struct rd_avl_node_s { 52 struct rd_avl_node_s *ran_p[2]; /* RD_AVL_LEFT and RD_AVL_RIGHT */ 53 int ran_height; /* Sub-tree height */ 54 void *ran_elm; /* Backpointer to the containing 55 * element. This could be considered 56 * costly but is convenient for the 57 * caller: RAM is cheap, 58 * development time isn't*/ 59 } rd_avl_node_t; 60 61 62 63 /** 64 * Per-AVL application-provided element comparator. 65 */ 66 typedef int (*rd_avl_cmp_t) (const void *, const void *); 67 68 69 /** 70 * AVL tree 71 */ 72 typedef struct rd_avl_s { 73 rd_avl_node_t *ravl_root; /* Root node */ 74 rd_avl_cmp_t ravl_cmp; /* Comparator */ 75 int ravl_flags; /* Flags */ 76 #define RD_AVL_F_LOCKS 0x1 /* Enable thread-safeness */ 77 #define RD_AVL_F_OWNER 0x2 /* internal: rd_avl_init() allocated ravl */ 78 rwlock_t ravl_rwlock; /* Mutex when .._F_LOCKS is set. */ 79 } rd_avl_t; 80 81 82 83 84 /** 85 * 86 * 87 * Public API 88 * 89 * 90 */ 91 92 /** 93 * Insert 'elm' into AVL tree. 94 * In case of collision the previous entry is overwritten by the 95 * new one and the previous element is returned, else NULL. 96 */ 97 #define RD_AVL_INSERT(ravl,elm,field) \ 98 rd_avl_insert(ravl, elm, &(elm)->field) 99 100 101 /** 102 * Remove element by matching value 'elm' using compare function. 103 */ 104 #define RD_AVL_REMOVE_ELM(ravl,elm) \ 105 rd_avl_remove_elm(ravl, elm) 106 107 /** 108 * Search for (by value using compare function) and return matching elm. 109 */ 110 #define RD_AVL_FIND(ravl,elm) \ 111 rd_avl_find(ravl, elm, 1) 112 113 114 /** 115 * Search (by value using compare function) for and return matching elm. 116 * Same as RD_AVL_FIND_NL() but assumes 'ravl' ís already locked 117 * by 'rd_avl_*lock()'. 118 * 119 * NOTE: rd_avl_wrlock() must be held. 120 */ 121 #define RD_AVL_FIND_NL(ravl,elm) \ 122 rd_avl_find_node(ravl, (ravl)->ravl_root, elm, 0) 123 124 125 /** 126 * Search (by value using compare function) for elm and return its AVL node. 127 * 128 * NOTE: rd_avl_wrlock() must be held. 129 */ 130 #define RD_AVL_FIND_NODE_NL(ravl,elm) \ 131 rd_avl_find(ravl, elm, 0) 132 133 134 /** 135 * Changes the element pointer for an existing AVL node in the tree. 136 * The new element must be identical (according to the comparator) 137 * to the previous element. 138 * 139 * NOTE: rd_avl_wrlock() must be held. 140 */ 141 #define RD_AVL_ELM_SET_NL(ran,elm) ((ran)->ran_elm = (elm)) 142 143 /** 144 * Returns the current element pointer for an existing AVL node in the tree 145 * 146 * NOTE: rd_avl_*lock() must be held. 147 */ 148 #define RD_AVL_ELM_GET_NL(ran) ((ran)->ran_elm) 149 150 151 152 /** 153 * Destroy previously initialized (by rd_avl_init()) AVL tree. 154 */ 155 void rd_avl_destroy (rd_avl_t *ravl); 156 157 /** 158 * Initialize (and optionally allocate if 'ravl' is NULL) AVL tree. 159 * 'cmp' is the comparison function that takes two const pointers 160 * pointing to the elements being compared (rather than the avl_nodes). 161 * 'flags' is zero or more of the RD_AVL_F_.. flags. 162 * 163 * For thread-safe AVL trees supply RD_AVL_F_LOCKS in 'flags'. 164 */ 165 rd_avl_t *rd_avl_init (rd_avl_t *ravl, rd_avl_cmp_t cmp, int flags); 166 167 168 /** 169 * 'ravl' locking functions. 170 * Locking is performed automatically for all methods except for 171 * those with the "_NL"/"_nl" suffix ("not locked") which expects 172 * either read or write lock to be held. 173 * 174 * rdavl utilizes rwlocks to allow multiple concurrent read threads. 175 */ 176 static RD_INLINE RD_UNUSED void rd_avl_rdlock (rd_avl_t *ravl) { 177 if (ravl->ravl_flags & RD_AVL_F_LOCKS) 178 rwlock_rdlock(&ravl->ravl_rwlock); 179 } 180 181 static RD_INLINE RD_UNUSED void rd_avl_wrlock (rd_avl_t *ravl) { 182 if (ravl->ravl_flags & RD_AVL_F_LOCKS) 183 rwlock_wrlock(&ravl->ravl_rwlock); 184 } 185 186 static RD_INLINE RD_UNUSED void rd_avl_rdunlock (rd_avl_t *ravl) { 187 if (ravl->ravl_flags & RD_AVL_F_LOCKS) 188 rwlock_rdunlock(&ravl->ravl_rwlock); 189 } 190 191 static RD_INLINE RD_UNUSED void rd_avl_wrunlock (rd_avl_t *ravl) { 192 if (ravl->ravl_flags & RD_AVL_F_LOCKS) 193 rwlock_wrunlock(&ravl->ravl_rwlock); 194 } 195 196 197 198 199 /** 200 * Private API, dont use directly. 201 */ 202 203 rd_avl_node_t *rd_avl_insert_node (rd_avl_t *ravl, 204 rd_avl_node_t *parent, 205 rd_avl_node_t *ran, 206 rd_avl_node_t **existing); 207 208 static RD_UNUSED void *rd_avl_insert (rd_avl_t *ravl, void *elm, 209 rd_avl_node_t *ran) { 210 rd_avl_node_t *existing = NULL; 211 212 memset(ran, 0, sizeof(*ran)); 213 ran->ran_elm = elm; 214 215 rd_avl_wrlock(ravl); 216 ravl->ravl_root = rd_avl_insert_node(ravl, ravl->ravl_root, 217 ran, &existing); 218 rd_avl_wrunlock(ravl); 219 220 return existing ? existing->ran_elm : NULL; 221 } 222 223 rd_avl_node_t *rd_avl_remove_elm0 (rd_avl_t *ravl, rd_avl_node_t *parent, 224 const void *elm); 225 226 static RD_INLINE RD_UNUSED 227 void rd_avl_remove_elm (rd_avl_t *ravl, const void *elm) { 228 rd_avl_wrlock(ravl); 229 ravl->ravl_root = rd_avl_remove_elm0(ravl, ravl->ravl_root, elm); 230 rd_avl_wrunlock(ravl); 231 } 232 233 234 rd_avl_node_t *rd_avl_find_node (const rd_avl_t *ravl, 235 const rd_avl_node_t *begin, 236 const void *elm); 237 238 239 static RD_INLINE RD_UNUSED void *rd_avl_find (rd_avl_t *ravl, const void *elm, 240 int dolock) { 241 const rd_avl_node_t *ran; 242 void *ret; 243 244 if (dolock) 245 rd_avl_rdlock(ravl); 246 247 ran = rd_avl_find_node(ravl, ravl->ravl_root, elm); 248 ret = ran ? ran->ran_elm : NULL; 249 250 if (dolock) 251 rd_avl_rdunlock(ravl); 252 253 return ret; 254 } 255 256 #endif /* _RDAVL_H_ */ 257