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 <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 }

Generated at Fri Feb 15 10:32:35 2002 for rpm by doxygen1.2.8.1 written by Dimitri van Heesch, © 1997-2001