bin/mandoc/compat_ohash.c

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