8 #include "GenericHashtable.h"
14 void * getfirstkey(struct genhashtable *ht) {
18 int genputtable(struct genhashtable *ht, void * key, void * object) {
19 unsigned int bin=genhashfunction(ht,key);
20 struct genpointerlist * newptrlist=(struct genpointerlist *) RUNMALLOC(sizeof(struct genpointerlist));
22 newptrlist->object=object;
23 newptrlist->next=ht->bins[bin];
24 newptrlist->inext=NULL;
25 /* maintain linked list of ht entries for iteration*/
29 newptrlist->iprev=NULL;
31 ht->last->inext=newptrlist;
32 newptrlist->iprev=ht->last;
35 ht->bins[bin]=newptrlist;
37 if(ht->counter>ht->currentsize&&ht->currentsize!=INT_MAX) {
38 /* Expand hashtable */
39 long newcurrentsize=(ht->currentsize<(INT_MAX/2))?ht->currentsize*2:INT_MAX;
40 long oldcurrentsize=ht->currentsize;
41 struct genpointerlist **newbins=(struct genpointerlist **) RUNMALLOC(sizeof (struct genpointerlist *)*newcurrentsize);
42 struct genpointerlist **oldbins=ht->bins;
44 for(j=0;j<newcurrentsize;j++) newbins[j]=NULL;
45 ht->currentsize=newcurrentsize;
46 for(i=0;i<oldcurrentsize;i++) {
47 struct genpointerlist * tmpptr=oldbins[i];
49 unsigned int hashcode=genhashfunction(ht, tmpptr->src);
50 struct genpointerlist *nextptr=tmpptr->next;
51 tmpptr->next=newbins[hashcode];
52 newbins[hashcode]=tmpptr;
62 int hashsize(struct genhashtable *ht) {
66 void genrehash(struct genhashtable * ht) {
67 struct genpointerlist **newbins=(struct genpointerlist **) RUNMALLOC(sizeof (struct genpointerlist *)*ht->currentsize);
68 struct genpointerlist **oldbins=ht->bins;
71 for(i=0;i<ht->currentsize;i++) {
72 struct genpointerlist * tmpptr=oldbins[i];
74 unsigned int hashcode=genhashfunction(ht, tmpptr->src);
75 struct genpointerlist *nextptr=tmpptr->next;
76 tmpptr->next=newbins[hashcode];
77 newbins[hashcode]=tmpptr;
85 void * gengettable(struct genhashtable *ht, void * key) {
86 struct genpointerlist * ptr=ht->bins[genhashfunction(ht,key)];
88 if (((ht->comp_function==NULL)&&(ptr->src==key))||((ht->comp_function!=NULL)&&(*ht->comp_function)(ptr->src,key)))
92 printf("XXXXXXXXX: COULDN'T FIND ENTRY FOR KEY %p\n",key);
96 void * getnext(struct genhashtable *ht, void * key) {
97 struct genpointerlist * ptr=ht->bins[genhashfunction(ht,key)];
99 if (((ht->comp_function==NULL)&&(ptr->src==key))||((ht->comp_function!=NULL)&&(*ht->comp_function)(ptr->src,key)))
100 if (ptr->inext!=NULL) {
101 return ptr->inext->src;
106 printf("XXXXXXXXX: COULDN'T FIND ENTRY FOR KEY %p...\n Likely concurrent removal--bad user!!!\n",key);
110 int gencontains(struct genhashtable *ht, void * key) {
111 struct genpointerlist * ptr=ht->bins[genhashfunction(ht,key)];
112 //printf("In gencontains2\n");fflush(NULL);
114 if (((ht->comp_function==NULL)&&(ptr->src==key))||((ht->comp_function!=NULL)&&(*ht->comp_function)(ptr->src,key)))
122 void genfreekey(struct genhashtable *ht, void * key) {
123 struct genpointerlist * ptr=ht->bins[genhashfunction(ht,key)];
125 if (((ht->comp_function==NULL)&&(ptr->src==key))||((ht->comp_function!=NULL)&&(*ht->comp_function)(ptr->src,key))) {
126 ht->bins[genhashfunction(ht,key)]=ptr->next;
134 if (ptr->iprev!=NULL)
135 ptr->iprev->inext=ptr->inext;
136 if (ptr->inext!=NULL)
137 ptr->inext->iprev=ptr->iprev;
143 while(ptr->next!=NULL) {
144 if (((ht->comp_function==NULL)&&(ptr->next->src==key))||((ht->comp_function!=NULL)&&(*ht->comp_function)(ptr->next->src,key))) {
145 struct genpointerlist *tmpptr=ptr->next;
146 ptr->next=tmpptr->next;
147 if (tmpptr==ht->list)
148 ht->list=tmpptr->inext;
149 if (tmpptr==ht->last)
150 ht->last=tmpptr->iprev;
151 if (tmpptr->iprev!=NULL)
152 tmpptr->iprev->inext=tmpptr->inext;
153 if (tmpptr->inext!=NULL)
154 tmpptr->inext->iprev=tmpptr->iprev;
161 printf("XXXXXXXXX: COULDN'T FIND ENTRY FOR KEY %p\n",key);
164 unsigned int genhashfunction(struct genhashtable *ht, void * key) {
165 if (ht->hash_function==NULL)
166 return ((long unsigned int)key) % ht->currentsize;
168 return ((*ht->hash_function)(key)) % ht->currentsize;
171 struct genhashtable * genallocatehashtable(unsigned int (*hash_function)(void *),int (*comp_function)(void *, void *)) {
172 struct genhashtable *ght=(struct genhashtable *) RUNMALLOC(sizeof(struct genhashtable));
173 struct genpointerlist **gpl=(struct genpointerlist **) RUNMALLOC(sizeof(struct genpointerlist *)*geninitialnumbins);
175 for(i=0;i<geninitialnumbins;i++)
177 ght->hash_function=hash_function;
178 ght->comp_function=comp_function;
179 ght->currentsize=geninitialnumbins;
187 void genfreehashtable(struct genhashtable * ht) {
189 for (i=0;i<ht->currentsize;i++) {
190 if (ht->bins[i]!=NULL) {
191 struct genpointerlist *genptr=ht->bins[i];
192 while(genptr!=NULL) {
193 struct genpointerlist *tmpptr=genptr->next;
203 struct geniterator * gengetiterator(struct genhashtable *ht) {
204 struct geniterator *gi=(struct geniterator*)RUNMALLOC(sizeof(struct geniterator));
209 void * gennext(struct geniterator *it) {
210 struct genpointerlist *curr=it->ptr;
213 if (it->finished&&(curr->inext==NULL))
219 if(curr->inext!=NULL)
222 it->finished=1; /* change offsetting scheme */
226 void genfreeiterator(struct geniterator *it) {