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