1#define _GNU_SOURCE 2#include <stdlib.h> 3#include <string.h> 4#include <search.h> 5#include <features.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 25#ifdef __HAIKU__ 26struct hsearch_data { 27 struct __tab *__tab; 28 unsigned int __unused1; 29 unsigned int __unused2; 30}; 31#endif 32 33static struct hsearch_data htab; 34 35static int __hcreate_r(size_t, struct hsearch_data *); 36static void __hdestroy_r(struct hsearch_data *); 37static int __hsearch_r(ENTRY, ACTION, ENTRY **, struct hsearch_data *); 38 39static 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 49static 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 81int hcreate(size_t nel) 82{ 83 return __hcreate_r(nel, &htab); 84} 85 86void hdestroy(void) 87{ 88 __hdestroy_r(&htab); 89} 90 91static 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 104ENTRY *hsearch(ENTRY item, ACTION action) 105{ 106 ENTRY *e; 107 108 __hsearch_r(item, action, &e, &htab); 109 return e; 110} 111 112static 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} 126weak_alias(__hcreate_r, hcreate_r); 127 128static 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} 134weak_alias(__hdestroy_r, hdestroy_r); 135 136static 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} 162weak_alias(__hsearch_r, hsearch_r); 163