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