1 /* Copyright (c) 1999, 2004 Marc Espie <espie@openbsd.org> 2 * 3 * Permission to use, copy, modify, and distribute this software for any 4 * purpose with or without fee is hereby granted, provided that the above 5 * copyright notice and this permission notice appear in all copies. 6 * 7 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES 8 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 9 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR 10 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 11 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN 12 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF 13 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 14 */ 15 16 #include <stddef.h> 17 #include <stdint.h> 18 #include <stdlib.h> 19 #include <string.h> 20 #include <limits.h> 21 22 #include "hash.h" 23 24 struct _hash_record { 25 uint32_t hv; 26 struct hash_entry *p; 27 }; 28 29 struct hash { 30 struct _hash_record *t; 31 unsigned int size; 32 unsigned int total; 33 unsigned int deleted; 34 }; 35 36 #define DELETED ((struct hash_entry *)h) 37 #define NONE (h->size) 38 39 /* Don't bother changing the hash table if the change is small enough. */ 40 #define MINSIZE (1UL << 4) 41 #define MINDELETED 4 42 43 static void hash_resize(struct hash *); 44 static uint32_t hash_interval(const char *, const char **); 45 static unsigned int hash_qlookup(struct hash *, const char *); 46 47 48 /* hash_delete only frees the hash structure. Use hash_first/hash_next 49 * to free entries as well. */ 50 void 51 hash_delete(struct hash *h) 52 { 53 free(h->t); 54 h->t = NULL; 55 } 56 57 static void 58 hash_resize(struct hash *h) 59 { 60 struct _hash_record *n; 61 size_t ns; 62 unsigned int j; 63 unsigned int i, incr; 64 65 if (4 * h->deleted < h->total) { 66 if (h->size >= (UINT_MAX >> 1U)) 67 ns = UINT_MAX; 68 else 69 ns = h->size << 1U; 70 } else if (3 * h->deleted > 2 * h->total) 71 ns = h->size >> 1U; 72 else 73 ns = h->size; 74 if (ns < MINSIZE) 75 ns = MINSIZE; 76 77 n = calloc(ns, sizeof(struct _hash_record)); 78 if (!n) 79 return; 80 81 for (j = 0; j < h->size; j++) { 82 if (h->t[j].p != NULL && h->t[j].p != DELETED) { 83 i = h->t[j].hv % ns; 84 incr = ((h->t[j].hv % (ns - 2)) & ~1) + 1; 85 while (n[i].p != NULL) { 86 i += incr; 87 if (i >= ns) 88 i -= ns; 89 } 90 n[i].hv = h->t[j].hv; 91 n[i].p = h->t[j].p; 92 } 93 } 94 free(h->t); 95 h->t = n; 96 h->size = ns; 97 h->total -= h->deleted; 98 h->deleted = 0; 99 } 100 101 void * 102 hash_remove(struct hash *h, unsigned int i) 103 { 104 void *result = (void *)h->t[i].p; 105 106 if (result == NULL || result == DELETED) 107 return NULL; 108 109 h->t[i].p = DELETED; 110 h->deleted++; 111 if (h->deleted >= MINDELETED && 4 * h->deleted > h->total) 112 hash_resize(h); 113 return result; 114 } 115 116 void 117 hash_insert(struct hash *h, unsigned int i, struct hash_entry *p, 118 const char *key) 119 { 120 p->hkey = key; 121 122 if (h->t[i].p == DELETED) { 123 h->deleted--; 124 h->t[i].p = p; 125 } else { 126 h->t[i].p = p; 127 /* Arbitrary resize boundary. Tweak if not efficient enough. */ 128 if (++h->total * 4 > h->size * 3) 129 hash_resize(h); 130 } 131 } 132 133 void * 134 hash_first(struct hash *h, unsigned int *pos) 135 { 136 *pos = 0; 137 return hash_next(h, pos); 138 } 139 140 void * 141 hash_next(struct hash *h, unsigned int *pos) 142 { 143 for (; *pos < h->size; (*pos)++) 144 if (h->t[*pos].p != DELETED && h->t[*pos].p != NULL) 145 return (void *)h->t[(*pos)++].p; 146 return NULL; 147 } 148 149 struct hash * 150 hash_init(unsigned int size) 151 { 152 struct hash *h; 153 154 h = calloc(1, sizeof(*h)); 155 if (h == NULL) 156 return NULL; 157 158 h->size = 1UL << size; 159 if (h->size < MINSIZE) 160 h->size = MINSIZE; 161 /* Copy info so that caller may free it. */ 162 h->total = h->deleted = 0; 163 h->t = calloc(h->size, sizeof(struct _hash_record)); 164 if (h->t == NULL) { 165 free(h); 166 return NULL; 167 } 168 169 return h; 170 } 171 172 static uint32_t 173 hash_interval(const char *s, const char **e) 174 { 175 uint32_t k; 176 177 if (!*e) 178 *e = s + strlen(s); 179 if (s == *e) 180 k = 0; 181 else 182 k = *s++; 183 while (s != *e) 184 k = ((k << 2) | (k >> 30)) ^ *s++; 185 return k; 186 } 187 188 static unsigned int 189 hash_qlookup(struct hash *h, const char *start) 190 { 191 const char *end = NULL; 192 unsigned int i, incr; 193 unsigned int empty; 194 uint32_t hv; 195 196 hv = hash_interval(start, &end); 197 198 empty = NONE; 199 i = hv % h->size; 200 incr = ((hv % (h->size-2)) & ~1) + 1; 201 while (h->t[i].p != NULL) { 202 if (h->t[i].p == DELETED) { 203 if (empty == NONE) 204 empty = i; 205 } else if (h->t[i].hv == hv && 206 strncmp(h->t[i].p->hkey, start, end - start) == 0 && 207 (h->t[i].p->hkey)[end-start] == '\0') { 208 if (empty != NONE) { 209 h->t[empty].hv = hv; 210 h->t[empty].p = h->t[i].p; 211 h->t[i].p = DELETED; 212 return empty; 213 } else { 214 return i; 215 } 216 } 217 i += incr; 218 if (i >= h->size) 219 i -= h->size; 220 } 221 222 /* Found an empty position. */ 223 if (empty != NONE) 224 i = empty; 225 h->t[i].hv = hv; 226 return i; 227 } 228 229 struct hash_entry * 230 hash_find(struct hash *h, const char *start, unsigned int *slot) 231 { 232 unsigned int i; 233 234 i = hash_qlookup(h, start); 235 if (slot != NULL) 236 *slot = i; 237 238 if (h->t[i].p == DELETED) 239 return NULL; 240 241 return h->t[i].p; 242 } 243