Compilation fixes for gcc 3.1, MSVC 6.0 & 7.0
[dyninst.git] / common / h / Dictionary.h
1 /*
2  * Copyright (c) 1996 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  * This license is for research uses.  For such uses, there is no
12  * charge. We define "research use" to mean you may freely use it
13  * inside your organization for whatever purposes you see fit. But you
14  * may not re-distribute Paradyn or parts of Paradyn, in any form
15  * source or binary (including derivatives), electronic or otherwise,
16  * to any other organization or entity without our permission.
17  * 
18  * (for other uses, please contact us at paradyn@cs.wisc.edu)
19  * 
20  * All warranties, including without limitation, any warranty of
21  * merchantability or fitness for a particular purpose, are hereby
22  * excluded.
23  * 
24  * By your use of Paradyn, you understand and agree that we (or any
25  * other person or entity with proprietary rights in Paradyn) are
26  * under no obligation to provide either maintenance services,
27  * update services, notices of latent defects, or correction of
28  * defects for Paradyn.
29  * 
30  * Even if advised of the possibility of such damages, under no
31  * circumstances shall we (or any other person or entity with
32  * proprietary rights in the software licensed hereunder) be liable
33  * to you or any third party for direct, indirect, or consequential
34  * damages of any character regardless of type of action, including,
35  * without limitation, loss of profits, loss of use, loss of good
36  * will, or computer failure or malfunction.  You agree to indemnify
37  * us (and any other person or entity with proprietary rights in the
38  * software licensed hereunder) for any and all liability it may
39  * incur to third parties resulting from your use of Paradyn.
40  */
41
42 // Dictionary.h
43
44 #ifndef _DICTIONARY_H_
45 #define _DICTIONARY_H_
46
47 #include "common/h/Vector.h" // takes care of redefining assert as ASSERT for _KERNEL
48 #include "common/h/Pair.h"
49
50 /************************************************************************
51  * template<class K, class V> class dictionary_hash
52  * Ari Tamches
53  *
54  * See Stroustrup, The C++ Programming Language, 3d edition, which
55  * provided inspiration for this hash table class via an extended
56  * example in section 17.6
57  *
58  * This class tries very hard to ensure that there are enough bins s.t.
59  * hash collisions are few (though if you provide a bad hash function,
60  * all bets are off, as usual).  Toward that end, the following invariant
61  * is maintained at all times:
62  *         #bins * max_bin_load >= total # items
63  *         Note about "total # items": includes items that are marked as removed
64  *         (after all, such items do indeed clutter up the bins and so should be
65  *         taken into account for this performance invariant.)
66  * max_bin_load is a user-settable parameter (see ctor).
67  *
68  * When adding a new hash table item would break the invariant,
69  * #bins is multiplied by bin_grow_factor (another user-settable parameter in ctor),
70  * and everything is rehashed (expensive, but not needed often, since growth
71  * is exponential).  NOTE: since the performance invariant doesn't distinguish
72  * between items marked as 'removed' and non-removed items, when we clear the
73  * 'removed' flag of any item, the invariant cannot possibly be broken.
74  *
75  * Note: We don't make any effort to keep num_bins always a power of 2.
76  *       If such an invariant were maintained, then "x % num_bins"
77  *       simplifies to "x % (1U << lg_num_bins)-1".  We could get away
78  *       with just storing lg_num_bins, and use "1U << lg_num_bins"
79  *       to get num_bins at any time.
80  * 
81 ************************************************************************/
82
83 //ifdef this to nothing if it bothers old broken compilers
84 #define TYPENAME typename
85
86 template<class K, class V> class dictionary_hash_iter;
87
88 template<class K, class V>
89 class dictionary_hash {
90   typedef const V &RET;
91   friend class dictionary_hash_iter<K,V>;
92
93  public:
94   typedef K key_type;
95   typedef V value_type;
96   typedef RET iter_value_return_type;
97   typedef V& value_reference_type;
98    
99   dictionary_hash (unsigned (*hashfunc)(const K &),
100                    unsigned nbins=101,
101                    unsigned max_bin_load=70
102                    // we keep #bins*max_bin_load >= total # items * 100, 
103                    // to make sure that there are enough bins s.t. 
104                    // (assuming a good hash function) collisions are few.
105                    );
106   ~dictionary_hash () {}
107
108   // I'd rather not have provided these methods, but apparantly some code
109   // in paradynd actually copies entire dictionaries (!)
110   dictionary_hash (const dictionary_hash<K,V> &);
111   dictionary_hash<K,V>&  operator= (const dictionary_hash<K,V> &);
112
113   unsigned getMemUsage_exceptObjItself_AndExtraFromKeyOrValue() const {
114     return all_elems.capacity() * sizeof(entry) + bins.capacity() * sizeof(unsigned);
115   }
116
117   unsigned size () const;
118
119   V& operator[] (const K &);
120   // If key doesn't exist, creates a new entry (using the default ctor for the
121   // value).  Hence this can't be a const method; contrast with get().
122
123   V& get(const K &);
124   const V& get(const K &) const;
125   // If key doesn't exist, then barfs.  Contrast with operator[].
126
127   const V& get_and_remove(const K &);
128   // returns a reference the to value part of the deleted item (possible because
129   // in reality, deleting an item just sets the 'removed' flag).
130    
131   bool find_and_remove(const K &, V&);
132
133   void set(const K &, const V &);
134   // If key already exists, barfs.  Contrast with operator[].
135
136   bool      find (const K &, V &) const;
137   bool      defines (const K &) const;
138   void      undef (const K &); 
139
140 #ifndef _KERNEL
141   // Sun's compiler can't handle the return types
142   vector<K> keys () const;
143   vector<V> values () const;
144   vector< pair<K, V> > keysAndValues() const;
145 #endif
146
147   void      clear ();
148
149   typedef dictionary_hash_iter<K,V> const_iterator;
150   const_iterator begin() const {
151     //return const_iterator(all_elems.begin(), all_elems.end());
152     return const_iterator(*this);
153   }
154   const_iterator end() const {
155     //return const_iterator(all_elems.end(), all_elems.end());
156     return const_iterator(*this).end();
157   }
158
159  private:
160   bool enoughBins() const {
161     //return bins.size() * max_bin_load >= size();
162     // ABOVE WAS BUGGY: use all_elems.size(), not size()!
163     return bins.size() * max_bin_load >= all_elems.size();
164   }
165   bool enoughBinsIf1MoreItemAdded() const {
166     return bins.size() * max_bin_load >= all_elems.size() + 1;
167   }
168
169   unsigned add(const K &, const V &);
170   // internal routine called by locate_addIfNotFound() and by set()
171   // Assumes an entry with that key does not exist; adds to the dictionary.
172   // returns ndx within all_elems[]
173    
174   unsigned locate_addIfNotFound(const K &);
175   // returns ndx within all_elems[]; never returns UINT_MAX
176
177   unsigned locate(const K &, bool even_if_removed) const;
178   // never adds a new entry if not found.  Okay to call from const member fns
179
180   void grow_numbins(unsigned new_numbins);
181
182   // We keep a ptr to the hash function:
183   unsigned (*hasher)(const K &);
184   // NOTE: always squeeze the result into 31 bits before using it, since
185   // key_hashval, below, is a 31-bit bitfield.
186
187   // Important structure:
188   struct entry {
189     K key;
190     V val;
191     unsigned key_hashval : 31;
192     // we could always rehash, since we have 'key', but this
193     // is faster.
194     unsigned removed : 1;
195     // since removal would require a lot of shifting w/in all_elems[],
196     // we use this flag instead, and only do the actual removal on
197     // resize.
198     unsigned next; // an index into 'all_elems', for hash collisions.  UINT_MAX
199                    // implies end of collision chain for this bin
200
201     entry() {} // needed by vector class
202     entry(const K &ikey, unsigned ikey_hashval, const V &ival, unsigned inext) :
203           key(ikey), val(ival), key_hashval(ikey_hashval), next(inext) {
204       removed = false;
205     }
206     entry(const entry &src) : key(src.key), val(src.val) {
207       key_hashval = src.key_hashval;
208       removed = src.removed;
209       next = src.next;
210     }
211     entry& operator=(const entry &src) {
212       if (&src == this) return *this;
213
214       key = src.key;
215       val = src.val;
216       key_hashval = src.key_hashval;
217       removed = src.removed;
218       next = src.next;
219       return *this;
220     }
221   };
222
223   // The actual elements, in one big vector.  This enables certain important
224   // operations, (specifically rehashing the entire dictionary) to be done
225   // efficiently.  Plus, it's a clean approach to storage.
226   // Since we use vector<>::operator+= on this vector, we're glad that class vector<>
227   // preallocates some extra stuff when growing.
228   vector<entry> all_elems;
229
230   // The bins.  Note: since the number of bins doesn't change often (only when
231   // growing), we use resize with the exact flag set.
232   vector<unsigned> bins;
233   // each entry in 'bins' gives the index (w/in 'all_elems') of the first element
234   // in the bin.  In other words, the first element in bin X is all_elems[bin[X]].
235   // If bin[X] is UINT_MAX, then the bin is empty.
236
237   unsigned num_removed_elems;
238    
239   // Notes:
240   // 1) At any given time, all_elems.size()-num_removed_items gives us the
241   //    total # of items in the dictionary.
242   // 2) At any given time, bins.size() gives us the total # of bins in the dictionary.
243   // 3) We keep the invariant #bins * max_bin_load >= total # items * 100,
244   //    incrementing #bins (by a factor of bin_grow_factor) if needed to maintain it.
245
246   unsigned max_bin_load;        // percentage of total number of items
247   static const unsigned bin_grow_factor;
248 };
249
250 // Typical way to use an iterator for this class:
251 // for (dictionary_hash<K,V>::iterator iter=thedict.begin();
252 //      iter != thedict.end(); iter++) {
253 //    V &v = *iter; // or use iter-> directly to access the value.
254 //    // You can write to iter-> to change the value.  You can't change or even access
255 //    // the key right now.
256 // }
257
258 template<class K, class V>
259 class dictionary_hash_iter {
260  private:
261   typedef const V &RET; // RET: type returned by operator*()
262   const dictionary_hash<K,V> &dict;
263   TYPENAME vector< TYPENAME dictionary_hash<K,V>::entry >::const_iterator i;
264   TYPENAME vector< TYPENAME dictionary_hash<K,V>::entry >::const_iterator the_end;
265   // too bad we need to store the_end (for make_valid_or_end())
266    
267   void move_to_next() {
268     i++;
269     make_valid_or_end();
270   }
271   void make_valid_or_end() {
272     while (i != the_end && i->removed)
273       i++;
274   }
275    
276  public:
277   //dictionary_hash_iter(vector< dictionary_hash<K,V>::entry >::const_iterator ii,
278   //                   vector< dictionary_hash<K,V>::entry >::const_iterator iend) :
279   //                   i(ii), the_end(iend) {
280   //make_valid_or_end();
281   //}
282   dictionary_hash_iter(const dictionary_hash<K,V> &idict) : dict(idict) {
283     reset();
284   }
285   dictionary_hash_iter(const dictionary_hash_iter<K,V> &src) :
286                        dict(src.dict), i(src.i), the_end(src.the_end) { }
287   //dictionary_hash_iter& operator=(const dictionary_hash_iter<K,V> &src) {
288   //  dict = src.dict;
289   //  i = src.i;
290   //  the_end = src.the_end;
291   //  return *this;
292   //}
293
294   dictionary_hash_iter operator++(int) {
295     dictionary_hash_iter result = *this;
296     move_to_next();
297     return result;
298   }
299   dictionary_hash_iter operator++() { // prefix
300     move_to_next();
301     return *this;
302   }
303
304   bool next(K &k, V &v) {
305     for (; i != the_end; i++) {
306       if (!i->removed) {
307         k = i->key;
308         v = i->val;
309         i++;
310         return true;
311       }
312     }
313     return false;
314   }
315
316   void reset() {
317     // start the iterator off at the first non-removed item now:
318     if (dict.all_elems.size() == 0) {
319       i = the_end = NULL;
320     }
321     else {
322       i = dict.all_elems.begin();
323       the_end = dict.all_elems.end();
324
325       while (i != the_end && i->removed)
326         i++;
327     }
328   }
329
330   dictionary_hash_iter end() {
331     i = the_end;
332     return *this;
333   }
334
335   RET operator*() {
336     return i->val;
337   }
338 //   RET *operator->() {
339 //      return &i->val;
340 //   }
341
342   const K &currkey() const {
343     return i->key;
344   }
345   RET currval() const {
346     return i->val;
347   }
348
349   bool operator==(const dictionary_hash_iter &other) const {
350     return i == other.i; // no need to check the_end, right?
351   }
352   bool operator!=(const dictionary_hash_iter &other) const {
353     return i != other.i; // no need to check the_end, right?
354   }
355
356   operator bool() const {return i < the_end;}
357 };
358
359 // methods of this class implemented in .h so compiler has no trouble finding
360 // them for template instantiation
361
362 #include <limits.h> // UINT_MAX
363
364 template<class K, class V>
365 const unsigned dictionary_hash<K,V>::bin_grow_factor = 2;
366
367 template<class K, class V>
368 dictionary_hash<K,V>::dictionary_hash(unsigned (*hf)(const K &),
369                                       unsigned nbins,
370                                       unsigned imax_bin_load) {
371   // we keep #bins*max_bin_load <= total # items * 100
372   assert(imax_bin_load > 0);
373   assert(imax_bin_load < 1000); // why would you want to allow so many
374                                 // collisions per bin?
375   hasher = hf;
376
377   // Note: all_elems[] starts off as an empty vector.
378
379   // Pre-size the # of bins from parameter.  
380   // Each bins starts off empty (UINT_MAX)
381   assert(nbins > 0);
382   bins.resize(nbins);
383   for (unsigned binlcv=0; binlcv < bins.size(); binlcv++)
384     bins[binlcv] = UINT_MAX;
385
386   num_removed_elems = 0;
387
388   max_bin_load = imax_bin_load;
389
390   assert(enoughBins());
391 }
392
393 template<class K, class V>
394 dictionary_hash<K,V>::dictionary_hash(const dictionary_hash<K,V> &src) :
395                                       all_elems(src.all_elems), bins(src.bins) {
396   // copying an entire dictionary should be a rare occurance; we provide it only
397   // for completeness (I'd prefer to leave it out, actually)
398   hasher = src.hasher;
399   num_removed_elems = src.num_removed_elems;
400   max_bin_load = src.max_bin_load;
401
402   assert(enoughBins());
403 }
404
405 template<class K, class V>
406 dictionary_hash<K,V> &
407 dictionary_hash<K,V>::operator=(const dictionary_hash<K,V> &src) {
408   // assigning an entire dictionary should be a rare occurance; we provide it only
409   // for completeness (I'd prefer to leave it out, actually)
410   if (&src == this) return *this;
411
412   hasher = src.hasher;
413   all_elems = src.all_elems;
414   bins = src.bins;
415
416   num_removed_elems = src.num_removed_elems;
417   max_bin_load = src.max_bin_load;
418
419   assert(enoughBins());
420
421   return *this;
422 }
423
424 template<class K, class V>
425 unsigned dictionary_hash<K,V>::size() const {
426   assert(num_removed_elems <= all_elems.size());
427   return all_elems.size() - num_removed_elems;
428 }
429
430 template<class K, class V>
431 V& dictionary_hash<K,V>::operator[](const K& key) {
432   const unsigned ndx = locate_addIfNotFound(key);
433
434   //assert(defines(key)); // WARNING: expensive assert!
435    
436   return all_elems[ndx].val;
437 }
438
439 template<class K, class V>
440 const V& dictionary_hash<K,V>::get(const K &key) const {
441   const unsigned ndx = locate(key, false);
442   // false: if removed, then it doesn't count
443
444   if (ndx == UINT_MAX)
445     assert(false && "dictionary_hash get() requires a hit");
446    
447   return all_elems[ndx].val;
448 }
449
450 template<class K, class V>
451 V& dictionary_hash<K,V>::get(const K &key) {
452   const unsigned ndx = locate(key, false);
453   // false: if removed, then it doesn't count
454
455   if (ndx == UINT_MAX)
456     assert(false && "dictionary_hash get() requires a hit");
457    
458   return all_elems[ndx].val;
459 }
460
461 template<class K, class V>
462 const V& dictionary_hash<K,V>::get_and_remove(const K &key) {
463   const unsigned ndx = locate(key, false);
464   // false: if removed, then it doesn't count
465
466   if (ndx == UINT_MAX)
467     assert(false && "dictionary_hash get_and_remove() requires a hit");
468
469   const unsigned oldsize = size();
470
471   entry &e = all_elems[ndx];
472
473   assert(!e.removed);
474   e.removed = true;
475   num_removed_elems++;
476   assert(num_removed_elems <= all_elems.size());
477
478   assert(size() + 1 == oldsize);
479    
480   return e.val;
481 }
482
483 template<class K, class V>
484 bool dictionary_hash<K,V>::find_and_remove(const K &key, V &val) {
485   const unsigned ndx = locate(key, false);
486   // false: if removed, then it doesn't count
487
488   if (ndx == UINT_MAX)
489     return false;
490
491   const unsigned oldsize = size();
492
493   entry &e = all_elems[ndx];
494
495   assert(!e.removed);
496   e.removed = true;
497   num_removed_elems++;
498   assert(num_removed_elems <= all_elems.size());
499
500   assert(size() + 1 == oldsize);
501
502   val = e.val;
503
504   return true;
505 }
506
507 template<class K, class V>
508 void dictionary_hash<K,V>::set(const K &key, const V &val) {
509   const unsigned ndx = locate(key, true); // true --> if removed, count as a find
510
511   if (ndx != UINT_MAX) {
512     // Found an entry.  If this entry is actually 'removed', then un-remove it.
513     // Otherwise, barf.
514     entry &theEntry = all_elems[ndx];
515     if (theEntry.removed) {
516       assert(num_removed_elems > 0);
517       theEntry.val = val;
518       theEntry.removed = false;
519       num_removed_elems--;
520
521       // clearing the removed flag can't possibly invalidate the performance
522       // invariant
523     }
524     else
525       assert(false && "dictionary set(): an entry with that key already exists");
526   }
527   else {
528     // Didn't find that entry.  Good.  Create that entry and add to the dictionary.
529     add(key, val);
530       
531     //assert(defines(key)); // WARNING: expensive assert()
532   }
533 }
534
535 template<class K, class V>
536 bool dictionary_hash<K,V>::find(const K& key, V& el) const {
537   const unsigned ndx = locate(key, false); // false --> don't find removed items
538   if (ndx == UINT_MAX)
539     return false;
540   else {
541     el = all_elems[ndx].val;
542     return true;
543   }
544 }
545
546 template<class K, class V>
547 bool dictionary_hash<K,V>::defines(const K& key) const {
548   const unsigned ndx = locate(key, false); // false --> don't find removed items
549   return (ndx != UINT_MAX);
550 }
551
552 template<class K, class V>
553 void dictionary_hash<K,V>::undef(const K& key) {
554   unsigned ndx = locate(key, false); // false --> don't find removed items
555   if (ndx == UINT_MAX)
556     return; // nothing to do...either doesn't exist, or already removed
557
558 #ifndef NDEBUG
559   const unsigned oldsize = size();
560 #endif
561
562   entry &e = all_elems[ndx];
563   assert(!e.removed);
564   e.removed = true;
565   num_removed_elems++;
566
567 #ifndef NDEBUG
568   assert(oldsize == size()+1);
569   assert(num_removed_elems <= all_elems.size());
570 #endif
571 }
572
573 #ifndef _KERNEL
574 // Sun's compiler can't handle the return types
575
576 template<class K, class V>
577 vector<K>
578 dictionary_hash<K,V>::keys() const {
579   // One can argue that this method (and values(), below) should be removed in
580   // favor of using the dictionary iterator class.  I agree; it's here only for
581   // backwards compatibility.
582   vector<K> result;
583   result.reserve(size());
584    
585   // note that the iterator class automatically skips elems tagged for removal
586   const_iterator finish = end();
587   for (const_iterator iter=begin(); iter != finish; iter++)
588     result.push_back(iter.currkey());
589
590   return result;
591 }
592
593 template<class K, class V>
594 vector<V>
595 dictionary_hash<K,V>::values() const {
596   // One can argue that this method (and keys(), above) should be removed in
597   // favor of using the dictionary iterator class.  I agree; it's here only for
598   // backwards compatibility.
599   vector<V> result;
600   result.reserve(size());
601    
602   // note that the iterator class automatically skips elems tagged for removal
603   const_iterator finish = end();
604   for (const_iterator iter=begin(); iter != finish; ++iter)
605     result.push_back(*iter);
606
607   return result;
608 }
609
610 template<class K, class V>
611 vector< pair<K, V> >
612 dictionary_hash<K,V>::keysAndValues() const {
613   vector< pair<K, V> > result;
614   result.reserve(size());
615    
616   const_iterator finish = end();
617   for (const_iterator iter = begin(); iter != finish; ++iter)
618     result.push_back( make_pair(iter.currkey(), iter.currval()) );
619
620   return result;
621 }
622
623 #endif //ifndef(_KERNEL)
624
625 template<class K, class V>
626 void dictionary_hash<K,V>::clear() {
627   // max_bin_load and bin_grow_factor don't change.
628   // Also, bins.size() doesn't change; is this best (perhaps we should shrink
629   // bins down to its original size...not trivial since we didn't set that value
630   // aside in the ctor.  In any event we don't lose sleep since calling clear() is
631   // rare.)  Like class vector, we could also provide a zap() method which actually
632   // does free up memory.
633
634   all_elems.clear();
635
636   for (unsigned lcv=0; lcv < bins.size(); lcv++)
637     bins[lcv] = UINT_MAX;
638
639   num_removed_elems = 0;
640
641   assert(size() == 0);
642
643   assert(enoughBins());
644 }
645
646 template<class K, class V>
647 unsigned
648 dictionary_hash<K,V>::locate(const K& key, bool evenIfRemoved) const {
649   // An internal routine used by everyone.
650
651   // call hasher(key), but make sure it fits in 31 bits:
652   unsigned hashval = hasher(key) & 0x7fffffff;
653
654   const unsigned bin = hashval % bins.size();
655    
656   unsigned elem_ndx = bins[bin];
657   while (elem_ndx != UINT_MAX) {
658     const entry &elem = all_elems[elem_ndx];
659
660     // verify that this elem is in the right bin!
661     assert(elem.key_hashval % bins.size() == bin);
662       
663     if (elem.key_hashval == hashval && elem.key == key) {
664       // found it...unless it was removed
665       if (elem.removed && !evenIfRemoved)
666         elem_ndx = UINT_MAX;
667
668       break;
669     }
670     else
671       elem_ndx = elem.next;
672   }
673
674   return elem_ndx;
675 }
676
677
678 template<class K, class V>
679 unsigned
680 dictionary_hash<K,V>::add(const K& key, const V &val) {
681   // internal routine called by locate_addIfNotFound() and by set()
682   // returns ndx (within all_elems[]) of newly added item
683
684   // before the insert, we should have enough bins to fit everything nicely...
685   assert(enoughBins());
686
687   if (!enoughBinsIf1MoreItemAdded()) {
688     // ...but adding 1 more element would make things too big.  So, grow (add
689     // some new bins) before adding.
690          
691     const unsigned new_numbins = (unsigned)(bins.size() * bin_grow_factor);
692     assert(new_numbins > bins.size() && "bin_grow_factor too small");
693
694     grow_numbins(new_numbins);
695
696     // ...verify that we have enough bins after the grow:
697     assert(enoughBinsIf1MoreItemAdded());
698
699     // fall through...
700   }
701       
702   // We don't need to grow.
703   const unsigned hashval = hasher(key) & 0x7fffffff; // make sure it fits in 31 bits
704   const unsigned bin     = hashval % bins.size();
705
706   entry e(key, hashval, val, UINT_MAX);
707   e.next = bins[bin];
708   all_elems.push_back(e);
709   //entry *e = all_elems.append_with_inplace_construction();
710   //new((void*)e)entry(key, hashval, val, UINT_MAX);
711   const unsigned new_entry_ndx = all_elems.size()-1;
712
713   // Insert at the head of the bin (we could insert at the tail, but this
714   // is a tad easier, and besides, position in the bin doesn't matter)
715   bins[bin] = new_entry_ndx;
716
717   //assert(defines(key)); // WARNING: expensive assert()
718       
719   assert(enoughBins());
720   return new_entry_ndx;
721 }
722
723 template<class K, class V>
724 unsigned
725 dictionary_hash<K,V>::locate_addIfNotFound(const K& key) {
726   // An internal routine used by everyone.
727   // Returns ndx (within all_elems[]) of the item.
728
729   unsigned result = locate(key, true); // true --> find even if 'removed' flag set
730   // UINT_MAX if not found
731
732   if (result == UINT_MAX)
733     return add(key, V());
734   else {
735     // found the item.
736     entry &e = all_elems[result];
737     if (e.removed) {
738       // Item has been removed.  We're gonna un-remove it.
739
740       //assert(!defines(key)); // WARNING: expensive assert
741       
742       assert(num_removed_elems > 0);
743
744       e.removed = false;
745       e.val = V();
746       num_removed_elems--;
747
748       // Clearing the 'removed' flag of an entry can't possibly invalidate the
749       // performance assertion
750     }
751
752     //assert(defines(key)); // WARNING: expensive assert
753       
754     return result;
755   }
756 }
757
758 template<class K, class V>
759 void
760 dictionary_hash<K,V>::grow_numbins(unsigned new_numbins) {
761   assert(new_numbins > bins.size() && "grow_numbins not adding any bins?");
762
763   bins.resize(new_numbins, true); // true --> exact resize flag
764   for (unsigned binlcv=0; binlcv < bins.size(); binlcv++)
765     bins[binlcv] = UINT_MAX;
766
767   // Look for elems to remove; shrink all_elems[] as appropriate
768   if (num_removed_elems > 0) {
769     for (unsigned lcv=0; lcv < all_elems.size(); ) {
770       entry &e = all_elems[lcv];
771       if (e.removed) {
772         const unsigned oldsize = all_elems.size();
773         assert(oldsize > 0);
774
775         // remove item from vector by swap with last item & resizing/-1
776         all_elems[lcv] = all_elems[oldsize-1]; // should be OK if lcv==oldsize-1
777         all_elems.resize(oldsize-1);
778
779         num_removed_elems--;
780             
781         // note: we DON'T bump up lcv in this case
782       }
783       else
784         lcv++;
785     }
786
787     assert(num_removed_elems == 0);
788   }
789
790   // Now rehash everything.  Sounds awfully expensive, and I guess it is -- it's
791   // linear in the total # of items in the hash table.  But take heart: beyond this
792   // point, we don't need to make any copies of type KEY or VALUE, resize any vectors,
793   // or recalculate any hash values.  We just need to assign to <n> unsigned
794   // integers.
795
796   const unsigned numbins = bins.size(); // loop invariant
797   for (unsigned lcv=0; lcv < all_elems.size(); lcv++) {
798     entry &e = all_elems[lcv];
799     assert(!e.removed);
800
801     // the entry's key_hashval stays the same, but it may go into a different bin:
802     const unsigned bin = e.key_hashval % numbins;
803
804     // prepend element to bin:
805     unsigned &thebin = bins[bin];
806       
807     e.next = thebin;
808     thebin = lcv;
809   }
810
811   // The invariant might not have held at the top of this routine, but it
812   // should now hold.
813   assert(enoughBins());
814 }
815
816 #endif