Main Page | Modules | Data Structures | Directories | File List | Data Fields | Globals | Related Pages

# hash.c

Go to the documentation of this file.

    00001
    00005 #include <stdlib.h>
    00006 #include <unistd.h>
    00007 #include <stdio.h>
    00008 #include <string.h>
    00009
    00010 #include "hash.h"
    00011
    00012 #define CHUNK 1
    00013
    00014 struct filePath {
    00015     char * dir;
    00016     char * base;
    00017 } ;
    00018
    00019 struct bucket {
    00020     struct filePath * data;
    00021     int allocated;
    00022     int firstFree; /* as in data[firstFree] */
    00023 };
    00024
    00025 struct hash_table {
    00026     int size;
    00027     int entries;
    00028     int overHead;
    00029     struct bucket *bucket;
    00030 };
    00031
    00032 struct hash_table *htNewTable(int size)
    00033 {
    00034     struct hash_table *res;
    00035     int i = 0;
    00036
    00037     res = malloc(sizeof(struct hash_table));
    00038     res->bucket = malloc(sizeof(struct bucket) * size);
    00039     res->size = size;
    00040     res->entries = 0;
    00041     res->overHead = sizeof(struct bucket) * size + CHUNK * sizeof(char *);
    00042
    00043     while (i < size) {
    00044         res->bucket[i].data = malloc(CHUNK * sizeof(*res->bucket[i].data));
    00045         res->bucket[i].allocated = CHUNK;
    00046         res->bucket[i].firstFree = 0;
    00047         i++;
    00048     }
    00049
    00050     return res;
    00051 }
    00052
    00053 void htFreeHashTable(struct hash_table *ht)
    00054 {
    00055     struct bucket * b;
    00056     int item;
    00057
    00058     b = ht->bucket;
    00059     while (ht->size--) {
    00060         for (item = 0; item < b->firstFree; item++) {
    00061             free(b->data[item].dir);
    00062             free(b->data[item].base);
    00063         }
    00064         free(b->data);
    00065         b++;
    00066     }
    00067     free(ht->bucket);
    00068     free(ht);
    00069 }
    00070
    00071 void htHashStats(const struct hash_table *t)
    00072 {
    00073     int i = 0;
    00074     int empty = 0;
    00075
    00076     while (i < t->size) {
    00077         if (t->bucket[i].firstFree != 0) {
    00078             /*printf("Bucket %d used %d\n", i, t->bucket[i].firstFree);*/
    00079         } else {
    00080             empty++;
    00081         }
    00082         i++;
    00083     }
    00084
    00085     printf("Total Buckets : %d\n", t->size);
    00086     printf("Empty Buckets : %d\n", empty);
    00087     printf("Total Entries : %d\n", t->entries);
    00088     printf("Total Overhead: %d\n", t->overHead);
    00089     printf("Avergage Depth: %f\n", (double)t->entries / (double)t->size);
    00090 }
    00091
    00092 static unsigned int htHashStrings(const char * s, const char * t)
    00093 {
    00094     unsigned int res = 0;
    00095
    00096     while (*s != '\0')
    00097         res = ((res<<1) + (int)(*(s++)));
    00098     while (*t != '\0')
    00099         res = ((res<<1) + (int)(*(t++)));
    00100
    00101     return res;
    00102 }
    00103
    00104 /* returns bucket # containing item, or -1 */
    00105 static int in_table_aux(struct hash_table *t, int hash, const char * dir,
    00106                         const char * base)
    00107 {
    00108     int x;
    00109
    00110     x = 0;
    00111     while (x < t->bucket[hash].firstFree) {
    00112         if (! strcmp(t->bucket[hash].data[x].dir, dir) &&
    00113             ! strcmp(t->bucket[hash].data[x].base, base)) {
    00114             return x;
    00115         }
    00116         x++;
    00117     }
    00118
    00119     return -1;
    00120 }
    00121
    00122 int htInTable(struct hash_table *t,  const char * dir, const char * base)
    00123 {
    00124     int hash;
    00125
    00126     hash = htHashStrings(dir, base) % t->size;
    00127
    00128     if (in_table_aux(t, hash, dir, base) == -1)
    00129         return 0;
    00130     return 1;
    00131 }
    00132
    00133 void htAddToTable(struct hash_table *t, const char * dir, const char * base)
    00134 {
    00135     static int hash = 1;
    00136
    00137     if (!dir || !base)
    00138         return;
    00139
    00140     hash = htHashStrings(dir, base) % t->size;
    00141     if (in_table_aux(t, hash, dir, base) != -1)
    00142         return;
    00143
    00144     if (t->bucket[hash].firstFree == t->bucket[hash].allocated) {
    00145         t->bucket[hash].allocated += CHUNK;
    00146         t->bucket[hash].data =
    00147             realloc(t->bucket[hash].data,
    00148                     t->bucket[hash].allocated * sizeof(*(t->bucket->data)));
    00149         /*printf("Bucket %d grew to %d\n", hash, t->bucket[hash].allocated);*/
    00150         t->overHead += sizeof(char *) * CHUNK;
    00151     }
    00152     /*printf("In bucket %d, item %d\n", hash, t->bucket[hash].firstFree);*/
    00153     t->bucket[hash].data[t->bucket[hash].firstFree].dir = strdup(dir);
    00154     t->bucket[hash].data[t->bucket[hash].firstFree++].base = strdup(base);
    00155     t->entries++;
    00156 }
    00157
    00158 void htRemoveFromTable(struct hash_table *t, const char * dir,
    00159                        const char * base) {
    00160     int hash;
    00161     int item;
    00162     int last;
    00163
    00164     hash = htHashStrings(dir, base) % t->size;
    00165     if ((item = in_table_aux(t, hash, dir, base)) == -1) {
    00166         return;
    00167     }
    00168
    00169     free(t->bucket[hash].data[item].dir);
    00170     free(t->bucket[hash].data[item].base);
    00171
    00172     last = --t->bucket[hash].firstFree;
    00173     t->bucket[hash].data[item] = t->bucket[hash].data[last];
    00174 }
    00175
    00176 int htNumEntries(struct hash_table *t) {
    00177     return t->entries;
    00178 }
    00179
    00180 void htIterStart(htIterator * iter) {
    00181     iter->bucket = 0;
    00182     iter->item = -1;
    00183 }
    00184
    00185 int htIterGetNext(struct hash_table * t, htIterator * iter,
    00186                   const char ** dir, const char ** base) {
    00187     iter->item++;
    00188
    00189     while (iter->bucket < t->size) {
    00190         if (iter->item < t->bucket[iter->bucket].firstFree) {
    00191             *dir = t->bucket[iter->bucket].data[iter->item].dir;
    00192             *base = t->bucket[iter->bucket].data[iter->item].base;
    00193
    00194             return 1;
    00195         }
    00196
    00197         iter->item++;
    00198         if (iter->item >= t->bucket[iter->bucket].firstFree) {
    00199             iter->bucket++;
    00200             iter->item = 0;
    00201         }
    00202     }
    00203
    00204     return 0;
    00205 }