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

# python/hash.c

Go to the documentation of this file.

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