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