Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(642)

Unified Diff: fusl/src/search/hsearch.c

Issue 1573973002: Add a "fork" of musl as //fusl. (Closed) Base URL: https://github.com/domokit/mojo.git@master
Patch Set: Created 4 years, 11 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View side-by-side diff with in-line comments
Download patch
« no previous file with comments | « fusl/src/sched/sched_yield.c ('k') | fusl/src/search/insque.c » ('j') | no next file with comments »
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
Index: fusl/src/search/hsearch.c
diff --git a/fusl/src/search/hsearch.c b/fusl/src/search/hsearch.c
new file mode 100644
index 0000000000000000000000000000000000000000..5c8965114bdcb320562ae4661c05ac8bd9374a66
--- /dev/null
+++ b/fusl/src/search/hsearch.c
@@ -0,0 +1,154 @@
+#define _GNU_SOURCE
+#include <stdlib.h>
+#include <string.h>
+#include <search.h>
+#include "libc.h"
+
+/*
+open addressing hash table with 2^n table size
+quadratic probing is used in case of hash collision
+tab indices and hash are size_t
+after resize fails with ENOMEM the state of tab is still usable
+
+with the posix api items cannot be iterated and length cannot be queried
+*/
+
+#define MINSIZE 8
+#define MAXSIZE ((size_t)-1/2 + 1)
+
+struct __tab {
+ ENTRY *entries;
+ 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)
+{
+ unsigned char *p = (void *)k;
+ size_t h = 0;
+
+ while (*p)
+ h = 31*h + *p++;
+ return h;
+}
+
+static int resize(size_t nel, struct hsearch_data *htab)
+{
+ size_t newsize;
+ size_t i, j;
+ 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->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->key) {
+ for (i=keyhash(e->key),j=1; ; i+=j++) {
+ newe = htab->__tab->entries + (i & htab->__tab->mask);
+ if (!newe->key)
+ break;
+ }
+ *newe = *e;
+ }
+ free(oldtab);
+ return 1;
+}
+
+int hcreate(size_t nel)
+{
+ return __hcreate_r(nel, &htab);
+}
+
+void hdestroy(void)
+{
+ __hdestroy_r(&htab);
+}
+
+static ENTRY *lookup(char *key, size_t hash, struct hsearch_data *htab)
+{
+ size_t i, j;
+ ENTRY *e;
+
+ for (i=hash,j=1; ; i+=j++) {
+ e = htab->__tab->entries + (i & htab->__tab->mask);
+ if (!e->key || strcmp(e->key, key) == 0)
+ break;
+ }
+ return e;
+}
+
+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->entries);
+ 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);
+ ENTRY *e = lookup(item.key, hash, htab);
+
+ if (e->key) {
+ *retval = e;
+ return 1;
+ }
+ if (action == FIND) {
+ *retval = 0;
+ return 0;
+ }
+ *e = item;
+ if (++htab->__tab->used > htab->__tab->mask - htab->__tab->mask/4) {
+ if (!resize(2*htab->__tab->used, htab)) {
+ htab->__tab->used--;
+ e->key = 0;
+ *retval = 0;
+ return 0;
+ }
+ e = lookup(item.key, hash, htab);
+ }
+ *retval = e;
+ return 1;
+}
+weak_alias(__hsearch_r, hsearch_r);
« no previous file with comments | « fusl/src/sched/sched_yield.c ('k') | fusl/src/search/insque.c » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698