improvements to iterator class; bug fix to undef
[dyninst.git] / common / 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 an average of 10
59                                  // collisions per bin?
60
61    hasher = hf;
62
63    // Note: all_elems[] starts off as an empty vector.
64    // pre-size the # of bins from parameter.  Each bins starts off empty.
65    assert(nbins > 0);
66    bins.resize(nbins);
67    for (unsigned binlcv=0; binlcv < bins.size(); binlcv++)
68       bins[binlcv] = UINT_MAX;
69
70    num_removed_elems = 0;
71
72    max_bin_load = imax_bin_load;
73    bin_grow_factor = ibin_grow_factor;
74 }
75
76 template<class K, class V>
77 dictionary_hash<K,V>::dictionary_hash(const dictionary_hash &src) :
78                               all_elems(src.all_elems),
79                               bins(src.bins) {
80    hasher = src.hasher;
81    num_removed_elems = src.num_removed_elems;
82    max_bin_load = src.max_bin_load;
83    bin_grow_factor = src.bin_grow_factor;
84 }
85
86 template<class K, class V>
87 dictionary_hash<K,V> &
88 dictionary_hash<K,V>::operator=(const dictionary_hash &src) {
89    if (&src == this) return *this;
90
91    hasher = src.hasher;
92    all_elems = src.all_elems;
93    bins = src.bins;
94
95    num_removed_elems = src.num_removed_elems;
96    max_bin_load = src.max_bin_load;
97    bin_grow_factor = src.bin_grow_factor;
98
99    return *this;
100 }
101
102 template<class K, class V>
103 unsigned
104 dictionary_hash<K,V>::size() const {
105    assert(num_removed_elems <= all_elems.size());
106    return all_elems.size() - num_removed_elems;
107 }
108
109 template<class K, class V>
110 V&
111 dictionary_hash<K,V>::operator[](const K& key) {
112    const unsigned ndx = locate_addIfNotFound(key);
113
114 //   assert(defines(key)); // WARNING: expensive assert!
115    
116    return all_elems[ndx].val;
117 }
118
119 template<class K, class V>
120 bool
121 dictionary_hash<K,V>::find(const K& key, V& el) const {
122    const unsigned ndx = locate(key, false); // false --> don't find removed items
123    if (ndx == UINT_MAX)
124       return false;
125    else {
126       el = all_elems[ndx].val;
127       return true;
128    }
129 }
130
131 template<class K, class V>
132 bool
133 dictionary_hash<K,V>::defines(const K& key) const {
134    const unsigned ndx = locate(key, false); // false --> don't find removed items
135    return (ndx != UINT_MAX);
136 }
137
138 template<class K, class V>
139 void
140 dictionary_hash<K,V>::undef(const K& key) {
141    unsigned ndx = locate(key, false); // false --> don't find removed items
142    if (ndx == UINT_MAX)
143       return; // nothing to do...either doesn't exist, or already removed
144
145    const unsigned oldsize = size();
146    entry &e = all_elems[ndx];
147    assert(!e.removed);
148    e.removed = true;
149    num_removed_elems++;
150    assert(oldsize == size()+1);
151    assert(num_removed_elems <= all_elems.size());
152 }
153
154 template<class K, class V>
155 vector<K>
156 dictionary_hash<K,V>::keys() const {
157    vector<K> result(size());
158    unsigned ndx=0;
159    for (unsigned i=0; i < all_elems.size(); i++)
160       if (!all_elems[i].removed)
161          result[ndx++] = all_elems[i].key;
162    assert(ndx == size());
163    return result;
164 }
165
166 template<class K, class V>
167 vector<V>
168 dictionary_hash<K,V>::values() const {
169    vector<V> result(size());
170    unsigned ndx=0;
171    for (unsigned i=0; i < all_elems.size(); i++)
172       if (!all_elems[i].removed)
173          result[ndx++] = all_elems[i].val;
174    assert(ndx == size());
175    return result;
176 }
177
178 template<class K, class V>
179 void dictionary_hash<K,V>::clear() {
180    // max_bin_load, bin_grow_factor, bins.size() remain unchanged
181
182    all_elems.resize(0);
183
184    for (unsigned lcv=0; lcv < bins.size(); lcv++)
185       bins[lcv] = UINT_MAX;
186
187    num_removed_elems = 0;
188
189    assert(size() == 0);
190 }
191
192 template<class K, class V>
193 unsigned
194 dictionary_hash<K,V>::locate(const K& key, bool evenIfRemoved) const {
195    // An internal routine used by everyone.
196    const unsigned hashval = hasher(key);
197    const unsigned bin     = hashval % bins.size();
198    
199    unsigned elem_ndx = bins[bin];
200    while (elem_ndx != UINT_MAX) {
201       const entry &elem = all_elems[elem_ndx];
202
203       // verify that this elem is in the right bin!
204       assert(elem.key_hashval % bins.size() == bin);
205       
206       if (elem.key_hashval == hashval && elem.key == key) {
207          // found it...unless it was removed
208          if (elem.removed && !evenIfRemoved)
209             elem_ndx = UINT_MAX;
210
211          break;
212       }
213       else
214          elem_ndx = elem.next;
215    }
216
217    return elem_ndx;
218 }
219
220
221 template<class K, class V>
222 unsigned
223 dictionary_hash<K,V>::locate_addIfNotFound(const K& key) {
224    // An internal routine used by everyone.
225    // Returns ndx (within all_elems[]) of the item.
226
227    unsigned result = locate(key, true); // true --> find even if 'removed' flag set
228       // UINT_MAX if not found
229
230    if (result == UINT_MAX) {
231       // didn't find the item.  We're gonna insert.
232       // we know that the item's removed flag isn't set; if it was, result wouldn't
233       // have been UINT_MAX.  So we truly need to add an item.
234
235       // before the insert, we should have enough bins to fit everything nicely...
236       assert(bins.size() * max_bin_load >= size());
237       
238       if (bins.size() * max_bin_load < (size() + 1)) {
239          // ...but adding 1 more element would make things too big.  So, grow (add
240          // some new bins) before adding.
241          
242          const unsigned new_numbins = (unsigned)(bins.size() * bin_grow_factor);
243          assert(new_numbins > bins.size() && "grow factor negative or barely > 1.00?");
244
245          // ... after the grow, we should have enough bins:
246          assert(new_numbins * max_bin_load >= (size()+1));
247
248          grow_numbins(new_numbins);
249
250          // ...verify that we have enough bins after the grow:
251          assert(bins.size() * max_bin_load >= (size()+1));
252
253          // fall through...
254       }
255       
256       // We don't need to grow.
257       const unsigned hashval = hasher(key);
258       const unsigned bin     = hashval % bins.size();
259
260       all_elems += entry(key, hashval, V(), UINT_MAX);
261       const unsigned new_entry_ndx = all_elems.size()-1;
262
263       // Insert at the head of the bin (we could insert at the tail, but this
264       // is a tad easier, and besides, position in the bin doesn't matter)
265       entry &e = all_elems[new_entry_ndx];
266       e.next = bins[bin];
267       bins[bin] = new_entry_ndx;
268
269 //      assert(defines(key)); // WARNING: expensive assert()
270       
271       return new_entry_ndx;
272    }
273    else {
274       // found the item.
275       entry &e = all_elems[result];
276       if (e.removed) {
277          // Item has been removed.  We're gonna un-remove it.
278
279 //         assert(!defines(key)); // WARNING: expensive assert
280       
281          assert(num_removed_elems > 0);
282
283          e.removed = false;
284          e.val = V();
285          num_removed_elems--;
286       }
287
288 //      assert(defines(key)); // WARNING: expensive assert
289       
290       return result;
291    }
292 }
293
294 template<class K, class V>
295 void
296 dictionary_hash<K,V>::grow_numbins(unsigned new_numbins) {
297    assert(new_numbins > bins.size() && "grow_numbins not adding any bins?");
298
299    bins.resize(new_numbins);
300    for (unsigned binlcv=0; binlcv < bins.size(); binlcv++)
301       bins[binlcv] = UINT_MAX;
302
303    // look for elems to remove; shrink all_elems[] as appropriate
304    if (num_removed_elems > 0) {
305       for (unsigned lcv=0; lcv < all_elems.size(); ) {
306          entry &e = all_elems[lcv];
307          if (e.removed) {
308             const unsigned oldsize = all_elems.size();
309             assert(oldsize > 0);
310
311             // remove item from vector by swap with last item & resizing/-1
312             all_elems[lcv] = all_elems[oldsize-1]; // should be OK if lcv==oldsize-1
313             all_elems.resize(oldsize-1);
314
315             num_removed_elems--;
316             
317             // note: we DON'T bump up lcv in this case
318          }
319          else
320             lcv++;
321       }
322
323       assert(num_removed_elems == 0);
324    }
325
326    // Now rehash everything.  Sounds awfully expensive, and I guess it is -- it's
327    // linear in the total # of items in the hash table.  But take some heart: beyond this
328    // point, we don't need to make any copies of type KEY or VALUE, resize any vectors, or
329    // recalculate any hashes.  We just need to play with a bunch of unsigned integers.
330
331    for (unsigned lcv=0; lcv < all_elems.size(); lcv++) {
332       entry &e = all_elems[lcv];
333       assert(!e.removed);
334
335       // the entry's key_hashval stays the same, but it may go into a different bin:
336       const unsigned bin = e.key_hashval % bins.size();
337
338       // prepend element to bin:
339       e.next = bins[bin];
340       bins[bin] = lcv;
341    }
342
343    // the invariant should now hold
344    assert(bins.size() * max_bin_load >= size());
345 }