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