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