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