LibRCG  3.1.1
hashmap.c
Go to the documentation of this file.
1 
9 #include <stdlib.h>
10 #include "hashmap.h"
11 
24 static int reHash(HashMap hmap)
25 {
26  int i,index,result=0;
27  HashNode* new=NULL;
28  HashNode this,next;
29  new=calloc(hmap->length*2,sizeof(HashNode));
30  if(!new) result=1;
31  else
32  {
33  for(i=0;i<hmap->length;i++)
34  {
35  for(this=hmap->elems[i];this;this=next)
36  {
37  next=this->next;
38  index=(hmap->hash)(this->key)%(2*hmap->length);
39  this->next=new[index];
40  new[index]=this;
41  }
42  }
43  free(hmap->elems);
44  hmap->elems=new;
45  hmap->length=2*hmap->length;
46  }
47  return result;
48 }
49 
50 //==============================================================================
51 
52 HashMap newHash(int size,float factor,int(*hash)(void*),
53  int(*equals)(void*,void*))
54 {
55  HashMap hmap=NULL;
56  if(hash&&equals)
57  {
58  hmap=malloc(sizeof(SHashMap));
59  if(hmap)
60  {
61  hmap->size=0;
62  hmap->length=size;
63  if(factor<0.1) hmap->factor=0.1;
64  else hmap->factor=factor;
65  hmap->hash=*hash;
66  hmap->equals=*equals;
67  hmap->elems=calloc(size,sizeof(HashNode));
68  if(!hmap->elems)
69  {
70  free(hmap);
71  hmap=NULL;
72  }
73  }
74  }
75  return hmap;
76 }
77 
78 //==============================================================================
79 
80 int hashSetHash(HashMap hmap,int(*hash)(void*))
81 {
82  int result=0;
83  if(!hash) result=1;
84  else hmap->hash=*hash;
85  return result;
86 }
87 
88 //==============================================================================
89 
90 int hashSetEquals(HashMap hmap,int(*equals)(void*,void*))
91 {
92  int result=0;
93  if(!equals) result=1;
94  else hmap->equals=*equals;
95  return result;
96 }
97 
98 //==============================================================================
99 
100 int hashSetFactor(HashMap hmap,int factor)
101 {
102  int result=0;
103  if(factor<0.1) result=1;
104  else hmap->factor=factor;
105  return result;
106 }
107 
108 //==============================================================================
109 
110 void hashDelete(HashMap hmap)
111 {
112  int i;
113  HashNode p,aux;
114  for(i=0;i<hmap->length;i++)
115  {
116  for(p=hmap->elems[i];p;)
117  {
118  aux=p;
119  p=p->next;
120  free(aux);
121  }
122  }
123  free(hmap->elems);
124  free(hmap);
125 }
126 
127 //==============================================================================
128 
129 int hashInsert(HashMap hmap,void* key,void* value,int replace)
130 {
131  int h,stop,error=0,result=0;
132  HashNode aux;
133  if(hmap->size>hmap->factor*hmap->length) error=reHash(hmap);
134  if(!error)
135  {
136  h=(hmap->hash)(key)%hmap->length;
137  for(aux=hmap->elems[h],stop=0;aux&&!stop;aux=aux->next)
138  {
139  if(!(hmap->equals)(aux->key,key))
140  {
141  if(replace) aux->value=value;
142  stop=1;
143  }
144  }
145  if(!stop)
146  {
147  aux=malloc(sizeof(SHashNode));
148  if(aux)
149  {
150  aux->key=key;
151  aux->value=value;
152  aux->next=hmap->elems[h];
153  hmap->elems[h]=aux;
154  hmap->size++;
155  result=0;
156  }
157  else result=2;
158  }
159  else result=1;
160  }
161  else result=2;
162  return result;
163 }
164 
165 //==============================================================================
166 
167 int hashRemove(HashMap hmap,void* key,void** value,void(*del)(void*))
168 {
169  int index,result=0;
170  HashNode aux,*last;
171  index=(hmap->hash)(key)%hmap->length;
172  for(aux=hmap->elems[index],last=&(hmap->elems[index]);
173  aux&&(hmap->equals)(key,aux->key);
174  last=&(aux->next),aux=aux->next);
175  if(aux)
176  {
177  *last=aux->next;
178  if(del) del(aux->key);
179  if(*value) *value=aux->value;
180  free(aux);
181  hmap->size--;
182  }
183  else
184  {
185  if(value) *value=NULL;
186  result=1;
187  }
188  return result;
189 }
190 
191 //==============================================================================
192 
193 int hashGet(HashMap hmap,void* key,void** value)
194 {
195  int result=0;
196  HashNode aux;
197  for(aux=hmap->elems[(hmap->hash)(key)%hmap->length];
198  aux&&(hmap->equals)(key,aux->key);
199  aux=aux->next);
200  if(aux) *value=aux->value;
201  else
202  {
203  *value=NULL;
204  result=1;
205  }
206  return result;
207 }
208 
209 //==============================================================================
210 
211 int hashSize(HashMap hmap)
212 {
213  return hmap->size;
214 }
215 
216 //==============================================================================
217 
219 {
220  int i,error;
221  HashNode aux;
222  Iterator it=newIt(hmap->size);
223  if(it)
224  {
225  for(i=0,error=0;i<hmap->length&&!error;i++)
226  for(aux=hmap->elems[i];aux&&!error;aux=aux->next)
227  error=itAdd(it,aux->key);
228  if(error)
229  {
230  itDelete(it);
231  it=NULL;
232  }
233  }
234  return it;
235 }
236 
237 //==============================================================================
238 
240 {
241  int i,error;
242  HashNode aux;
243  Iterator it=newIt(hmap->size);
244  if(it)
245  {
246  for(i=0,error=0;i<hmap->length&&!error;i++)
247  for(aux=hmap->elems[i];aux&&!error;aux=aux->next)
248  error=itAdd(it,aux->value);
249  if(error)
250  {
251  itDelete(it);
252  it=NULL;
253  }
254  }
255  return it;
256 }
int hashSetEquals(HashMap hmap, int(*equals)(void *, void *))
Sets the comparison function of a hash table.
Definition: hashmap.c:90
int hashInsert(HashMap hmap, void *key, void *value, int replace)
Associates a value to a key in a hash table.
Definition: hashmap.c:129
Implementation of a hash table.
Iterator hashKeys(HashMap hmap)
Creates an iterator from the keys of a hash table.
Definition: hashmap.c:218
void * value
Node's value.
Definition: hashmap.h:69
void * key
Node's key.
Definition: hashmap.h:67
int hashGet(HashMap hmap, void *key, void **value)
Provides the mapping for a key from a hash table.
Definition: hashmap.c:193
Iterator hashValues(HashMap hmap)
Creates an iterator from the values of a hash table.
Definition: hashmap.c:239
float factor
Load factor.
Definition: hashmap.h:93
Iterator structure.
Definition: iterator.h:17
struct sHashNode * next
Next node.
Definition: hashmap.h:71
void itDelete(Iterator it)
Deletes an iterator.
Definition: iterator.c:36
HashNode * elems
Buckets of this hash table.
Definition: hashmap.h:95
static int reHash(HashMap hmap)
Resizes a hash table.
Definition: hashmap.c:24
int length
Number of buckets of this hash table.
Definition: hashmap.h:91
int itAdd(Iterator it, void *val)
Adds an element to an iterator.
Definition: iterator.c:44
Hash table structure.
Definition: hashmap.h:82
int(* hash)(void *)
Hash function of this hash table.
Definition: hashmap.h:85
HashMap newHash(int size, float factor, int(*hash)(void *), int(*equals)(void *, void *))
Creates a hash table.
Definition: hashmap.c:52
int hashSetHash(HashMap hmap, int(*hash)(void *))
Sets the hash function of a hash table.
Definition: hashmap.c:80
void hashDelete(HashMap hmap)
Deletes a hash table.
Definition: hashmap.c:110
int size
Number of elements of this hash table.
Definition: hashmap.h:89
Hash table node structure.
Definition: hashmap.h:64
int hashSetFactor(HashMap hmap, int factor)
Sets the load factor of a hash table.
Definition: hashmap.c:100
int hashSize(HashMap hmap)
Returns the number of elements present in a hash table.
Definition: hashmap.c:211
int hashRemove(HashMap hmap, void *key, void **value, void(*del)(void *))
Removes the mapping for a key from a hash table.
Definition: hashmap.c:167
Iterator newIt(int size)
Creates an iterator.
Definition: iterator.c:12
int(* equals)(void *, void *)
Comparison function of this hash table.
Definition: hashmap.h:87

LibRCG © 2004-2015   Rui Carlos Gonçalves