1#define _GNU_SOURCE 2#include <stdlib.h> 3#include <string.h> 4#include <search.h> 5#include "libc.h" 6 7/* 8open addressing hash table with 2^n table size 9quadratic probing is used in case of hash collision 10tab indices and hash are size_t 11after resize fails with ENOMEM the state of tab is still usable 12 13with 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 19struct __tab { 20 ENTRY *entries; 21 size_t mask; 22 size_t used; 23}; 24 25static struct hsearch_data htab; 26 27int __hcreate_r(size_t, struct hsearch_data *); 28void __hdestroy_r(struct hsearch_data *); 29int __hsearch_r(ENTRY, ACTION, ENTRY **, struct hsearch_data *); 30 31static 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 41static 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 73int hcreate(size_t nel) 74{ 75 return __hcreate_r(nel, &htab); 76} 77 78void hdestroy(void) 79{ 80 __hdestroy_r(&htab); 81} 82 83static 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 96ENTRY *hsearch(ENTRY item, ACTION action) 97{ 98 ENTRY *e; 99 100 __hsearch_r(item, action, &e, &htab); 101 return e; 102} 103 104int __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} 118weak_alias(__hcreate_r, hcreate_r); 119 120void __hdestroy_r(struct hsearch_data *htab) 121{ 122 if (htab->__tab) free(htab->__tab->entries); 123 free(htab->__tab); 124 htab->__tab = 0; 125} 126weak_alias(__hdestroy_r, hdestroy_r); 127 128int __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} 154weak_alias(__hsearch_r, hsearch_r); 155