bin/tsort/compat_ohash.c

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