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

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