1269162Sbapt/* $OpenBSD: src/lib/libutil/ohash.c,v 1.1 2014/06/02 18:52:03 deraadt Exp $ */ 2269162Sbapt 3269162Sbapt/* Copyright (c) 1999, 2004 Marc Espie <espie@openbsd.org> 4269162Sbapt * 5269162Sbapt * Permission to use, copy, modify, and distribute this software for any 6269162Sbapt * purpose with or without fee is hereby granted, provided that the above 7269162Sbapt * copyright notice and this permission notice appear in all copies. 8269162Sbapt * 9269162Sbapt * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES 10269162Sbapt * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 11269162Sbapt * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR 12269162Sbapt * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 13269162Sbapt * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN 14269162Sbapt * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF 15269162Sbapt * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 16269162Sbapt */ 17269162Sbapt 18269162Sbapt#include <sys/cdefs.h> 19269162Sbapt__FBSDID("$FreeBSD: releng/11.0/lib/libopenbsd/ohash.c 269162 2014-07-27 22:54:13Z bapt $"); 20269162Sbapt 21269162Sbapt#include <stddef.h> 22269162Sbapt#include <stdint.h> 23269162Sbapt#include <stdlib.h> 24269162Sbapt#include <string.h> 25269162Sbapt#include <limits.h> 26269162Sbapt#include "ohash.h" 27269162Sbapt 28269162Sbaptstruct _ohash_record { 29269162Sbapt uint32_t hv; 30269162Sbapt const char *p; 31269162Sbapt}; 32269162Sbapt 33269162Sbapt#define DELETED ((const char *)h) 34269162Sbapt#define NONE (h->size) 35269162Sbapt 36269162Sbapt/* Don't bother changing the hash table if the change is small enough. */ 37269162Sbapt#define MINSIZE (1UL << 4) 38269162Sbapt#define MINDELETED 4 39269162Sbapt 40269162Sbaptstatic void ohash_resize(struct ohash *); 41269162Sbapt 42269162Sbapt 43269162Sbapt/* This handles the common case of variable length keys, where the 44269162Sbapt * key is stored at the end of the record. 45269162Sbapt */ 46269162Sbaptvoid * 47269162Sbaptohash_create_entry(struct ohash_info *i, const char *start, const char **end) 48269162Sbapt{ 49269162Sbapt char *p; 50269162Sbapt 51269162Sbapt if (!*end) 52269162Sbapt *end = start + strlen(start); 53269162Sbapt p = (i->alloc)(i->key_offset + (*end - start) + 1, i->data); 54269162Sbapt if (p) { 55269162Sbapt memcpy(p+i->key_offset, start, *end-start); 56269162Sbapt p[i->key_offset + (*end - start)] = '\0'; 57269162Sbapt } 58269162Sbapt return (void *)p; 59269162Sbapt} 60269162Sbapt 61269162Sbapt/* hash_delete only frees the hash structure. Use hash_first/hash_next 62269162Sbapt * to free entries as well. */ 63269162Sbaptvoid 64269162Sbaptohash_delete(struct ohash *h) 65269162Sbapt{ 66269162Sbapt (h->info.free)(h->t, h->info.data); 67269162Sbapt#ifndef NDEBUG 68269162Sbapt h->t = NULL; 69269162Sbapt#endif 70269162Sbapt} 71269162Sbapt 72269162Sbaptstatic void 73269162Sbaptohash_resize(struct ohash *h) 74269162Sbapt{ 75269162Sbapt struct _ohash_record *n; 76269162Sbapt size_t ns; 77269162Sbapt unsigned int j; 78269162Sbapt unsigned int i, incr; 79269162Sbapt 80269162Sbapt if (4 * h->deleted < h->total) { 81269162Sbapt if (h->size >= (UINT_MAX >> 1U)) 82269162Sbapt ns = UINT_MAX; 83269162Sbapt else 84269162Sbapt ns = h->size << 1U; 85269162Sbapt } else if (3 * h->deleted > 2 * h->total) 86269162Sbapt ns = h->size >> 1U; 87269162Sbapt else 88269162Sbapt ns = h->size; 89269162Sbapt if (ns < MINSIZE) 90269162Sbapt ns = MINSIZE; 91269162Sbapt#ifdef STATS_HASH 92269162Sbapt STAT_HASH_EXPAND++; 93269162Sbapt STAT_HASH_SIZE += ns - h->size; 94269162Sbapt#endif 95269162Sbapt 96269162Sbapt n = (h->info.calloc)(ns, sizeof(struct _ohash_record), h->info.data); 97269162Sbapt if (!n) 98269162Sbapt return; 99269162Sbapt 100269162Sbapt for (j = 0; j < h->size; j++) { 101269162Sbapt if (h->t[j].p != NULL && h->t[j].p != DELETED) { 102269162Sbapt i = h->t[j].hv % ns; 103269162Sbapt incr = ((h->t[j].hv % (ns - 2)) & ~1) + 1; 104269162Sbapt while (n[i].p != NULL) { 105269162Sbapt i += incr; 106269162Sbapt if (i >= ns) 107269162Sbapt i -= ns; 108269162Sbapt } 109269162Sbapt n[i].hv = h->t[j].hv; 110269162Sbapt n[i].p = h->t[j].p; 111269162Sbapt } 112269162Sbapt } 113269162Sbapt (h->info.free)(h->t, h->info.data); 114269162Sbapt h->t = n; 115269162Sbapt h->size = ns; 116269162Sbapt h->total -= h->deleted; 117269162Sbapt h->deleted = 0; 118269162Sbapt} 119269162Sbapt 120269162Sbaptvoid * 121269162Sbaptohash_remove(struct ohash *h, unsigned int i) 122269162Sbapt{ 123269162Sbapt void *result = (void *)h->t[i].p; 124269162Sbapt 125269162Sbapt if (result == NULL || result == DELETED) 126269162Sbapt return NULL; 127269162Sbapt 128269162Sbapt#ifdef STATS_HASH 129269162Sbapt STAT_HASH_ENTRIES--; 130269162Sbapt#endif 131269162Sbapt h->t[i].p = DELETED; 132269162Sbapt h->deleted++; 133269162Sbapt if (h->deleted >= MINDELETED && 4 * h->deleted > h->total) 134269162Sbapt ohash_resize(h); 135269162Sbapt return result; 136269162Sbapt} 137269162Sbapt 138269162Sbaptvoid * 139269162Sbaptohash_find(struct ohash *h, unsigned int i) 140269162Sbapt{ 141269162Sbapt if (h->t[i].p == DELETED) 142269162Sbapt return NULL; 143269162Sbapt else 144269162Sbapt return (void *)h->t[i].p; 145269162Sbapt} 146269162Sbapt 147269162Sbaptvoid * 148269162Sbaptohash_insert(struct ohash *h, unsigned int i, void *p) 149269162Sbapt{ 150269162Sbapt#ifdef STATS_HASH 151269162Sbapt STAT_HASH_ENTRIES++; 152269162Sbapt#endif 153269162Sbapt if (h->t[i].p == DELETED) { 154269162Sbapt h->deleted--; 155269162Sbapt h->t[i].p = p; 156269162Sbapt } else { 157269162Sbapt h->t[i].p = p; 158269162Sbapt /* Arbitrary resize boundary. Tweak if not efficient enough. */ 159269162Sbapt if (++h->total * 4 > h->size * 3) 160269162Sbapt ohash_resize(h); 161269162Sbapt } 162269162Sbapt return p; 163269162Sbapt} 164269162Sbapt 165269162Sbaptunsigned int 166269162Sbaptohash_entries(struct ohash *h) 167269162Sbapt{ 168269162Sbapt return h->total - h->deleted; 169269162Sbapt} 170269162Sbapt 171269162Sbaptvoid * 172269162Sbaptohash_first(struct ohash *h, unsigned int *pos) 173269162Sbapt{ 174269162Sbapt *pos = 0; 175269162Sbapt return ohash_next(h, pos); 176269162Sbapt} 177269162Sbapt 178269162Sbaptvoid * 179269162Sbaptohash_next(struct ohash *h, unsigned int *pos) 180269162Sbapt{ 181269162Sbapt for (; *pos < h->size; (*pos)++) 182269162Sbapt if (h->t[*pos].p != DELETED && h->t[*pos].p != NULL) 183269162Sbapt return (void *)h->t[(*pos)++].p; 184269162Sbapt return NULL; 185269162Sbapt} 186269162Sbapt 187269162Sbaptvoid 188269162Sbaptohash_init(struct ohash *h, unsigned int size, struct ohash_info *info) 189269162Sbapt{ 190269162Sbapt h->size = 1UL << size; 191269162Sbapt if (h->size < MINSIZE) 192269162Sbapt h->size = MINSIZE; 193269162Sbapt#ifdef STATS_HASH 194269162Sbapt STAT_HASH_CREATION++; 195269162Sbapt STAT_HASH_SIZE += h->size; 196269162Sbapt#endif 197269162Sbapt /* Copy info so that caller may free it. */ 198269162Sbapt h->info.key_offset = info->key_offset; 199269162Sbapt h->info.calloc = info->calloc; 200269162Sbapt h->info.free = info->free; 201269162Sbapt h->info.alloc = info->alloc; 202269162Sbapt h->info.data = info->data; 203269162Sbapt h->t = (h->info.calloc)(h->size, sizeof(struct _ohash_record), 204269162Sbapt h->info.data); 205269162Sbapt h->total = h->deleted = 0; 206269162Sbapt} 207269162Sbapt 208269162Sbaptuint32_t 209269162Sbaptohash_interval(const char *s, const char **e) 210269162Sbapt{ 211269162Sbapt uint32_t k; 212269162Sbapt 213269162Sbapt if (!*e) 214269162Sbapt *e = s + strlen(s); 215269162Sbapt if (s == *e) 216269162Sbapt k = 0; 217269162Sbapt else 218269162Sbapt k = *s++; 219269162Sbapt while (s != *e) 220269162Sbapt k = ((k << 2) | (k >> 30)) ^ *s++; 221269162Sbapt return k; 222269162Sbapt} 223269162Sbapt 224269162Sbaptunsigned int 225269162Sbaptohash_lookup_interval(struct ohash *h, const char *start, const char *end, 226269162Sbapt uint32_t hv) 227269162Sbapt{ 228269162Sbapt unsigned int i, incr; 229269162Sbapt unsigned int empty; 230269162Sbapt 231269162Sbapt#ifdef STATS_HASH 232269162Sbapt STAT_HASH_LOOKUP++; 233269162Sbapt#endif 234269162Sbapt empty = NONE; 235269162Sbapt i = hv % h->size; 236269162Sbapt incr = ((hv % (h->size-2)) & ~1) + 1; 237269162Sbapt while (h->t[i].p != NULL) { 238269162Sbapt#ifdef STATS_HASH 239269162Sbapt STAT_HASH_LENGTH++; 240269162Sbapt#endif 241269162Sbapt if (h->t[i].p == DELETED) { 242269162Sbapt if (empty == NONE) 243269162Sbapt empty = i; 244269162Sbapt } else if (h->t[i].hv == hv && 245269162Sbapt strncmp(h->t[i].p+h->info.key_offset, start, 246269162Sbapt end - start) == 0 && 247269162Sbapt (h->t[i].p+h->info.key_offset)[end-start] == '\0') { 248269162Sbapt if (empty != NONE) { 249269162Sbapt h->t[empty].hv = hv; 250269162Sbapt h->t[empty].p = h->t[i].p; 251269162Sbapt h->t[i].p = DELETED; 252269162Sbapt return empty; 253269162Sbapt } else { 254269162Sbapt#ifdef STATS_HASH 255269162Sbapt STAT_HASH_POSITIVE++; 256269162Sbapt#endif 257269162Sbapt return i; 258269162Sbapt } 259269162Sbapt } 260269162Sbapt i += incr; 261269162Sbapt if (i >= h->size) 262269162Sbapt i -= h->size; 263269162Sbapt } 264269162Sbapt 265269162Sbapt /* Found an empty position. */ 266269162Sbapt if (empty != NONE) 267269162Sbapt i = empty; 268269162Sbapt h->t[i].hv = hv; 269269162Sbapt return i; 270269162Sbapt} 271269162Sbapt 272269162Sbaptunsigned int 273269162Sbaptohash_lookup_memory(struct ohash *h, const char *k, size_t size, uint32_t hv) 274269162Sbapt{ 275269162Sbapt unsigned int i, incr; 276269162Sbapt unsigned int empty; 277269162Sbapt 278269162Sbapt#ifdef STATS_HASH 279269162Sbapt STAT_HASH_LOOKUP++; 280269162Sbapt#endif 281269162Sbapt empty = NONE; 282269162Sbapt i = hv % h->size; 283269162Sbapt incr = ((hv % (h->size-2)) & ~1) + 1; 284269162Sbapt while (h->t[i].p != NULL) { 285269162Sbapt#ifdef STATS_HASH 286269162Sbapt STAT_HASH_LENGTH++; 287269162Sbapt#endif 288269162Sbapt if (h->t[i].p == DELETED) { 289269162Sbapt if (empty == NONE) 290269162Sbapt empty = i; 291269162Sbapt } else if (h->t[i].hv == hv && 292269162Sbapt memcmp(h->t[i].p+h->info.key_offset, k, size) == 0) { 293269162Sbapt if (empty != NONE) { 294269162Sbapt h->t[empty].hv = hv; 295269162Sbapt h->t[empty].p = h->t[i].p; 296269162Sbapt h->t[i].p = DELETED; 297269162Sbapt return empty; 298269162Sbapt } else { 299269162Sbapt#ifdef STATS_HASH 300269162Sbapt STAT_HASH_POSITIVE++; 301269162Sbapt#endif 302269162Sbapt } return i; 303269162Sbapt } 304269162Sbapt i += incr; 305269162Sbapt if (i >= h->size) 306269162Sbapt i -= h->size; 307269162Sbapt } 308269162Sbapt 309269162Sbapt /* Found an empty position. */ 310269162Sbapt if (empty != NONE) 311269162Sbapt i = empty; 312269162Sbapt h->t[i].hv = hv; 313269162Sbapt return i; 314269162Sbapt} 315269162Sbapt 316269162Sbaptunsigned int 317269162Sbaptohash_qlookup(struct ohash *h, const char *s) 318269162Sbapt{ 319269162Sbapt const char *e = NULL; 320269162Sbapt return ohash_qlookupi(h, s, &e); 321269162Sbapt} 322269162Sbapt 323269162Sbaptunsigned int 324269162Sbaptohash_qlookupi(struct ohash *h, const char *s, const char **e) 325269162Sbapt{ 326269162Sbapt uint32_t hv; 327269162Sbapt 328269162Sbapt hv = ohash_interval(s, e); 329269162Sbapt return ohash_lookup_interval(h, s, *e, hv); 330269162Sbapt} 331