00001
00009 #include <stdlib.h>
00010 #include "hashmap.h"
00011
00012
00023 static int reHash(HashMap hmap)
00024 {
00025 int i,index;
00026 HashNode* new;
00027 HashNode this,next;
00028
00029 new=(HashNode*)calloc(hmap->length*2,sizeof(HashNode));
00030
00031 if(!new) return 1;
00032 else
00033 {
00034 for(i=0;i<hmap->length*2;i++)
00035 new[i]=NULL;
00036
00037 for(i=0;i<hmap->length;i++)
00038 {
00039 for(this=hmap->elems[i];this;this=next)
00040 {
00041 next=this->next;
00042 index=(hmap->hash)(this->key)%(hmap->length*2);
00043 this->next=new[index];
00044 new[index]=this;
00045 }
00046 }
00047
00048 free(hmap->elems);
00049 hmap->elems=new;
00050 hmap->length=2*hmap->length;
00051
00052 return 0;
00053 }
00054 }
00055
00056
00057
00058 HashMap newHash(int size,float factor
00059 ,int(*hash)(void*)
00060 ,int(*equals)(void*,void*)
00061 )
00062 {
00063 if(!hash||!equals) return NULL;
00064 else
00065 {
00066 HashMap hmap=(HashMap)malloc(sizeof(SHashMap));
00067
00068 if(!hmap) return NULL;
00069 else
00070 {
00071 hmap->size=0;
00072 hmap->length=size;
00073 hmap->factor=factor;
00074 hmap->hash=*hash;
00075 hmap->equals=*equals;
00076 hmap->elems=(HashNode*)calloc(size,sizeof(HashNode));
00077
00078 if(hmap->elems) return hmap;
00079 else return NULL;
00080 }
00081 }
00082 }
00083
00084
00085
00086 int hashSetHash(HashMap hmap,int(*hash)(void*))
00087 {
00088 if(!hash) return 1;
00089 else
00090 {
00091 hmap->hash=*hash;
00092 return 0;
00093 }
00094 }
00095
00096
00097
00098 int hashSetEquals(HashMap hmap,int(*equals)(void*,void*))
00099 {
00100 if(!equals) return 1;
00101 else
00102 {
00103 hmap->equals=*equals;
00104 return 0;
00105 }
00106 }
00107
00108
00109
00110 int hashSetFactor(HashMap hmap,int factor)
00111 {
00112 if(factor<0.1) return 1;
00113 else
00114 {
00115 hmap->factor=factor;
00116 return 0;
00117 }
00118 }
00119
00120
00121
00122 void hashDelete(HashMap hmap)
00123 {
00124 int i;
00125 HashNode p,aux;
00126
00127 for(i=0;i<hmap->length;i++)
00128 for(p=hmap->elems[i];p;)
00129 {
00130 aux=p;
00131 p=p->next;
00132 free(aux);
00133 }
00134
00135 free(hmap->elems);
00136 free(hmap);
00137 }
00138
00139
00140
00141 int hashInsert(HashMap hmap,void* key,void* value,int replace)
00142 {
00143 int h,stop;
00144 HashNode aux;
00145
00146 if(hmap->size>hmap->factor*hmap->length) reHash(hmap);
00147
00148 h=(hmap->hash)(key)%hmap->length;
00149 for(aux=hmap->elems[h],stop=1;aux&&stop;aux=aux->next)
00150 {
00151 if(!(hmap->equals)(aux->key,key))
00152 {
00153 if(replace) aux->value=value;
00154 stop=0;
00155 }
00156 }
00157
00158 if(stop)
00159 {
00160 aux=(HashNode)malloc(sizeof(SHashNode));
00161
00162 if(aux)
00163 {
00164 aux->key=key;
00165 aux->value=value;
00166 aux->next=hmap->elems[h];
00167 hmap->elems[h]=aux;
00168
00169 hmap->size++;
00170
00171 return 0;
00172 }
00173 else return 2;
00174 }
00175 else return 1;
00176 }
00177
00178
00179
00180 int hashRemove(HashMap hmap,void* key,void** value,void(*del)(void*))
00181 {
00182 int index;
00183 HashNode aux,*last;
00184
00185 index=(hmap->hash)(key)%hmap->length;
00186
00187 for(aux=hmap->elems[index],last=&(hmap->elems[index]);
00188 aux&&(hmap->equals)(key,aux->key);
00189 last=&(aux->next),aux=aux->next);
00190
00191 if(aux)
00192 {
00193 *last=aux->next;
00194 if(del) del(aux->key);
00195 if(*value) *value=aux->value;
00196 free(aux);
00197 hmap->size--;
00198
00199 return 0;
00200 }
00201 else
00202 {
00203 if(value) *value=NULL;
00204 return 1;
00205 }
00206 }
00207
00208
00209
00210 int hashGet(HashMap hmap,void* key,void** value)
00211 {
00212 HashNode aux;
00213
00214 for(aux=hmap->elems[(hmap->hash)(key)%hmap->length];
00215 aux&&(hmap->equals)(key,aux->key);
00216 aux=aux->next);
00217
00218 if(aux)
00219 {
00220 *value=aux->value;
00221 return 0;
00222 }
00223 else
00224 {
00225 *value=NULL;
00226 return 1;
00227 }
00228 }
00229
00230
00231
00232 int hashSize(HashMap hmap)
00233 {
00234 return(hmap->size);
00235 }
00236
00237
00238
00239 Iterator hashKeys(HashMap hmap)
00240 {
00241 int i,erro;
00242 HashNode aux;
00243 Iterator it=newIt(hmap->size);
00244 if(!it) return NULL;
00245 else
00246 {
00247 for(i=0,erro=0;i<hmap->length&&!erro;i++)
00248 for(aux=hmap->elems[i];aux&&!erro;aux=aux->next)
00249 erro=itAdd(it,aux->key);
00250
00251 if(erro)
00252 {
00253 itDelete(it);
00254 return NULL;
00255 }
00256 else return it;
00257 }
00258 }
00259
00260
00261
00262 Iterator hashValues(HashMap hmap)
00263 {
00264 int i,erro;
00265 HashNode aux;
00266 Iterator it=newIt(hmap->size);
00267 if(!it) return NULL;
00268 else
00269 {
00270 for(i=0,erro=0;i<hmap->length&&!erro;i++)
00271 for(aux=hmap->elems[i];aux&&!erro;aux=aux->next)
00272 erro=itAdd(it,aux->value);
00273
00274 if(erro)
00275 {
00276 itDelete(it);
00277 return NULL;
00278 }
00279 else return it;
00280 }
00281 }