Build identifier class
[dyninst.git] / pdutil / src / Dictionary.C
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.C
43
44 #include "util/h/Dictionary.h"
45 #include <limits.h> // UINT_MAX
46
47 template<class K, class V>
48 dictionary_hash<K,V>::dictionary_hash(unsigned (*hf)(const K &),
49                                     unsigned nbins,
50                                     float imax_bin_load,
51                                        // we keep #bins*max_bin_load <= total # items
52                                     float ibin_grow_factor
53                                        // when we have to grow, by how much?
54    ) {
55    assert(ibin_grow_factor > 1.0);
56    assert(ibin_grow_factor < 10.0); // let's not go nuts and grow like crazy!
57    assert(imax_bin_load > 0.0);
58    assert(imax_bin_load < 10.0); // why would you want to allow so many
59                                  // collisions per bin?
60
61    hasher = hf;
62
63    // Note: all_elems[] starts off as an empty vector.
64
65    // Pre-size the # of bins from parameter.  Each bins starts off empty (UINT_MAX)
66    assert(nbins > 0);
67    bins.resize(nbins);
68    for (unsigned binlcv=0; binlcv < bins.size(); binlcv++)
69       bins[binlcv] = UINT_MAX;
70
71    num_removed_elems = 0;
72
73    max_bin_load = imax_bin_load;
74    bin_grow_factor = ibin_grow_factor;
75 }
76
77 template<class K, class V>
78 dictionary_hash<K,V>::dictionary_hash(const dictionary_hash &src) :
79                               all_elems(src.all_elems),
80                               bins(src.bins) {
81    // copying an entire dictionary should be a rare occurance; we provide it only
82    // for completeness (I'd prefer to leave it out, actually)
83    hasher = src.hasher;
84    num_removed_elems = src.num_removed_elems;
85    max_bin_load = src.max_bin_load;
86    bin_grow_factor = src.bin_grow_factor;
87 }
88
89 template<class K, class V>
90 dictionary_hash<K,V> &
91 dictionary_hash<K,V>::operator=(const dictionary_hash &src) {
92    // assigning an entire dictionary should be a rare occurance; we provide it only
93    // for completeness (I'd prefer to leave it out, actually)
94    if (&src == this) return *this;
95
96    hasher = src.hasher;
97    all_elems = src.all_elems;
98    bins = src.bins;
99
100    num_removed_elems = src.num_removed_elems;
101    max_bin_load = src.max_bin_load;
102    bin_grow_factor = src.bin_grow_factor;
103
104    return *this;
105 }
106
107 template<class K, class V>
108 unsigned
109 dictionary_hash<K,V>::size() const {
110    assert(num_removed_elems <= all_elems.size());
111    return all_elems.size() - num_removed_elems;
112 }
113
114 template<class K, class V>
115 V&
116 dictionary_hash<K,V>::operator[](const K& key) {
117    const unsigned ndx = locate_addIfNotFound(key);
118
119 //   assert(defines(key)); // WARNING: expensive assert!
120    
121    return all_elems[ndx].val;
122 }
123
124 template<class K, class V>
125 bool
126 dictionary_hash<K,V>::find(const K& key, V& el) const {
127    const unsigned ndx = locate(key, false); // false --> don't find removed items
128    if (ndx == UINT_MAX)
129       return false;
130    else {
131       el = all_elems[ndx].val;
132       return true;
133    }
134 }
135
136 template<class K, class V>
137 bool
138 dictionary_hash<K,V>::defines(const K& key) const {
139    const unsigned ndx = locate(key, false); // false --> don't find removed items
140    return (ndx != UINT_MAX);
141 }
142
143 template<class K, class V>
144 void
145 dictionary_hash<K,V>::undef(const K& key) {
146    unsigned ndx = locate(key, false); // false --> don't find removed items
147    if (ndx == UINT_MAX)
148       return; // nothing to do...either doesn't exist, or already removed
149
150    const unsigned oldsize = size();
151    entry &e = all_elems[ndx];
152    assert(!e.removed);
153    e.removed = true;
154    num_removed_elems++;
155    assert(oldsize == size()+1);
156    assert(num_removed_elems <= all_elems.size());
157 }
158
159 template<class K, class V>
160 vector<K>
161 dictionary_hash<K,V>::keys() const {
162    // One can argue that this method (and values(), below) should be removed in
163    // favor of using the dictionary iterator class.  I agree; it's here only for
164    // backwards compatibility.
165    vector<K> result(size());
166    unsigned ndx=0;
167    for (unsigned i=0; i < all_elems.size(); i++)
168       if (!all_elems[i].removed)
169          result[ndx++] = all_elems[i].key;
170    assert(ndx == size());
171    return result;
172 }
173
174 template<class K, class V>
175 vector<V>
176 dictionary_hash<K,V>::values() const {
177    // One can argue that this method (and keys(), above) should be removed in
178    // favor of using the dictionary iterator class.  I agree; it's here only for
179    // backwards compatibility.
180    vector<V> result(size());
181    unsigned ndx=0;
182    for (unsigned i=0; i < all_elems.size(); i++)
183       if (!all_elems[i].removed)
184          result[ndx++] = all_elems[i].val;
185    assert(ndx == size());
186    return result;
187 }
188
189 template<class K, class V>
190 void dictionary_hash<K,V>::clear() {
191    // max_bin_load and bin_grow_factor don't change.
192    // Also, bins.size() doesn't change; is this best (perhaps we should shrink
193    // bins down to its original size...not trivial since we didn't set that value
194    // aside in the ctor.  In any event we don't lose sleep since calling clear() is
195    // rare.)
196
197    all_elems.resize(0);
198
199    for (unsigned lcv=0; lcv < bins.size(); lcv++)
200       bins[lcv] = UINT_MAX;
201
202    num_removed_elems = 0;
203
204    assert(size() == 0);
205 }
206
207 template<class K, class V>
208 unsigned
209 dictionary_hash<K,V>::locate(const K& key, bool evenIfRemoved) const {
210    // An internal routine used by everyone.
211    const unsigned hashval = hasher(key);
212    const unsigned bin     = hashval % bins.size();
213    
214    unsigned elem_ndx = bins[bin];
215    while (elem_ndx != UINT_MAX) {
216       const entry &elem = all_elems[elem_ndx];
217
218       // verify that this elem is in the right bin!
219       assert(elem.key_hashval % bins.size() == bin);
220       
221       if (elem.key_hashval == hashval && elem.key == key) {
222          // found it...unless it was removed
223          if (elem.removed && !evenIfRemoved)
224             elem_ndx = UINT_MAX;
225
226          break;
227       }
228       else
229          elem_ndx = elem.next;
230    }
231
232    return elem_ndx;
233 }
234
235
236 template<class K, class V>
237 unsigned
238 dictionary_hash<K,V>::locate_addIfNotFound(const K& key) {
239    // An internal routine used by everyone.
240    // Returns ndx (within all_elems[]) of the item.
241
242    unsigned result = locate(key, true); // true --> find even if 'removed' flag set
243       // UINT_MAX if not found
244
245    if (result == UINT_MAX) {
246       // didn't find the item.  We're gonna insert.
247       // we know that the item's removed flag isn't set; if it was, result wouldn't
248       // have been UINT_MAX.  So we truly need to add an item.
249
250       // before the insert, we should have enough bins to fit everything nicely...
251       assert(bins.size() * max_bin_load >= size());
252       
253       if (bins.size() * max_bin_load < (size() + 1)) {
254          // ...but adding 1 more element would make things too big.  So, grow (add
255          // some new bins) before adding.
256          
257          const unsigned new_numbins = (unsigned)(bins.size() * bin_grow_factor);
258          assert(new_numbins > bins.size() && "grow factor negative or barely > 1.00?");
259
260          // ... after the grow, we should have enough bins:
261          assert(new_numbins * max_bin_load >= (size()+1));
262
263          grow_numbins(new_numbins);
264
265          // ...verify that we have enough bins after the grow:
266          assert(bins.size() * max_bin_load >= (size()+1));
267
268          // fall through...
269       }
270       
271       // We don't need to grow.
272       const unsigned hashval = hasher(key);
273       const unsigned bin     = hashval % bins.size();
274
275       all_elems += entry(key, hashval, V(), UINT_MAX);
276       const unsigned new_entry_ndx = all_elems.size()-1;
277
278       // Insert at the head of the bin (we could insert at the tail, but this
279       // is a tad easier, and besides, position in the bin doesn't matter)
280       entry &e = all_elems[new_entry_ndx];
281       e.next = bins[bin];
282       bins[bin] = new_entry_ndx;
283
284 //      assert(defines(key)); // WARNING: expensive assert()
285
286       assert(bins.size() * max_bin_load >= size());  // Check invariant again
287
288       return new_entry_ndx;
289    }
290    else {
291       // found the item.
292      
293       assert(bins.size() * max_bin_load >= size());  // Check invariant first
294
295       entry &e = all_elems[result];
296       if (e.removed) {
297          // Item has been removed.  We're gonna un-remove it.
298
299 //         assert(!defines(key)); // WARNING: expensive assert
300       
301          assert(num_removed_elems > 0);
302
303          e.removed = false;
304          e.val = V();
305          num_removed_elems--;
306
307          if (! (bins.size() * max_bin_load >= size())) {
308            // Oops, the un-remove just broke the invariant!
309            // Grow some bins to re-establish the invariant.
310
311            const unsigned new_numbins = (unsigned)(bins.size() * bin_grow_factor);
312            assert(new_numbins > bins.size() && "grow factor negative or barely > 1.00?");
313
314            // ... after the grow, we should have enough bins:
315            assert(new_numbins * max_bin_load >= size());
316
317            grow_numbins(new_numbins);
318
319            // ...verify that we have enough bins after the grow:
320            assert(bins.size() * max_bin_load >= size());
321
322            result = locate(key, true); // true --> find even if 'removed' flag set
323            assert(result != UINT_MAX); // should exist
324         }
325       }
326
327 //      assert(defines(key)); // WARNING: expensive assert
328
329       assert(bins.size() * max_bin_load >= size());  // Check invariant again
330
331       return result;
332    }
333 }
334
335 template<class K, class V>
336 void
337 dictionary_hash<K,V>::grow_numbins(unsigned new_numbins) {
338    assert(new_numbins > bins.size() && "grow_numbins not adding any bins?");
339
340    bins.resize(new_numbins);
341    for (unsigned binlcv=0; binlcv < bins.size(); binlcv++)
342       bins[binlcv] = UINT_MAX;
343
344    // Look for elems to remove; shrink all_elems[] as appropriate
345    if (num_removed_elems > 0) {
346       for (unsigned lcv=0; lcv < all_elems.size(); ) {
347          entry &e = all_elems[lcv];
348          if (e.removed) {
349             const unsigned oldsize = all_elems.size();
350             assert(oldsize > 0);
351
352             // remove item from vector by swap with last item & resizing/-1
353             all_elems[lcv] = all_elems[oldsize-1]; // should be OK if lcv==oldsize-1
354             all_elems.resize(oldsize-1);
355
356             num_removed_elems--;
357             
358             // note: we DON'T bump up lcv in this case
359          }
360          else
361             lcv++;
362       }
363
364       assert(num_removed_elems == 0);
365    }
366
367    // Now rehash everything.  Sounds awfully expensive, and I guess it is -- it's
368    // linear in the total # of items in the hash table.  But take heart: beyond this
369    // point, we don't need to make any copies of type KEY or VALUE, resize any vectors,
370    // or recalculate any hash values.  We just need to assign to <n> unsigned
371    // integers.
372
373    const unsigned numbins = bins.size(); // loop invariant
374    for (unsigned lcv=0; lcv < all_elems.size(); lcv++) {
375       entry &e = all_elems[lcv];
376       assert(!e.removed);
377
378       // the entry's key_hashval stays the same, but it may go into a different bin:
379       const unsigned bin = e.key_hashval % numbins;
380
381       // prepend element to bin:
382       unsigned &thebin = bins[bin];
383       
384       e.next = thebin;
385       thebin = lcv;
386    }
387
388    // the invariant should now hold
389    assert(bins.size() * max_bin_load >= size());
390 }