1 /* $OpenBSD: src/lib/libutil/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 <sys/cdefs.h> 19 __FBSDID("$FreeBSD$"); 20 21 #include <stddef.h> 22 #include <stdint.h> 23 #include <stdlib.h> 24 #include <string.h> 25 #include <limits.h> 26 #include "ohash.h" 27 28 struct _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 40 static 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 */ 46 void * 47 ohash_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. */ 63 void 64 ohash_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 72 static void 73 ohash_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 120 void * 121 ohash_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 138 void * 139 ohash_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 147 void * 148 ohash_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 165 unsigned int 166 ohash_entries(struct ohash *h) 167 { 168 return h->total - h->deleted; 169 } 170 171 void * 172 ohash_first(struct ohash *h, unsigned int *pos) 173 { 174 *pos = 0; 175 return ohash_next(h, pos); 176 } 177 178 void * 179 ohash_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 187 void 188 ohash_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 208 uint32_t 209 ohash_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 224 unsigned int 225 ohash_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 272 unsigned int 273 ohash_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 316 unsigned int 317 ohash_qlookup(struct ohash *h, const char *s) 318 { 319 const char *e = NULL; 320 return ohash_qlookupi(h, s, &e); 321 } 322 323 unsigned int 324 ohash_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