12 #include "GenericHashtable.h"
18 void * getfirstkey(struct genhashtable *ht) {
19 if(ht->list == NULL) {
25 int genputtable(struct genhashtable *ht, void * key, void * object) {
26 unsigned int bin=genhashfunction(ht,key);
27 struct genpointerlist * newptrlist=(struct genpointerlist *) RUNMALLOC(sizeof(struct genpointerlist));
29 newptrlist->object=object;
30 newptrlist->next=ht->bins[bin];
31 newptrlist->inext=NULL;
32 /* maintain linked list of ht entries for iteration*/
36 newptrlist->iprev=NULL;
38 ht->last->inext=newptrlist;
39 newptrlist->iprev=ht->last;
42 ht->bins[bin]=newptrlist;
44 if(ht->counter>ht->currentsize&&ht->currentsize!=INT_MAX) {
45 /* Expand hashtable */
46 long newcurrentsize=(ht->currentsize<(INT_MAX/2)) ? ht->currentsize*2 : INT_MAX;
47 long oldcurrentsize=ht->currentsize;
48 struct genpointerlist **newbins=(struct genpointerlist **) RUNMALLOC(sizeof (struct genpointerlist *)*newcurrentsize);
49 struct genpointerlist **oldbins=ht->bins;
51 for(j=0; j<newcurrentsize; j++) newbins[j]=NULL;
52 ht->currentsize=newcurrentsize;
53 for(i=0; i<oldcurrentsize; i++) {
54 struct genpointerlist * tmpptr=oldbins[i];
56 unsigned int hashcode=genhashfunction(ht, tmpptr->src);
57 struct genpointerlist *nextptr=tmpptr->next;
58 tmpptr->next=newbins[hashcode];
59 newbins[hashcode]=tmpptr;
70 int genputtable_I(struct genhashtable *ht, void * key, void * object) {
71 unsigned int bin=genhashfunction(ht,key);
72 struct genpointerlist * newptrlist=(struct genpointerlist *) RUNMALLOC_I(sizeof(struct genpointerlist));
74 newptrlist->object=object;
75 newptrlist->next=ht->bins[bin];
76 newptrlist->inext=NULL;
77 /* maintain linked list of ht entries for iteration*/
81 newptrlist->iprev=NULL;
83 ht->last->inext=newptrlist;
84 newptrlist->iprev=ht->last;
87 ht->bins[bin]=newptrlist;
89 if(ht->counter>ht->currentsize&&ht->currentsize!=INT_MAX) {
90 /* Expand hashtable */
91 long newcurrentsize=(ht->currentsize<(INT_MAX/2)) ? ht->currentsize*2 : INT_MAX;
92 long oldcurrentsize=ht->currentsize;
93 struct genpointerlist **newbins=(struct genpointerlist **) RUNMALLOC_I(sizeof (struct genpointerlist *)*newcurrentsize);
94 struct genpointerlist **oldbins=ht->bins;
96 for(j=0; j<newcurrentsize; j++) newbins[j]=NULL;
97 ht->currentsize=newcurrentsize;
98 for(i=0; i<oldcurrentsize; i++) {
99 struct genpointerlist * tmpptr=oldbins[i];
100 while(tmpptr!=NULL) {
101 unsigned int hashcode=genhashfunction(ht, tmpptr->src);
102 struct genpointerlist *nextptr=tmpptr->next;
103 tmpptr->next=newbins[hashcode];
104 newbins[hashcode]=tmpptr;
115 int hashsize(struct genhashtable *ht) {
119 void genrehash(struct genhashtable * ht) {
120 struct genpointerlist **newbins=(struct genpointerlist **) RUNMALLOC(sizeof (struct genpointerlist *)*ht->currentsize);
121 struct genpointerlist **oldbins=ht->bins;
124 for(i=0; i<ht->currentsize; i++) {
125 struct genpointerlist * tmpptr=oldbins[i];
126 while(tmpptr!=NULL) {
127 unsigned int hashcode=genhashfunction(ht, tmpptr->src);
128 struct genpointerlist *nextptr=tmpptr->next;
129 tmpptr->next=newbins[hashcode];
130 newbins[hashcode]=tmpptr;
138 void * gengettable(struct genhashtable *ht, void * key) {
139 struct genpointerlist * ptr=ht->bins[genhashfunction(ht,key)];
141 if (((ht->comp_function==NULL)&&(ptr->src==key))||((ht->comp_function!=NULL)&&(*ht->comp_function)(ptr->src,key)))
146 printf("XXXXXXXXX: COULDN'T FIND ENTRY FOR KEY %p\n",key);
151 void * getnext(struct genhashtable *ht, void * key) {
152 struct genpointerlist * ptr=ht->bins[genhashfunction(ht,key)];
154 if (((ht->comp_function==NULL)&&(ptr->src==key))||((ht->comp_function!=NULL)&&(*ht->comp_function)(ptr->src,key)))
155 if (ptr->inext!=NULL) {
156 return ptr->inext->src;
162 printf("XXXXXXXXX: COULDN'T FIND ENTRY FOR KEY %p...\n Likely concurrent removal--bad user!!!\n",key);
167 int gencontains(struct genhashtable *ht, void * key) {
168 struct genpointerlist * ptr=ht->bins[genhashfunction(ht,key)];
169 //printf("In gencontains2\n");fflush(NULL);
171 if (((ht->comp_function==NULL)&&(ptr->src==key))||((ht->comp_function!=NULL)&&(*ht->comp_function)(ptr->src,key)))
179 void genfreekey(struct genhashtable *ht, void * key) {
180 struct genpointerlist * ptr=ht->bins[genhashfunction(ht,key)];
182 if (((ht->comp_function==NULL)&&(ptr->src==key))||((ht->comp_function!=NULL)&&(*ht->comp_function)(ptr->src,key))) {
183 ht->bins[genhashfunction(ht,key)]=ptr->next;
191 if (ptr->iprev!=NULL)
192 ptr->iprev->inext=ptr->inext;
193 if (ptr->inext!=NULL)
194 ptr->inext->iprev=ptr->iprev;
200 while(ptr->next!=NULL) {
201 if (((ht->comp_function==NULL)&&(ptr->next->src==key))||((ht->comp_function!=NULL)&&(*ht->comp_function)(ptr->next->src,key))) {
202 struct genpointerlist *tmpptr=ptr->next;
203 ptr->next=tmpptr->next;
204 if (tmpptr==ht->list)
205 ht->list=tmpptr->inext;
206 if (tmpptr==ht->last)
207 ht->last=tmpptr->iprev;
208 if (tmpptr->iprev!=NULL)
209 tmpptr->iprev->inext=tmpptr->inext;
210 if (tmpptr->inext!=NULL)
211 tmpptr->inext->iprev=tmpptr->iprev;
219 printf("XXXXXXXXX: COULDN'T FIND ENTRY FOR KEY %p\n",key);
223 unsigned int genhashfunction(struct genhashtable *ht, void * key) {
224 if (ht->hash_function==NULL)
225 return ((long unsigned int)key) % ht->currentsize;
227 return ((*ht->hash_function)(key)) % ht->currentsize;
230 struct genhashtable * genallocatehashtable(unsigned int (*hash_function)(void *),int (*comp_function)(void *, void *)) {
231 struct genhashtable *ght;
232 struct genpointerlist **gpl;
236 raw_test_pass(0xf000);
239 gpl=(struct genpointerlist **) RUNMALLOC(sizeof(struct genpointerlist *)*geninitialnumbins);
241 raw_test_pass(0xf001);
243 for(i=0; i<geninitialnumbins; i++) {
247 raw_test_pass(0xf002);
249 ght=(struct genhashtable *) RUNMALLOC(sizeof(struct genhashtable));
251 raw_test_pass(0xf003);
253 ght->hash_function=hash_function;
254 ght->comp_function=comp_function;
255 ght->currentsize=geninitialnumbins;
261 raw_test_pass(0xf004);
266 void genfreehashtable(struct genhashtable * ht) {
268 for (i=0; i<ht->currentsize; i++) {
269 if (ht->bins[i]!=NULL) {
270 struct genpointerlist *genptr=ht->bins[i];
271 while(genptr!=NULL) {
272 struct genpointerlist *tmpptr=genptr->next;
282 struct geniterator * gengetiterator(struct genhashtable *ht) {
283 struct geniterator *gi=(struct geniterator*)RUNMALLOC(sizeof(struct geniterator));
288 void * gennext(struct geniterator *it) {
289 struct genpointerlist *curr=it->ptr;
292 if (it->finished&&(curr->inext==NULL))
298 if(curr->inext!=NULL)
301 it->finished=1; /* change offsetting scheme */
305 void genfreeiterator(struct geniterator *it) {