1 /* GBSearchArray - Binary Searchable Array implementation 2 * Copyright (C) 2000-2003 Tim Janik 3 * 4 * This software is provided "as is"; redistribution and modification 5 * is permitted, provided that the following disclaimer is retained. 6 * 7 * This software is distributed in the hope that it will be useful, 8 * but WITHOUT ANY WARRANTY; without even the implied warranty of 9 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. 10 * In no event shall the authors or contributors be liable for any 11 * direct, indirect, incidental, special, exemplary, or consequential 12 * damages (including, but not limited to, procurement of substitute 13 * goods or services; loss of use, data, or profits; or business 14 * interruption) however caused and on any theory of liability, whether 15 * in contract, strict liability, or tort (including negligence or 16 * otherwise) arising in any way out of the use of this software, even 17 * if advised of the possibility of such damage. 18 */ 19 #ifndef __G_BSEARCH_ARRAY_H__ 20 #define __G_BSEARCH_ARRAY_H__ 21 22 #include <glib.h> 23 #include <string.h> 24 25 26 G_BEGIN_DECLS /* c++ guards */ 27 28 /* this implementation is intended to be usable in third-party code 29 * simply by pasting the contents of this file. as such, the 30 * implementation needs to be self-contained within this file. 31 */ 32 33 /* convenience macro to avoid signed overflow for value comparisions */ 34 #define G_BSEARCH_ARRAY_CMP(v1,v2) ((v1) > (v2) ? +1 : (v1) == (v2) ? 0 : -1) 35 36 37 /* --- typedefs --- */ 38 typedef gint (*GBSearchCompareFunc) (gconstpointer bsearch_node1, /* key */ 39 gconstpointer bsearch_node2); 40 typedef enum 41 { 42 G_BSEARCH_ARRAY_ALIGN_POWER2 = 1 << 0, /* align memory to power2 sizes */ 43 G_BSEARCH_ARRAY_AUTO_SHRINK = 1 << 1 /* shrink array upon removal */ 44 } GBSearchArrayFlags; 45 46 47 /* --- structures --- */ 48 typedef struct 49 { 50 guint sizeof_node; 51 GBSearchCompareFunc cmp_nodes; 52 guint flags; 53 } GBSearchConfig; 54 typedef union 55 { 56 guint n_nodes; 57 /*< private >*/ 58 gpointer alignment_dummy1; 59 glong alignment_dummy2; 60 gdouble alignment_dummy3; 61 } GBSearchArray; 62 63 64 /* --- public API --- */ 65 static inline GBSearchArray* g_bsearch_array_create (const GBSearchConfig *bconfig); 66 static inline gpointer g_bsearch_array_get_nth (GBSearchArray *barray, 67 const GBSearchConfig *bconfig, 68 guint nth); 69 static inline guint g_bsearch_array_get_index (GBSearchArray *barray, 70 const GBSearchConfig *bconfig, 71 gconstpointer node_in_array); 72 static inline GBSearchArray* g_bsearch_array_remove (GBSearchArray *barray, 73 const GBSearchConfig *bconfig, 74 guint index_); 75 /* provide uninitialized space at index for node insertion */ 76 static inline GBSearchArray* g_bsearch_array_grow (GBSearchArray *barray, 77 const GBSearchConfig *bconfig, 78 guint index); 79 /* insert key_node into array if it does not exist, otherwise do nothing */ 80 static inline GBSearchArray* g_bsearch_array_insert (GBSearchArray *barray, 81 const GBSearchConfig *bconfig, 82 gconstpointer key_node); 83 /* insert key_node into array if it does not exist, 84 * otherwise replace the existing node's contents with key_node 85 */ 86 static inline GBSearchArray* g_bsearch_array_replace (GBSearchArray *barray, 87 const GBSearchConfig *bconfig, 88 gconstpointer key_node); 89 static inline void g_bsearch_array_free (GBSearchArray *barray, 90 const GBSearchConfig *bconfig); 91 #define g_bsearch_array_get_n_nodes(barray) (((GBSearchArray*) (barray))->n_nodes) 92 93 /* g_bsearch_array_lookup(): 94 * return NULL or exact match node 95 */ 96 #define g_bsearch_array_lookup(barray, bconfig, key_node) \ 97 g_bsearch_array_lookup_fuzzy ((barray), (bconfig), (key_node), 0) 98 99 /* g_bsearch_array_lookup_sibling(): 100 * return NULL for barray->n_nodes==0, otherwise return the 101 * exact match node, or, if there's no such node, return the 102 * node last visited, which is pretty close to an exact match 103 * (will be one off into either direction). 104 */ 105 #define g_bsearch_array_lookup_sibling(barray, bconfig, key_node) \ 106 g_bsearch_array_lookup_fuzzy ((barray), (bconfig), (key_node), 1) 107 108 /* g_bsearch_array_lookup_insertion(): 109 * return NULL for barray->n_nodes==0 or exact match, otherwise 110 * return the node where key_node should be inserted (may be one 111 * after end, i.e. g_bsearch_array_get_index(result) <= barray->n_nodes). 112 */ 113 #define g_bsearch_array_lookup_insertion(barray, bconfig, key_node) \ 114 g_bsearch_array_lookup_fuzzy ((barray), (bconfig), (key_node), 2) 115 116 117 /* --- implementation --- */ 118 /* helper macro to cut down realloc()s */ 119 #ifdef DISABLE_MEM_POOLS 120 #define G_BSEARCH_UPPER_POWER2(n) (n) 121 #else /* !DISABLE_MEM_POOLS */ 122 #define G_BSEARCH_UPPER_POWER2(n) ((n) ? 1 << g_bit_storage ((n) - 1) : 0) 123 #endif /* !DISABLE_MEM_POOLS */ 124 #define G_BSEARCH_ARRAY_NODES(barray) (((guint8*) (barray)) + sizeof (GBSearchArray)) 125 static inline GBSearchArray* 126 g_bsearch_array_create (const GBSearchConfig *bconfig) 127 { 128 GBSearchArray *barray; 129 guint size; 130 131 g_return_val_if_fail (bconfig != NULL, NULL); 132 133 size = sizeof (GBSearchArray) + bconfig->sizeof_node; 134 if (bconfig->flags & G_BSEARCH_ARRAY_ALIGN_POWER2) 135 size = G_BSEARCH_UPPER_POWER2 (size); 136 barray = (GBSearchArray *) g_realloc (NULL, size); 137 memset (barray, 0, sizeof (GBSearchArray)); 138 139 return barray; 140 } 141 static inline gpointer 142 g_bsearch_array_lookup_fuzzy (GBSearchArray *barray, 143 const GBSearchConfig *bconfig, 144 gconstpointer key_node, 145 const guint sibling_or_after); 146 static inline gpointer 147 g_bsearch_array_lookup_fuzzy (GBSearchArray *barray, 148 const GBSearchConfig *bconfig, 149 gconstpointer key_node, 150 const guint sibling_or_after) 151 { 152 GBSearchCompareFunc cmp_nodes = bconfig->cmp_nodes; 153 guint8 *check = NULL, *nodes = G_BSEARCH_ARRAY_NODES (barray); 154 guint n_nodes = barray->n_nodes, offs = 0; 155 guint sizeof_node = bconfig->sizeof_node; 156 gint cmp = 0; 157 158 while (offs < n_nodes) 159 { 160 guint i = (offs + n_nodes) >> 1; 161 162 check = nodes + i * sizeof_node; 163 cmp = cmp_nodes (key_node, check); 164 if (cmp == 0) 165 return sibling_or_after > 1 ? NULL : check; 166 else if (cmp < 0) 167 n_nodes = i; 168 else /* (cmp > 0) */ 169 offs = i + 1; 170 } 171 172 /* check is last mismatch, cmp > 0 indicates greater key */ 173 return G_LIKELY (!sibling_or_after) ? NULL : (sibling_or_after > 1 && cmp > 0) ? check + sizeof_node : check; 174 } 175 static inline gpointer 176 g_bsearch_array_get_nth (GBSearchArray *barray, 177 const GBSearchConfig *bconfig, 178 guint nth) 179 { 180 return (G_LIKELY (nth < barray->n_nodes) ? 181 G_BSEARCH_ARRAY_NODES (barray) + nth * bconfig->sizeof_node : 182 NULL); 183 } 184 static inline guint 185 g_bsearch_array_get_index (GBSearchArray *barray, 186 const GBSearchConfig *bconfig, 187 gconstpointer node_in_array) 188 { 189 guint distance = ((guint8*) node_in_array) - G_BSEARCH_ARRAY_NODES (barray); 190 191 g_return_val_if_fail (node_in_array != NULL, barray->n_nodes); 192 193 distance /= bconfig->sizeof_node; 194 195 return MIN (distance, barray->n_nodes + 1); /* may return one after end */ 196 } 197 static inline GBSearchArray* 198 g_bsearch_array_grow (GBSearchArray *barray, 199 const GBSearchConfig *bconfig, 200 guint index_) 201 { 202 guint old_size = barray->n_nodes * bconfig->sizeof_node; 203 guint new_size = old_size + bconfig->sizeof_node; 204 guint8 *node; 205 206 g_return_val_if_fail (index_ <= barray->n_nodes, NULL); 207 208 if (G_UNLIKELY (bconfig->flags & G_BSEARCH_ARRAY_ALIGN_POWER2)) 209 { 210 new_size = G_BSEARCH_UPPER_POWER2 (sizeof (GBSearchArray) + new_size); 211 old_size = G_BSEARCH_UPPER_POWER2 (sizeof (GBSearchArray) + old_size); 212 if (old_size != new_size) 213 barray = (GBSearchArray *) g_realloc (barray, new_size); 214 } 215 else 216 barray = (GBSearchArray *) g_realloc (barray, sizeof (GBSearchArray) + new_size); 217 node = G_BSEARCH_ARRAY_NODES (barray) + index_ * bconfig->sizeof_node; 218 g_memmove (node + bconfig->sizeof_node, node, (barray->n_nodes - index_) * bconfig->sizeof_node); 219 barray->n_nodes += 1; 220 return barray; 221 } 222 static inline GBSearchArray* 223 g_bsearch_array_insert (GBSearchArray *barray, 224 const GBSearchConfig *bconfig, 225 gconstpointer key_node) 226 { 227 guint8 *node; 228 229 if (G_UNLIKELY (!barray->n_nodes)) 230 { 231 barray = g_bsearch_array_grow (barray, bconfig, 0); 232 node = G_BSEARCH_ARRAY_NODES (barray); 233 } 234 else 235 { 236 node = (guint8 *) g_bsearch_array_lookup_insertion (barray, bconfig, key_node); 237 if (G_LIKELY (node)) 238 { 239 guint index_ = g_bsearch_array_get_index (barray, bconfig, node); 240 241 /* grow and insert */ 242 barray = g_bsearch_array_grow (barray, bconfig, index_); 243 node = G_BSEARCH_ARRAY_NODES (barray) + index_ * bconfig->sizeof_node; 244 } 245 else /* no insertion needed, node already there */ 246 return barray; 247 } 248 memcpy (node, key_node, bconfig->sizeof_node); 249 return barray; 250 } 251 static inline GBSearchArray* 252 g_bsearch_array_replace (GBSearchArray *barray, 253 const GBSearchConfig *bconfig, 254 gconstpointer key_node) 255 { 256 guint8 *node = (guint8 *) g_bsearch_array_lookup (barray, bconfig, key_node); 257 if (G_LIKELY (node)) /* expected path */ 258 memcpy (node, key_node, bconfig->sizeof_node); 259 else /* revert to insertion */ 260 barray = g_bsearch_array_insert (barray, bconfig, key_node); 261 return barray; 262 } 263 static inline GBSearchArray* 264 g_bsearch_array_remove (GBSearchArray *barray, 265 const GBSearchConfig *bconfig, 266 guint index_) 267 { 268 guint8 *node; 269 270 g_return_val_if_fail (index_ < barray->n_nodes, NULL); 271 272 barray->n_nodes -= 1; 273 node = G_BSEARCH_ARRAY_NODES (barray) + index_ * bconfig->sizeof_node; 274 g_memmove (node, node + bconfig->sizeof_node, (barray->n_nodes - index_) * bconfig->sizeof_node); 275 if (G_UNLIKELY (bconfig->flags & G_BSEARCH_ARRAY_AUTO_SHRINK)) 276 { 277 guint new_size = barray->n_nodes * bconfig->sizeof_node; 278 guint old_size = new_size + bconfig->sizeof_node; 279 280 if (G_UNLIKELY (bconfig->flags & G_BSEARCH_ARRAY_ALIGN_POWER2)) 281 { 282 new_size = G_BSEARCH_UPPER_POWER2 (sizeof (GBSearchArray) + new_size); 283 old_size = G_BSEARCH_UPPER_POWER2 (sizeof (GBSearchArray) + old_size); 284 if (old_size != new_size) 285 barray = (GBSearchArray *) g_realloc (barray, new_size); 286 } 287 else 288 barray = (GBSearchArray *) g_realloc (barray, sizeof (GBSearchArray) + new_size); 289 } 290 return barray; 291 } 292 static inline void 293 g_bsearch_array_free (GBSearchArray *barray, 294 const GBSearchConfig *bconfig) 295 { 296 g_return_if_fail (barray != NULL); 297 298 g_free (barray); 299 } 300 301 G_END_DECLS /* c++ guards */ 302 303 #endif /* !__G_BSEARCH_ARRAY_H__ */ 304
