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;
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
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
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
00149 t->overHead += sizeof(char *) * CHUNK;
00150 }
00151
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 }