improvements to iterator class
[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 #ifdef external_templates
48 #pragma interface
49 #endif
50
51 #include "util/h/Vector.h"
52
53 /************************************************************************
54  * template<class K, class V> class dictionary_hash
55  * Ari Tamches
56  *
57  * See Stroustrup, The C++ Programming Language, 3d edition, which
58  * provided inspiration for this hash table class via an extended
59  * example in section 17.6
60  *
61  * This class tries very hard to ensure that there are enough bins s.t.
62  * hash collisions are few (though if you provide a bad hash function,
63  * all bets are off, as usual).  Toward that end, the following invariant
64  * is maintained at all times:
65  *         #bins * max_bin_load >= total # items
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).
72  * 
73 ************************************************************************/
74
75 template<class K, class V>
76 class dictionary_hash {
77    friend class dictionary_hash_iter<K,V>;
78  public:
79    dictionary_hash (unsigned (*hashfunc)(const K &),
80                    unsigned nbins=101,
81                    float max_bin_load=0.7,
82                       // we keep #bins*max_bin_load >= total # items, to make
83                       // sure that there are enough bins s.t. (assuming a good
84                       // hash function) collisions are few.
85                    float bin_grow_factor = 1.6
86                       // when we need more bins, we grow by this factor
87                       // i.e., new #bins = old #bins * bin_grow_factor
88                   );
89   ~dictionary_hash () {}
90
91    // I'd rather not have provided these methods, but apparantly some code
92    // in paradynd actually copies entire dictionaries (!)
93    dictionary_hash (const dictionary_hash<K,V> &);
94    dictionary_hash<K,V>&  operator= (const dictionary_hash<K,V> &);
95
96    unsigned                    size ()                       const;
97    V&                    operator[] (const K &);
98    bool                        find (const K &, V &)         const;
99    bool                     defines (const K &)              const;
100    void                       undef (const K &);
101    vector<K>                 keys ()                         const;
102    vector<V>                 values ()                       const;
103    void                      clear ();
104
105  private:
106    unsigned locate_addIfNotFound(const K &);
107       // returns ndx within all_elems[]; never returns UINT_MAX
108
109    unsigned locate(const K &, bool even_if_removed) const;
110       // never adds a new entry if not found.  Okay to call from const member fns
111
112    void grow_numbins(unsigned new_numbins);
113
114    // We keep a ptr to the hash function:
115    unsigned (*hasher)(const K &);
116
117    // Important structure:
118    struct entry {
119       K key;
120       unsigned key_hashval; // we could always rehash, since we have 'key', but this
121                             // is faster.
122       V val;
123       bool removed; // since removal would require a lot of shifting w/in all_elems[],
124                     // we use this flag instead, and only do the actual removal on
125                     // resize.
126       unsigned next; // an index into 'all_elems', for hash collisions.  UINT_MAX
127                      // implies end of collision chain for this bin
128
129       entry() {} // needed by vector class
130       entry(const K &ikey, unsigned ikey_hashval, const V &ival, unsigned inext) :
131                         key(ikey), key_hashval(ikey_hashval), val(ival), next(inext) {
132          removed = false;
133       }
134       entry(const entry &src) : key(src.key), val(src.val) {
135          key_hashval = src.key_hashval;
136          removed = src.removed;
137          next = src.next;
138       }
139       entry& operator=(const entry &src) {
140          if (&src == this) return *this;
141          
142          key = src.key;
143          key_hashval = src.key_hashval;
144          val = src.val;
145          removed = src.removed;
146          next = src.next;
147          return *this;
148       }
149    };
150
151    // The actual elements, in one big vector (certain operations are more efficient
152    // this way, and it's a clean approach to storage).  Since we use
153    // vector<>::operator+= on this, we're glad that class vector<> preallocates some
154    // extra stuff when growing.
155    vector<entry> all_elems;
156
157    // The bins.  Note: since the number of bins doesn't change often (only when
158    // growing), we don't really want the extra-buffer storage that vector<>
159    // preallocates when using resize().
160    // Oh well.
161    vector<unsigned> bins;
162       // each entry in 'bins' gives the index (w/in 'all_elems') of the first element
163       // in the bin.  In other words, the first element in bin X is all_elems[bin[X]].
164       // If bin[X] is UINT_MAX, then the bin is empty.
165
166    unsigned num_removed_elems;
167    
168    // Notes:
169    // 1) At any given time, all_elems.size()-num_removed_items gives us the
170    //    total # of items
171    // 2) At any given time, bins.size() gives us the total # of bins
172    // 3) We keep the invariant #bins * max_bin_load >= total # items,
173    //    incrementing #bins (by a factor of bin_grow_factor) when needed.
174
175    float max_bin_load, bin_grow_factor;
176 };
177
178 // Typical way to use an iterator:
179 // for (dictionary_hash_iter iter=thedict; iter; iter++) {
180 //    ... make use of iter.currkey() and iter.currval() ...
181 // }
182 template<class K, class V>
183 class dictionary_hash_iter {
184  private:
185    bool done() const {return (curr == last);} // works if both are NULL (empty iter)
186    void movetonext() {
187       do {
188          curr++;
189       } while (curr != last && curr->removed);
190    }
191    
192  public:
193    dictionary_hash_iter(const dictionary_hash<K,V> &idict) : dict(idict) {
194       reset();
195    }
196
197    bool next(K &k, V &v) {
198       for (; curr != last; curr++) {
199          if (!curr->removed) {
200             k = curr->key;
201             v = curr->val;
202             curr++;
203             return true;
204          }
205       }
206       return false;
207    }
208
209    void reset() {
210       // start the iterator off at the first non-removed item now:
211       if (dict.all_elems.size() == 0) {
212          curr = last = NULL;
213       }
214       else {
215          curr = &dict.all_elems[0];
216          last = curr + dict.all_elems.size(); // 1 past the last element
217
218          while (curr < last && curr->removed)
219             curr++;
220       }
221    }
222
223    operator bool() const {return curr < last;} // correct if both NULL
224
225    void operator++(int) { movetonext(); }
226
227    const K &currkey() const {
228       assert(!curr->removed);
229       return curr->key;
230    }
231    const V &currval() const {
232       assert(!curr->removed);
233       return curr->val;
234    }
235
236  private:
237    // private to make sure they're not used:
238    dictionary_hash_iter(const dictionary_hash_iter &src);
239    dictionary_hash_iter &operator=(const dictionary_hash_iter &);
240
241    const dictionary_hash<K,V> &dict;
242    dictionary_hash<K,V>::entry *curr;
243    dictionary_hash<K,V>::entry *last; // one past the last elem, a la STL style
244 };
245
246 #endif