1 #ifdef HAVE_CONFIG_H 2 #include "config.h" 3 #endif 4 5 #ifdef HAVE_OHASH 6 7 int dummy; 8 9 #else 10 11 /* $OpenBSD: ohash_int.h,v 1.3 2006/01/16 15:52:25 espie Exp $ */ 12 13 #include <stddef.h> 14 #include <stdint.h> 15 #include <stdlib.h> 16 #include <string.h> 17 #include "compat_ohash.h" 18 19 struct _ohash_record { 20 uint32_t hv; 21 const char *p; 22 }; 23 24 #define DELETED ((const char *)h) 25 #define NONE (h->size) 26 27 /* Don't bother changing the hash table if the change is small enough. */ 28 #define MINSIZE (1UL << 4) 29 #define MINDELETED 4 30 /* $OpenBSD: ohash_create_entry.c,v 1.2 2004/06/22 20:00:16 espie Exp $ */ 31 /* ex:ts=8 sw=4: 32 */ 33 34 /* Copyright (c) 1999, 2004 Marc Espie <espie@openbsd.org> 35 * 36 * Permission to use, copy, modify, and distribute this software for any 37 * purpose with or without fee is hereby granted, provided that the above 38 * copyright notice and this permission notice appear in all copies. 39 * 40 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES 41 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 42 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR 43 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 44 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN 45 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF 46 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 47 */ 48 49 /* This handles the common case of variable length keys, where the 50 * key is stored at the end of the record. 51 */ 52 void * 53 ohash_create_entry(struct ohash_info *i, const char *start, const char **end) 54 { 55 char *p; 56 57 if (!*end) 58 *end = start + strlen(start); 59 p = (i->alloc)(i->key_offset + (*end - start) + 1, i->data); 60 if (p) { 61 memcpy(p+i->key_offset, start, *end-start); 62 p[i->key_offset + (*end - start)] = '\0'; 63 } 64 return (void *)p; 65 } 66 67 /* hash_delete only frees the hash structure. Use hash_first/hash_next 68 * to free entries as well. */ 69 void 70 ohash_delete(struct ohash *h) 71 { 72 (h->info.hfree)(h->t, sizeof(struct _ohash_record) * h->size, 73 h->info.data); 74 #ifndef NDEBUG 75 h->t = NULL; 76 #endif 77 } 78 79 static void ohash_resize(struct ohash *); 80 81 static void 82 ohash_resize(struct ohash *h) 83 { 84 struct _ohash_record *n; 85 unsigned int ns, j; 86 unsigned int i, incr; 87 88 if (4 * h->deleted < h->total) 89 ns = h->size << 1; 90 else if (3 * h->deleted > 2 * h->total) 91 ns = h->size >> 1; 92 else 93 ns = h->size; 94 if (ns < MINSIZE) 95 ns = MINSIZE; 96 #ifdef STATS_HASH 97 STAT_HASH_EXPAND++; 98 STAT_HASH_SIZE += ns - h->size; 99 #endif 100 n = (h->info.halloc)(sizeof(struct _ohash_record) * ns, h->info.data); 101 if (!n) 102 return; 103 104 for (j = 0; j < h->size; j++) { 105 if (h->t[j].p != NULL && h->t[j].p != DELETED) { 106 i = h->t[j].hv % ns; 107 incr = ((h->t[j].hv % (ns - 2)) & ~1) + 1; 108 while (n[i].p != NULL) { 109 i += incr; 110 if (i >= ns) 111 i -= ns; 112 } 113 n[i].hv = h->t[j].hv; 114 n[i].p = h->t[j].p; 115 } 116 } 117 (h->info.hfree)(h->t, sizeof(struct _ohash_record) * h->size, 118 h->info.data); 119 h->t = n; 120 h->size = ns; 121 h->total -= h->deleted; 122 h->deleted = 0; 123 } 124 125 void * 126 ohash_remove(struct ohash *h, unsigned int i) 127 { 128 void *result = (void *)h->t[i].p; 129 130 if (result == NULL || result == DELETED) 131 return NULL; 132 133 #ifdef STATS_HASH 134 STAT_HASH_ENTRIES--; 135 #endif 136 h->t[i].p = DELETED; 137 h->deleted++; 138 if (h->deleted >= MINDELETED && 4 * h->deleted > h->total) 139 ohash_resize(h); 140 return result; 141 } 142 143 void * 144 ohash_find(struct ohash *h, unsigned int i) 145 { 146 if (h->t[i].p == DELETED) 147 return NULL; 148 else 149 return (void *)h->t[i].p; 150 } 151 152 void * 153 ohash_insert(struct ohash *h, unsigned int i, void *p) 154 { 155 #ifdef STATS_HASH 156 STAT_HASH_ENTRIES++; 157 #endif 158 if (h->t[i].p == DELETED) { 159 h->deleted--; 160 h->t[i].p = p; 161 } else { 162 h->t[i].p = p; 163 /* Arbitrary resize boundary. Tweak if not efficient enough. */ 164 if (++h->total * 4 > h->size * 3) 165 ohash_resize(h); 166 } 167 return p; 168 } 169 170 unsigned int 171 ohash_entries(struct ohash *h) 172 { 173 return h->total - h->deleted; 174 } 175 176 void * 177 ohash_first(struct ohash *h, unsigned int *pos) 178 { 179 *pos = 0; 180 return ohash_next(h, pos); 181 } 182 183 void * 184 ohash_next(struct ohash *h, unsigned int *pos) 185 { 186 for (; *pos < h->size; (*pos)++) 187 if (h->t[*pos].p != DELETED && h->t[*pos].p != NULL) 188 return (void *)h->t[(*pos)++].p; 189 return NULL; 190 } 191 192 void 193 ohash_init(struct ohash *h, unsigned int size, struct ohash_info *info) 194 { 195 h->size = 1UL << size; 196 if (h->size < MINSIZE) 197 h->size = MINSIZE; 198 #ifdef STATS_HASH 199 STAT_HASH_CREATION++; 200 STAT_HASH_SIZE += h->size; 201 #endif 202 /* Copy info so that caller may free it. */ 203 h->info.key_offset = info->key_offset; 204 h->info.halloc = info->halloc; 205 h->info.hfree = info->hfree; 206 h->info.alloc = info->alloc; 207 h->info.data = info->data; 208 h->t = (h->info.halloc)(sizeof(struct _ohash_record) * h->size, 209 h->info.data); 210 h->total = h->deleted = 0; 211 } 212 213 uint32_t 214 ohash_interval(const char *s, const char **e) 215 { 216 uint32_t k; 217 218 if (!*e) 219 *e = s + strlen(s); 220 if (s == *e) 221 k = 0; 222 else 223 k = *s++; 224 while (s != *e) 225 k = ((k << 2) | (k >> 30)) ^ *s++; 226 return k; 227 } 228 229 unsigned int 230 ohash_lookup_interval(struct ohash *h, const char *start, const char *end, 231 uint32_t hv) 232 { 233 unsigned int i, incr; 234 unsigned int empty; 235 236 #ifdef STATS_HASH 237 STAT_HASH_LOOKUP++; 238 #endif 239 empty = NONE; 240 i = hv % h->size; 241 incr = ((hv % (h->size-2)) & ~1) + 1; 242 while (h->t[i].p != NULL) { 243 #ifdef STATS_HASH 244 STAT_HASH_LENGTH++; 245 #endif 246 if (h->t[i].p == DELETED) { 247 if (empty == NONE) 248 empty = i; 249 } else if (h->t[i].hv == hv && 250 strncmp(h->t[i].p+h->info.key_offset, start, 251 end - start) == 0 && 252 (h->t[i].p+h->info.key_offset)[end-start] == '\0') { 253 if (empty != NONE) { 254 h->t[empty].hv = hv; 255 h->t[empty].p = h->t[i].p; 256 h->t[i].p = DELETED; 257 return empty; 258 } else { 259 #ifdef STATS_HASH 260 STAT_HASH_POSITIVE++; 261 #endif 262 return i; 263 } 264 } 265 i += incr; 266 if (i >= h->size) 267 i -= h->size; 268 } 269 270 /* Found an empty position. */ 271 if (empty != NONE) 272 i = empty; 273 h->t[i].hv = hv; 274 return i; 275 } 276 277 unsigned int 278 ohash_lookup_memory(struct ohash *h, const char *k, size_t size, uint32_t hv) 279 { 280 unsigned int i, incr; 281 unsigned int empty; 282 283 #ifdef STATS_HASH 284 STAT_HASH_LOOKUP++; 285 #endif 286 empty = NONE; 287 i = hv % h->size; 288 incr = ((hv % (h->size-2)) & ~1) + 1; 289 while (h->t[i].p != NULL) { 290 #ifdef STATS_HASH 291 STAT_HASH_LENGTH++; 292 #endif 293 if (h->t[i].p == DELETED) { 294 if (empty == NONE) 295 empty = i; 296 } else if (h->t[i].hv == hv && 297 memcmp(h->t[i].p+h->info.key_offset, k, size) == 0) { 298 if (empty != NONE) { 299 h->t[empty].hv = hv; 300 h->t[empty].p = h->t[i].p; 301 h->t[i].p = DELETED; 302 return empty; 303 } else { 304 #ifdef STATS_HASH 305 STAT_HASH_POSITIVE++; 306 #endif 307 } return i; 308 } 309 i += incr; 310 if (i >= h->size) 311 i -= h->size; 312 } 313 314 /* Found an empty position. */ 315 if (empty != NONE) 316 i = empty; 317 h->t[i].hv = hv; 318 return i; 319 } 320 321 unsigned int 322 ohash_qlookup(struct ohash *h, const char *s) 323 { 324 const char *e = NULL; 325 return ohash_qlookupi(h, s, &e); 326 } 327 328 unsigned int 329 ohash_qlookupi(struct ohash *h, const char *s, const char **e) 330 { 331 uint32_t hv; 332 333 hv = ohash_interval(s, e); 334 return ohash_lookup_interval(h, s, *e, hv); 335 } 336 337 #endif /*!HAVE_OHASH*/ 338