Minor change for NT - naim
[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 class dictionary_hash_iter;
76
77 template<class K, class V>
78 class dictionary_hash {
79    friend class dictionary_hash_iter<K,V>;
80  public:
81    dictionary_hash (unsigned (*hashfunc)(const K &),
82                    unsigned nbins=101,
83                    float max_bin_load=0.7,
84                       // we keep #bins*max_bin_load >= total # items, to make
85                       // sure that there are enough bins s.t. (assuming a good
86                       // hash function) collisions are few.
87                    float bin_grow_factor = 1.6
88                       // when we need more bins, we grow by this factor
89                       // i.e., new #bins = old #bins * bin_grow_factor
90                   );
91   ~dictionary_hash () {}
92
93    // I'd rather not have provided these methods, but apparantly some code
94    // in paradynd actually copies entire dictionaries (!)
95    dictionary_hash (const dictionary_hash<K,V> &);
96    dictionary_hash<K,V>&  operator= (const dictionary_hash<K,V> &);
97
98    unsigned                    size ()                       const;
99    V&                    operator[] (const K &);
100    bool                        find (const K &, V &)         const;
101    bool                     defines (const K &)              const;
102    void                       undef (const K &);
103    vector<K>                 keys ()                         const;
104    vector<V>                 values ()                       const;
105    void                      clear ();
106
107  private:
108    unsigned locate_addIfNotFound(const K &);
109       // returns ndx within all_elems[]; never returns UINT_MAX
110
111    unsigned locate(const K &, bool even_if_removed) const;
112       // never adds a new entry if not found.  Okay to call from const member fns
113
114    void grow_numbins(unsigned new_numbins);
115
116    // We keep a ptr to the hash function:
117    unsigned (*hasher)(const K &);
118
119    // Important structure:
120    struct entry {
121       K key;
122       unsigned key_hashval; // we could always rehash, since we have 'key', but this
123                             // is faster.
124       V val;
125       bool removed; // since removal would require a lot of shifting w/in all_elems[],
126                     // we use this flag instead, and only do the actual removal on
127                     // resize.
128       unsigned next; // an index into 'all_elems', for hash collisions.  UINT_MAX
129                      // implies end of collision chain for this bin
130
131       entry() {} // needed by vector class
132       entry(const K &ikey, unsigned ikey_hashval, const V &ival, unsigned inext) :
133                         key(ikey), key_hashval(ikey_hashval), val(ival), next(inext) {
134          removed = false;
135       }
136       entry(const entry &src) : key(src.key), val(src.val) {
137          key_hashval = src.key_hashval;
138          removed = src.removed;
139          next = src.next;
140       }
141       entry& operator=(const entry &src) {
142          if (&src == this) return *this;
143          
144          key = src.key;
145          key_hashval = src.key_hashval;
146          val = src.val;
147          removed = src.removed;
148          next = src.next;
149          return *this;
150       }
151    };
152
153    // The actual elements, in one big vector (certain operations are more efficient
154    // this way, and it's a clean approach to storage).  Since we use
155    // vector<>::operator+= on this, we're glad that class vector<> preallocates some
156    // extra stuff when growing.
157    vector<entry> all_elems;
158
159    // The bins.  Note: since the number of bins doesn't change often (only when
160    // growing), we don't really want the extra-buffer storage that vector<>
161    // preallocates when using resize().
162    // Oh well.
163    vector<unsigned> bins;
164       // each entry in 'bins' gives the index (w/in 'all_elems') of the first element
165       // in the bin.  In other words, the first element in bin X is all_elems[bin[X]].
166       // If bin[X] is UINT_MAX, then the bin is empty.
167
168    unsigned num_removed_elems;
169    
170    // Notes:
171    // 1) At any given time, all_elems.size()-num_removed_items gives us the
172    //    total # of items
173    // 2) At any given time, bins.size() gives us the total # of bins
174    // 3) We keep the invariant #bins * max_bin_load >= total # items,
175    //    incrementing #bins (by a factor of bin_grow_factor) when needed.
176
177    float max_bin_load, bin_grow_factor;
178 };
179
180 template<class K, class V>
181 class dictionary_hash_iter {
182  public:
183    dictionary_hash_iter(const dictionary_hash<K,V> &idict) : dict(idict) {
184       reset();
185    }
186
187    bool next(K &k, V &v) {
188       for (; ndx < dict.all_elems.size(); ndx++) {
189          if (!dict.all_elems[ndx].removed) {
190             k = dict.all_elems[ndx].key;
191             v = dict.all_elems[ndx].val;
192             ndx++;
193             return true;
194          }
195       }
196       return false;
197    }
198          
199    void reset() {
200       ndx = 0;
201    }
202
203  private:
204    // private to make sure they're not used:
205    dictionary_hash_iter(const dictionary_hash_iter &);
206    dictionary_hash_iter &operator=(const dictionary_hash_iter &);
207
208    const dictionary_hash<K,V> &dict;
209    unsigned ndx;
210 };
211
212 #endif