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