1#include "config.h" 2 3#if HAVE_OHASH 4 5int 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 36struct _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 48static 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 */ 54void * 55ohash_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. */ 71void 72ohash_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 80static void 81ohash_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 128void * 129ohash_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 146void * 147ohash_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 155void * 156ohash_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 173unsigned int 174ohash_entries(struct ohash *h) 175{ 176 return h->total - h->deleted; 177} 178 179void * 180ohash_first(struct ohash *h, unsigned int *pos) 181{ 182 *pos = 0; 183 return ohash_next(h, pos); 184} 185 186void * 187ohash_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 195void 196ohash_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 216uint32_t 217ohash_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 232unsigned int 233ohash_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 280unsigned int 281ohash_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 324unsigned int 325ohash_qlookup(struct ohash *h, const char *s) 326{ 327 const char *e = NULL; 328 return ohash_qlookupi(h, s, &e); 329} 330 331unsigned int 332ohash_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