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