diff options
Diffstat (limited to 'utils/hash.c')
| -rw-r--r-- | utils/hash.c | 201 |
1 files changed, 201 insertions, 0 deletions
diff --git a/utils/hash.c b/utils/hash.c new file mode 100644 index 000000000..2bc6e0bf2 --- /dev/null +++ b/utils/hash.c @@ -0,0 +1,201 @@ +#include <stdlib.h> +#include <unistd.h> +#include <stdio.h> +#include <string.h> + +#include "hash.h" + +#define CHUNK 1 + +struct filePath { + char * dir; + char * base; +} ; + +struct bucket { + struct filePath * data; + int allocated; + int firstFree; /* as in data[firstFree] */ +}; + +struct hash_table { + int size; + int entries; + int overHead; + struct bucket *bucket; +}; + +struct hash_table *htNewTable(int size) +{ + struct hash_table *res; + int i = 0; + + res = malloc(sizeof(struct hash_table)); + res->bucket = malloc(sizeof(struct bucket) * size); + res->size = size; + res->entries = 0; + res->overHead = sizeof(struct bucket) * size + CHUNK * sizeof(char *); + + while (i < size) { + res->bucket[i].data = malloc(CHUNK * sizeof(*res->bucket[i].data)); + res->bucket[i].allocated = CHUNK; + res->bucket[i].firstFree = 0; + i++; + } + + return res; +} + +void htFreeHashTable(struct hash_table *ht) +{ + struct bucket * b; + int item; + + b = ht->bucket; + while (ht->size--) { + for (item = 0; item < b->firstFree; item++) { + free(b->data[item].dir); + free(b->data[item].base); + } + free(b->data); + b++; + } + free(ht->bucket); + free(ht); +} + +void htHashStats(struct hash_table *t) +{ + int i = 0; + int empty = 0; + + while (i < t->size) { + if (t->bucket[i].firstFree != 0) { + /*printf("Bucket %d used %d\n", i, t->bucket[i].firstFree);*/ + } else { + empty++; + } + i++; + } + + printf("Total Buckets : %d\n", t->size); + printf("Empty Buckets : %d\n", empty); + printf("Total Entries : %d\n", t->entries); + printf("Total Overhead: %d\n", t->overHead); + printf("Avergage Depth: %f\n", (double)t->entries / (double)t->size); +} + +static unsigned int htHashStrings(const char *s, const char *t) +{ + unsigned int res = 0; + + while (*s) + res = ((res<<1) + (int)(*(s++))); + while (*t) + res = ((res<<1) + (int)(*(t++))); + + return res; +} + +/* returns bucket # containing item, or -1 */ +static int in_table_aux(struct hash_table *t, int hash, const char * dir, + const char * base) +{ + int x; + + x = 0; + while (x < t->bucket[hash].firstFree) { + if (! strcmp(t->bucket[hash].data[x].dir, dir) && + ! strcmp(t->bucket[hash].data[x].base, base)) { + return x; + } + x++; + } + + return -1; +} + +int htInTable(struct hash_table *t, const char * dir, const char * base) +{ + int hash; + + hash = htHashStrings(dir, base) % t->size; + + if (in_table_aux(t, hash, dir, base) == -1) + return 0; + return 1; +} + +void htAddToTable(struct hash_table *t, const char * dir, const char * base) +{ + static int hash = 1; + + if (!dir || !base) + return; + + hash = htHashStrings(dir, base) % t->size; + if (in_table_aux(t, hash, dir, base) != -1) + return; + + if (t->bucket[hash].firstFree == t->bucket[hash].allocated) { + t->bucket[hash].allocated += CHUNK; + t->bucket[hash].data = + realloc(t->bucket[hash].data, + t->bucket[hash].allocated * sizeof(*(t->bucket->data))); + /*printf("Bucket %d grew to %d\n", hash, t->bucket[hash].allocated);*/ + t->overHead += sizeof(char *) * CHUNK; + } + /*printf("In bucket %d, item %d\n", hash, t->bucket[hash].firstFree);*/ + t->bucket[hash].data[t->bucket[hash].firstFree].dir = strdup(dir); + t->bucket[hash].data[t->bucket[hash].firstFree++].base = strdup(base); + t->entries++; +} + +void htRemoveFromTable(struct hash_table *t, const char * dir, + const char * base) { + int hash; + int item; + int last; + + hash = htHashStrings(dir, base) % t->size; + if ((item = in_table_aux(t, hash, dir, base)) == -1) { + return; + } + + free(t->bucket[hash].data[item].dir); + free(t->bucket[hash].data[item].base); + + last = --t->bucket[hash].firstFree; + t->bucket[hash].data[item] = t->bucket[hash].data[last]; +} + +int htNumEntries(struct hash_table *t) { + return t->entries; +} + +void htIterStart(htIterator * iter) { + iter->bucket = 0; + iter->item = -1; +} + +int htIterGetNext(struct hash_table * t, htIterator * iter, + const char ** dir, const char ** base) { + iter->item++; + + while (iter->bucket < t->size) { + if (iter->item < t->bucket[iter->bucket].firstFree) { + *dir = t->bucket[iter->bucket].data[iter->item].dir; + *base = t->bucket[iter->bucket].data[iter->item].base; + + return 1; + } + + iter->item++; + if (iter->item >= t->bucket[iter->bucket].firstFree) { + iter->bucket++; + iter->item = 0; + } + } + + return 0; +} |