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 }

Generated on Wed Sep 4 12:49:54 2002 for rpm by doxygen1.2.14 written by Dimitri van Heesch, © 1997-2002