Changing PIOCUSAGE by PIOCPSINFO in the /proc call to compute the CPU time
[dyninst.git] / common / src / DictionaryLite.C
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 // DictionaryLite.C
43
44 /*
45  * $Log: DictionaryLite.C,v $
46  * Revision 1.8  1996/11/26 16:09:32  naim
47  * Fixing asserts - naim
48  *
49  * Revision 1.7  1996/10/31 07:32:31  tamches
50  * locate() now returns V* instead of bool
51  *
52  * Revision 1.6  1996/08/16 21:31:45  tamches
53  * updated copyright for release 1.1
54  *
55  * Revision 1.5  1996/05/10 05:09:25  tamches
56  * find() is a const member function
57  *
58  * Revision 1.4  1996/05/06 04:39:20  karavan
59  * added new function find() to dictionary_lite class
60  *
61  * Revision 1.3  1995/12/26 19:57:17  tamches
62  * made (empty) destructor inline.
63  * removed unused member function clear()
64  *
65  * Revision 1.2  1995/12/16 00:24:12  tamches
66  * commented out keys()
67  *
68  * Revision 1.1  1995/11/06 19:20:28  tamches
69  * first version of DictionaryLite
70  *
71  */
72
73 /************************************************************************
74  * DictionaryLite.C: same as Dictionary.h, but with some template baggage
75  * removed.  Should lead to smaller binaries. --ari
76 ************************************************************************/
77
78 #include "util/h/DictionaryLite.h"
79
80 /************************************************************************
81  * template<class K, class V> class dictionary_lite
82 ************************************************************************/
83
84 template<class K, class V>
85 DO_INLINE_F
86 dictionary_lite<K,V>::dictionary_lite(unsigned (*hf)(const K &))
87     : hashf_(hf), data_(1), chain_size_(DEFAULT_LITE_CHAIN_SIZE),
88     nbuckets_(data_.size()), llevel_(data_.size(), 0),
89     glevel_(0), next_(0) {
90 }
91
92 template<class K, class V>
93 DO_INLINE_F
94 dictionary_lite<K,V>::dictionary_lite(unsigned (*hf)(const K &), unsigned s1)
95     : hashf_(hf), data_(s1), chain_size_(s1), nbuckets_(data_.size()),
96     llevel_(data_.size(), 0), glevel_(0), next_(0) {
97     assert(s1 != 0);
98 }
99
100 template<class K, class V>
101 DO_INLINE_F
102 dictionary_lite<K,V>::dictionary_lite(const dictionary_lite<K,V>& d)
103     : hashf_(d.hashf_), data_(d.data_), chain_size_(d.chain_size_),
104     nbuckets_(d.nbuckets_), llevel_(d.llevel_), glevel_(d.glevel_),
105     next_(d.next_) {
106 }
107
108 template<class K, class V>
109 DO_INLINE_F
110 dictionary_lite<K,V>&
111 dictionary_lite<K,V>::operator=(const dictionary_lite<K,V>& d) {
112     if (this == &d) {
113         return *this;
114     }
115
116     hashf_      = d.hashf_;
117     data_       = d.data_;
118     chain_size_ = d.chain_size_;
119     nbuckets_   = d.nbuckets_;
120     llevel_     = d.llevel_;
121     glevel_     = d.glevel_;
122     next_       = d.next_;
123
124     return *this;
125 }
126
127 template<class K, class V>
128 DO_INLINE_F
129 unsigned
130 dictionary_lite<K,V>::size() const {
131     unsigned sz = 0;
132     for (unsigned chain = 0; chain < data_.size(); chain++) {
133         sz += data_[chain].size();
134     }
135     return sz;
136 }
137
138 template<class K, class V>
139 DO_INLINE_F
140 V&
141 dictionary_lite<K,V>::operator[](const K& key) {
142     unsigned hash, chain, i;
143     V *value = locate(key, hash, chain, i);
144     if (value != NULL)
145         return *value;
146     else
147         return insert(key, hash, chain);
148 }
149
150 template<class K, class V>
151 DO_INLINE_F
152 bool 
153 dictionary_lite<K,V>::find(const K& key, V& el) const {
154    unsigned hash, chain, i;
155    V *value = locate(key, hash, chain, i);
156    if (value != NULL) {
157       el = *value; // makes a copy of type V; don't use this if V::operator=(const V&) is expensive
158       return true;
159    }
160    else
161       return false;
162 }
163
164 template<class K, class V>
165 DO_INLINE_F
166 bool
167 dictionary_lite<K,V>::defines(const K& key) const {
168     unsigned hash, chain, i;
169     return (locate(key, hash, chain, i) != NULL);
170 }
171
172 template<class K, class V>
173 DO_INLINE_F
174 void
175 dictionary_lite<K,V>::undef(const K& key) {
176     unsigned hash, chain, i;
177     if (locate(key, hash, chain, i) != NULL) {
178         remove(chain, i);
179     }
180 }
181
182 //template<class K, class V>
183 //DO_INLINE_F
184 //void
185 //dictionary_lite<K,V>::clear() {
186 //    for (unsigned i = 0; i < data_.size(); i++) {
187 //        data_[i].resize(0);
188 //    }
189 //}
190
191 template<class K, class V>
192 DO_INLINE_F
193 vector<V>
194 dictionary_lite<K,V>::values() const {
195     vector<V> v;
196     for (unsigned i = 0; i < data_.size(); i++) {
197         for (unsigned j = 0; j < data_[i].size(); j++) {
198             v += data_[i][j].value;
199         }
200     }
201     return v;
202 }
203
204 template<class K, class V>
205 DO_INLINE_F
206 unsigned
207 (*dictionary_lite<K,V>::hashf() const)(const K &) {
208     return hashf_;
209 }
210
211 template<class K, class V>
212 DO_INLINE_P
213 unsigned
214 dictionary_lite<K,V>::chain_of(unsigned hash) const {
215     unsigned chain = hash % nbuckets_;
216     if (llevel_[chain] > glevel_) {
217         chain = hash % (nbuckets_*2);
218         assert(chain < data_.size());
219     }
220     return chain;
221 }
222
223 template<class K, class V>
224 DO_INLINE_P
225 V*
226 dictionary_lite<K,V>::locate(const K& key, unsigned& hash,
227                              unsigned& chain, unsigned& index) const {
228     // returns ptr to value if found; else, returns NULL;
229
230     hash           = hashf_(key);
231     chain          = chain_of(hash);
232
233     const hash_chain &ch = data_[chain];
234     const unsigned hash_chain_size = ch.size();
235
236     for (index = 0; index < hash_chain_size; index++) {
237         hash_pair &thePair = ch[index];
238
239         if (hash == thePair.hash_ && key == thePair.key)
240             return &thePair.value;
241     }
242     return NULL;
243 }
244
245 template<class K, class V>
246 DO_INLINE_P
247 V&
248 dictionary_lite<K,V>::insert(const K& key, unsigned hash, unsigned chain) {
249     data_[chain] += hash_pair(key, hash);
250     unsigned i      = data_[chain].size()-1;
251     unsigned nchain = chain;
252
253     if (data_[chain].size() > chain_size_) {
254         unsigned onext = next_;
255         split();
256         if (chain == onext) {
257             unsigned nhash;
258             bool aflag;
259             aflag=(locate(key, nhash, nchain, i) != NULL);
260             assert(aflag);
261             assert(hash == nhash);
262         }
263     }
264     return data_[nchain][i].value;
265 }
266
267 template<class K, class V>
268 DO_INLINE_P
269 void
270 dictionary_lite<K,V>::remove(unsigned chain, unsigned i) {
271     hash_chain&   ch   = data_[chain];
272     unsigned last = ch.size()-1;
273     if (i != last) {
274         ch[i] = ch[last];
275     }
276     ch.resize(last);
277 }
278
279 template<class K, class V>
280 DO_INLINE_P
281 void
282 dictionary_lite<K,V>::split() {
283     unsigned nch = data_.size();
284     unsigned nsz = nch+1;
285
286     data_.resize(nsz);
287     llevel_.resize(nsz); llevel_[nch] = ++llevel_[next_];
288
289     hash_chain& ch = data_[next_];
290     unsigned i = 0;
291     while (i < ch.size()) {
292         if (chain_of(ch[i].hash_) != next_) {
293             data_[nch] += ch[i];
294             remove(next_, i);
295         }
296         else {
297             i++;
298         }
299     }
300
301     next_++;
302     if (next_ == nbuckets_) {
303         next_ = 0;
304         nbuckets_ *= 2;
305         glevel_++;
306     }
307 }