contrib/mdocml/compat_ohash.c

   1 /* $Id: compat_ohash.c,v 1.7 2020/06/15 01:37:15 schwarze 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@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 #include "config.h"
  19
  20 #include <sys/types.h>
  21 #include <stddef.h>
  22 #include <stdint.h>
  23 #include <stdlib.h>
  24 #include <string.h>
  25 #include <limits.h>
  26 #include "compat_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 }