summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--include/search.h12
-rw-r--r--src/search/hsearch.c103
2 files changed, 85 insertions, 30 deletions
diff --git a/include/search.h b/include/search.h
index 27f61072..02e407e3 100644
--- a/include/search.h
+++ b/include/search.h
@@ -22,6 +22,18 @@ int hcreate(size_t);
void hdestroy(void);
ENTRY *hsearch(ENTRY, ACTION);
+#ifdef _GNU_SOURCE
+struct hsearch_data {
+ struct __tab *__tab;
+ unsigned int __unused1;
+ unsigned int __unused2;
+};
+
+int hcreate_r(size_t, struct hsearch_data *);
+void hdestroy_r(struct hsearch_data *);
+int hsearch_r(ENTRY, ACTION, ENTRY **, struct hsearch_data *);
+#endif
+
void insque(void *, void *);
void remque(void *);
diff --git a/src/search/hsearch.c b/src/search/hsearch.c
index 6fe5ced0..88edb263 100644
--- a/src/search/hsearch.c
+++ b/src/search/hsearch.c
@@ -1,6 +1,8 @@
+#define _GNU_SOURCE
#include <stdlib.h>
#include <string.h>
#include <search.h>
+#include "libc.h"
/*
open addressing hash table with 2^n table size
@@ -19,9 +21,17 @@ struct elem {
size_t hash;
};
-static size_t mask;
-static size_t used;
-static struct elem *tab;
+struct __tab {
+ struct elem *elems;
+ size_t mask;
+ size_t used;
+};
+
+static struct hsearch_data htab;
+
+int __hcreate_r(size_t, struct hsearch_data *);
+void __hdestroy_r(struct hsearch_data *);
+int __hsearch_r(ENTRY, ACTION, ENTRY **, struct hsearch_data *);
static size_t keyhash(char *k)
{
@@ -33,29 +43,29 @@ static size_t keyhash(char *k)
return h;
}
-static int resize(size_t nel)
+static int resize(size_t nel, struct hsearch_data *htab)
{
size_t newsize;
size_t i, j;
struct elem *e, *newe;
- struct elem *oldtab = tab;
- struct elem *oldend = tab + mask + 1;
+ struct elem *oldtab = htab->__tab->elems;
+ struct elem *oldend = htab->__tab->elems + htab->__tab->mask + 1;
if (nel > MAXSIZE)
nel = MAXSIZE;
for (newsize = MINSIZE; newsize < nel; newsize *= 2);
- tab = calloc(newsize, sizeof *tab);
- if (!tab) {
- tab = oldtab;
+ htab->__tab->elems = calloc(newsize, sizeof *htab->__tab->elems);
+ if (!htab->__tab->elems) {
+ htab->__tab->elems = oldtab;
return 0;
}
- mask = newsize - 1;
+ 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 = tab + (i & mask);
+ newe = htab->__tab->elems + (i & htab->__tab->mask);
if (!newe->item.key)
break;
}
@@ -67,27 +77,21 @@ static int resize(size_t nel)
int hcreate(size_t nel)
{
- mask = 0;
- used = 0;
- tab = 0;
- return resize(nel);
+ return __hcreate_r(nel, &htab);
}
void hdestroy(void)
{
- free(tab);
- tab = 0;
- mask = 0;
- used = 0;
+ __hdestroy_r(&htab);
}
-static struct elem *lookup(char *key, size_t hash)
+static struct elem *lookup(char *key, size_t hash, struct hsearch_data *htab)
{
size_t i, j;
struct elem *e;
for (i=hash,j=1; ; i+=j++) {
- e = tab + (i & mask);
+ e = htab->__tab->elems + (i & htab->__tab->mask);
if (!e->item.key ||
(e->hash==hash && strcmp(e->item.key, key)==0))
break;
@@ -97,22 +101,61 @@ static struct elem *lookup(char *key, size_t hash)
ENTRY *hsearch(ENTRY item, ACTION action)
{
+ ENTRY *e;
+
+ __hsearch_r(item, action, &e, &htab);
+ return e;
+}
+
+int __hcreate_r(size_t nel, struct hsearch_data *htab)
+{
+ int r;
+
+ htab->__tab = calloc(1, sizeof *htab->__tab);
+ if (!htab->__tab)
+ return 0;
+ r = resize(nel, htab);
+ if (r == 0) {
+ free(htab->__tab);
+ htab->__tab = 0;
+ }
+ return r;
+}
+weak_alias(__hcreate_r, hcreate_r);
+
+void __hdestroy_r(struct hsearch_data *htab)
+{
+ if (htab->__tab) free(htab->__tab->elems);
+ free(htab->__tab);
+ htab->__tab = 0;
+}
+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);
+ struct elem *e = lookup(item.key, hash, htab);
- if (e->item.key)
- return &e->item;
- if (action == FIND)
+ if (e->item.key) {
+ *retval = &e->item;
+ return 1;
+ }
+ if (action == FIND) {
+ *retval = 0;
return 0;
+ }
e->item = item;
e->hash = hash;
- if (++used > mask - mask/4) {
- if (!resize(2*used)) {
- used--;
+ 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;
+ *retval = 0;
return 0;
}
- e = lookup(item.key, hash);
+ e = lookup(item.key, hash, htab);
}
- return &e->item;
+ *retval = &e->item;
+ return 1;
}
+weak_alias(__hsearch_r, hsearch_r);