From f4d1b8acc04c4f2beeffafa8ff1cca0bdfbe71b2 Mon Sep 17 00:00:00 2001 From: Michael Forney Date: Wed, 17 Apr 2019 20:01:51 -0700 Subject: htab -> map --- Makefile | 10 ++--- cc.h | 4 +- decl.c | 12 +++--- deps.mk | 10 ++--- htab.c | 137 --------------------------------------------------------------- htab.h | 13 ------ map.c | 137 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ map.h | 13 ++++++ qbe.c | 12 +++--- scope.c | 34 ++++++++-------- 10 files changed, 191 insertions(+), 191 deletions(-) delete mode 100644 htab.c delete mode 100644 htab.h create mode 100644 map.c create mode 100644 map.h diff --git a/Makefile b/Makefile index 4477c66..50a0c58 100644 --- a/Makefile +++ b/Makefile @@ -23,16 +23,16 @@ SRC=\ decl.c\ eval.c\ expr.c\ - htab.c\ init.c\ main.c\ + map.c\ pp.c\ scan.c\ scope.c\ siphash.c\ stmt.c\ - tree.c\ token.c\ + tree.c\ type.c\ util.c\ $(BACKEND).c @@ -45,19 +45,19 @@ $(objdir)/decl.o : decl.c $(stagedeps) ; $(CC) $(CFLAGS) -c -o $@ decl.c $(objdir)/driver.o : driver.c $(stagedeps) ; $(CC) $(CFLAGS) -c -o $@ driver.c $(objdir)/eval.o : eval.c $(stagedeps) ; $(CC) $(CFLAGS) -c -o $@ eval.c $(objdir)/expr.o : expr.c $(stagedeps) ; $(CC) $(CFLAGS) -c -o $@ expr.c -$(objdir)/htab.o : htab.c $(stagedeps) ; $(CC) $(CFLAGS) -c -o $@ htab.c $(objdir)/init.o : init.c $(stagedeps) ; $(CC) $(CFLAGS) -c -o $@ init.c $(objdir)/main.o : main.c $(stagedeps) ; $(CC) $(CFLAGS) -c -o $@ main.c +$(objdir)/map.o : map.c $(stagedeps) ; $(CC) $(CFLAGS) -c -o $@ map.c $(objdir)/pp.o : pp.c $(stagedeps) ; $(CC) $(CFLAGS) -c -o $@ pp.c +$(objdir)/qbe.o : qbe.c $(stagedeps) ; $(CC) $(CFLAGS) -c -o $@ qbe.c $(objdir)/scan.o : scan.c $(stagedeps) ; $(CC) $(CFLAGS) -c -o $@ scan.c $(objdir)/scope.o : scope.c $(stagedeps) ; $(CC) $(CFLAGS) -c -o $@ scope.c $(objdir)/siphash.o : siphash.c $(stagedeps) ; $(CC) $(CFLAGS) -c -o $@ siphash.c $(objdir)/stmt.o : stmt.c $(stagedeps) ; $(CC) $(CFLAGS) -c -o $@ stmt.c -$(objdir)/tree.o : tree.c $(stagedeps) ; $(CC) $(CFLAGS) -c -o $@ tree.c $(objdir)/token.o : token.c $(stagedeps) ; $(CC) $(CFLAGS) -c -o $@ token.c +$(objdir)/tree.o : tree.c $(stagedeps) ; $(CC) $(CFLAGS) -c -o $@ tree.c $(objdir)/type.o : type.c $(stagedeps) ; $(CC) $(CFLAGS) -c -o $@ type.c $(objdir)/util.o : util.c $(stagedeps) ; $(CC) $(CFLAGS) -c -o $@ util.c -$(objdir)/qbe.o : qbe.c $(stagedeps) ; $(CC) $(CFLAGS) -c -o $@ qbe.c .PHONY: stage2 stage2: all diff --git a/cc.h b/cc.h index bb5e23b..0de4d2b 100644 --- a/cc.h +++ b/cc.h @@ -264,8 +264,8 @@ struct decl { }; struct scope { - struct hashtable *tags; - struct hashtable *decls; + struct map *tags; + struct map *decls; struct value *breaklabel; struct value *continuelabel; struct switchcases *switchcases; diff --git a/decl.c b/decl.c index 06ded9e..46d1336 100644 --- a/decl.c +++ b/decl.c @@ -8,7 +8,7 @@ #include #include "util.h" #include "cc.h" -#include "htab.h" +#include "map.h" static struct list tentativedefns = {&tentativedefns, &tentativedefns}; @@ -954,16 +954,16 @@ decl(struct scope *s, struct func *f) struct decl *stringdecl(struct expr *expr) { - static struct hashtable *strings; - struct hashtablekey key; + static struct map *strings; + struct mapkey key; void **entry; struct decl *d; if (!strings) - strings = mkhtab(64); + strings = mkmap(64); assert(expr->kind == EXPRSTRING); - htabbufkey(&key, expr->string.data, expr->string.size); - entry = htabput(strings, &key); + mapbufkey(&key, expr->string.data, expr->string.size); + entry = mapput(strings, &key); d = *entry; if (!d) { d = mkdecl(DECLOBJECT, expr->type, QUALNONE, LINKNONE); diff --git a/deps.mk b/deps.mk index 053b261..10e0a12 100644 --- a/deps.mk +++ b/deps.mk @@ -1,18 +1,18 @@ $(objdir)/driver.o: driver.c util.h config.h $(objdir)/util.o: util.c util.h -$(objdir)/decl.o: decl.c util.h cc.h htab.h +$(objdir)/decl.o: decl.c util.h cc.h map.h $(objdir)/eval.o: eval.c util.h cc.h $(objdir)/expr.o: expr.c util.h cc.h -$(objdir)/htab.o: htab.c util.h htab.h $(objdir)/init.o: init.c util.h cc.h $(objdir)/main.o: main.c util.h arg.h cc.h +$(objdir)/map.o: map.c util.h map.h $(objdir)/pp.o: pp.c util.h cc.h $(objdir)/scan.o: scan.c util.h cc.h -$(objdir)/scope.o: scope.c util.h cc.h htab.h +$(objdir)/scope.o: scope.c util.h cc.h map.h $(objdir)/siphash.o: siphash.c $(objdir)/stmt.o: stmt.c util.h cc.h -$(objdir)/tree.o: tree.c util.h tree.h $(objdir)/token.o: token.c util.h cc.h +$(objdir)/tree.o: tree.c util.h tree.h $(objdir)/type.o: type.c util.h cc.h $(objdir)/util.o: util.c util.h -$(objdir)/qbe.o: qbe.c util.h cc.h htab.h tree.h ops.h +$(objdir)/qbe.o: qbe.c util.h cc.h map.h tree.h ops.h diff --git a/htab.c b/htab.c deleted file mode 100644 index 5b4cb0a..0000000 --- a/htab.c +++ /dev/null @@ -1,137 +0,0 @@ -#include -#include -#include -#include -#include -#include "util.h" -#include "htab.h" - -struct hashtable { - size_t len, cap; - struct hashtablekey *keys; - void **vals; -}; - -static uint64_t -hash(const void *ptr, size_t len) -{ - extern int siphash(const uint8_t *, const size_t, const uint8_t *, uint8_t *, const size_t); - static const uint8_t k[16] = {0}; // XXX: we don't have a way to get entropy in standard C - uint64_t r; - - siphash(ptr, len, k, (uint8_t *)&r, sizeof(r)); - - return r; -} - -void -htabbufkey(struct hashtablekey *k, const char *s, size_t n) -{ - k->str = s; - k->len = n; - k->hash = hash(s, n); -} - -void -htabstrkey(struct hashtablekey *k, const char *s) -{ - htabbufkey(k, s, strlen(s)); -} - -struct hashtable * -mkhtab(size_t cap) -{ - struct hashtable *h; - size_t i; - - assert(!(cap & cap - 1)); - h = xmalloc(sizeof(*h)); - h->len = 0; - h->cap = cap; - h->keys = xreallocarray(NULL, cap, sizeof(h->keys[0])); - h->vals = xreallocarray(NULL, cap, sizeof(h->vals[0])); - for (i = 0; i < cap; ++i) - h->keys[i].str = NULL; - - return h; -} - -void -delhtab(struct hashtable *h, void del(void *)) -{ - size_t i; - - if (!h) - return; - if (del) { - for (i = 0; i < h->cap; ++i) { - if (h->keys[i].str) - del(h->vals[i]); - } - } - free(h->keys); - free(h->vals); - free(h); -} - -static bool -keyequal(struct hashtablekey *k1, struct hashtablekey *k2) -{ - if (k1->hash != k2->hash || k1->len != k2->len) - return false; - return memcmp(k1->str, k2->str, k1->len) == 0; -} - -static size_t -keyindex(struct hashtable *h, struct hashtablekey *k) -{ - size_t i; - - i = k->hash & h->cap - 1; - while (h->keys[i].str && !keyequal(&h->keys[i], k)) - i = i + 1 & h->cap - 1; - return i; -} - -void ** -htabput(struct hashtable *h, struct hashtablekey *k) -{ - struct hashtablekey *oldkeys; - void **oldvals; - size_t i, j, oldcap; - - if (h->cap / 2 < h->len) { - oldkeys = h->keys; - oldvals = h->vals; - oldcap = h->cap; - h->cap *= 2; - h->keys = xreallocarray(NULL, h->cap, sizeof(h->keys[0])); - h->vals = xreallocarray(NULL, h->cap, sizeof(h->vals[0])); - for (i = 0; i < h->cap; ++i) - h->keys[i].str = NULL; - for (i = 0; i < oldcap; ++i) { - if (oldkeys[i].str) { - j = keyindex(h, &oldkeys[i]); - h->keys[j] = oldkeys[i]; - h->vals[j] = oldvals[i]; - } - } - } - i = keyindex(h, k); - if (!h->keys[i].str) { - h->keys[i] = *k; - h->vals[i] = NULL; - ++h->len; - } - - return &h->vals[i]; -} - -void * -htabget(struct hashtable *h, struct hashtablekey *k) -{ - size_t i; - - i = keyindex(h, k); - return h->keys[i].str ? h->vals[i] : NULL; -} diff --git a/htab.h b/htab.h deleted file mode 100644 index eb0b663..0000000 --- a/htab.h +++ /dev/null @@ -1,13 +0,0 @@ -struct hashtablekey { - uint64_t hash; - const char *str; - size_t len; -}; - -void htabstrkey(struct hashtablekey *, const char *); -void htabbufkey(struct hashtablekey *, const char *, size_t); - -struct hashtable *mkhtab(size_t); -void delhtab(struct hashtable *, void(void *)); -void **htabput(struct hashtable *, struct hashtablekey *); -void *htabget(struct hashtable *, struct hashtablekey *); diff --git a/map.c b/map.c new file mode 100644 index 0000000..736233b --- /dev/null +++ b/map.c @@ -0,0 +1,137 @@ +#include +#include +#include +#include +#include +#include "util.h" +#include "map.h" + +struct map { + size_t len, cap; + struct mapkey *keys; + void **vals; +}; + +static uint64_t +hash(const void *ptr, size_t len) +{ + extern int siphash(const uint8_t *, const size_t, const uint8_t *, uint8_t *, const size_t); + static const uint8_t k[16] = {0}; // XXX: we don't have a way to get entropy in standard C + uint64_t r; + + siphash(ptr, len, k, (uint8_t *)&r, sizeof(r)); + + return r; +} + +void +mapbufkey(struct mapkey *k, const char *s, size_t n) +{ + k->str = s; + k->len = n; + k->hash = hash(s, n); +} + +void +mapstrkey(struct mapkey *k, const char *s) +{ + mapbufkey(k, s, strlen(s)); +} + +struct map * +mkmap(size_t cap) +{ + struct map *h; + size_t i; + + assert(!(cap & cap - 1)); + h = xmalloc(sizeof(*h)); + h->len = 0; + h->cap = cap; + h->keys = xreallocarray(NULL, cap, sizeof(h->keys[0])); + h->vals = xreallocarray(NULL, cap, sizeof(h->vals[0])); + for (i = 0; i < cap; ++i) + h->keys[i].str = NULL; + + return h; +} + +void +delmap(struct map *h, void del(void *)) +{ + size_t i; + + if (!h) + return; + if (del) { + for (i = 0; i < h->cap; ++i) { + if (h->keys[i].str) + del(h->vals[i]); + } + } + free(h->keys); + free(h->vals); + free(h); +} + +static bool +keyequal(struct mapkey *k1, struct mapkey *k2) +{ + if (k1->hash != k2->hash || k1->len != k2->len) + return false; + return memcmp(k1->str, k2->str, k1->len) == 0; +} + +static size_t +keyindex(struct map *h, struct mapkey *k) +{ + size_t i; + + i = k->hash & h->cap - 1; + while (h->keys[i].str && !keyequal(&h->keys[i], k)) + i = i + 1 & h->cap - 1; + return i; +} + +void ** +mapput(struct map *h, struct mapkey *k) +{ + struct mapkey *oldkeys; + void **oldvals; + size_t i, j, oldcap; + + if (h->cap / 2 < h->len) { + oldkeys = h->keys; + oldvals = h->vals; + oldcap = h->cap; + h->cap *= 2; + h->keys = xreallocarray(NULL, h->cap, sizeof(h->keys[0])); + h->vals = xreallocarray(NULL, h->cap, sizeof(h->vals[0])); + for (i = 0; i < h->cap; ++i) + h->keys[i].str = NULL; + for (i = 0; i < oldcap; ++i) { + if (oldkeys[i].str) { + j = keyindex(h, &oldkeys[i]); + h->keys[j] = oldkeys[i]; + h->vals[j] = oldvals[i]; + } + } + } + i = keyindex(h, k); + if (!h->keys[i].str) { + h->keys[i] = *k; + h->vals[i] = NULL; + ++h->len; + } + + return &h->vals[i]; +} + +void * +mapget(struct map *h, struct mapkey *k) +{ + size_t i; + + i = keyindex(h, k); + return h->keys[i].str ? h->vals[i] : NULL; +} diff --git a/map.h b/map.h new file mode 100644 index 0000000..c1dd5e1 --- /dev/null +++ b/map.h @@ -0,0 +1,13 @@ +struct mapkey { + uint64_t hash; + const char *str; + size_t len; +}; + +void mapstrkey(struct mapkey *, const char *); +void mapbufkey(struct mapkey *, const char *, size_t); + +struct map *mkmap(size_t); +void delmap(struct map *, void(void *)); +void **mapput(struct map *, struct mapkey *); +void *mapget(struct map *, struct mapkey *); diff --git a/qbe.c b/qbe.c index f12a024..3364df2 100644 --- a/qbe.c +++ b/qbe.c @@ -7,7 +7,7 @@ #include #include "util.h" #include "cc.h" -#include "htab.h" +#include "map.h" #include "tree.h" struct name { @@ -73,7 +73,7 @@ struct func { struct decl *namedecl; struct type *type; struct block *start, *end; - struct hashtable *gotos; + struct map *gotos; uint64_t lastid; }; @@ -379,7 +379,7 @@ mkfunc(char *name, struct type *t, struct scope *s) f->name = name; f->type = t; f->start = f->end = (struct block *)mkblock("start"); - f->gotos = mkhtab(8); + f->gotos = mkmap(8); f->lastid = 0; emittype(t->base); @@ -460,10 +460,10 @@ funcgoto(struct func *f, char *name) { void **entry; struct gotolabel *g; - struct hashtablekey key; + struct mapkey key; - htabstrkey(&key, name); - entry = htabput(f->gotos, &key); + mapstrkey(&key, name); + entry = mapput(f->gotos, &key); g = *entry; if (!g) { g = xmalloc(sizeof(*g)); diff --git a/scope.c b/scope.c index f7207d1..c9461d7 100644 --- a/scope.c +++ b/scope.c @@ -4,7 +4,7 @@ #include #include "util.h" #include "cc.h" -#include "htab.h" +#include "map.h" struct scope filescope; @@ -56,9 +56,9 @@ delscope(struct scope *s) struct scope *parent = s->parent; if (s->decls) - delhtab(s->decls, NULL); + delmap(s->decls, NULL); if (s->tags) - delhtab(s->tags, NULL); + delmap(s->tags, NULL); free(s); return parent; @@ -68,11 +68,11 @@ struct decl * scopegetdecl(struct scope *s, const char *name, bool recurse) { struct decl *d; - struct hashtablekey k; + struct mapkey k; - htabstrkey(&k, name); + mapstrkey(&k, name); do { - d = s->decls ? htabget(s->decls, &k) : NULL; + d = s->decls ? mapget(s->decls, &k) : NULL; s = s->parent; } while (!d && s && recurse); @@ -83,11 +83,11 @@ struct type * scopegettag(struct scope *s, const char *name, bool recurse) { struct type *t; - struct hashtablekey k; + struct mapkey k; - htabstrkey(&k, name); + mapstrkey(&k, name); do { - t = s->tags ? htabget(s->tags, &k) : NULL; + t = s->tags ? mapget(s->tags, &k) : NULL; s = s->parent; } while (!t && s && recurse); @@ -97,21 +97,21 @@ scopegettag(struct scope *s, const char *name, bool recurse) void scopeputdecl(struct scope *s, const char *name, struct decl *d) { - struct hashtablekey k; + struct mapkey k; if (!s->decls) - s->decls = mkhtab(32); - htabstrkey(&k, name); - *htabput(s->decls, &k) = d; + s->decls = mkmap(32); + mapstrkey(&k, name); + *mapput(s->decls, &k) = d; } void scopeputtag(struct scope *s, const char *name, struct type *t) { - struct hashtablekey k; + struct mapkey k; if (!s->tags) - s->tags = mkhtab(32); - htabstrkey(&k, name); - *htabput(s->tags, &k) = t; + s->tags = mkmap(32); + mapstrkey(&k, name); + *mapput(s->tags, &k) = t; } -- cgit v1.2.3