nsz Git - musl/blob - src/search/hsearch.c

   1 #define _GNU_SOURCE
   2 #include <stdlib.h>
   3 #include <string.h>
   4 #include <search.h>
   5
   6 /*
   7 open addressing hash table with 2^n table size
   8 quadratic probing is used in case of hash collision
   9 tab indices and hash are size_t
  10 after resize fails with ENOMEM the state of tab is still usable
  11
  12 with the posix api items cannot be iterated and length cannot be queried
  13 */
  14
  15 #define MINSIZE 8
  16 #define MAXSIZE ((size_t)-1/2 + 1)
  17
  18 struct __tab {
  19         ENTRY *entries;
  20         size_t mask;
  21         size_t used;
  22 };
  23
  24 static struct hsearch_data htab;
  25
  26 static int __hcreate_r(size_t, struct hsearch_data *);
  27 static void __hdestroy_r(struct hsearch_data *);
  28 static int __hsearch_r(ENTRY, ACTION, ENTRY **, struct hsearch_data *);
  29
  30 static size_t keyhash(char *k)
  31 {
  32         unsigned char *p = (void *)k;
  33         size_t h = 0;
  34
  35         while (*p)
  36                 h = 31*h + *p++;
  37         return h;
  38 }
  39
  40 static int resize(size_t nel, struct hsearch_data *htab)
  41 {
  42         size_t newsize;
  43         size_t i, j;
  44         size_t oldsize = htab->__tab->mask + 1;
  45         ENTRY *e, *newe;
  46         ENTRY *oldtab = htab->__tab->entries;
  47
  48         if (nel > MAXSIZE)
  49                 nel = MAXSIZE;
  50         for (newsize = MINSIZE; newsize < nel; newsize *= 2);
  51         htab->__tab->entries = calloc(newsize, sizeof *htab->__tab->entries);
  52         if (!htab->__tab->entries) {
  53                 htab->__tab->entries = oldtab;
  54                 return 0;
  55         }
  56         htab->__tab->mask = newsize - 1;
  57         if (!oldtab)
  58                 return 1;
  59         for (e = oldtab; e < oldtab + oldsize; e++)
  60                 if (e->key) {
  61                         for (i=keyhash(e->key),j=1; ; i+=j++) {
  62                                 newe = htab->__tab->entries + (i & htab->__tab->mask);
  63                                 if (!newe->key)
  64                                         break;
  65                         }
  66                         *newe = *e;
  67                 }
  68         free(oldtab);
  69         return 1;
  70 }
  71
  72 int hcreate(size_t nel)
  73 {
  74         return __hcreate_r(nel, &htab);
  75 }
  76
  77 void hdestroy(void)
  78 {
  79         __hdestroy_r(&htab);
  80 }
  81
  82 static ENTRY *lookup(char *key, size_t hash, struct hsearch_data *htab)
  83 {
  84         size_t i, j;
  85         ENTRY *e;
  86
  87         for (i=hash,j=1; ; i+=j++) {
  88                 e = htab->__tab->entries + (i & htab->__tab->mask);
  89                 if (!e->key || strcmp(e->key, key) == 0)
  90                         break;
  91         }
  92         return e;
  93 }
  94
  95 ENTRY *hsearch(ENTRY item, ACTION action)
  96 {
  97         ENTRY *e;
  98
  99         __hsearch_r(item, action, &e, &htab);
 100         return e;
 101 }
 102
 103 static int __hcreate_r(size_t nel, struct hsearch_data *htab)
 104 {
 105         int r;
 106
 107         htab->__tab = calloc(1, sizeof *htab->__tab);
 108         if (!htab->__tab)
 109                 return 0;
 110         r = resize(nel, htab);
 111         if (r == 0) {
 112                 free(htab->__tab);
 113                 htab->__tab = 0;
 114         }
 115         return r;
 116 }
 117 weak_alias(__hcreate_r, hcreate_r);
 118
 119 static void __hdestroy_r(struct hsearch_data *htab)
 120 {
 121         if (htab->__tab) free(htab->__tab->entries);
 122         free(htab->__tab);
 123         htab->__tab = 0;
 124 }
 125 weak_alias(__hdestroy_r, hdestroy_r);
 126
 127 static int __hsearch_r(ENTRY item, ACTION action, ENTRY **retval, struct hsearch_data *htab)
 128 {
 129         size_t hash = keyhash(item.key);
 130         ENTRY *e = lookup(item.key, hash, htab);
 131
 132         if (e->key) {
 133                 *retval = e;
 134                 return 1;
 135         }
 136         if (action == FIND) {
 137                 *retval = 0;
 138                 return 0;
 139         }
 140         *e = item;
 141         if (++htab->__tab->used > htab->__tab->mask - htab->__tab->mask/4) {
 142                 if (!resize(2*htab->__tab->used, htab)) {
 143                         htab->__tab->used--;
 144                         e->key = 0;
 145                         *retval = 0;
 146                         return 0;
 147                 }
 148                 e = lookup(item.key, hash, htab);
 149         }
 150         *retval = e;
 151         return 1;
 152 }
 153 weak_alias(__hsearch_r, hsearch_r);