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