Changeset 793 for cpp/frams/util/hashtable.cpp
 Timestamp:
 05/29/18 16:51:14 (5 years ago)
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

cpp/frams/util/hashtable.cpp
r348 r793 7 7 int HashTable::hash(const SString &s) 8 8 { 9 return s.hash()&0x7fffffff;9 return s.hash() & 0x7fffffff; 10 10 } 11 11 12 void HashTable::init(int initsize, float lo)12 void HashTable::init(int initsize, float lo) 13 13 { 14 size=initsize;15 load=lo;16 threshold=(int)(load*(float)size);17 tab=(HashEntry**)calloc(size,sizeof(HashEntry*));18 count=0;19 sync=0;14 size = initsize; 15 load = lo; 16 threshold = (int)(load*(float)size); 17 tab = (HashEntry**)calloc(size, sizeof(HashEntry*)); 18 count = 0; 19 sync = 0; 20 20 } 21 21 22 22 void HashTable::rehash(int newsize) 23 23 { 24 if (newsize==size) return;25 HashEntry **newtab=(HashEntry**)calloc(newsize,sizeof(HashEntry*));26 HashEntry **te=tab,*e,*ne;27 int i;28 for (int s=size;s>0;s,te++)29 for (e=*te;e;)30 {31 ne=e; e=e>next;32 i=ne>hash%newsize;33 ne>next=newtab[i];34 newtab[i]=ne;35 }36 free(tab);37 tab=newtab;38 size=newsize;39 threshold=int(load*(float)size);40 sync++;24 if (newsize == size) return; 25 HashEntry **newtab = (HashEntry**)calloc(newsize, sizeof(HashEntry*)); 26 HashEntry **te = tab, *e, *ne; 27 int i; 28 for (int s = size; s > 0; s, te++) 29 for (e = *te; e;) 30 { 31 ne = e; e = e>next; 32 i = ne>hash%newsize; 33 ne>next = newtab[i]; 34 newtab[i] = ne; 35 } 36 free(tab); 37 tab = newtab; 38 size = newsize; 39 threshold = int(load*(float)size); 40 sync++; 41 41 } 42 42 43 43 void HashTable::clear() 44 44 { 45 HashEntry *e,**te,*next;46 int n;47 for (n=size,te=tab;n>0;n,te++)48 for (e=*te;e;e=next)45 HashEntry *e, **te, *next; 46 int n; 47 for (n = size, te = tab; n > 0; n, te++) 48 for (e = *te; e; e = next) 49 49 { 50 next =e>next;50 next = e>next; 51 51 delete e; 52 52 } 53 if (tab) free(tab);54 tab=0; size=0;55 sync++;53 if (tab) free(tab); 54 tab = 0; size = 0; 55 sync++; 56 56 } 57 57 58 58 HashTable::~HashTable() 59 59 { 60 clear();60 clear(); 61 61 } 62 62 63 void* HashTable::put(const SString& key, void *value)63 void* HashTable::put(const SString& key, void *value) 64 64 { 65 int h=hash(key); 66 int i=h%size; 67 for (HashEntry *e=tab[i];e;e=e>next) 68 { 69 if (e>key==key) 65 int h = hash(key); 66 int i = h%size; 67 for (HashEntry *e = tab[i]; e; e = e>next) 70 68 { 71 void *v=e>value; 72 e>value=value; 73 return v; 69 if (e>key == key) 70 { 71 void *v = e>value; 72 e>value = value; 73 return v; 74 } 74 75 } 75 } 76 if (count>=threshold) { rehash(2*size+1); i=h%size; } 77 HashEntry *e=new HashEntry(h,key,value); 78 e>next=tab[i]; 79 tab[i]=e; 80 count++; 81 sync++; 82 return 0; 76 if (count >= threshold) { rehash(2 * size + 1); i = h%size; } 77 HashEntry *e = new HashEntry(h, key, value); 78 e>next = tab[i]; 79 tab[i] = e; 80 count++; 81 sync++; 82 return 0; 83 83 } 84 84 85 85 void* HashTable::remove(const SString& key) 86 86 { 87 int i=hash(key)%size; 88 HashEntry **ptr=tab+i,*e; 89 for (;e=*ptr;ptr=&e>next) 90 { 91 if (e>key==key) 87 int i = hash(key) % size; 88 HashEntry **ptr = tab + i, *e; 89 for (; e = *ptr; ptr = &e>next) 92 90 { 93 *ptr=e>next; 94 void *v=e>value; 95 delete e; 96 count; 97 sync++; 98 return v; 91 if (e>key == key) 92 { 93 *ptr = e>next; 94 void *v = e>value; 95 delete e; 96 count; 97 sync++; 98 return v; 99 } 99 100 } 100 } 101 return 0; 101 return 0; 102 102 } 103 103 104 104 void* HashTable::remove(HashEntryIterator& it) 105 105 { 106 if (!it.entry) return 0; 107 HashEntry **ptr=tab+it.hashindex,*e; 108 for (;e=*ptr;ptr=&e>next) 109 { 110 if (e == it.entry) 106 if (!it.entry) return 0; 107 HashEntry **ptr = tab + it.hashindex, *e; 108 for (; e = *ptr; ptr = &e>next) 111 109 { 112 it++; 113 *ptr=e>next; 114 void *v=e>value; 115 delete e; 116 count; 117 sync++; 118 it.sync++; 119 return v; 110 if (e == it.entry) 111 { 112 it++; 113 *ptr = e>next; 114 void *v = e>value; 115 delete e; 116 count; 117 sync++; 118 it.sync++; 119 return v; 120 } 120 121 } 121 } 122 return NULL; 122 return NULL; 123 123 } 124 124 125 void* HashTable::get(const SString& key, int *reallygot)125 void* HashTable::get(const SString& key, int *reallygot) 126 126 { 127 int i=hash(key)%size;128 for (HashEntry *e=tab[i];e;e=e>next)129 if (e>key==key) {if (reallygot) *reallygot=1; return e>value;}130 return 0;127 int i = hash(key) % size; 128 for (HashEntry *e = tab[i]; e; e = e>next) 129 if (e>key == key) { if (reallygot) *reallygot = 1; return e>value; } 130 return 0; 131 131 } 132 132 … … 135 135 void HashEntryIterator::findNext() 136 136 { 137 while (hashindex < (ht>size1))137 while (hashindex < (ht>size  1)) 138 138 { 139 hashindex++;140 if (entry=ht>tab[hashindex]) return;139 hashindex++; 140 if (entry = ht>tab[hashindex]) return; 141 141 } 142 142 } … … 145 145 void HashEntryIterator::operator++() 146 146 { 147 if (entry) entry=entry>next;148 if (!entry) findNext();147 if (entry) entry = entry>next; 148 if (!entry) findNext(); 149 149 } 150 150 … … 153 153 void HashTable::debugprint() 154 154 { 155 printf("HashTable: %d/%d (max %d)\n",count,size,threshold);156 HashEntry *e,**te;157 int n;158 for (n=0,te=tab;n<size;n++,te++)159 if (e=*te)160 {161 printf(" %d:",n);162 for (;e;e=e>next)163 printf(" (%x)%s=%p",e>hash,e>key.c_str(),e>value);164 printf("\n");165 }155 printf("HashTable: %d/%d (max %d)\n", count, size, threshold); 156 HashEntry *e, **te; 157 int n; 158 for (n = 0, te = tab; n < size; n++, te++) 159 if (e = *te) 160 { 161 printf(" %d:", n); 162 for (; e; e = e>next) 163 printf(" (%x)%s=%p", e>hash, e>key.c_str(), e>value); 164 printf("\n"); 165 } 166 166 } 167 167 … … 171 171 stats[2]=avg keys in bucket 172 172 stats[3]=max keys in bucket 173 173 */ 174 174 void HashTable::getstats(float *stats) 175 175 { 176 HashEntry *e,**te;177 int used=0, ma=0, mi=count;178 int c,n;179 for (n=size,te=tab;n>0;n,te++)176 HashEntry *e, **te; 177 int used = 0, ma = 0, mi = count; 178 int c, n; 179 for (n = size, te = tab; n > 0; n, te++) 180 180 { 181 c=0;182 for (e=*te;e;e=e>next) c++;183 if (c>ma) ma=c;184 if ((c<mi)&&(c>0)) mi=c;185 if (c>0) used++;181 c = 0; 182 for (e = *te; e; e = e>next) c++; 183 if (c > ma) ma = c; 184 if ((c < mi) && (c>0)) mi = c; 185 if (c > 0) used++; 186 186 } 187 stats[0]=(float)used;188 stats[1]=(float)((mi==count)?0:mi);189 stats[2]=(float)count/(float)used;190 stats[3]=(float)ma;187 stats[0] = (float)used; 188 stats[1] = (float)((mi == count) ? 0 : mi); 189 stats[2] = (float)count / (float)used; 190 stats[3] = (float)ma; 191 191 }
Note: See TracChangeset
for help on using the changeset viewer.