00001
00002
00003 #include "hashtable.h"
00004 #include "utils.h"
00005
00006
00007
00008 struct bucket *newBucket(char* key, void* value) {
00009 struct bucket *b = (struct bucket *)malloc(sizeof(struct bucket));
00010 if(b==NULL) {
00011 return NULL;
00012 }
00013 b->next = NULL;
00014 b->key = key;
00015 b->value = value;
00016 return b;
00017 }
00018
00019 struct bucket *newBucket2(char* key, void* value, Region *r) {
00020 struct bucket *b = (struct bucket *)region_alloc(r, sizeof(struct bucket));
00021 if(b==NULL) {
00022 return NULL;
00023 }
00024 b->next = NULL;
00025 b->key = key;
00026 b->value = value;
00027 return b;
00028 }
00029
00030
00031
00032
00033 Hashtable *newHashTable(int size) {
00034 Hashtable *h = (Hashtable *)malloc(sizeof (Hashtable));
00035 if( NULL == h ) {
00036 return 0;
00037 }
00038 memset(h, 0, sizeof(Hashtable));
00039
00040
00041
00042
00043 h->dynamic = 0;
00044 h->bucketRegion = NULL;
00045 h->size = size;
00046 h->buckets = (struct bucket **)malloc(sizeof(struct bucket *)*size);
00047 if(h->buckets == NULL) {
00048 free(h);
00049 return NULL;
00050 }
00051 memset(h->buckets, 0, sizeof(struct bucket *)*size);
00052 h->len = 0;
00053 return h;
00054 }
00055
00056
00057
00058
00059 Hashtable *newHashTable2(int size, Region *r) {
00060
00061 Hashtable *h = (Hashtable *)region_alloc(r, sizeof (Hashtable));
00062 if( NULL == h ) {
00063 return 0;
00064 }
00065 memset(h, 0, sizeof(Hashtable));
00066
00067
00068
00069
00070 h->dynamic = 1;
00071 h->bucketRegion = r;
00072 h->size = size;
00073 h->buckets = (struct bucket **)region_alloc(h->bucketRegion, sizeof(struct bucket *)*size);
00074 if(h->buckets == NULL) {
00075 return NULL;
00076 }
00077 memset(h->buckets, 0, sizeof(struct bucket *)*size);
00078 h->len = 0;
00079 return h;
00080 }
00081
00082
00083
00084
00085
00086 int insertIntoHashTable(Hashtable *h, char* key, void *value) {
00087
00088
00089
00090 if(h->dynamic) {
00091 if(h->len >= h->size) {
00092 Hashtable *h2 = newHashTable2(h->size * 2, h->bucketRegion);
00093 int i;
00094 for(i=0;i<h->size;i++) {
00095 if(h->buckets[i]!=NULL) {
00096 struct bucket *b = h->buckets[i];
00097 do {
00098 insertIntoHashTable(h2, b->key, b->value);
00099 b=b->next;
00100
00101 } while (b!=NULL);
00102 }
00103 }
00104 memcpy(h, h2, sizeof(Hashtable));
00105 }
00106 struct bucket *b = newBucket2(cpStringExt(key, h->bucketRegion), value, h->bucketRegion);
00107 if(b==NULL) {
00108 return 0;
00109 }
00110
00111 unsigned long hs = myhash(key);
00112 unsigned long index = hs%h->size;
00113 if(h->buckets[index] == NULL) {
00114 h->buckets[index] = b;
00115 } else {
00116 struct bucket *b0 = h->buckets[index];
00117 while(b0->next!=NULL)
00118 b0=b0->next;
00119 b0->next = b;
00120 }
00121 h->len ++;
00122 return 1;
00123 } else {
00124 struct bucket *b = newBucket(strdup(key), value);
00125 if(b==NULL) {
00126 return 0;
00127 }
00128 unsigned long hs = myhash(key);
00129 unsigned long index = hs%h->size;
00130 if(h->buckets[index] == NULL) {
00131 h->buckets[index] = b;
00132 } else {
00133 struct bucket *b0 = h->buckets[index];
00134 while(b0->next!=NULL)
00135 b0=b0->next;
00136 b0->next = b;
00137 }
00138 h->len ++;
00139 return 1;
00140 }
00141 }
00142
00143
00144
00145 void* updateInHashTable(Hashtable *h, char* key, void* value) {
00146 unsigned long hs = myhash(key);
00147 unsigned long index = hs%h->size;
00148 if(h->buckets[index] != NULL) {
00149 struct bucket *b0 = h->buckets[index];
00150 while(b0!=NULL) {
00151 if(strcmp(b0->key, key) == 0) {
00152 void* tmp = b0->value;
00153 b0->value = value;
00154 return tmp;
00155
00156 }
00157 b0=b0->next;
00158 }
00159 }
00160 return NULL;
00161 }
00162
00163
00164
00165 void *deleteFromHashTable(Hashtable *h, char* key) {
00166 unsigned long hs = myhash(key);
00167 unsigned long index = hs%h->size;
00168 void *temp = NULL;
00169 if(h->buckets[index] != NULL) {
00170 struct bucket *b0 = h->buckets[index];
00171 if(strcmp(b0->key, key) == 0) {
00172 h->buckets[index] = b0->next;
00173 temp = b0->value;
00174 if(!h->dynamic) {
00175 free(b0->key);
00176 free(b0);
00177 }
00178 h->len --;
00179 } else {
00180 while(b0->next!=NULL) {
00181 if(strcmp(b0->next->key, key) == 0) {
00182 struct bucket *tempBucket = b0->next;
00183 temp = b0->next->value;
00184 b0->next = b0->next->next;
00185 if(!h->dynamic) {
00186 free(tempBucket->key);
00187 free(tempBucket);
00188 }
00189 h->len --;
00190 break;
00191 }
00192 b0 = b0->next;
00193 }
00194 }
00195 }
00196
00197 return temp;
00198 }
00199
00200
00201
00202 void* lookupFromHashTable(Hashtable *h, char* key) {
00203 unsigned long hs = myhash(key);
00204 unsigned long index = hs%h->size;
00205 struct bucket *b0 = h->buckets[index];
00206 while(b0!=NULL) {
00207 if(strcmp(b0->key,key)==0) {
00208 return b0->value;
00209 }
00210 b0=b0->next;
00211 }
00212 return NULL;
00213 }
00214
00215
00216
00217 struct bucket* lookupBucketFromHashTable(Hashtable *h, char* key) {
00218 unsigned long hs = myhash(key);
00219 unsigned long index = hs%h->size;
00220 struct bucket *b0 = h->buckets[index];
00221 while(b0!=NULL) {
00222 if(strcmp(b0->key,key)==0) {
00223 return b0;
00224 }
00225 b0=b0->next;
00226 }
00227 return NULL;
00228 }
00229 struct bucket* nextBucket(struct bucket *b0, char* key) {
00230 b0 = b0->next;
00231 while(b0!=NULL) {
00232 if(strcmp(b0->key,key)==0) {
00233 return b0;
00234 }
00235 b0=b0->next;
00236 }
00237 return NULL;
00238 }
00239
00240 void deleteHashTable(Hashtable *h, void (*f)(void *)) {
00241 if(h->dynamic) {
00242
00243
00244
00245
00246
00247
00248
00249
00250
00251
00252
00253 } else {
00254 int i;
00255 for(i =0;i<h->size;i++) {
00256 struct bucket *b0 = h->buckets[i];
00257 if(b0!=NULL)
00258 deleteBucket(b0,f);
00259 }
00260 free(h->buckets);
00261 free(h);
00262 }
00263 }
00264 void deleteBucket(struct bucket *b0, void (*f)(void *)) {
00265 if(b0->next!=NULL) {
00266 deleteBucket(b0->next, f);
00267 }
00268
00269 free(b0->key);
00270 if(f!=NULL) f(b0->value);
00271 free(b0);
00272 }
00273 void nop(void *a) {
00274 }
00275
00276
00277
00278
00279 unsigned long B_hash(unsigned char* string) {
00280 unsigned long hash = HASH_BASE;
00281 while(*string!='\0') {
00282 hash = ((hash << 5) + hash) + (int)*string;
00283 string++;
00284 }
00285 return hash;
00286
00287 }
00288 unsigned long sdbm_hash(char* str) {
00289 unsigned long hash = 0;
00290 while (*str!='\0') {
00291 hash = ((int)*str) + (hash << 6) + (hash << 16) - hash;
00292 str++;
00293 }
00294
00295 return hash;
00296 }
00297
00298 #include "utils.h"
00299 #include "index.h"
00300
00301 void dumpHashtableKeys(Hashtable *t) {
00302 int i;
00303 for(i = 0;i<t->size;i++) {
00304 struct bucket *b=t->buckets[i];
00305 while(b!=NULL) {
00306 writeToTmp("htdump", b->key);
00307 writeToTmp("htdump", "\n");
00308 b= b->next;
00309 }
00310 }
00311 }
00312