external/bsd/mdocml/dist/compat_ohash.c

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