Rewrite of dictionary class (handles bin overflow much better)
[dyninst.git] / pdutil / 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 template<class K, class V>
179 class dictionary_hash_iter {
180  public:
181    dictionary_hash_iter(const dictionary_hash<K,V> &idict) : dict(idict) {
182       reset();
183    }
184
185    bool next(K &k, V &v) {
186       for (; ndx < dict.all_elems.size(); ndx++) {
187          if (!dict.all_elems[ndx].removed) {
188             k = dict.all_elems[ndx].key;
189             v = dict.all_elems[ndx].val;
190             ndx++;
191             return true;
192          }
193       }
194       return false;
195    }
196          
197    void reset() {
198       ndx = 0;
199    }
200
201  private:
202    // private to make sure they're not used:
203    dictionary_hash_iter(const dictionary_hash_iter &);
204    dictionary_hash_iter &operator=(const dictionary_hash_iter &);
205
206    const dictionary_hash<K,V> &dict;
207    unsigned ndx;
208 };
209
210 #endif