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