summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--src/search/hsearch.c51
1 files changed, 22 insertions, 29 deletions
diff --git a/src/search/hsearch.c b/src/search/hsearch.c
index 88edb263..5c896511 100644
--- a/src/search/hsearch.c
+++ b/src/search/hsearch.c
@@ -16,13 +16,8 @@ with the posix api items cannot be iterated and length cannot be queried
#define MINSIZE 8
#define MAXSIZE ((size_t)-1/2 + 1)
-struct elem {
- ENTRY item;
- size_t hash;
-};
-
struct __tab {
- struct elem *elems;
+ ENTRY *entries;
size_t mask;
size_t used;
};
@@ -47,26 +42,26 @@ static int resize(size_t nel, struct hsearch_data *htab)
{
size_t newsize;
size_t i, j;
- struct elem *e, *newe;
- struct elem *oldtab = htab->__tab->elems;
- struct elem *oldend = htab->__tab->elems + htab->__tab->mask + 1;
+ ENTRY *e, *newe;
+ ENTRY *oldtab = htab->__tab->entries;
+ ENTRY *oldend = htab->__tab->entries + htab->__tab->mask + 1;
if (nel > MAXSIZE)
nel = MAXSIZE;
for (newsize = MINSIZE; newsize < nel; newsize *= 2);
- htab->__tab->elems = calloc(newsize, sizeof *htab->__tab->elems);
- if (!htab->__tab->elems) {
- htab->__tab->elems = oldtab;
+ htab->__tab->entries = calloc(newsize, sizeof *htab->__tab->entries);
+ if (!htab->__tab->entries) {
+ htab->__tab->entries = oldtab;
return 0;
}
htab->__tab->mask = newsize - 1;
if (!oldtab)
return 1;
for (e = oldtab; e < oldend; e++)
- if (e->item.key) {
- for (i=e->hash,j=1; ; i+=j++) {
- newe = htab->__tab->elems + (i & htab->__tab->mask);
- if (!newe->item.key)
+ if (e->key) {
+ for (i=keyhash(e->key),j=1; ; i+=j++) {
+ newe = htab->__tab->entries + (i & htab->__tab->mask);
+ if (!newe->key)
break;
}
*newe = *e;
@@ -85,15 +80,14 @@ void hdestroy(void)
__hdestroy_r(&htab);
}
-static struct elem *lookup(char *key, size_t hash, struct hsearch_data *htab)
+static ENTRY *lookup(char *key, size_t hash, struct hsearch_data *htab)
{
size_t i, j;
- struct elem *e;
+ ENTRY *e;
for (i=hash,j=1; ; i+=j++) {
- e = htab->__tab->elems + (i & htab->__tab->mask);
- if (!e->item.key ||
- (e->hash==hash && strcmp(e->item.key, key)==0))
+ e = htab->__tab->entries + (i & htab->__tab->mask);
+ if (!e->key || strcmp(e->key, key) == 0)
break;
}
return e;
@@ -125,7 +119,7 @@ weak_alias(__hcreate_r, hcreate_r);
void __hdestroy_r(struct hsearch_data *htab)
{
- if (htab->__tab) free(htab->__tab->elems);
+ if (htab->__tab) free(htab->__tab->entries);
free(htab->__tab);
htab->__tab = 0;
}
@@ -134,28 +128,27 @@ weak_alias(__hdestroy_r, hdestroy_r);
int __hsearch_r(ENTRY item, ACTION action, ENTRY **retval, struct hsearch_data *htab)
{
size_t hash = keyhash(item.key);
- struct elem *e = lookup(item.key, hash, htab);
+ ENTRY *e = lookup(item.key, hash, htab);
- if (e->item.key) {
- *retval = &e->item;
+ if (e->key) {
+ *retval = e;
return 1;
}
if (action == FIND) {
*retval = 0;
return 0;
}
- e->item = item;
- e->hash = hash;
+ *e = item;
if (++htab->__tab->used > htab->__tab->mask - htab->__tab->mask/4) {
if (!resize(2*htab->__tab->used, htab)) {
htab->__tab->used--;
- e->item.key = 0;
+ e->key = 0;
*retval = 0;
return 0;
}
e = lookup(item.key, hash, htab);
}
- *retval = &e->item;
+ *retval = e;
return 1;
}
weak_alias(__hsearch_r, hsearch_r);