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