1 /* $OpenBSD: hash.c,v 1.2 2017/08/11 14:58:56 jasper 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 <stddef.h> 19 #include <stdint.h> 20 #include <stdlib.h> 21 #include <string.h> 22 #include <limits.h> 23 24 #include "hash.h" 25 26 struct _hash_record { 27 uint32_t hv; 28 struct hash_entry *p; 29 }; 30 31 struct hash { 32 struct _hash_record *t; 33 unsigned int size; 34 unsigned int total; 35 unsigned int deleted; 36 }; 37 38 #define DELETED ((struct hash_entry *)h) 39 #define NONE (h->size) 40 41 /* Don't bother changing the hash table if the change is small enough. */ 42 #define MINSIZE (1UL << 4) 43 #define MINDELETED 4 44 45 static void hash_resize(struct hash *); 46 static uint32_t hash_interval(const char *, const char **); 47 static unsigned int hash_qlookup(struct hash *, const char *); 48 49 50 /* hash_delete only frees the hash structure. Use hash_first/hash_next 51 * to free entries as well. */ 52 void 53 hash_delete(struct hash *h) 54 { 55 free(h->t); 56 h->t = NULL; 57 } 58 59 static void 60 hash_resize(struct hash *h) 61 { 62 struct _hash_record *n; 63 size_t ns; 64 unsigned int j; 65 unsigned int i, incr; 66 67 if (4 * h->deleted < h->total) { 68 if (h->size >= (UINT_MAX >> 1U)) 69 ns = UINT_MAX; 70 else 71 ns = h->size << 1U; 72 } else if (3 * h->deleted > 2 * h->total) 73 ns = h->size >> 1U; 74 else 75 ns = h->size; 76 if (ns < MINSIZE) 77 ns = MINSIZE; 78 79 n = calloc(ns, sizeof(struct _hash_record)); 80 if (!n) 81 return; 82 83 for (j = 0; j < h->size; j++) { 84 if (h->t[j].p != NULL && h->t[j].p != DELETED) { 85 i = h->t[j].hv % ns; 86 incr = ((h->t[j].hv % (ns - 2)) & ~1) + 1; 87 while (n[i].p != NULL) { 88 i += incr; 89 if (i >= ns) 90 i -= ns; 91 } 92 n[i].hv = h->t[j].hv; 93 n[i].p = h->t[j].p; 94 } 95 } 96 free(h->t); 97 h->t = n; 98 h->size = ns; 99 h->total -= h->deleted; 100 h->deleted = 0; 101 } 102 103 void * 104 hash_remove(struct hash *h, unsigned int i) 105 { 106 void *result = (void *)h->t[i].p; 107 108 if (result == NULL || result == DELETED) 109 return NULL; 110 111 h->t[i].p = DELETED; 112 h->deleted++; 113 if (h->deleted >= MINDELETED && 4 * h->deleted > h->total) 114 hash_resize(h); 115 return result; 116 } 117 118 void 119 hash_insert(struct hash *h, unsigned int i, struct hash_entry *p, 120 const char *key) 121 { 122 p->hkey = key; 123 124 if (h->t[i].p == DELETED) { 125 h->deleted--; 126 h->t[i].p = p; 127 } else { 128 h->t[i].p = p; 129 /* Arbitrary resize boundary. Tweak if not efficient enough. */ 130 if (++h->total * 4 > h->size * 3) 131 hash_resize(h); 132 } 133 } 134 135 void * 136 hash_first(struct hash *h, unsigned int *pos) 137 { 138 *pos = 0; 139 return hash_next(h, pos); 140 } 141 142 void * 143 hash_next(struct hash *h, unsigned int *pos) 144 { 145 for (; *pos < h->size; (*pos)++) 146 if (h->t[*pos].p != DELETED && h->t[*pos].p != NULL) 147 return (void *)h->t[(*pos)++].p; 148 return NULL; 149 } 150 151 struct hash * 152 hash_init(unsigned int size) 153 { 154 struct hash *h; 155 156 h = calloc(1, sizeof(*h)); 157 if (h == NULL) 158 return NULL; 159 160 h->size = 1UL << size; 161 if (h->size < MINSIZE) 162 h->size = MINSIZE; 163 /* Copy info so that caller may free it. */ 164 h->total = h->deleted = 0; 165 h->t = calloc(h->size, sizeof(struct _hash_record)); 166 if (h->t == NULL) { 167 free(h); 168 return NULL; 169 } 170 171 return h; 172 } 173 174 static uint32_t 175 hash_interval(const char *s, const char **e) 176 { 177 uint32_t k; 178 179 if (!*e) 180 *e = s + strlen(s); 181 if (s == *e) 182 k = 0; 183 else 184 k = *s++; 185 while (s != *e) 186 k = ((k << 2) | (k >> 30)) ^ *s++; 187 return k; 188 } 189 190 static unsigned int 191 hash_qlookup(struct hash *h, const char *start) 192 { 193 const char *end = NULL; 194 unsigned int i, incr; 195 unsigned int empty; 196 uint32_t hv; 197 198 hv = hash_interval(start, &end); 199 200 empty = NONE; 201 i = hv % h->size; 202 incr = ((hv % (h->size-2)) & ~1) + 1; 203 while (h->t[i].p != NULL) { 204 if (h->t[i].p == DELETED) { 205 if (empty == NONE) 206 empty = i; 207 } else if (h->t[i].hv == hv && 208 strncmp(h->t[i].p->hkey, start, end - start) == 0 && 209 (h->t[i].p->hkey)[end-start] == '\0') { 210 if (empty != NONE) { 211 h->t[empty].hv = hv; 212 h->t[empty].p = h->t[i].p; 213 h->t[i].p = DELETED; 214 return empty; 215 } else { 216 return i; 217 } 218 } 219 i += incr; 220 if (i >= h->size) 221 i -= h->size; 222 } 223 224 /* Found an empty position. */ 225 if (empty != NONE) 226 i = empty; 227 h->t[i].hv = hv; 228 return i; 229 } 230 231 struct hash_entry * 232 hash_find(struct hash *h, const char *start, unsigned int *slot) 233 { 234 unsigned int i; 235 236 i = hash_qlookup(h, start); 237 if (slot != NULL) 238 *slot = i; 239 240 if (h->t[i].p == DELETED) 241 return NULL; 242 243 return h->t[i].p; 244 } 245