Branch data Line data Source code
1 : : // $Id: Dict.cc 6219 2008-10-01 05:39:07Z vern $
2 : : //
3 : : // See the file "COPYING" in the main distribution directory for copyright.
4 : :
5 : : #include "config.h"
6 : :
7 : : #ifdef HAVE_MEMORY_H
8 : : #include <memory.h>
9 : : #endif
10 : :
11 : : #include "Dict.h"
12 : :
13 : : // If the mean bucket length exceeds the following then Insert() will
14 : : // increase the size of the hash table.
15 : : #define DEFAULT_DENSITY_THRESH 3.0
16 : :
17 : : // Threshold above which we do not try to ensure that the hash size
18 : : // is prime.
19 : : #define PRIME_THRESH 1000
20 : :
21 : : class DictEntry {
22 : : public:
23 : 46104 : DictEntry(void* k, int l, hash_t h, void* val)
24 : 46104 : { key = k; len = l; hash = h; value = val; }
25 : :
26 : 32013 : ~DictEntry()
27 : : {
28 [ + + ]: 32013 : delete [] (char*) key;
29 : 32013 : }
30 : :
31 : : void* key;
32 : : int len;
33 : : hash_t hash;
34 : : void* value;
35 : : };
36 : :
37 : : // The value of an iteration cookie is the bucket and offset within the
38 : : // bucket at which to start looking for the next value to return.
39 : 9767 : class IterCookie {
40 : : public:
41 : 9767 : IterCookie(int b, int o)
42 : 9767 : {
43 : 9767 : bucket = b;
44 : 9767 : offset = o;
45 : 9767 : ttbl = 0;
46 : 9767 : num_buckets_p = 0;
47 : 9767 : }
48 : :
49 : : int bucket, offset;
50 : : PList(DictEntry)** ttbl;
51 : : const int* num_buckets_p;
52 : : PList(DictEntry) inserted; // inserted while iterating
53 : : };
54 : :
55 : 17252 : Dictionary::Dictionary(dict_order ordering, int initial_size)
56 : : {
57 : 17252 : Init(initial_size);
58 : 17252 : tbl2 = 0;
59 : :
60 [ # # + + ]: 17252 : if ( ordering == ORDERED )
61 : 1128 : order = new PList(DictEntry);
62 : : else
63 : 16124 : order = 0;
64 : :
65 : 17252 : SetDensityThresh(DEFAULT_DENSITY_THRESH);
66 : :
67 : 17252 : delete_func = 0;
68 : 17252 : }
69 : :
70 : 14147 : Dictionary::~Dictionary()
71 : : {
72 [ # # ][ # # ]: 254916 : for ( int i = 0; i < num_buckets; ++i )
[ + + ]
73 [ # # ][ # # ]: 240769 : if ( tbl[i] )
[ + + ]
74 : : {
75 : 18570 : PList(DictEntry)* chain = tbl[i];
76 [ # # ][ # # ]: 46993 : loop_over_list(*chain, j)
[ + + ]
77 : : {
78 : 28423 : DictEntry* e = (*chain)[j];
79 [ # # # # + : 28423 : if ( delete_func )
+ ]
80 : 28025 : delete_func(e->value);
81 [ # # ][ # # ]: 28423 : delete e;
[ + - ]
82 : : }
83 : :
84 [ # # ][ # # ]: 18570 : delete chain;
[ + - ]
85 : : }
86 : :
87 [ # # ][ # # ]: 14147 : delete [] tbl;
[ + - ]
88 [ # # ][ # # ]: 14147 : delete order;
[ - + ]
89 : :
90 [ # # ][ # # ]: 14147 : if ( tbl2 == 0 )
[ + + ]
91 : 14147 : return;
92 : :
93 [ # # ][ # # ]: 114 : for ( int i = 0; i < num_buckets2; ++i )
[ + + ]
94 [ # # ][ # # ]: 111 : if ( tbl2[i] )
[ + + ]
95 : : {
96 : 58 : PList(DictEntry)* chain = tbl2[i];
97 [ # # ][ # # ]: 145 : loop_over_list(*chain, j)
[ + + ]
98 : : {
99 : 87 : DictEntry* e = (*chain)[j];
100 [ # # # # + : 87 : if ( delete_func )
- ]
101 : 87 : delete_func(e->value);
102 [ # # ][ # # ]: 87 : delete e;
[ + - ]
103 : : }
104 : :
105 [ # # ][ # # ]: 58 : delete chain;
[ + - ]
106 : : }
107 [ # # ][ # # ]: 3 : delete [] tbl2;
[ + - ]
108 [ # # ][ # # ]: 28294 : }
[ # # ][ # # ]
[ + + ][ - + ]
109 : :
110 : 191810 : void* Dictionary::Lookup(const void* key, int key_size, hash_t hash) const
111 : : {
112 : : hash_t h;
113 : : PList(DictEntry)* chain;
114 : :
115 : : // Figure out which hash table to look in.
116 : 191810 : h = hash % num_buckets;
117 [ + + ][ + + ]: 191810 : if ( ! tbl2 || h >= tbl_next_ind )
118 : 188447 : chain = tbl[h];
119 : : else
120 : 3363 : chain = tbl2[hash % num_buckets2];
121 : :
122 [ + + ]: 191810 : if ( chain )
123 : : {
124 [ + + ]: 333899 : for ( int i = 0; i < chain->length(); ++i )
125 : : {
126 : 283828 : DictEntry* entry = (*chain)[i];
127 : :
128 [ + + + - ]: 283828 : if ( entry->hash == hash && entry->len == key_size &&
[ + - ]
129 : : ! memcmp(key, entry->key, key_size) )
130 : 101941 : return entry->value;
131 : : }
132 : : }
133 : :
134 : 191810 : return 0;
135 : : }
136 : :
137 : : void* Dictionary::Insert(void* key, int key_size, hash_t hash, void* val,
138 : 46104 : int copy_key)
139 : : {
140 : 46104 : DictEntry* new_entry = new DictEntry(key, key_size, hash, val);
141 : 46104 : void* old_val = Insert(new_entry, copy_key);
142 : :
143 [ + + ]: 46104 : if ( old_val )
144 : : {
145 : : // We didn't need the new DictEntry, the key was already
146 : : // present.
147 [ + - ]: 111 : delete new_entry;
148 : : }
149 [ + + ]: 45993 : else if ( order )
150 : 8932 : order->append(new_entry);
151 : :
152 : : // Resize logic.
153 [ + + ]: 46104 : if ( tbl2 )
154 : 1112 : MoveChains();
155 [ + + ]: 44992 : else if ( num_entries >= thresh_entries )
156 : 55 : StartChangeSize(num_buckets * 2 + 1);
157 : :
158 : 46104 : return old_val;
159 : : }
160 : :
161 : : void* Dictionary::Remove(const void* key, int key_size, hash_t hash,
162 : 10729 : bool dont_delete)
163 : : {
164 : : hash_t h;
165 : : PList(DictEntry)* chain;
166 : : int* num_entries_ptr;
167 : :
168 : : // Figure out which hash table to look in
169 : 10729 : h = hash % num_buckets;
170 [ + + ][ + + ]: 10729 : if ( ! tbl2 || h >= tbl_next_ind )
171 : : {
172 : 10698 : chain = tbl[h];
173 : 10698 : num_entries_ptr = &num_entries;
174 : : }
175 : : else
176 : : {
177 : 31 : chain = tbl2[hash % num_buckets2];
178 : 31 : num_entries_ptr = &num_entries2;
179 : : }
180 : :
181 [ + + ]: 10729 : if ( ! chain )
182 : 4956 : return 0;
183 : :
184 [ + + ]: 10533 : for ( int i = 0; i < chain->length(); ++i )
185 : : {
186 : 8152 : DictEntry* entry = (*chain)[i];
187 : :
188 [ + + + - ]: 8152 : if ( entry->hash == hash && entry->len == key_size &&
[ + - ]
189 : : ! memcmp(key, entry->key, key_size) )
190 : : {
191 : 3392 : void* entry_value = DoRemove(entry, h, chain, i);
192 : :
193 [ + + ]: 3392 : if ( dont_delete )
194 : 676 : entry->key = 0;
195 : :
196 [ + - ]: 3392 : delete entry;
197 : 3392 : --*num_entries_ptr;
198 : 3392 : return entry_value;
199 : : }
200 : : }
201 : :
202 : 10729 : return 0;
203 : : }
204 : :
205 : : void* Dictionary::DoRemove(DictEntry* entry, hash_t h,
206 : 3392 : PList(DictEntry)* chain, int chain_offset)
207 : : {
208 : 3392 : void* entry_value = entry->value;
209 : :
210 : 3392 : chain->remove_nth(chain_offset);
211 [ - + ]: 3392 : if ( order )
212 : 0 : order->remove(entry);
213 : :
214 : : // Adjust existing cookies.
215 [ + + ]: 3526 : loop_over_list(cookies, i)
216 : : {
217 : 134 : IterCookie* c = cookies[i];
218 : :
219 : : // Is the affected bucket the current one?
220 [ + - ]: 134 : if ( (unsigned int) c->bucket == h )
221 : : {
222 [ + - ]: 134 : if ( c->offset > chain_offset )
223 : 134 : --c->offset;
224 : :
225 : : // The only other important case here occurs when we
226 : : // are deleting the current entry which
227 : : // simultaniously happens to be the last one in this
228 : : // bucket. This means that we would have to move on
229 : : // to the next non-empty bucket. Fortunately,
230 : : // NextEntry() will do exactly the right thing in
231 : : // this case. :-)
232 : : }
233 : :
234 : : // This item may have been inserted during this iteration.
235 [ - + ]: 134 : if ( (unsigned int) c->bucket > h )
236 : 0 : c->inserted.remove(entry);
237 : : }
238 : :
239 : 3392 : return entry_value;
240 : : }
241 : :
242 : 0 : void* Dictionary::NthEntry(int n, const void*& key, int& key_len) const
243 : : {
244 [ # # ][ # # ]: 0 : if ( ! order || n < 0 || n >= Length() )
[ # # ][ # # ]
245 : 0 : return 0;
246 : :
247 : 0 : DictEntry* entry = (*order)[n];
248 : 0 : key = entry->key;
249 : 0 : key_len = entry->len;
250 : 0 : return entry->value;
251 : : }
252 : :
253 : 9767 : IterCookie* Dictionary::InitForIteration() const
254 : : {
255 : 9767 : return new IterCookie(0, 0);
256 : : }
257 : :
258 : 0 : void Dictionary::StopIteration(IterCookie* cookie) const
259 : : {
260 [ # # ]: 0 : delete cookie;
261 : 0 : }
262 : :
263 : 23532 : void* Dictionary::NextEntry(HashKey*& h, IterCookie*& cookie, int return_hash) const
264 : : {
265 : : // If there are any inserted entries, return them first.
266 : : // That keeps the list small and helps avoiding searching
267 : : // a large list when deleting an entry.
268 : :
269 : : DictEntry* entry;
270 : :
271 [ - + ]: 23532 : if ( cookie->inserted.length() )
272 : : {
273 : : // Return the last one. Order doesn't matter,
274 : : // and removing from the tail is cheaper.
275 : 0 : entry = cookie->inserted.remove_nth(cookie->inserted.length()-1);
276 [ # # ]: 0 : if ( return_hash )
277 : 0 : h = new HashKey(entry->key, entry->len, entry->hash);
278 : :
279 : 0 : return entry->value;
280 : : }
281 : :
282 : 23532 : int b = cookie->bucket;
283 : 23532 : int o = cookie->offset;
284 : : PList(DictEntry)** ttbl;
285 : : const int* num_buckets_p;
286 : :
287 [ + + ]: 23532 : if ( ! cookie->ttbl )
288 : : {
289 : : // XXX maybe we could update cookie->b from tbl_next_ind here?
290 : 9767 : cookie->ttbl = tbl;
291 : 9767 : cookie->num_buckets_p = &num_buckets;
292 : : }
293 : :
294 : 23532 : ttbl = cookie->ttbl;
295 : 23532 : num_buckets_p = cookie->num_buckets_p;
296 : :
297 [ + + ][ + + ]: 23532 : if ( ttbl[b] && ttbl[b]->length() > o )
[ + + ]
298 : : {
299 : 5177 : entry = (*ttbl[b])[o];
300 : 5177 : ++cookie->offset;
301 [ + - ]: 5177 : if ( return_hash )
302 : 5177 : h = new HashKey(entry->key, entry->len, entry->hash);
303 : 5177 : return entry->value;
304 : : }
305 : :
306 : 18355 : ++b; // Move on to next non-empty bucket.
307 [ + + ][ + + ]: 168117 : while ( b < *num_buckets_p && (! ttbl[b] || ttbl[b]->length() == 0) )
[ + + ][ + + ]
308 : 149762 : ++b;
309 : :
310 [ + + ]: 18355 : if ( b >= *num_buckets_p )
311 : : {
312 : : // If we're resizing, we need to search the 2nd table too.
313 [ + + ][ + + ]: 9773 : if ( ttbl == tbl && tbl2 )
314 : : {
315 : 6 : cookie->ttbl = tbl2;
316 : 6 : cookie->num_buckets_p = &num_buckets2;
317 : 6 : cookie->bucket = 0;
318 : 6 : cookie->offset = 0;
319 : 6 : return Dictionary::NextEntry(h, cookie, return_hash);
320 : : }
321 : :
322 : : // All done.
323 : :
324 : : // FIXME: I don't like removing the const here. But is there
325 : : // a better way?
326 : 9767 : const_cast<PList(IterCookie)*>(&cookies)->remove(cookie);
327 [ + - ]: 9767 : delete cookie;
328 : 9767 : cookie = 0;
329 : 9767 : return 0;
330 : : }
331 : :
332 : 8582 : entry = (*ttbl[b])[0];
333 [ + + ]: 8582 : if ( return_hash )
334 : 8574 : h = new HashKey(entry->key, entry->len, entry->hash);
335 : :
336 : 8582 : cookie->bucket = b;
337 : 8582 : cookie->offset = 1;
338 : :
339 : 23532 : return entry->value;
340 : : }
341 : :
342 : 17252 : void Dictionary::Init(int size)
343 : : {
344 : 17252 : num_buckets = NextPrime(size);
345 : 17252 : tbl = new PList(DictEntry)*[num_buckets];
346 : :
347 [ + + ]: 310536 : for ( int i = 0; i < num_buckets; ++i )
348 : 293284 : tbl[i] = 0;
349 : :
350 : 17252 : max_num_entries = num_entries = 0;
351 : 17252 : }
352 : :
353 : 55 : void Dictionary::Init2(int size)
354 : : {
355 : 55 : num_buckets2 = NextPrime(size);
356 : 55 : tbl2 = new PList(DictEntry)*[num_buckets2];
357 : :
358 [ + + ]: 7576 : for ( int i = 0; i < num_buckets2; ++i )
359 : 7521 : tbl2[i] = 0;
360 : :
361 : 55 : max_num_entries2 = num_entries2 = 0;
362 : 55 : }
363 : :
364 : : // private
365 : 56677 : void* Dictionary::Insert(DictEntry* new_entry, int copy_key)
366 : : {
367 : : PList(DictEntry)** ttbl;
368 : : int* num_entries_ptr;
369 : : int* max_num_entries_ptr;
370 : 56677 : hash_t h = new_entry->hash % num_buckets;
371 : :
372 : : // We must be careful when we are in the middle of resizing.
373 : : // If the new entry hashes to a bucket in the old table we
374 : : // haven't moved yet, we need to put it in the old table. If
375 : : // we didn't do it this way, we would sometimes have to
376 : : // search both tables which is probably more expensive.
377 : :
378 [ + + ][ + + ]: 56677 : if ( ! tbl2 || h >= tbl_next_ind )
379 : : {
380 : 45585 : ttbl = tbl;
381 : 45585 : num_entries_ptr = &num_entries;
382 : 45585 : max_num_entries_ptr = &max_num_entries;
383 : : }
384 : : else
385 : : {
386 : 11092 : ttbl = tbl2;
387 : 11092 : h = new_entry->hash % num_buckets2;
388 : 11092 : num_entries_ptr = &num_entries2;
389 : 11092 : max_num_entries_ptr = &max_num_entries2;
390 : : }
391 : :
392 : 56677 : PList(DictEntry)* chain = ttbl[h];
393 : :
394 : 56677 : int n = new_entry->len;
395 : :
396 [ + + ]: 56677 : if ( chain )
397 : : {
398 [ + + ]: 68090 : for ( int i = 0; i < chain->length(); ++i )
399 : : {
400 : 42314 : DictEntry* entry = (*chain)[i];
401 : :
402 [ + + + - ]: 42314 : if ( entry->hash == new_entry->hash &&
[ + - ]
403 : : entry->len == n &&
404 : : ! memcmp(entry->key, new_entry->key, n) )
405 : : {
406 : 111 : void* old_value = entry->value;
407 : 111 : entry->value = new_entry->value;
408 : 111 : return old_value;
409 : : }
410 : : }
411 : : }
412 : : else
413 : : // Create new chain.
414 : 30790 : chain = ttbl[h] = new PList(DictEntry);
415 : :
416 : : // If we got this far, then we couldn't use an existing copy
417 : : // of the key, so make a new one if necessary.
418 [ - + ]: 56566 : if ( copy_key )
419 : : {
420 : 0 : void* old_key = new_entry->key;
421 : 0 : new_entry->key = (void*) new char[n];
422 : 0 : memcpy(new_entry->key, old_key, n);
423 : 0 : delete (char*) old_key;
424 : : }
425 : :
426 : : // We happen to know (:-() that appending is more efficient
427 : : // on lists than prepending.
428 : 56566 : chain->append(new_entry);
429 : :
430 [ + + ]: 56566 : if ( *max_num_entries_ptr < ++*num_entries_ptr )
431 : 53168 : *max_num_entries_ptr = *num_entries_ptr;
432 : :
433 : : // For ongoing iterations: If we already passed the bucket where this
434 : : // entry was put, add it to the cookie's list of inserted entries.
435 [ - + ]: 56566 : loop_over_list(cookies, i)
436 : : {
437 : 0 : IterCookie* c = cookies[i];
438 [ # # ]: 0 : if ( h < (unsigned int) c->bucket )
439 : 0 : c->inserted.append(new_entry);
440 : : }
441 : :
442 : 56677 : return 0;
443 : : }
444 : :
445 : 17307 : int Dictionary::NextPrime(int n) const
446 : : {
447 [ + + ]: 17307 : if ( (n & 0x1) == 0 )
448 : : // Even.
449 : 17252 : ++n;
450 : :
451 [ + + ]: 17307 : if ( n > PRIME_THRESH )
452 : : // Too expensive to test for primality, just stick with it.
453 : 1 : return n;
454 : :
455 [ + + ]: 17394 : while ( ! IsPrime(n) )
456 : 88 : n += 2;
457 : :
458 : 17307 : return n;
459 : : }
460 : :
461 : 17394 : int Dictionary::IsPrime(int n) const
462 : : {
463 [ + + ]: 52509 : for ( int j = 3; j * j <= n; ++j )
464 [ + + ]: 35203 : if ( n % j == 0 )
465 : 88 : return 0;
466 : :
467 : 17394 : return 1;
468 : : }
469 : :
470 : 55 : void Dictionary::StartChangeSize(int new_size)
471 : : {
472 : : // Only start resizing if there isn't any iteration in progress.
473 [ - + ]: 55 : if ( cookies.length() > 0 )
474 : 0 : return;
475 : :
476 [ - + ]: 55 : if ( tbl2 )
477 : 0 : internal_error("Dictionary::StartChangeSize() tbl2 not NULL");
478 : :
479 : 55 : Init2(new_size);
480 : :
481 : 55 : tbl_next_ind = 0;
482 : :
483 : : // Preserve threshold density
484 : 55 : SetDensityThresh2(DensityThresh());
485 : : }
486 : :
487 : 1112 : void Dictionary::MoveChains()
488 : : {
489 : : // Do not change current distribution if there an ongoing iteration.
490 [ - + ]: 1112 : if ( cookies.length() > 0 )
491 : 0 : return;
492 : :
493 : : // Attempt to move this many entries (must do at least 2)
494 : 1112 : int num = 8;
495 : :
496 [ + + ][ + + ]: 3349 : do
497 : : {
498 : 3349 : PList(DictEntry)* chain = tbl[tbl_next_ind++];
499 : :
500 [ + + ]: 3349 : if ( ! chain )
501 : 115 : continue;
502 : :
503 : 3234 : tbl[tbl_next_ind - 1] = 0;
504 : :
505 [ + + ]: 13807 : for ( int j = 0; j < chain->length(); ++j )
506 : : {
507 : 10573 : Insert((*chain)[j], 0);
508 : 10573 : --num_entries;
509 : 10573 : --num;
510 : : }
511 : :
512 [ + - ]: 3234 : delete chain;
513 : : }
514 : : while ( num > 0 && int(tbl_next_ind) < num_buckets );
515 : :
516 [ + + ]: 1112 : if ( int(tbl_next_ind) >= num_buckets )
517 : 1112 : FinishChangeSize();
518 : : }
519 : :
520 : 42 : void Dictionary::FinishChangeSize()
521 : : {
522 : : // Cheap safety check.
523 [ - + ]: 42 : if ( num_entries != 0 )
524 : : internal_error(
525 : : "Dictionary::FinishChangeSize: num_entries is %d\n",
526 : 0 : num_entries);
527 : :
528 [ + + ]: 3152 : for ( int i = 0; i < num_buckets; ++i )
529 [ - + ]: 3110 : delete tbl[i];
530 [ + - ]: 42 : delete [] tbl;
531 : :
532 : 42 : tbl = tbl2;
533 : 42 : tbl2 = 0;
534 : :
535 : 42 : num_buckets = num_buckets2;
536 : 42 : num_entries = num_entries2;
537 : 42 : max_num_entries = max_num_entries2;
538 : 42 : den_thresh = den_thresh2;
539 : 42 : thresh_entries = thresh_entries2;
540 : :
541 : 42 : num_buckets2 = 0;
542 : 42 : num_entries2 = 0;
543 : 42 : max_num_entries2 = 0;
544 : 42 : den_thresh2 = 0;
545 : 42 : thresh_entries2 = 0;
546 : 42 : }
547 : :
548 : 0 : unsigned int Dictionary::MemoryAllocation() const
549 : : {
550 : 0 : int size = padded_sizeof(*this);
551 : :
552 [ # # ]: 0 : for ( int i = 0; i < num_buckets; ++i )
553 [ # # ]: 0 : if ( tbl[i] )
554 : : {
555 : 0 : PList(DictEntry)* chain = tbl[i];
556 [ # # ]: 0 : loop_over_list(*chain, j)
557 : 0 : size += padded_sizeof(DictEntry) + pad_size((*chain)[j]->len);
558 : 0 : size += chain->MemoryAllocation();
559 : : }
560 : :
561 : 0 : size += pad_size(num_buckets * sizeof(PList(DictEntry)*));
562 : :
563 [ # # ]: 0 : if ( order )
564 : 0 : size += order->MemoryAllocation();
565 : :
566 [ # # ]: 0 : if ( tbl2 )
567 : : {
568 [ # # ]: 0 : for ( int i = 0; i < num_buckets2; ++i )
569 [ # # ]: 0 : if ( tbl2[i] )
570 : : {
571 : 0 : PList(DictEntry)* chain = tbl2[i];
572 [ # # ]: 0 : loop_over_list(*chain, j)
573 : 0 : size += padded_sizeof(DictEntry) + pad_size((*chain)[j]->len);
574 : 0 : size += chain->MemoryAllocation();
575 : : }
576 : :
577 : 0 : size += pad_size(num_buckets2 * sizeof(PList(DictEntry)*));
578 : : }
579 : :
580 : 0 : return size;
581 : : }
582 : :
583 : 0 : void generic_delete_func(void* v)
584 : : {
585 : 0 : free(v);
586 [ + - ][ + - ]: 6 : }
|
