ref: 10e157391eb2e75c3d38620529b356b302c4a2e5
parent: 4f2262847fa6940fcfded7c36e6ed3a6772ec872
author: Ori Bernstein <[email protected]>
date: Tue Jan 3 14:06:55 EST 2012
Add hash table impl
--- a/parse/Makefile
+++ b/parse/Makefile
@@ -1,7 +1,8 @@
BIN=pt
-OBJ=dump.o \
- ds.o \
+OBJ=bitset.o \
+ dump.o \
gram.o \
+ htab.o \
infer.o \
main.o \
names.o \
--- /dev/null
+++ b/parse/bitset.c
@@ -1,0 +1,115 @@
+#include <stdlib.h>
+#include <stdio.h>
+#include <stdint.h>
+#include <assert.h>
+#include <limits.h>
+#include <string.h>
+
+#include "parse.h"
+
+#define Uintbits (CHAR_BIT*sizeof(int))
+
+static void eqsz(Bitset *a, Bitset *b)
+{+ int sz;
+
+ if (a->nchunks > b->nchunks)
+ sz = a->nchunks;
+ else
+ sz = b->nchunks;
+ a->chunks = zrealloc(a->chunks, a->nchunks*sizeof(uint), sz*sizeof(uint));
+ a->nchunks = sz;
+ b->chunks = zrealloc(b->chunks, a->nchunks*sizeof(uint), sz*sizeof(uint));
+ b->nchunks = sz;
+}
+
+Bitset *mkbs()
+{+ Bitset *bs;
+
+ bs = xalloc(sizeof(Bitset));
+ bs->nchunks = 1;
+ bs->chunks = zalloc(1*sizeof(uint));
+ return bs;
+}
+
+Bitset *dupbs(Bitset *a)
+{+ Bitset *bs;
+
+ bs = xalloc(sizeof(Bitset));
+ bs->nchunks = a->nchunks;
+ bs->chunks = xalloc(a->nchunks*sizeof(uint));
+ memcpy(bs->chunks, a->chunks, a->nchunks*sizeof(uint));
+ return bs;
+}
+
+int bscount(Bitset *bs)
+{+ int i, j, n;
+
+ n = 0;
+ for (i = 0; i < bs->nchunks; i++)
+ for (j = 1; j < sizeof(uint)*CHAR_BIT; j++)
+ if (bs->chunks[i] & 1 << j)
+ n++;
+ return n;
+}
+
+void delbs(Bitset *bs)
+{+ free(bs->chunks);
+ free(bs);
+}
+
+void bsput(Bitset *bs, uint elt)
+{+ size_t sz;
+ if (elt >= bs->nchunks*Uintbits) {+ sz = (elt/Uintbits)+1;
+ bs->chunks = zrealloc(bs->chunks, bs->nchunks*sizeof(uint), sz*sizeof(uint));
+ bs->nchunks = sz;
+ }
+ bs->chunks[elt/Uintbits] |= 1 << (elt % Uintbits);
+}
+
+void bsdel(Bitset *bs, uint elt)
+{+ if (elt < bs->nchunks*Uintbits)
+ bs->chunks[elt/Uintbits] &= ~(1 << (elt % Uintbits));
+}
+
+int bshas(Bitset *bs, uint elt)
+{+ if (elt >= bs->nchunks*Uintbits)
+ return 0;
+ else
+ return bs->chunks[elt/Uintbits] & (1 << (elt % Uintbits));
+}
+
+void bsunion(Bitset *a, Bitset *b)
+{+ int i;
+
+ eqsz(a, b);
+ for (i = 0; i < a->nchunks; i++)
+ a->chunks[i] |= b->chunks[i];
+}
+
+void bsintersect(Bitset *a, Bitset *b)
+{+ int i;
+
+ eqsz(a, b);
+ for (i = 0; i < a->nchunks; i++)
+ a->chunks[i] &= b->chunks[i];
+}
+
+void bsdiff(Bitset *a, Bitset *b)
+{+ int i;
+
+ eqsz(a, b);
+ for (i = 0; i < a->nchunks; i++)
+ a->chunks[i] &= ~b->chunks[i];
+}
--- a/parse/ds.c
+++ /dev/null
@@ -1,116 +1,0 @@
-#include <stdlib.h>
-#include <stdio.h>
-#include <stdint.h>
-#include <assert.h>
-#include <limits.h>
-#include <string.h>
-
-#include "parse.h"
-
-#define Uintbits (CHAR_BIT*sizeof(int))
-
-static void eqsz(Bitset *a, Bitset *b)
-{- int sz;
-
- if (a->nchunks > b->nchunks)
- sz = a->nchunks;
- else
- sz = b->nchunks;
- a->chunks = zrealloc(a->chunks, a->nchunks*sizeof(uint), sz*sizeof(uint));
- a->nchunks = sz;
- b->chunks = zrealloc(b->chunks, a->nchunks*sizeof(uint), sz*sizeof(uint));
- b->nchunks = sz;
-}
-
-Bitset *mkbs()
-{- Bitset *bs;
-
- bs = xalloc(sizeof(Bitset));
- bs->nchunks = 1;
- bs->chunks = zalloc(1*sizeof(uint));
- return bs;
-}
-
-Bitset *dupbs(Bitset *a)
-{- Bitset *bs;
-
- bs = xalloc(sizeof(Bitset));
- bs->nchunks = a->nchunks;
- bs->chunks = xalloc(a->nchunks*sizeof(uint));
- memcpy(bs->chunks, a->chunks, a->nchunks*sizeof(uint));
- return bs;
-}
-
-int bscount(Bitset *bs)
-{- int i, j, n;
-
- n = 0;
- for (i = 0; i < bs->nchunks; i++)
- for (j = 1; j < sizeof(uint)*CHAR_BIT; j++)
- if (bs->chunks[i] & 1 << j)
- n++;
- return n;
-}
-
-void delbs(Bitset *bs)
-{- free(bs->chunks);
- free(bs);
-}
-
-void bsput(Bitset *bs, uint elt)
-{- size_t sz;
- if (elt >= bs->nchunks*Uintbits) {- sz = (elt/Uintbits)+1;
- bs->chunks = zrealloc(bs->chunks, bs->nchunks*sizeof(uint), sz*sizeof(uint));
- bs->nchunks = sz;
- }
- bs->chunks[elt/Uintbits] |= 1 << (elt % Uintbits);
-}
-
-void bsdel(Bitset *bs, uint elt)
-{- if (elt < bs->nchunks*Uintbits)
- bs->chunks[elt/Uintbits] &= ~(1 << (elt % Uintbits));
-}
-
-int bshas(Bitset *bs, uint elt)
-{- if (elt >= bs->nchunks*Uintbits)
- return 0;
- else
- return bs->chunks[elt/Uintbits] & (1 << (elt % Uintbits));
-}
-
-void bsunion(Bitset *a, Bitset *b)
-{- int i;
-
- eqsz(a, b);
- for (i = 0; i < a->nchunks; i++)
- a->chunks[i] |= b->chunks[i];
-}
-
-void bsintersect(Bitset *a, Bitset *b)
-{- int i;
-
- eqsz(a, b);
- for (i = 0; i < a->nchunks; i++)
- a->chunks[i] &= b->chunks[i];
-}
-
-void bsdiff(Bitset *a, Bitset *b)
-{- int i;
-
- eqsz(a, b);
- for (i = 0; i < a->nchunks; i++)
- a->chunks[i] &= ~b->chunks[i];
-}
-
--- /dev/null
+++ b/parse/htab.c
@@ -1,0 +1,136 @@
+#include <stdlib.h>
+#include <stdio.h>
+#include <stdint.h>
+#include <assert.h>
+#include <limits.h>
+#include <string.h>
+
+#include "parse.h"
+
+#define Initsz 16
+
+Htab *mkht(ulong (*hash)(void *key), int (*cmp)(void *k1, void *k2))
+{+ Htab *ht;
+
+ ht = xalloc(sizeof(Htab));
+ ht->nelt = 0;
+ ht->sz = Initsz;
+ ht->hash = hash;
+ ht->cmp = cmp;
+ ht->keys = zalloc(Initsz*sizeof(void*));
+ ht->vals = zalloc(Initsz*sizeof(void*));
+ ht->hashes = zalloc(Initsz*sizeof(void*));
+
+ return ht;
+}
+
+static ulong hash(Htab *ht, void *k)
+{+ ulong h;
+ h = ht->hash(k);
+ if (h == 0)
+ return 1;
+ else
+ return h;
+}
+
+static void grow(Htab *ht, int sz)
+{+ void **oldk;
+ void **oldv;
+ ulong *oldh;
+ int oldsz;
+ int i;
+
+ oldk = ht->keys;
+ oldv = ht->vals;
+ oldh = ht->hashes;
+ oldsz = ht->sz;
+
+ ht->nelt = 0;
+ ht->sz = sz;
+ ht->keys = zalloc(sz*sizeof(void*));
+ ht->vals = zalloc(sz*sizeof(void*));
+ ht->hashes = zalloc(sz*sizeof(void*));
+
+ for (i = 0; i < oldsz; i++)
+ if (oldh[i])
+ htput(ht, oldk[i], oldv[i]);
+ free(oldh);
+ free(oldk);
+ free(oldv);
+}
+
+int htput(Htab *ht, void *k, void *v)
+{+ int i;
+ ulong h;
+ int di;
+
+ h = hash(ht, k);
+ i = h & (ht->sz - 1);
+ while (ht->hashes[i]) {+ /* second insertion overwrites first */
+ if (ht->hashes[i] == h && ht->cmp(ht->keys[i], k))
+ break;
+ di++;
+ i = (h + di) & (ht->sz - 1);
+ }
+ ht->hashes[i] = h;
+ ht->keys[i] = k;
+ ht->vals[i] = v;
+ ht->nelt++;
+ if (ht->sz < ht->nelt*2)
+ grow(ht, ht->sz*2);
+ return 1;
+}
+
+ssize_t htidx(Htab *ht, void *k)
+{+ int i;
+ ulong h;
+ int di;
+
+ h = hash(ht, k);
+ i = h & (ht->sz - 1);
+ while (ht->hashes[i] && ht->hashes[i] != h) {+searchmore:
+ di++;
+ i = (h + di) & (ht->sz - 1);
+ }
+ if (!ht->hashes[i])
+ return -1;
+ if (!ht->cmp(ht->keys[i], k))
+ goto searchmore; /* collision */
+ return i;
+}
+
+void *htget(Htab *ht, void *k)
+{+ ssize_t i;
+
+ i = htidx(ht, k);
+ if (i < 0)
+ return NULL;
+ else
+ return ht->vals[i];
+}
+
+int hthas(Htab *ht, void *k)
+{+ return htidx(ht, k) >= 0;
+}
+
+void **htkeys(Htab *ht)
+{+ void **k;
+ int i, j;
+
+ j = 0;
+ k = xalloc(sizeof(void*)*ht->nelt);
+ for (i = 0; i < ht->sz; i++)
+ if (ht->hashes[i])
+ k[j++] = ht->keys[i];
+ return k;
+}
--- a/parse/parse.h
+++ b/parse/parse.h
@@ -4,6 +4,7 @@
typedef unsigned long long uvlong;
typedef struct Bitset Bitset;
+typedef struct Htab Htab;
typedef struct Tok Tok;
typedef struct Node Node;
@@ -54,6 +55,16 @@
uint *chunks;
};
+struct Htab {+ size_t nelt;
+ size_t sz;
+ ulong (*hash)(void *k);
+ int (*cmp)(void *a, void *b);
+ void **keys;
+ void **vals;
+ ulong *hashes;
+};
+
struct Tok {int type;
int line;
@@ -214,6 +225,15 @@
void bsintersect(Bitset *a, Bitset *b);
void bsdiff(Bitset *a, Bitset *b);
int bscount(Bitset *bs);
+
+Htab *mkht(ulong (*hash)(void *key), int (*cmp)(void *k1, void *k2));
+int htput(Htab *ht, void *k, void *v);
+void *htget(Htab *ht, void *k);
+int hthas(Htab *ht, void *k);
+void **htkeys(Htab *ht);
+/* useful key types */
+ulong strhash(void *str);
+ulong streq(void *s1, void *s2);
/* util functions */
void *zalloc(size_t size);