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
13 with the posix api items cannot be iterated and length cannot be queried
17 #define MAXSIZE ((size_t)-1/2 + 1)
25 static struct hsearch_data htab
;
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
*);
31 static size_t keyhash(char *k
)
33 unsigned char *p
= (void *)k
;
41 static int resize(size_t nel
, struct hsearch_data
*htab
)
46 ENTRY
*oldtab
= htab
->__tab
->entries
;
47 ENTRY
*oldend
= htab
->__tab
->entries
+ htab
->__tab
->mask
+ 1;
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
;
57 htab
->__tab
->mask
= newsize
- 1;
60 for (e
= oldtab
; e
< oldend
; e
++)
62 for (i
=keyhash(e
->key
),j
=1; ; i
+=j
++) {
63 newe
= htab
->__tab
->entries
+ (i
& htab
->__tab
->mask
);
73 int hcreate(size_t nel
)
75 return __hcreate_r(nel
, &htab
);
83 static ENTRY
*lookup(char *key
, size_t hash
, struct hsearch_data
*htab
)
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)
96 ENTRY
*hsearch(ENTRY item
, ACTION action
)
100 __hsearch_r(item
, action
, &e
, &htab
);
104 int __hcreate_r(size_t nel
, struct hsearch_data
*htab
)
108 htab
->__tab
= calloc(1, sizeof *htab
->__tab
);
111 r
= resize(nel
, htab
);
118 weak_alias(__hcreate_r
, hcreate_r
);
120 void __hdestroy_r(struct hsearch_data
*htab
)
122 if (htab
->__tab
) free(htab
->__tab
->entries
);
126 weak_alias(__hdestroy_r
, hdestroy_r
);
128 int __hsearch_r(ENTRY item
, ACTION action
, ENTRY
**retval
, struct hsearch_data
*htab
)
130 size_t hash
= keyhash(item
.key
);
131 ENTRY
*e
= lookup(item
.key
, hash
, htab
);
137 if (action
== FIND
) {
142 if (++htab
->__tab
->used
> htab
->__tab
->mask
- htab
->__tab
->mask
/4) {
143 if (!resize(2*htab
->__tab
->used
, htab
)) {
149 e
= lookup(item
.key
, hash
, htab
);
154 weak_alias(__hsearch_r
, hsearch_r
);