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 "main.h" 34 #include "compat_ohash.h" 35 36 struct _ohash_record { 37 uint32_t hv; 38 const char *p; 39 }; 40 41 #define DELETED ((const char *)h) 42 #define NONE (h->size) 43 44 /* Don't bother changing the hash table if the change is small enough. */ 45 #define MINSIZE (1UL << 4) 46 #define MINDELETED 4 47 48 static void ohash_resize(struct ohash *); 49 50 51 /* This handles the common case of variable length keys, where the 52 * key is stored at the end of the record. 53 */ 54 void * 55 ohash_create_entry(struct ohash_info *i, const char *start, const char **end) 56 { 57 char *p; 58 59 if (!*end) 60 *end = start + strlen(start); 61 p = (i->alloc)(i->key_offset + (*end - start) + 1, i->data); 62 if (p) { 63 memcpy(p+i->key_offset, start, *end-start); 64 p[i->key_offset + (*end - start)] = '\0'; 65 } 66 return (void *)p; 67 } 68 69 /* hash_delete only frees the hash structure. Use hash_first/hash_next 70 * to free entries as well. */ 71 void 72 ohash_delete(struct ohash *h) 73 { 74 (h->info.free)(h->t, h->info.data); 75 #ifndef NDEBUG 76 h->t = NULL; 77 #endif 78 } 79 80 static void 81 ohash_resize(struct ohash *h) 82 { 83 struct _ohash_record *n; 84 size_t ns; 85 unsigned int j; 86 unsigned int i, incr; 87 88 if (4 * h->deleted < h->total) { 89 if (h->size >= (UINT_MAX >> 1U)) 90 ns = UINT_MAX; 91 else 92 ns = h->size << 1U; 93 } else if (3 * h->deleted > 2 * h->total) 94 ns = h->size >> 1U; 95 else 96 ns = h->size; 97 if (ns < MINSIZE) 98 ns = MINSIZE; 99 #ifdef STATS_HASH 100 STAT_HASH_EXPAND++; 101 STAT_HASH_SIZE += ns - h->size; 102 #endif 103 104 n = (h->info.calloc)(ns, sizeof(struct _ohash_record), h->info.data); 105 if (!n) 106 return; 107 108 for (j = 0; j < h->size; j++) { 109 if (h->t[j].p != NULL && h->t[j].p != DELETED) { 110 i = h->t[j].hv % ns; 111 incr = ((h->t[j].hv % (ns - 2)) & ~1) + 1; 112 while (n[i].p != NULL) { 113 i += incr; 114 if (i >= ns) 115 i -= ns; 116 } 117 n[i].hv = h->t[j].hv; 118 n[i].p = h->t[j].p; 119 } 120 } 121 (h->info.free)(h->t, h->info.data); 122 h->t = n; 123 h->size = ns; 124 h->total -= h->deleted; 125 h->deleted = 0; 126 } 127 128 void * 129 ohash_remove(struct ohash *h, unsigned int i) 130 { 131 void *result = __UNCONST(h->t[i].p); 132 133 if (result == NULL || result == DELETED) 134 return NULL; 135 136 #ifdef STATS_HASH 137 STAT_HASH_ENTRIES--; 138 #endif 139 h->t[i].p = DELETED; 140 h->deleted++; 141 if (h->deleted >= MINDELETED && 4 * h->deleted > h->total) 142 ohash_resize(h); 143 return result; 144 } 145 146 void * 147 ohash_find(struct ohash *h, unsigned int i) 148 { 149 if (h->t[i].p == DELETED) 150 return NULL; 151 else 152 return __UNCONST(h->t[i].p); 153 } 154 155 void * 156 ohash_insert(struct ohash *h, unsigned int i, void *p) 157 { 158 #ifdef STATS_HASH 159 STAT_HASH_ENTRIES++; 160 #endif 161 if (h->t[i].p == DELETED) { 162 h->deleted--; 163 h->t[i].p = p; 164 } else { 165 h->t[i].p = p; 166 /* Arbitrary resize boundary. Tweak if not efficient enough. */ 167 if (++h->total * 4 > h->size * 3) 168 ohash_resize(h); 169 } 170 return p; 171 } 172 173 unsigned int 174 ohash_entries(struct ohash *h) 175 { 176 return h->total - h->deleted; 177 } 178 179 void * 180 ohash_first(struct ohash *h, unsigned int *pos) 181 { 182 *pos = 0; 183 return ohash_next(h, pos); 184 } 185 186 void * 187 ohash_next(struct ohash *h, unsigned int *pos) 188 { 189 for (; *pos < h->size; (*pos)++) 190 if (h->t[*pos].p != DELETED && h->t[*pos].p != NULL) 191 return __UNCONST(h->t[(*pos)++].p); 192 return NULL; 193 } 194 195 void 196 ohash_init(struct ohash *h, unsigned int size, struct ohash_info *info) 197 { 198 h->size = 1UL << size; 199 if (h->size < MINSIZE) 200 h->size = MINSIZE; 201 #ifdef STATS_HASH 202 STAT_HASH_CREATION++; 203 STAT_HASH_SIZE += h->size; 204 #endif 205 /* Copy info so that caller may free it. */ 206 h->info.key_offset = info->key_offset; 207 h->info.calloc = info->calloc; 208 h->info.free = info->free; 209 h->info.alloc = info->alloc; 210 h->info.data = info->data; 211 h->t = (h->info.calloc)(h->size, sizeof(struct _ohash_record), 212 h->info.data); 213 h->total = h->deleted = 0; 214 } 215 216 uint32_t 217 ohash_interval(const char *s, const char **e) 218 { 219 uint32_t k; 220 221 if (!*e) 222 *e = s + strlen(s); 223 if (s == *e) 224 k = 0; 225 else 226 k = *s++; 227 while (s != *e) 228 k = ((k << 2) | (k >> 30)) ^ *s++; 229 return k; 230 } 231 232 unsigned int 233 ohash_lookup_interval(struct ohash *h, const char *start, const char *end, 234 uint32_t hv) 235 { 236 unsigned int i, incr; 237 unsigned int empty; 238 239 #ifdef STATS_HASH 240 STAT_HASH_LOOKUP++; 241 #endif 242 empty = NONE; 243 i = hv % h->size; 244 incr = ((hv % (h->size-2)) & ~1) + 1; 245 while (h->t[i].p != NULL) { 246 #ifdef STATS_HASH 247 STAT_HASH_LENGTH++; 248 #endif 249 if (h->t[i].p == DELETED) { 250 if (empty == NONE) 251 empty = i; 252 } else if (h->t[i].hv == hv && 253 strncmp(h->t[i].p+h->info.key_offset, start, 254 end - start) == 0 && 255 (h->t[i].p+h->info.key_offset)[end-start] == '\0') { 256 if (empty != NONE) { 257 h->t[empty].hv = hv; 258 h->t[empty].p = h->t[i].p; 259 h->t[i].p = DELETED; 260 return empty; 261 } else { 262 #ifdef STATS_HASH 263 STAT_HASH_POSITIVE++; 264 #endif 265 return i; 266 } 267 } 268 i += incr; 269 if (i >= h->size) 270 i -= h->size; 271 } 272 273 /* Found an empty position. */ 274 if (empty != NONE) 275 i = empty; 276 h->t[i].hv = hv; 277 return i; 278 } 279 280 unsigned int 281 ohash_lookup_memory(struct ohash *h, const char *k, size_t size, uint32_t hv) 282 { 283 unsigned int i, incr; 284 unsigned int empty; 285 286 #ifdef STATS_HASH 287 STAT_HASH_LOOKUP++; 288 #endif 289 empty = NONE; 290 i = hv % h->size; 291 incr = ((hv % (h->size-2)) & ~1) + 1; 292 while (h->t[i].p != NULL) { 293 #ifdef STATS_HASH 294 STAT_HASH_LENGTH++; 295 #endif 296 if (h->t[i].p == DELETED) { 297 if (empty == NONE) 298 empty = i; 299 } else if (h->t[i].hv == hv && 300 memcmp(h->t[i].p+h->info.key_offset, k, size) == 0) { 301 if (empty != NONE) { 302 h->t[empty].hv = hv; 303 h->t[empty].p = h->t[i].p; 304 h->t[i].p = DELETED; 305 return empty; 306 } else { 307 #ifdef STATS_HASH 308 STAT_HASH_POSITIVE++; 309 #endif 310 } return i; 311 } 312 i += incr; 313 if (i >= h->size) 314 i -= h->size; 315 } 316 317 /* Found an empty position. */ 318 if (empty != NONE) 319 i = empty; 320 h->t[i].hv = hv; 321 return i; 322 } 323 324 unsigned int 325 ohash_qlookup(struct ohash *h, const char *s) 326 { 327 const char *e = NULL; 328 return ohash_qlookupi(h, s, &e); 329 } 330 331 unsigned int 332 ohash_qlookupi(struct ohash *h, const char *s, const char **e) 333 { 334 uint32_t hv; 335 336 hv = ohash_interval(s, e); 337 return ohash_lookup_interval(h, s, *e, hv); 338 } 339 340 #endif /*!HAVE_OHASH*/ 341