summaryrefslogtreecommitdiff
path: root/parse/htab.c
diff options
context:
space:
mode:
Diffstat (limited to 'parse/htab.c')
-rw-r--r--parse/htab.c377
1 files changed, 182 insertions, 195 deletions
diff --git a/parse/htab.c b/parse/htab.c
index 1bdad3a..a8f3633 100644
--- a/parse/htab.c
+++ b/parse/htab.c
@@ -15,45 +15,45 @@
* hash collisions. */
Htab *mkht(ulong (*hash)(void *key), int (*cmp)(void *k1, void *k2))
{
- Htab *ht;
-
- ht = xalloc(sizeof(Htab));
- ht->nelt = 0;
- ht->ndead = 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*));
- ht->dead = zalloc(Initsz*sizeof(char));
-
- return ht;
+ Htab *ht;
+
+ ht = xalloc(sizeof(Htab));
+ ht->nelt = 0;
+ ht->ndead = 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 *));
+ ht->dead = zalloc(Initsz * sizeof(char));
+
+ return ht;
}
/* Frees a hash table. Passing this function
* NULL is a no-op. */
void htfree(Htab *ht)
{
- if (!ht)
- return;
- free(ht->keys);
- free(ht->vals);
- free(ht->hashes);
- free(ht->dead);
- free(ht);
+ if (!ht)
+ return;
+ free(ht->keys);
+ free(ht->vals);
+ free(ht->hashes);
+ free(ht->dead);
+ free(ht);
}
/* Offsets the hash so that '0' can be
* used as a 'no valid value */
static ulong hash(Htab *ht, void *k)
{
- ulong h;
- h = ht->hash(k);
- if (h == 0)
- return 1;
- else
- return h;
+ ulong h;
+ h = ht->hash(k);
+ if (h == 0)
+ return 1;
+ else
+ return h;
}
/* Resizes the hash table by copying all
@@ -61,35 +61,35 @@ static ulong hash(Htab *ht, void *k)
* new table. */
static void grow(Htab *ht, int sz)
{
- void **oldk;
- void **oldv;
- ulong *oldh;
- char *oldd;
- int oldsz;
- int i;
-
- oldk = ht->keys;
- oldv = ht->vals;
- oldh = ht->hashes;
- oldd = ht->dead;
- oldsz = ht->sz;
-
- ht->nelt = 0;
- ht->ndead = 0;
- ht->sz = sz;
- ht->keys = zalloc(sz*sizeof(void*));
- ht->vals = zalloc(sz*sizeof(void*));
- ht->hashes = zalloc(sz*sizeof(void*));
- ht->dead = zalloc(sz*sizeof(void*));
-
- for (i = 0; i < oldsz; i++)
- if (oldh[i] && !oldd[i])
- htput(ht, oldk[i], oldv[i]);
-
- free(oldh);
- free(oldk);
- free(oldv);
- free(oldd);
+ void **oldk;
+ void **oldv;
+ ulong *oldh;
+ char *oldd;
+ int oldsz;
+ int i;
+
+ oldk = ht->keys;
+ oldv = ht->vals;
+ oldh = ht->hashes;
+ oldd = ht->dead;
+ oldsz = ht->sz;
+
+ ht->nelt = 0;
+ ht->ndead = 0;
+ ht->sz = sz;
+ ht->keys = zalloc(sz * sizeof(void *));
+ ht->vals = zalloc(sz * sizeof(void *));
+ ht->hashes = zalloc(sz * sizeof(void *));
+ ht->dead = zalloc(sz * sizeof(void *));
+
+ for (i = 0; i < oldsz; i++)
+ if (oldh[i] && !oldd[i])
+ htput(ht, oldk[i], oldv[i]);
+
+ free(oldh);
+ free(oldk);
+ free(oldv);
+ free(oldd);
}
/* Inserts 'k' into the hash table, possibly
@@ -97,62 +97,62 @@ static void grow(Htab *ht, int sz)
* as equal. */
int htput(Htab *ht, void *k, void *v)
{
- int i;
- ulong h;
- int di;
-
- di = 0;
- h = hash(ht, k);
- i = h & (ht->sz - 1);
- while (ht->hashes[i] && !ht->dead[i]) {
- /* second insertion overwrites first. nb, we shouldn't touch the
- * keys for dead values */
- if (ht->hashes[i] == h) {
- if (ht->dead[i])
- break;
- else if (ht->cmp(ht->keys[i], k))
- goto conflicted;
- }
- di++;
- i = (h + di) & (ht->sz - 1);
- }
- ht->nelt++;
+ int i;
+ ulong h;
+ int di;
+
+ di = 0;
+ h = hash(ht, k);
+ i = h & (ht->sz - 1);
+ while (ht->hashes[i] && !ht->dead[i]) {
+ /* second insertion overwrites first. nb, we shouldn't touch the
+ * keys for dead values */
+ if (ht->hashes[i] == h) {
+ if (ht->dead[i])
+ break;
+ else if (ht->cmp(ht->keys[i], k))
+ goto conflicted;
+ }
+ di++;
+ i = (h + di) & (ht->sz - 1);
+ }
+ ht->nelt++;
conflicted:
- if (ht->dead[i])
- ht->ndead--;
- ht->hashes[i] = h;
- ht->keys[i] = k;
- ht->vals[i] = v;
- ht->dead[i] = 0;
-
- if (ht->sz < ht->nelt * 2)
- grow(ht, ht->sz * 2);
- if (ht->sz < ht->ndead * 4)
- grow(ht, ht->sz);
- return 1;
+ if (ht->dead[i])
+ ht->ndead--;
+ ht->hashes[i] = h;
+ ht->keys[i] = k;
+ ht->vals[i] = v;
+ ht->dead[i] = 0;
+
+ if (ht->sz < ht->nelt * 2)
+ grow(ht, ht->sz * 2);
+ if (ht->sz < ht->ndead * 4)
+ grow(ht, ht->sz);
+ return 1;
}
/* Finds the index that we would insert
* the key into */
static ssize_t htidx(Htab *ht, void *k)
{
- ssize_t i;
- ulong h;
- int di;
-
- di = 0;
- h = hash(ht, k);
- i = h & (ht->sz - 1);
- while (ht->hashes[i] && !ht->dead[i] && ht->hashes[i] != h) {
+ ssize_t i;
+ ulong h;
+ int di;
+
+ di = 0;
+ h = hash(ht, k);
+ i = h & (ht->sz - 1);
+ while (ht->hashes[i] && !ht->dead[i] && ht->hashes[i] != h) {
searchmore:
- di++;
- i = (h + di) & (ht->sz - 1);
- }
- if (!ht->hashes[i])
- return -1;
- if ((ht->hashes[i] == h && ht->dead[i]) || !ht->cmp(ht->keys[i], k))
- goto searchmore; /* collision */
- return i;
+ di++;
+ i = (h + di) & (ht->sz - 1);
+ }
+ if (!ht->hashes[i])
+ return -1;
+ if ((ht->hashes[i] == h && ht->dead[i]) || !ht->cmp(ht->keys[i], k))
+ goto searchmore; /* collision */
+ return i;
}
/* Looks up a key, returning NULL if
@@ -162,35 +162,31 @@ searchmore:
* not there */
void *htget(Htab *ht, void *k)
{
- ssize_t i;
+ ssize_t i;
- i = htidx(ht, k);
- if (i < 0)
- return NULL;
- else
- return ht->vals[i];
+ i = htidx(ht, k);
+ if (i < 0)
+ return NULL;
+ else
+ return ht->vals[i];
}
void htdel(Htab *ht, void *k)
{
- ssize_t i;
-
- i = htidx(ht, k);
- if (i < 0)
- return;
- assert(!ht->dead[i]);
- assert(ht->hashes[i]);
- ht->dead[i] = 1;
- ht->nelt--;
- ht->ndead++;
+ ssize_t i;
+
+ i = htidx(ht, k);
+ if (i < 0)
+ return;
+ assert(!ht->dead[i]);
+ assert(ht->hashes[i]);
+ ht->dead[i] = 1;
+ ht->nelt--;
+ ht->ndead++;
}
-
/* Tests for 'k's presence in 'ht' */
-int hthas(Htab *ht, void *k)
-{
- return htidx(ht, k) >= 0;
-}
+int hthas(Htab *ht, void *k) { return htidx(ht, k) >= 0; }
/* Returns a list of all keys in the hash
* table, storing the size of the returned
@@ -199,103 +195,94 @@ int hthas(Htab *ht, void *k)
* job of the caller to free it */
void **htkeys(Htab *ht, size_t *nkeys)
{
- void **k;
- size_t i, j;
-
- j = 0;
- k = xalloc(sizeof(void*)*ht->nelt);
- for (i = 0; i < ht->sz; i++)
- if (ht->hashes[i] && !ht->dead[i])
- k[j++] = ht->keys[i];
- *nkeys = ht->nelt;
- return k;
+ void **k;
+ size_t i, j;
+
+ j = 0;
+ k = xalloc(sizeof(void *) * ht->nelt);
+ for (i = 0; i < ht->sz; i++)
+ if (ht->hashes[i] && !ht->dead[i])
+ k[j++] = ht->keys[i];
+ *nkeys = ht->nelt;
+ return k;
}
ulong strhash(void *_s)
{
- char *s;
- ulong h;
- ulong g;
+ char *s;
+ ulong h;
+ ulong g;
- s = _s;
- h = 0;
- while (s && *s) {
- h = ((h << 4) + *s++);
+ s = _s;
+ h = 0;
+ while (s && *s) {
+ h = ((h << 4) + *s++);
- if ((g = (h & 0xF0000000)))
- h ^= (g >> 24);
+ if ((g = (h & 0xF0000000)))
+ h ^= (g >> 24);
- h &= ~g;
- }
- return h;
+ h &= ~g;
+ }
+ return h;
}
int streq(void *a, void *b)
{
- if (a == b)
- return 1;
- if (a == NULL || b == NULL)
- return 0;
- return !strcmp(a, b);
+ if (a == b)
+ return 1;
+ if (a == NULL || b == NULL)
+ return 0;
+ return !strcmp(a, b);
}
ulong strlithash(void *_s)
{
- Str *s;
- ulong h, g, i;
+ Str *s;
+ ulong h, g, i;
- s = _s;
- h = 0;
- for (i = 0; i < s->len; i++) {
- h = ((h << 4) + s->buf[i]);
+ s = _s;
+ h = 0;
+ for (i = 0; i < s->len; i++) {
+ h = ((h << 4) + s->buf[i]);
- if ((g = (h & 0xF0000000)))
- h ^= (g >> 24);
+ if ((g = (h & 0xF0000000)))
+ h ^= (g >> 24);
- h &= ~g;
- }
- return h;
+ h &= ~g;
+ }
+ return h;
}
int strliteq(void *_a, void *_b)
{
- Str *a, *b;
-
- a = _a;
- b = _b;
- if (a == b)
- return 1;
- if (a == NULL || b == NULL)
- return 0;
- if (a->len != b->len)
- return 0;
- return !memcmp(a, b, a->len);
+ Str *a, *b;
+
+ a = _a;
+ b = _b;
+ if (a == b)
+ return 1;
+ if (a == NULL || b == NULL)
+ return 0;
+ if (a->len != b->len)
+ return 0;
+ return !memcmp(a, b, a->len);
}
-ulong ptrhash(void *key)
-{
- return inthash((uintptr_t)key);
-}
+ulong ptrhash(void *key) { return inthash((uintptr_t)key); }
ulong inthash(uint64_t key)
{
- uintptr_t h;
-
- h = (uintptr_t) key;
- h *= 357913941;
- h ^= h << 24;
- h += ~357913941;
- h ^= h >> 31;
- h ^= h << 31;
- return h;
+ uintptr_t h;
+
+ h = (uintptr_t)key;
+ h *= 357913941;
+ h ^= h << 24;
+ h += ~357913941;
+ h ^= h >> 31;
+ h ^= h << 31;
+ return h;
}
-int inteq(uint64_t a, uint64_t b)
-{
- return a == b;
-}
+int inteq(uint64_t a, uint64_t b) { return a == b; }
-int ptreq(void *a, void *b)
-{
- return a == b;
-}
+int ptreq(void *a, void *b) { return a == b; }