1 : #include "aterm-map.hh"
2 :
3 : #include <iostream>
4 :
5 : #include <assert.h>
6 : #include <stdlib.h>
7 :
8 : #include <aterm2.h>
9 :
10 :
11 : namespace nix {
12 :
13 :
14 : static const unsigned int maxLoadFactor = /* 1 / */ 3;
15 : static unsigned int nrResizes = 0;
16 : static unsigned int sizeTotalAlloc = 0;
17 : static unsigned int sizeCurAlloc = 0;
18 : static unsigned int sizeMaxAlloc = 0;
19 :
20 :
21 11009 : ATermMap::ATermMap(unsigned int expectedCount)
22 : {
23 11009 : init(expectedCount);
24 11009 : }
25 :
26 :
27 646 : ATermMap::ATermMap(const ATermMap & map)
28 : {
29 646 : init(map.maxCount);
30 646 : copy(map.hashTable, map.capacity);
31 646 : }
32 :
33 :
34 0 : ATermMap & ATermMap::operator = (const ATermMap & map)
35 : {
36 0 : if (this == &map) return *this;
37 0 : free();
38 0 : init(map.maxCount);
39 0 : copy(map.hashTable, map.capacity);
40 0 : return *this;
41 : }
42 :
43 :
44 11655 : ATermMap::~ATermMap()
45 : {
46 11655 : free();
47 11655 : }
48 :
49 :
50 11655 : void ATermMap::init(unsigned int expectedCount)
51 : {
52 : assert(sizeof(ATerm) * 2 == sizeof(KeyValue));
53 11655 : capacity = 0;
54 11655 : count = 0;
55 11655 : maxCount = 0;
56 11655 : hashTable = 0;
57 11655 : resizeTable(expectedCount);
58 11655 : }
59 :
60 :
61 11655 : void ATermMap::free()
62 : {
63 11655 : if (hashTable) {
64 11655 : ATunprotectArray((ATerm *) hashTable);
65 11655 : ::free(hashTable);
66 11655 : sizeCurAlloc -= sizeof(KeyValue) * capacity;
67 11655 : hashTable = 0;
68 : }
69 11655 : }
70 :
71 :
72 11687 : static unsigned int roundToPowerOf2(unsigned int x)
73 : {
74 11687 : x--;
75 11687 : x |= x >> 1; x |= x >> 2; x |= x >> 4; x |= x >> 8; x |= x >> 16;
76 11687 : x++;
77 11687 : return x;
78 : }
79 :
80 :
81 11687 : void ATermMap::resizeTable(unsigned int expectedCount)
82 : {
83 11687 : if (expectedCount == 0) expectedCount = 1;
84 : // cout << maxCount << " -> " << expectedCount << endl;
85 : // cout << maxCount << " " << size << endl;
86 : // cout << (double) size / maxCount << endl;
87 :
88 11687 : unsigned int oldCapacity = capacity;
89 11687 : KeyValue * oldHashTable = hashTable;
90 :
91 11687 : maxCount = expectedCount;
92 11687 : capacity = roundToPowerOf2(maxCount * maxLoadFactor);
93 11687 : hashTable = (KeyValue *) calloc(sizeof(KeyValue), capacity);
94 11687 : sizeTotalAlloc += sizeof(KeyValue) * capacity;
95 11687 : sizeCurAlloc += sizeof(KeyValue) * capacity;
96 11687 : if (sizeCurAlloc > sizeMaxAlloc) sizeMaxAlloc = sizeCurAlloc;
97 11687 : ATprotectArray((ATerm *) hashTable, capacity * 2);
98 :
99 : // cout << capacity << endl;
100 :
101 : /* Re-hash the elements in the old table. */
102 11687 : if (oldCapacity != 0) {
103 32 : count = 0;
104 32 : copy(oldHashTable, oldCapacity);
105 32 : ATunprotectArray((ATerm *) oldHashTable);
106 32 : ::free(oldHashTable);
107 32 : sizeCurAlloc -= sizeof(KeyValue) * oldCapacity;
108 32 : nrResizes++;
109 : }
110 11687 : }
111 :
112 :
113 678 : void ATermMap::copy(KeyValue * elements, unsigned int capacity)
114 : {
115 334630 : for (unsigned int i = 0; i < capacity; ++i)
116 333952 : if (elements[i].value) /* i.e., non-empty, non-deleted element */
117 36014 : set(elements[i].key, elements[i].value);
118 678 : }
119 :
120 :
121 : /* !!! use a bigger shift for 64-bit platforms? */
122 : static const unsigned int shift = 16;
123 : static const unsigned long knuth = (unsigned long) (0.6180339887 * (1 << shift));
124 :
125 :
126 162012 : unsigned long ATermMap::hash1(ATerm key) const
127 : {
128 : /* Don't care about the least significant bits of the ATerm
129 : pointer since they're always 0. */
130 162012 : unsigned long key2 = ((unsigned long) key) >> 2;
131 :
132 : /* Approximately equal to:
133 : double d = key2 * 0.6180339887;
134 : unsigned int h = (int) (capacity * (d - floor(d)));
135 : */
136 :
137 162012 : unsigned long h = (capacity * ((key2 * knuth) & ((1 << shift) - 1))) >> shift;
138 :
139 162012 : return h;
140 : }
141 :
142 :
143 4336 : unsigned long ATermMap::hash2(ATerm key) const
144 : {
145 4336 : unsigned long key2 = ((unsigned long) key) >> 2;
146 : /* Note: the result must be relatively prime to `capacity' (which
147 : is a power of 2), so we make sure that the result is always
148 : odd. */
149 4336 : unsigned long h = ((key2 * 134217689) & (capacity - 1)) | 1;
150 4336 : return h;
151 : }
152 :
153 :
154 : static unsigned int nrItemsSet = 0;
155 : static unsigned int nrSetProbes = 0;
156 :
157 :
158 105991 : void ATermMap::set(ATerm key, ATerm value)
159 : {
160 105991 : if (count == maxCount) resizeTable(capacity * 2 / maxLoadFactor);
161 :
162 105991 : nrItemsSet++;
163 108229 : for (unsigned int i = 0, h = hash1(key); i < capacity;
164 : ++i, h = (h + hash2(key)) & (capacity - 1))
165 : {
166 : // assert(h < capacity);
167 108229 : nrSetProbes++;
168 : /* Note: to see whether a slot is free, we check
169 : hashTable[h].value, not hashTable[h].key, since we use
170 : value == 0 to mark deleted slots. */
171 108229 : if (hashTable[h].value == 0 || hashTable[h].key == key) {
172 105991 : if (hashTable[h].value == 0) count++;
173 105991 : hashTable[h].key = key;
174 105991 : hashTable[h].value = value;
175 : return;
176 : }
177 : }
178 :
179 0 : abort();
180 : }
181 :
182 :
183 : static unsigned int nrItemsGet = 0;
184 : static unsigned int nrGetProbes = 0;
185 :
186 :
187 55714 : ATerm ATermMap::get(ATerm key) const
188 : {
189 55714 : nrItemsGet++;
190 57812 : for (unsigned int i = 0, h = hash1(key); i < capacity;
191 : ++i, h = (h + hash2(key)) & (capacity - 1))
192 : {
193 57812 : nrGetProbes++;
194 57812 : if (hashTable[h].key == 0) return 0;
195 29203 : if (hashTable[h].key == key) return hashTable[h].value;
196 : }
197 0 : return 0;
198 : }
199 :
200 :
201 307 : void ATermMap::remove(ATerm key)
202 : {
203 307 : for (unsigned int i = 0, h = hash1(key); i < capacity;
204 : ++i, h = (h + hash2(key)) & (capacity - 1))
205 : {
206 307 : if (hashTable[h].key == 0) return;
207 307 : if (hashTable[h].key == key) {
208 307 : if (hashTable[h].value != 0) {
209 307 : hashTable[h].value = 0;
210 307 : count--;
211 : }
212 307 : return;
213 : }
214 : }
215 : }
216 :
217 :
218 2287 : unsigned int ATermMap::size()
219 : {
220 2287 : return count; /* STL nomenclature */
221 : }
222 :
223 :
224 0 : void printATermMapStats()
225 : {
226 : using std::cerr;
227 : using std::endl;
228 :
229 : cerr << "RESIZES: " << nrResizes << " "
230 : << sizeTotalAlloc << " "
231 : << sizeCurAlloc << " "
232 0 : << sizeMaxAlloc << endl;
233 :
234 : cerr << "SET: "
235 : << nrItemsSet << " "
236 : << nrSetProbes << " "
237 0 : << (double) nrSetProbes / nrItemsSet << endl;
238 :
239 : cerr << "GET: "
240 : << nrItemsGet << " "
241 : << nrGetProbes << " "
242 0 : << (double) nrGetProbes / nrItemsGet << endl;
243 0 : }
244 :
245 :
246 : #if 0
247 : int main(int argc, char * * argv)
248 : {
249 : ATerm bottomOfStack;
250 : ATinit(argc, argv, &bottomOfStack);
251 :
252 : /* Make test terms. */
253 : int nrTestTerms = 100000;
254 : ATerm testTerms[nrTestTerms];
255 :
256 : for (int i = 0; i < nrTestTerms; ++i) {
257 : char name[10];
258 : sprintf(name, "%d", (int) random() % 37);
259 :
260 : int arity = i == 0 ? 0 : (random() % 37);
261 : ATerm kids[arity];
262 : for (int j = 0; j < arity; ++j)
263 : kids[j] = testTerms[random() % i];
264 :
265 : testTerms[i] = (ATerm) ATmakeApplArray(ATmakeAFun(name, arity, ATfalse), kids);
266 : // ATwriteToSharedTextFile(testTerms[i], stdout);
267 : // printf("\n");
268 : }
269 :
270 :
271 : cout << "testing...\n";
272 :
273 :
274 : #define someTerm() (testTerms[(int) random() % nrTestTerms])
275 :
276 :
277 : for (int test = 0; test < 100000; ++test) {
278 : //cerr << test << endl;
279 : unsigned int n = 300;
280 : ATermMap map(300);
281 : ATerm keys[n], values[n];
282 : for (unsigned int i = 0; i < n; ++i) {
283 : keys[i] = someTerm();
284 : values[i] = someTerm();
285 : map.set(keys[i], values[i]);
286 : //cerr << "INSERT: " << keys[i] << " " << values[i] << endl;
287 : }
288 :
289 : unsigned int size = map.size();
290 : assert(size <= n);
291 : values[n - 1] = 0;
292 : map.remove(keys[n - 1]);
293 : assert(map.size() == size - 1);
294 :
295 : unsigned int checksum;
296 : unsigned int count = 0;
297 : for (ATermMap::const_iterator i = map.begin(); i != map.end(); ++i, ++count) {
298 : assert(i->key);
299 : assert(i->value);
300 : checksum += (unsigned int) (*i).key;
301 : checksum += (unsigned int) (*i).value;
302 : // cout << (*i).key << " " << (*i).value << endl;
303 : }
304 : assert(count == size - 1);
305 :
306 : for (unsigned int i = 0; i < n; ++i) {
307 : for (unsigned int j = i + 1; j < n; ++j)
308 : if (keys[i] == keys[j]) goto x;
309 : if (map.get(keys[i]) != values[i]) {
310 : cerr << "MISMATCH: " << keys[i] << " " << values[i] << " " << map.get(keys[i]) << " " << i << endl;
311 : abort();
312 : }
313 : if (values[i] != 0) {
314 : checksum -= (unsigned int) keys[i];
315 : checksum -= (unsigned int) values[i];
316 : }
317 : x: ;
318 : }
319 :
320 : assert(checksum == 0);
321 :
322 : for (unsigned int i = 0; i < 100; ++i)
323 : map.get(someTerm());
324 :
325 : }
326 :
327 : printATermMapStats();
328 : }
329 : #endif
330 :
331 :
332 478 : }
|
