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