update to set up make variables for compiling modules with libhrtime
[dyninst.git] / common / src / Dictionary.C
1 /*
2  * Copyright (c) 1996-2000 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 "common/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    unsigned elem_ndx = UINT_MAX;
212
213    if( bins.size() > 0 )
214    {
215        const unsigned hashval = hasher(key);
216        const unsigned bin     = hashval % bins.size();
217    
218        elem_ndx = bins[bin];
219        while (elem_ndx != UINT_MAX) {
220           const entry &elem = all_elems[elem_ndx];
221
222           // verify that this elem is in the right bin!
223           assert(elem.key_hashval % bins.size() == bin);
224       
225           if (elem.key_hashval == hashval && elem.key == key) {
226              // found it...unless it was removed
227              if (elem.removed && !evenIfRemoved)
228                 elem_ndx = UINT_MAX;
229
230              break;
231           }
232           else
233              elem_ndx = elem.next;
234        }
235    }
236    return elem_ndx;
237 }
238
239
240 template<class K, class V>
241 unsigned
242 dictionary_hash<K,V>::locate_addIfNotFound(const K& key) {
243    // An internal routine used by everyone.
244    // Returns ndx (within all_elems[]) of the item.
245
246    unsigned result = locate(key, true); // true --> find even if 'removed' flag set
247       // UINT_MAX if not found
248
249    if (result == UINT_MAX) {
250       // didn't find the item.  We're gonna insert.
251       // we know that the item's removed flag isn't set; if it was, result wouldn't
252       // have been UINT_MAX.  So we truly need to add an item.
253
254       // before the insert, we should have enough bins to fit everything nicely...
255       assert(bins.size() * max_bin_load >= size());
256       
257       if (bins.size() * max_bin_load < (size() + 1)) {
258          // ...but adding 1 more element would make things too big.  So, grow (add
259          // some new bins) before adding.
260          
261          const unsigned new_numbins = (unsigned)(bins.size() * bin_grow_factor);
262          assert(new_numbins > bins.size() && "grow factor negative or barely > 1.00?");
263
264          // ... after the grow, we should have enough bins:
265          assert(new_numbins * max_bin_load >= (size()+1));
266
267          grow_numbins(new_numbins);
268
269          // ...verify that we have enough bins after the grow:
270          assert(bins.size() * max_bin_load >= (size()+1));
271
272          // fall through...
273       }
274       
275       // We don't need to grow.
276       const unsigned hashval = hasher(key);
277       const unsigned bin     = hashval % bins.size();
278
279       all_elems += entry(key, hashval, V(), UINT_MAX);
280       const unsigned new_entry_ndx = all_elems.size()-1;
281
282       // Insert at the head of the bin (we could insert at the tail, but this
283       // is a tad easier, and besides, position in the bin doesn't matter)
284       entry &e = all_elems[new_entry_ndx];
285       e.next = bins[bin];
286       bins[bin] = new_entry_ndx;
287
288 //      assert(defines(key)); // WARNING: expensive assert()
289
290       assert(bins.size() * max_bin_load >= size());  // Check invariant again
291
292       return new_entry_ndx;
293    }
294    else {
295       // found the item.
296      
297       assert(bins.size() * max_bin_load >= size());  // Check invariant first
298
299       entry &e = all_elems[result];
300       if (e.removed) {
301          // Item has been removed.  We're gonna un-remove it.
302
303 //         assert(!defines(key)); // WARNING: expensive assert
304       
305          assert(num_removed_elems > 0);
306
307          e.removed = false;
308          e.val = V();
309          num_removed_elems--;
310
311          if (! (bins.size() * max_bin_load >= size())) {
312            // Oops, the un-remove just broke the invariant!
313            // Grow some bins to re-establish the invariant.
314
315            const unsigned new_numbins = (unsigned)(bins.size() * bin_grow_factor);
316            assert(new_numbins > bins.size() && "grow factor negative or barely > 1.00?");
317
318            // ... after the grow, we should have enough bins:
319            assert(new_numbins * max_bin_load >= size());
320
321            grow_numbins(new_numbins);
322
323            // ...verify that we have enough bins after the grow:
324            assert(bins.size() * max_bin_load >= size());
325
326            result = locate(key, true); // true --> find even if 'removed' flag set
327            assert(result != UINT_MAX); // should exist
328         }
329       }
330
331 //      assert(defines(key)); // WARNING: expensive assert
332
333       assert(bins.size() * max_bin_load >= size());  // Check invariant again
334
335       return result;
336    }
337 }
338
339 template<class K, class V>
340 void
341 dictionary_hash<K,V>::grow_numbins(unsigned new_numbins) {
342    assert(new_numbins > bins.size() && "grow_numbins not adding any bins?");
343
344    bins.resize(new_numbins);
345    for (unsigned binlcv=0; binlcv < bins.size(); binlcv++)
346       bins[binlcv] = UINT_MAX;
347
348    // Look for elems to remove; shrink all_elems[] as appropriate
349    if (num_removed_elems > 0) {
350       for (unsigned lcv=0; lcv < all_elems.size(); ) {
351          entry &e = all_elems[lcv];
352          if (e.removed) {
353             const unsigned oldsize = all_elems.size();
354             assert(oldsize > 0);
355
356             // remove item from vector by swap with last item & resizing/-1
357             all_elems[lcv] = all_elems[oldsize-1]; // should be OK if lcv==oldsize-1
358             all_elems.resize(oldsize-1);
359
360             num_removed_elems--;
361             
362             // note: we DON'T bump up lcv in this case
363          }
364          else
365             lcv++;
366       }
367
368       assert(num_removed_elems == 0);
369    }
370
371    // Now rehash everything.  Sounds awfully expensive, and I guess it is -- it's
372    // linear in the total # of items in the hash table.  But take heart: beyond this
373    // point, we don't need to make any copies of type KEY or VALUE, resize any vectors,
374    // or recalculate any hash values.  We just need to assign to <n> unsigned
375    // integers.
376
377    const unsigned numbins = bins.size(); // loop invariant
378    for (unsigned lcv=0; lcv < all_elems.size(); lcv++) {
379       entry &e = all_elems[lcv];
380       assert(!e.removed);
381
382       // the entry's key_hashval stays the same, but it may go into a different bin:
383       const unsigned bin = e.key_hashval % numbins;
384
385       // prepend element to bin:
386       unsigned &thebin = bins[bin];
387       
388       e.next = thebin;
389       thebin = lcv;
390    }
391
392    // the invariant should now hold
393    assert(bins.size() * max_bin_load >= size());
394 }