10 #include "GenericHashtable.h"
16 void * getfirstkey(struct genhashtable *ht) {
17 if(ht->list == NULL) {
23 int genputtable(struct genhashtable *ht, void * key, void * object) {
24 unsigned int bin=genhashfunction(ht,key);
25 struct genpointerlist * newptrlist=(struct genpointerlist *) RUNMALLOC(sizeof(struct genpointerlist));
27 newptrlist->object=object;
28 newptrlist->next=ht->bins[bin];
29 newptrlist->inext=NULL;
30 /* maintain linked list of ht entries for iteration*/
34 newptrlist->iprev=NULL;
36 ht->last->inext=newptrlist;
37 newptrlist->iprev=ht->last;
40 ht->bins[bin]=newptrlist;
42 if(ht->counter>ht->currentsize&&ht->currentsize!=INT_MAX) {
43 /* Expand hashtable */
44 long newcurrentsize=(ht->currentsize<(INT_MAX/2)) ? ht->currentsize*2 : INT_MAX;
45 long oldcurrentsize=ht->currentsize;
46 struct genpointerlist **newbins=(struct genpointerlist **) RUNMALLOC(sizeof (struct genpointerlist *)*newcurrentsize);
47 struct genpointerlist **oldbins=ht->bins;
49 for(j=0; j<newcurrentsize; j++) newbins[j]=NULL;
50 ht->currentsize=newcurrentsize;
51 for(i=0; i<oldcurrentsize; i++) {
52 struct genpointerlist * tmpptr=oldbins[i];
54 unsigned int hashcode=genhashfunction(ht, tmpptr->src);
55 struct genpointerlist *nextptr=tmpptr->next;
56 tmpptr->next=newbins[hashcode];
57 newbins[hashcode]=tmpptr;
68 int genputtable_I(struct genhashtable *ht, void * key, void * object) {
69 unsigned int bin=genhashfunction(ht,key);
70 struct genpointerlist * newptrlist=(struct genpointerlist *) RUNMALLOC_I(sizeof(struct genpointerlist));
72 newptrlist->object=object;
73 newptrlist->next=ht->bins[bin];
74 newptrlist->inext=NULL;
75 /* maintain linked list of ht entries for iteration*/
79 newptrlist->iprev=NULL;
81 ht->last->inext=newptrlist;
82 newptrlist->iprev=ht->last;
85 ht->bins[bin]=newptrlist;
87 if(ht->counter>ht->currentsize&&ht->currentsize!=INT_MAX) {
88 /* Expand hashtable */
89 long newcurrentsize=(ht->currentsize<(INT_MAX/2)) ? ht->currentsize*2 : INT_MAX;
90 long oldcurrentsize=ht->currentsize;
91 struct genpointerlist **newbins=(struct genpointerlist **) RUNMALLOC_I(sizeof (struct genpointerlist *)*newcurrentsize);
92 struct genpointerlist **oldbins=ht->bins;
94 for(j=0; j<newcurrentsize; j++) newbins[j]=NULL;
95 ht->currentsize=newcurrentsize;
96 for(i=0; i<oldcurrentsize; i++) {
97 struct genpointerlist * tmpptr=oldbins[i];
99 unsigned int hashcode=genhashfunction(ht, tmpptr->src);
100 struct genpointerlist *nextptr=tmpptr->next;
101 tmpptr->next=newbins[hashcode];
102 newbins[hashcode]=tmpptr;
113 int hashsize(struct genhashtable *ht) {
117 void genrehash(struct genhashtable * ht) {
118 struct genpointerlist **newbins=(struct genpointerlist **) RUNMALLOC(sizeof (struct genpointerlist *)*ht->currentsize);
119 struct genpointerlist **oldbins=ht->bins;
122 for(i=0; i<ht->currentsize; i++) {
123 struct genpointerlist * tmpptr=oldbins[i];
124 while(tmpptr!=NULL) {
125 unsigned int hashcode=genhashfunction(ht, tmpptr->src);
126 struct genpointerlist *nextptr=tmpptr->next;
127 tmpptr->next=newbins[hashcode];
128 newbins[hashcode]=tmpptr;
136 void * gengettable(struct genhashtable *ht, void * key) {
137 struct genpointerlist * ptr=ht->bins[genhashfunction(ht,key)];
139 if (((ht->comp_function==NULL)&&(ptr->src==key))||((ht->comp_function!=NULL)&&(*ht->comp_function)(ptr->src,key)))
144 printf("XXXXXXXXX: COULDN'T FIND ENTRY FOR KEY %p\n",key);
149 void * getnext(struct genhashtable *ht, void * key) {
150 struct genpointerlist * ptr=ht->bins[genhashfunction(ht,key)];
152 if (((ht->comp_function==NULL)&&(ptr->src==key))||((ht->comp_function!=NULL)&&(*ht->comp_function)(ptr->src,key)))
153 if (ptr->inext!=NULL) {
154 return ptr->inext->src;
160 printf("XXXXXXXXX: COULDN'T FIND ENTRY FOR KEY %p...\n Likely concurrent removal--bad user!!!\n",key);
165 int gencontains(struct genhashtable *ht, void * key) {
166 struct genpointerlist * ptr=ht->bins[genhashfunction(ht,key)];
167 //printf("In gencontains2\n");fflush(NULL);
169 if (((ht->comp_function==NULL)&&(ptr->src==key))||((ht->comp_function!=NULL)&&(*ht->comp_function)(ptr->src,key)))
177 void genfreekey(struct genhashtable *ht, void * key) {
178 struct genpointerlist * ptr=ht->bins[genhashfunction(ht,key)];
180 if (((ht->comp_function==NULL)&&(ptr->src==key))||((ht->comp_function!=NULL)&&(*ht->comp_function)(ptr->src,key))) {
181 ht->bins[genhashfunction(ht,key)]=ptr->next;
189 if (ptr->iprev!=NULL)
190 ptr->iprev->inext=ptr->inext;
191 if (ptr->inext!=NULL)
192 ptr->inext->iprev=ptr->iprev;
198 while(ptr->next!=NULL) {
199 if (((ht->comp_function==NULL)&&(ptr->next->src==key))||((ht->comp_function!=NULL)&&(*ht->comp_function)(ptr->next->src,key))) {
200 struct genpointerlist *tmpptr=ptr->next;
201 ptr->next=tmpptr->next;
202 if (tmpptr==ht->list)
203 ht->list=tmpptr->inext;
204 if (tmpptr==ht->last)
205 ht->last=tmpptr->iprev;
206 if (tmpptr->iprev!=NULL)
207 tmpptr->iprev->inext=tmpptr->inext;
208 if (tmpptr->inext!=NULL)
209 tmpptr->inext->iprev=tmpptr->iprev;
217 printf("XXXXXXXXX: COULDN'T FIND ENTRY FOR KEY %p\n",key);
221 unsigned int genhashfunction(struct genhashtable *ht, void * key) {
222 if (ht->hash_function==NULL)
223 return ((long unsigned int)key) % ht->currentsize;
225 return ((*ht->hash_function)(key)) % ht->currentsize;
228 struct genhashtable * genallocatehashtable(unsigned int (*hash_function)(void *),int (*comp_function)(void *, void *)) {
229 struct genhashtable *ght;
230 struct genpointerlist **gpl;
233 gpl=(struct genpointerlist **) RUNMALLOC(sizeof(struct genpointerlist *)*geninitialnumbins);
234 for(i=0; i<geninitialnumbins; i++) {
237 ght=(struct genhashtable *) RUNMALLOC(sizeof(struct genhashtable));
238 ght->hash_function=hash_function;
239 ght->comp_function=comp_function;
240 ght->currentsize=geninitialnumbins;
248 void genfreehashtable(struct genhashtable * ht) {
250 for (i=0; i<ht->currentsize; i++) {
251 if (ht->bins[i]!=NULL) {
252 struct genpointerlist *genptr=ht->bins[i];
253 while(genptr!=NULL) {
254 struct genpointerlist *tmpptr=genptr->next;
264 struct geniterator * gengetiterator(struct genhashtable *ht) {
265 struct geniterator *gi=(struct geniterator*)RUNMALLOC(sizeof(struct geniterator));
270 void * gennext(struct geniterator *it) {
271 struct genpointerlist *curr=it->ptr;
274 if (it->finished&&(curr->inext==NULL))
280 if(curr->inext!=NULL)
283 it->finished=1; /* change offsetting scheme */
287 void genfreeiterator(struct geniterator *it) {