1 | // This file is a part of Framsticks SDK. http://www.framsticks.com/ |
---|
2 | // Copyright (C) 1999-2015 Maciej Komosinski and Szymon Ulatowski. |
---|
3 | // See LICENSE.txt for details. |
---|
4 | |
---|
5 | #include "hashtable.h" |
---|
6 | |
---|
7 | int HashTable::hash(const SString &s) |
---|
8 | { |
---|
9 | return s.hash()&0x7fffffff; |
---|
10 | } |
---|
11 | |
---|
12 | void HashTable::init(int initsize,float lo) |
---|
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; |
---|
20 | } |
---|
21 | |
---|
22 | void HashTable::rehash(int newsize) |
---|
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++; |
---|
41 | } |
---|
42 | |
---|
43 | void HashTable::clear() |
---|
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) |
---|
49 | { |
---|
50 | next=e->next; |
---|
51 | delete e; |
---|
52 | } |
---|
53 | if (tab) free(tab); |
---|
54 | tab=0; size=0; |
---|
55 | sync++; |
---|
56 | } |
---|
57 | |
---|
58 | HashTable::~HashTable() |
---|
59 | { |
---|
60 | clear(); |
---|
61 | } |
---|
62 | |
---|
63 | void* HashTable::put(const SString& key,void *value) |
---|
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) |
---|
70 | { |
---|
71 | void *v=e->value; |
---|
72 | e->value=value; |
---|
73 | return v; |
---|
74 | } |
---|
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; |
---|
83 | } |
---|
84 | |
---|
85 | void* HashTable::remove(const SString& key) |
---|
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) |
---|
92 | { |
---|
93 | *ptr=e->next; |
---|
94 | void *v=e->value; |
---|
95 | delete e; |
---|
96 | count--; |
---|
97 | sync++; |
---|
98 | return v; |
---|
99 | } |
---|
100 | } |
---|
101 | return 0; |
---|
102 | } |
---|
103 | |
---|
104 | void* HashTable::remove(HashEntryIterator& it) |
---|
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) |
---|
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 | } |
---|
121 | } |
---|
122 | return NULL; |
---|
123 | } |
---|
124 | |
---|
125 | void* HashTable::get(const SString& key,int *reallygot) |
---|
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; |
---|
131 | } |
---|
132 | |
---|
133 | ///////// |
---|
134 | |
---|
135 | void HashEntryIterator::findNext() |
---|
136 | { |
---|
137 | while (hashindex < (ht->size-1)) |
---|
138 | { |
---|
139 | hashindex++; |
---|
140 | if (entry=ht->tab[hashindex]) return; |
---|
141 | } |
---|
142 | } |
---|
143 | |
---|
144 | |
---|
145 | void HashEntryIterator::operator++() |
---|
146 | { |
---|
147 | if (entry) entry=entry->next; |
---|
148 | if (!entry) findNext(); |
---|
149 | } |
---|
150 | |
---|
151 | ////////////////////////// |
---|
152 | |
---|
153 | void HashTable::debugprint() |
---|
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 | } |
---|
166 | } |
---|
167 | |
---|
168 | /** |
---|
169 | stats[0]=buckets used |
---|
170 | stats[1]=min keys in bucket |
---|
171 | stats[2]=avg keys in bucket |
---|
172 | stats[3]=max keys in bucket |
---|
173 | */ |
---|
174 | void HashTable::getstats(float *stats) |
---|
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++) |
---|
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++; |
---|
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; |
---|
191 | } |
---|