Update copyright to LGPL on all files
[dyninst.git] / common / src / Dictionary.C
1 /*
2  * Copyright (c) 1996-2009 Barton P. Miller
3  * 
4  * We provide the Paradyn Parallel Performance Tools (below
5  * described as "Paradyn") on an AS IS basis, and do not warrant its
6  * validity or performance.  We reserve the right to update, modify,
7  * or discontinue this software at any time.  We shall have no
8  * obligation to supply such updates or modifications or any other
9  * form of support to you.
10  * 
11  * By your use of Paradyn, you understand and agree that we (or any
12  * other person or entity with proprietary rights in Paradyn) are
13  * under no obligation to provide either maintenance services,
14  * update services, notices of latent defects, or correction of
15  * defects for Paradyn.
16  * 
17  * This library is free software; you can redistribute it and/or
18  * modify it under the terms of the GNU Lesser General Public
19  * License as published by the Free Software Foundation; either
20  * version 2.1 of the License, or (at your option) any later version.
21  * 
22  * This library is distributed in the hope that it will be useful,
23  * but WITHOUT ANY WARRANTY; without even the implied warranty of
24  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
25  * Lesser General Public License for more details.
26  * 
27  * You should have received a copy of the GNU Lesser General Public
28  * License along with this library; if not, write to the Free Software
29  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
30  */
31
32 // Dictionary.C
33
34 #if (!defined (__XLC__) && !defined(__xlC__)) || defined(DICT_C_IS_HEADER)
35
36 #include "common/h/std_namesp.h"
37 #include "common/h/Dictionary.h"
38 //#include "common/h/String.h"
39
40 // methods of this class implemented in .h so compiler has no trouble finding
41 // them for template instantiation
42
43 #include <limits.h> // UINT_MAX
44 #include <assert.h>
45
46 template<class K, class V>
47 const unsigned dictionary_hash<K,V>::bin_grow_factor = 2;
48
49 template<class K, class V>
50 dictionary_hash<K,V>::dictionary_hash(unsigned (*hf)(const K &),
51                                       unsigned nbins,
52                                       unsigned imax_bin_load) {
53   // we keep #bins*max_bin_load <= total # items * 100
54   assert(imax_bin_load > 0);
55   assert(imax_bin_load < 1000); // why would you want to allow so many
56                                 // collisions per bin?
57   hasher = hf;
58
59   // Note: all_elems[] starts off as an empty pdvector.
60
61   // Pre-size the # of bins from parameter.  
62   // Each bins starts off empty (UINT_MAX)
63   assert(nbins > 0);
64   bins.resize(nbins);
65   for (unsigned binlcv=0; binlcv < bins.size(); binlcv++)
66     bins[binlcv] = UINT_MAX;
67
68   num_removed_elems = 0;
69
70   max_bin_load = imax_bin_load;
71
72   assert(enoughBins());
73 }
74
75 template<class K, class V>
76 dictionary_hash<K,V>::dictionary_hash(const dictionary_hash<K,V> &src) :
77                                       all_elems(src.all_elems), bins(src.bins) {
78   // copying an entire dictionary should be a rare occurance; we provide it only
79   // for completeness (I'd prefer to leave it out, actually)
80   hasher = src.hasher;
81   num_removed_elems = src.num_removed_elems;
82   max_bin_load = src.max_bin_load;
83
84   assert(enoughBins());
85 }
86
87 template<class K, class V>
88 dictionary_hash<K,V> &
89 dictionary_hash<K,V>::operator=(const dictionary_hash<K,V> &src) {
90   // assigning an entire dictionary should be a rare occurance; we provide it only
91   // for completeness (I'd prefer to leave it out, actually)
92   if (&src == this) return *this;
93
94   hasher = src.hasher;
95   all_elems = src.all_elems;
96   bins = src.bins;
97
98   num_removed_elems = src.num_removed_elems;
99   max_bin_load = src.max_bin_load;
100
101   assert(enoughBins());
102
103   return *this;
104 }
105
106 template<class K, class V>
107 unsigned dictionary_hash<K,V>::size() const {
108   assert(num_removed_elems <= all_elems.size());
109   return all_elems.size() - num_removed_elems;
110 }
111
112 template<class K, class V>
113 V& dictionary_hash<K,V>::operator[](const K& key) {
114   const unsigned ndx = locate_addIfNotFound(key);
115
116   //assert(defines(key)); // WARNING: expensive assert!
117    
118   return all_elems[ndx].val;
119 }
120
121 template<class K, class V>
122 const V& dictionary_hash<K,V>::operator[](const K& key) const {
123   const unsigned ndx = locate(key, false);
124   assert(ndx != UINT_MAX);
125   //assert(defines(key)); // WARNING: expensive assert!
126    
127   return all_elems[ndx].val;
128 }
129
130 template<class K, class V>
131 const V& dictionary_hash<K,V>::get(const K &key) const {
132   const unsigned ndx = locate(key, false);
133   // false: if removed, then it doesn't count
134
135   if (ndx == UINT_MAX)
136     assert(false && "dictionary_hash get() requires a hit");
137    
138   return all_elems[ndx].val;
139 }
140
141 template<class K, class V>
142 V& dictionary_hash<K,V>::get(const K &key) {
143   const unsigned ndx = locate(key, false);
144   // false: if removed, then it doesn't count
145
146   if (ndx == UINT_MAX)
147     assert(false && "dictionary_hash get() requires a hit");
148    
149   return all_elems[ndx].val;
150 }
151
152 template<class K, class V>
153 const V& dictionary_hash<K,V>::get_and_remove(const K &key) {
154   const unsigned ndx = locate(key, false);
155   // false: if removed, then it doesn't count
156
157   if (ndx == UINT_MAX)
158     assert(false && "dictionary_hash get_and_remove() requires a hit");
159
160   const unsigned oldsize = size();
161
162   entry &e = all_elems[ndx];
163
164   assert(!e.removed);
165   e.removed = true;
166   num_removed_elems++;
167   assert(num_removed_elems <= all_elems.size());
168
169   assert(size() + 1 == oldsize);
170    
171   return e.val;
172 }
173
174 template<class K, class V>
175 bool dictionary_hash<K,V>::find_and_remove(const K &key, V &val) {
176   const unsigned ndx = locate(key, false);
177   // false: if removed, then it doesn't count
178
179   if (ndx == UINT_MAX)
180     return false;
181
182   const unsigned oldsize = size();
183
184   entry &e = all_elems[ndx];
185
186   assert(!e.removed);
187   e.removed = true;
188   num_removed_elems++;
189   assert(num_removed_elems <= all_elems.size());
190
191   assert(size() + 1 == oldsize);
192
193   val = e.val;
194
195   return true;
196 }
197
198 template<class K, class V>
199 void dictionary_hash<K,V>::set(const K &key, const V &val) {
200   const unsigned ndx = locate(key, true); // true --> if removed, count as a find
201
202   if (ndx != UINT_MAX) {
203     // Found an entry.  If this entry is actually 'removed', then un-remove it.
204     // Otherwise, barf.
205     entry &theEntry = all_elems[ndx];
206     if (theEntry.removed) {
207       assert(num_removed_elems > 0);
208       theEntry.val = val;
209       theEntry.removed = false;
210       num_removed_elems--;
211
212       // clearing the removed flag can't possibly invalidate the performance
213       // invariant
214     }
215     else
216       assert(false && "dictionary set(): an entry with that key already exists");
217   }
218   else {
219     // Didn't find that entry.  Good.  Create that entry and add to the dictionary.
220     add(key, val);
221       
222     //assert(defines(key)); // WARNING: expensive assert()
223   }
224 }
225
226 template<class K, class V>
227 TYPENAME dictionary_hash<K,V>::iterator
228 dictionary_hash<K,V>::find(const K& key) {
229   const unsigned ndx = locate(key, false); // false -->don't find removed items
230   if (ndx == UINT_MAX) {
231     return end();
232   }
233   else {
234      TYPENAME dictionary_hash<K,V>::iterator dictIter(*this,
235            GET_ITER(all_elems,ndx));
236         
237     return dictIter;
238   }
239 }
240
241 template<class K, class V>
242 TYPENAME dictionary_hash<K,V>::const_iterator
243 dictionary_hash<K,V>::find(const K& key) 
244      const {
245   const unsigned ndx = locate(key, false); // false -->don't find removed items
246   if (ndx == UINT_MAX) {
247     return end();
248   }
249   else {
250      TYPENAME dictionary_hash<K,V>::const_iterator dictIter(*this,
251            GET_ITER(all_elems,ndx));
252
253 #if 0
254     TYPENAME dictionary_hash<K,V>::const_iterator dictIter(*this, 
255                                                                                 all_elems.getIter(ndx));
256 #endif
257     return dictIter;
258   }
259 }
260
261 template<class K, class V>
262 bool dictionary_hash<K,V>::find(const K& key, V& el) const {
263   const unsigned ndx = locate(key, false); // false --> don't find removed items
264   if (ndx == UINT_MAX)
265     return false;
266   else {
267     el = all_elems[ndx].val;
268     return true;
269   }
270 }
271
272 template<class K, class V>
273 bool dictionary_hash<K,V>::find(const K& key, const V **el) const {
274   const unsigned ndx = locate(key, false); // false --> don't find removed items
275   if (ndx == UINT_MAX)
276     return false;
277   else {
278     (*el) = &all_elems[ndx].val;
279     return true;
280   }
281 }
282
283 template<class K, class V>
284 bool dictionary_hash<K,V>::defines(const K& key) const {
285   const unsigned ndx = locate(key, false); // false --> don't find removed items
286   return (ndx != UINT_MAX);
287 }
288
289 template<class K, class V>
290 void dictionary_hash<K,V>::undef(const K& key) {
291   unsigned ndx = locate(key, false); // false --> don't find removed items
292   if (ndx == UINT_MAX)
293     return; // nothing to do...either doesn't exist, or already removed
294
295 #ifndef NDEBUG
296   const unsigned oldsize = size();
297 #endif
298
299   entry &e = all_elems[ndx];
300   assert(!e.removed);
301   e.removed = true;
302   num_removed_elems++;
303
304 #ifndef NDEBUG
305   assert(oldsize == size()+1);
306   assert(num_removed_elems <= all_elems.size());
307 #endif
308 }
309
310 #ifndef _KERNEL
311 // Sun's compiler can't handle the return types
312
313 template<class K, class V>
314 pdvector<K>
315 dictionary_hash<K,V>::keys() const {
316   // One can argue that this method (and values(), below) should be removed in
317   // favor of using the dictionary iterator class.  I agree; it's here only for
318   // backwards compatibility.
319   pdvector<K> result;
320   result.reserve(size());
321    
322   // note that the iterator class automatically skips elems tagged for removal
323   const_iterator finish = end();
324   for (const_iterator iter=begin(); iter != finish; iter++)
325     result.push_back(iter.currkey());
326
327   return result;
328 }
329
330 template<class K, class V>
331 pdvector<V>
332 dictionary_hash<K,V>::values() const {
333   // One can argue that this method (and keys(), above) should be removed in
334   // favor of using the dictionary iterator class.  I agree; it's here only for
335   // backwards compatibility.
336   pdvector<V> result;
337   result.reserve(size());
338    
339   // note that the iterator class automatically skips elems tagged for removal
340   const_iterator finish = end();
341   for (const_iterator iter=begin(); iter != finish; ++iter)
342     result.push_back(*iter);
343
344   return result;
345 }
346
347 template<class K, class V>
348 pdvector< pdpair<K, V> >
349 dictionary_hash<K,V>::keysAndValues() const {
350   pdvector< pdpair<K, V> > result;
351   result.reserve(size());
352    
353   const_iterator finish = end();
354   for (const_iterator iter = begin(); iter != finish; ++iter)
355     result.push_back( pdpair<K,V>(iter.currkey(), iter.currval()) );
356
357   return result;
358 }
359
360 #endif //ifndef(_KERNEL)
361 /*
362 template<class K, class V>
363 int dictionary_hash<K,V>::linear_filter(pdvector< pdpair<K, V> > &matches, 
364                                         bool (*filt_func)(const V&)) 
365 {
366   const_iterator finish = end();
367   for (const_iterator iter = begin(); iter != finish; ++iter) {
368     if ((*filt_func)(*iter))
369       matches.push_back(pdpair<K,V>(iter.currkey(),iter.currval()));
370   }
371   return 0;
372 }
373 */
374 /*
375 template<class K, class V>
376 pdvector<V>  dictionary_hash<K,V>::linear_filter(bool (*filt_func)(const K&, void *data),
377                                                  void *param) 
378 {
379   pdvector< V > result;
380   result.reserve(size());
381   const_iterator finish = end();
382   for (const_iterator iter = begin(); iter != finish; ++iter) {
383     if ((*filt_func)(iter.currkey(), param)) {
384       cerr << "adding value" << endl;
385       result.push_back(iter.currval());
386     }
387   }
388   cerr <<"result.size() = " << result.size() <<endl;
389   return result;
390 }
391 */
392 template<class K, class V>
393 void dictionary_hash<K,V>::clear() {
394   // max_bin_load and bin_grow_factor don't change.
395   // Also, bins.size() doesn't change; is this best (perhaps we should shrink
396   // bins down to its original size...not trivial since we didn't set that value
397   // aside in the ctor.  In any event we don't lose sleep since calling clear() is
398   // rare.)  Like class pdvector, we could also provide a zap() method which actually
399   // does free up memory.
400
401   all_elems.clear();
402
403   for (unsigned lcv=0; lcv < bins.size(); lcv++)
404     bins[lcv] = UINT_MAX;
405
406   num_removed_elems = 0;
407
408   assert(size() == 0);
409
410   assert(enoughBins());
411 }
412
413 template<class K, class V>
414 unsigned
415 dictionary_hash<K,V>::locate(const K& key, bool evenIfRemoved) const {
416   // An internal routine used by everyone.
417
418   // call hasher(key), but make sure it fits in 31 bits:
419   if(hasher == NULL) {
420     cerr << "hasher == NULL\n";
421     assert(false);
422   }
423   unsigned hashval = hasher(key) & 0x7fffffff;
424
425   const unsigned bin = hashval % bins.size();
426    
427   unsigned elem_ndx = bins[bin];
428   while (elem_ndx != UINT_MAX) {
429     const entry &elem = all_elems[elem_ndx];
430
431     // verify that this elem is in the right bin!
432     assert(elem.key_hashval % bins.size() == bin);
433       
434     if (elem.key_hashval == hashval && elem.key == key) {
435       // found it...unless it was removed
436       if (elem.removed && !evenIfRemoved)
437         elem_ndx = UINT_MAX;
438
439       break;
440     }
441     else
442       elem_ndx = elem.next;
443   }
444
445   return elem_ndx;
446 }
447
448
449 template<class K, class V>
450 unsigned
451 dictionary_hash<K,V>::add(const K& key, const V &val) {
452   // internal routine called by locate_addIfNotFound() and by set()
453   // returns ndx (within all_elems[]) of newly added item
454
455   // before the insert, we should have enough bins to fit everything nicely...
456   assert(enoughBins());
457
458   if (!enoughBinsIf1MoreItemAdded()) {
459     // ...but adding 1 more element would make things too big.  So, grow (add
460     // some new bins) before adding.
461          
462     const unsigned new_numbins = (unsigned)(bins.size() * bin_grow_factor);
463     assert(new_numbins > bins.size() && "bin_grow_factor too small");
464
465     grow_numbins(new_numbins);
466
467     // ...verify that we have enough bins after the grow:
468     assert(enoughBinsIf1MoreItemAdded());
469
470     // fall through...
471   }
472       
473   // We don't need to grow.
474   const unsigned hashval = hasher(key) & 0x7fffffff; // make sure it fits in 31 bits
475   const unsigned bin     = hashval % bins.size();
476
477   entry e(key, hashval, val, UINT_MAX);
478   e.next = bins[bin];
479   all_elems.push_back(e);
480   //entry *e = all_elems.append_with_inplace_construction();
481   //new((void*)e)entry(key, hashval, val, UINT_MAX);
482   const unsigned new_entry_ndx = all_elems.size()-1;
483
484   // Insert at the head of the bin (we could insert at the tail, but this
485   // is a tad easier, and besides, position in the bin doesn't matter)
486   bins[bin] = new_entry_ndx;
487
488   //assert(defines(key)); // WARNING: expensive assert()
489       
490   assert(enoughBins());
491   return new_entry_ndx;
492 }
493
494 template<class K, class V>
495 unsigned
496 dictionary_hash<K,V>::locate_addIfNotFound(const K& key) {
497   // An internal routine used by everyone.
498   // Returns ndx (within all_elems[]) of the item.
499
500   unsigned result = locate(key, true); // true --> find even if 'removed' flag set
501   // UINT_MAX if not found
502
503   if (result == UINT_MAX)
504     return add(key, V());
505   else {
506     // found the item.
507     entry &e = all_elems[result];
508     if (e.removed) {
509       // Item has been removed.  We're gonna un-remove it.
510
511       //assert(!defines(key)); // WARNING: expensive assert
512       
513       assert(num_removed_elems > 0);
514
515       e.removed = false;
516       e.val = V();
517       num_removed_elems--;
518
519       // Clearing the 'removed' flag of an entry can't possibly invalidate the
520       // performance assertion
521     }
522
523     //assert(defines(key)); // WARNING: expensive assert
524       
525     return result;
526   }
527 }
528
529 template<class K, class V>
530 void
531 dictionary_hash<K,V>::grow_numbins(unsigned new_numbins) {
532   assert(new_numbins > bins.size() && "grow_numbins not adding any bins?");
533
534   bins.resize(new_numbins, true); // true --> exact resize flag
535   for (unsigned binlcv=0; binlcv < bins.size(); binlcv++)
536     bins[binlcv] = UINT_MAX;
537
538   // Look for elems to remove; shrink all_elems[] as appropriate
539   if (num_removed_elems > 0) {
540     for (unsigned lcv=0; lcv < all_elems.size(); ) {
541       entry &e = all_elems[lcv];
542       if (e.removed) {
543         const unsigned oldsize = all_elems.size();
544         assert(oldsize > 0);
545
546         // remove item from pdvector by swap with last item & resizing/-1
547         all_elems[lcv] = all_elems[oldsize-1]; // should be OK if lcv==oldsize-1
548         all_elems.resize(oldsize-1);
549
550         num_removed_elems--;
551             
552         // note: we DON'T bump up lcv in this case
553       }
554       else
555         lcv++;
556     }
557
558     assert(num_removed_elems == 0);
559   }
560
561   // Now rehash everything.  Sounds awfully expensive, and I guess it is -- it's
562   // linear in the total # of items in the hash table.  But take heart: beyond this
563   // point, we don't need to make any copies of type KEY or VALUE, resize any pdvectors,
564   // or recalculate any hash values.  We just need to assign to <n> unsigned
565   // integers.
566
567   const unsigned numbins = bins.size(); // loop invariant
568   for (unsigned lcv=0; lcv < all_elems.size(); lcv++) {
569     entry &e = all_elems[lcv];
570     assert(!e.removed);
571
572     // the entry's key_hashval stays the same, but it may go into a different bin:
573     const unsigned bin = e.key_hashval % numbins;
574
575     // prepend element to bin:
576     unsigned &thebin = bins[bin];
577       
578     e.next = thebin;
579     thebin = lcv;
580   }
581
582   // The invariant might not have held at the top of this routine, but it
583   // should now hold.
584   assert(enoughBins());
585 }
586
587 #endif