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 #include <stddef.h> 20 #include <stdint.h> 21 #include <stdlib.h> 22 #include <string.h> 23 #include <limits.h> 24 #include "ohash.h" 25 26 struct _ohash_record { 27 uint32_t hv; 28 const char *p; 29 }; 30 31 #define DELETED ((const char *)h) 32 #define NONE (h->size) 33 34 /* Don't bother changing the hash table if the change is small enough. */ 35 #define MINSIZE (1UL << 4) 36 #define MINDELETED 4 37 38 static void ohash_resize(struct ohash *); 39 40 41 /* This handles the common case of variable length keys, where the 42 * key is stored at the end of the record. 43 */ 44 void * 45 ohash_create_entry(struct ohash_info *i, const char *start, const char **end) 46 { 47 char *p; 48 49 if (!*end) 50 *end = start + strlen(start); 51 p = (i->alloc)(i->key_offset + (*end - start) + 1, i->data); 52 if (p) { 53 memcpy(p+i->key_offset, start, *end-start); 54 p[i->key_offset + (*end - start)] = '\0'; 55 } 56 return (void *)p; 57 } 58 59 /* hash_delete only frees the hash structure. Use hash_first/hash_next 60 * to free entries as well. */ 61 void 62 ohash_delete(struct ohash *h) 63 { 64 (h->info.free)(h->t, h->info.data); 65 #ifndef NDEBUG 66 h->t = NULL; 67 #endif 68 } 69 70 static void 71 ohash_resize(struct ohash *h) 72 { 73 struct _ohash_record *n; 74 size_t ns; 75 unsigned int j; 76 unsigned int i, incr; 77 78 if (4 * h->deleted < h->total) { 79 if (h->size >= (UINT_MAX >> 1U)) 80 ns = UINT_MAX; 81 else 82 ns = h->size << 1U; 83 } else if (3 * h->deleted > 2 * h->total) 84 ns = h->size >> 1U; 85 else 86 ns = h->size; 87 if (ns < MINSIZE) 88 ns = MINSIZE; 89 #ifdef STATS_HASH 90 STAT_HASH_EXPAND++; 91 STAT_HASH_SIZE += ns - h->size; 92 #endif 93 94 n = (h->info.calloc)(ns, sizeof(struct _ohash_record), h->info.data); 95 if (!n) 96 return; 97 98 for (j = 0; j < h->size; j++) { 99 if (h->t[j].p != NULL && h->t[j].p != DELETED) { 100 i = h->t[j].hv % ns; 101 incr = ((h->t[j].hv % (ns - 2)) & ~1) + 1; 102 while (n[i].p != NULL) { 103 i += incr; 104 if (i >= ns) 105 i -= ns; 106 } 107 n[i].hv = h->t[j].hv; 108 n[i].p = h->t[j].p; 109 } 110 } 111 (h->info.free)(h->t, h->info.data); 112 h->t = n; 113 h->size = ns; 114 h->total -= h->deleted; 115 h->deleted = 0; 116 } 117 118 void * 119 ohash_remove(struct ohash *h, unsigned int i) 120 { 121 void *result = (void *)h->t[i].p; 122 123 if (result == NULL || result == DELETED) 124 return NULL; 125 126 #ifdef STATS_HASH 127 STAT_HASH_ENTRIES--; 128 #endif 129 h->t[i].p = DELETED; 130 h->deleted++; 131 if (h->deleted >= MINDELETED && 4 * h->deleted > h->total) 132 ohash_resize(h); 133 return result; 134 } 135 136 void * 137 ohash_find(struct ohash *h, unsigned int i) 138 { 139 if (h->t[i].p == DELETED) 140 return NULL; 141 else 142 return (void *)h->t[i].p; 143 } 144 145 void * 146 ohash_insert(struct ohash *h, unsigned int i, void *p) 147 { 148 #ifdef STATS_HASH 149 STAT_HASH_ENTRIES++; 150 #endif 151 if (h->t[i].p == DELETED) { 152 h->deleted--; 153 h->t[i].p = p; 154 } else { 155 h->t[i].p = p; 156 /* Arbitrary resize boundary. Tweak if not efficient enough. */ 157 if (++h->total * 4 > h->size * 3) 158 ohash_resize(h); 159 } 160 return p; 161 } 162 163 unsigned int 164 ohash_entries(struct ohash *h) 165 { 166 return h->total - h->deleted; 167 } 168 169 void * 170 ohash_first(struct ohash *h, unsigned int *pos) 171 { 172 *pos = 0; 173 return ohash_next(h, pos); 174 } 175 176 void * 177 ohash_next(struct ohash *h, unsigned int *pos) 178 { 179 for (; *pos < h->size; (*pos)++) 180 if (h->t[*pos].p != DELETED && h->t[*pos].p != NULL) 181 return (void *)h->t[(*pos)++].p; 182 return NULL; 183 } 184 185 void 186 ohash_init(struct ohash *h, unsigned int size, struct ohash_info *info) 187 { 188 h->size = 1UL << size; 189 if (h->size < MINSIZE) 190 h->size = MINSIZE; 191 #ifdef STATS_HASH 192 STAT_HASH_CREATION++; 193 STAT_HASH_SIZE += h->size; 194 #endif 195 /* Copy info so that caller may free it. */ 196 h->info.key_offset = info->key_offset; 197 h->info.calloc = info->calloc; 198 h->info.free = info->free; 199 h->info.alloc = info->alloc; 200 h->info.data = info->data; 201 h->t = (h->info.calloc)(h->size, sizeof(struct _ohash_record), 202 h->info.data); 203 h->total = h->deleted = 0; 204 } 205 206 uint32_t 207 ohash_interval(const char *s, const char **e) 208 { 209 uint32_t k; 210 211 if (!*e) 212 *e = s + strlen(s); 213 if (s == *e) 214 k = 0; 215 else 216 k = *s++; 217 while (s != *e) 218 k = ((k << 2) | (k >> 30)) ^ *s++; 219 return k; 220 } 221 222 unsigned int 223 ohash_lookup_interval(struct ohash *h, const char *start, const char *end, 224 uint32_t hv) 225 { 226 unsigned int i, incr; 227 unsigned int empty; 228 229 #ifdef STATS_HASH 230 STAT_HASH_LOOKUP++; 231 #endif 232 empty = NONE; 233 i = hv % h->size; 234 incr = ((hv % (h->size-2)) & ~1) + 1; 235 while (h->t[i].p != NULL) { 236 #ifdef STATS_HASH 237 STAT_HASH_LENGTH++; 238 #endif 239 if (h->t[i].p == DELETED) { 240 if (empty == NONE) 241 empty = i; 242 } else if (h->t[i].hv == hv && 243 strncmp(h->t[i].p+h->info.key_offset, start, 244 end - start) == 0 && 245 (h->t[i].p+h->info.key_offset)[end-start] == '\0') { 246 if (empty != NONE) { 247 h->t[empty].hv = hv; 248 h->t[empty].p = h->t[i].p; 249 h->t[i].p = DELETED; 250 return empty; 251 } else { 252 #ifdef STATS_HASH 253 STAT_HASH_POSITIVE++; 254 #endif 255 return i; 256 } 257 } 258 i += incr; 259 if (i >= h->size) 260 i -= h->size; 261 } 262 263 /* Found an empty position. */ 264 if (empty != NONE) 265 i = empty; 266 h->t[i].hv = hv; 267 return i; 268 } 269 270 unsigned int 271 ohash_lookup_memory(struct ohash *h, const char *k, size_t size, uint32_t hv) 272 { 273 unsigned int i, incr; 274 unsigned int empty; 275 276 #ifdef STATS_HASH 277 STAT_HASH_LOOKUP++; 278 #endif 279 empty = NONE; 280 i = hv % h->size; 281 incr = ((hv % (h->size-2)) & ~1) + 1; 282 while (h->t[i].p != NULL) { 283 #ifdef STATS_HASH 284 STAT_HASH_LENGTH++; 285 #endif 286 if (h->t[i].p == DELETED) { 287 if (empty == NONE) 288 empty = i; 289 } else if (h->t[i].hv == hv && 290 memcmp(h->t[i].p+h->info.key_offset, k, size) == 0) { 291 if (empty != NONE) { 292 h->t[empty].hv = hv; 293 h->t[empty].p = h->t[i].p; 294 h->t[i].p = DELETED; 295 return empty; 296 } else { 297 #ifdef STATS_HASH 298 STAT_HASH_POSITIVE++; 299 #endif 300 } return i; 301 } 302 i += incr; 303 if (i >= h->size) 304 i -= h->size; 305 } 306 307 /* Found an empty position. */ 308 if (empty != NONE) 309 i = empty; 310 h->t[i].hv = hv; 311 return i; 312 } 313 314 unsigned int 315 ohash_qlookup(struct ohash *h, const char *s) 316 { 317 const char *e = NULL; 318 return ohash_qlookupi(h, s, &e); 319 } 320 321 unsigned int 322 ohash_qlookupi(struct ohash *h, const char *s, const char **e) 323 { 324 uint32_t hv; 325 326 hv = ohash_interval(s, e); 327 return ohash_lookup_interval(h, s, *e, hv); 328 } 329