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 __tab {
  20         ENTRY *entries;
  21         size_t mask;
  22         size_t used;
  23 };
  24
  25 static struct hsearch_data htab;
  26
  27 int __hcreate_r(size_t, struct hsearch_data *);
  28 void __hdestroy_r(struct hsearch_data *);
  29 int __hsearch_r(ENTRY, ACTION, ENTRY **, struct hsearch_data *);
  30
  31 static size_t keyhash(char *k)
  32 {
  33         unsigned char *p = (void *)k;
  34         size_t h = 0;
  35
  36         while (*p)
  37                 h = 31*h + *p++;
  38         return h;
  39 }
  40
  41 static int resize(size_t nel, struct hsearch_data *htab)
  42 {
  43         size_t newsize;
  44         size_t i, j;
  45         ENTRY *e, *newe;
  46         ENTRY *oldtab = htab->__tab->entries;
  47         ENTRY *oldend = htab->__tab->entries + htab->__tab->mask + 1;
  48
  49         if (nel > MAXSIZE)
  50                 nel = MAXSIZE;
  51         for (newsize = MINSIZE; newsize < nel; newsize *= 2);
  52         htab->__tab->entries = calloc(newsize, sizeof *htab->__tab->entries);
  53         if (!htab->__tab->entries) {
  54                 htab->__tab->entries = oldtab;
  55                 return 0;
  56         }
  57         htab->__tab->mask = newsize - 1;
  58         if (!oldtab)
  59                 return 1;
  60         for (e = oldtab; e < oldend; e++)
  61                 if (e->key) {
  62                         for (i=keyhash(e->key),j=1; ; i+=j++) {
  63                                 newe = htab->__tab->entries + (i & htab->__tab->mask);
  64                                 if (!newe->key)
  65                                         break;
  66                         }
  67                         *newe = *e;
  68                 }
  69         free(oldtab);
  70         return 1;
  71 }
  72
  73 int hcreate(size_t nel)
  74 {
  75         return __hcreate_r(nel, &htab);
  76 }
  77
  78 void hdestroy(void)
  79 {
  80         __hdestroy_r(&htab);
  81 }
  82
  83 static ENTRY *lookup(char *key, size_t hash, struct hsearch_data *htab)
  84 {
  85         size_t i, j;
  86         ENTRY *e;
  87
  88         for (i=hash,j=1; ; i+=j++) {
  89                 e = htab->__tab->entries + (i & htab->__tab->mask);
  90                 if (!e->key || strcmp(e->key, key) == 0)
  91                         break;
  92         }
  93         return e;
  94 }
  95
  96 ENTRY *hsearch(ENTRY item, ACTION action)
  97 {
  98         ENTRY *e;
  99
 100         __hsearch_r(item, action, &e, &htab);
 101         return e;
 102 }
 103
 104 int __hcreate_r(size_t nel, struct hsearch_data *htab)
 105 {
 106         int r;
 107
 108         htab->__tab = calloc(1, sizeof *htab->__tab);
 109         if (!htab->__tab)
 110                 return 0;
 111         r = resize(nel, htab);
 112         if (r == 0) {
 113                 free(htab->__tab);
 114                 htab->__tab = 0;
 115         }
 116         return r;
 117 }
 118 weak_alias(__hcreate_r, hcreate_r);
 119
 120 void __hdestroy_r(struct hsearch_data *htab)
 121 {
 122         if (htab->__tab) free(htab->__tab->entries);
 123         free(htab->__tab);
 124         htab->__tab = 0;
 125 }
 126 weak_alias(__hdestroy_r, hdestroy_r);
 127
 128 int __hsearch_r(ENTRY item, ACTION action, ENTRY **retval, struct hsearch_data *htab)
 129 {
 130         size_t hash = keyhash(item.key);
 131         ENTRY *e = lookup(item.key, hash, htab);
 132
 133         if (e->key) {
 134                 *retval = e;
 135                 return 1;
 136         }
 137         if (action == FIND) {
 138                 *retval = 0;
 139                 return 0;
 140         }
 141         *e = item;
 142         if (++htab->__tab->used > htab->__tab->mask - htab->__tab->mask/4) {
 143                 if (!resize(2*htab->__tab->used, htab)) {
 144                         htab->__tab->used--;
 145                         e->key = 0;
 146                         *retval = 0;
 147                         return 0;
 148                 }
 149                 e = lookup(item.key, hash, htab);
 150         }
 151         *retval = e;
 152         return 1;
 153 }
 154 weak_alias(__hsearch_r, hsearch_r);