updated copyright for release 1.1
[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 /************************************************************************
43  * Dictionary.h: implementation of template-based dictionaries.
44 ************************************************************************/
45
46
47 \f
48
49 #if defined(external_templates)
50 #pragma interface
51 #endif
52
53 #if !defined(_Dictionary_h_)
54 #define _Dictionary_h_
55
56 \f
57
58
59 /************************************************************************
60  * header files.
61 ************************************************************************/
62
63 #include "util/h/Pair.h"
64 #include "util/h/Vector.h"
65
66 \f
67
68 #if !defined(DO_INLINE_P)
69 #define DO_INLINE_P 
70 #endif
71
72 #if !defined(DO_INLINE_F)
73 #define DO_INLINE_F
74 #endif
75
76
77 /************************************************************************
78  * template<class K, class V> class dictionary
79 ************************************************************************/
80
81 template<class K, class V>
82 class dictionary {
83 public:
84     DO_INLINE_F         dictionary ();
85     DO_INLINE_F virtual ~dictionary ();
86
87     virtual unsigned                  size ()                        const =0;
88     virtual V&                  operator[] (const K &)                     =0;
89     virtual bool                   defines (const K &)               const =0;
90     virtual void                     undef (const K &)                     =0;
91     virtual void                     clear ()                              =0;
92     virtual vector<K>                 keys ()                        const =0;
93     virtual vector<V>               values ()                        const =0;
94     virtual vector< pair<K,V> >      items ()                        const =0;
95     virtual void                       app (void (*)(const K &, V &))      =0;
96     virtual void                    revapp (void (*)(const K &, V &))      =0;
97     virtual V  fold (V (*)(const K &, const V &, const V &), const V &) const =0;
98     virtual V revfold (V (*)(const K &, const V &, const V &), const V &) const =0;
99
100 private:
101     DO_INLINE_F dictionary                 (const dictionary<K,V> &); // not allowed
102     DO_INLINE_F dictionary<K,V>& operator= (const dictionary<K,V> &); // not allowed
103 };
104
105 template<class K, class V>
106 DO_INLINE_F
107 dictionary<K,V>::dictionary() {
108 }
109
110 template<class K, class V>
111 DO_INLINE_F
112 dictionary<K,V>::~dictionary() {
113 }
114
115
116 \f
117
118
119 /************************************************************************
120  * template<class K, class V> class dictionary_hash
121 ************************************************************************/
122
123 static const unsigned DEFAULT_CHAIN_SIZE = 32;
124
125 template<class K, class V>
126 class dictionary_hash : public dictionary<K,V> {
127
128 public:
129     DO_INLINE_F         dictionary_hash (unsigned (*)(const K &));
130     DO_INLINE_F         dictionary_hash (unsigned (*)(const K &), unsigned);
131     DO_INLINE_F         dictionary_hash (const dictionary_hash<K,V> &);
132     DO_INLINE_F virtual ~dictionary_hash ();
133
134     DO_INLINE_F dictionary_hash<K,V>&  operator= (const dictionary_hash<K,V> &);
135     DO_INLINE_F unsigned                    size ()                       const;
136     DO_INLINE_F V&                    operator[] (const K &);
137     DO_INLINE_F bool                        find (const K &, V &) const;
138     DO_INLINE_F bool                     defines (const K &)              const;
139     DO_INLINE_F void                       undef (const K &);
140     DO_INLINE_F void                       clear ();
141     DO_INLINE_F vector<K>                   keys ()                       const;
142     DO_INLINE_F vector<V>                 values ()                       const;
143     DO_INLINE_F vector< pair<K,V> >        items ()                       const;
144     DO_INLINE_F void                         app (void (*)(const K &, V &));
145     DO_INLINE_F void                      revapp (void (*)(const K &, V &));
146     DO_INLINE_F V                           fold (V (*)(const K &, const V &, const V &), const V &) const;
147     DO_INLINE_F V                        revfold (V (*)(const K &, const V &, const V &), const V &) const;
148
149     unsigned (*hashf () const) (const K &);
150
151 private:
152     DO_INLINE_P unsigned chain_of (unsigned)                                      const;
153     DO_INLINE_P bool       locate (const K &, unsigned &, unsigned &, unsigned &) const;
154     DO_INLINE_P V&         insert (const K &, unsigned, unsigned);
155     DO_INLINE_P void       remove (unsigned, unsigned);
156     DO_INLINE_P void        split ();
157
158     struct hash_pair : public pair<K,V> {
159         unsigned hash_;
160
161         hash_pair()                                   : pair<K,V>(),    hash_(0) {}
162         hash_pair(const K& k, unsigned h)             : pair<K,V>(k),   hash_(h) {}
163         hash_pair(const K& k, unsigned h, const V& v) : pair<K,V>(k,v), hash_(h) {}
164
165         unsigned operator==(const hash_pair& p) const {
166           return ((hash_ == p.hash_) && pair<K,V>::operator==(p));
167           // ((*((pair<K,V> *) ((void*)this))) == p));
168         }
169         // unsigned operator==(const hash_pair& p) const {
170         // return ((hash_ == p.hash_) &&
171         // ((*((pair<K,V> *) ((void*)this))) == p));
172         // }
173     };
174     typedef vector<hash_pair> hash_chain;
175
176     unsigned           (*hashf_)(const K &);
177     vector<hash_chain> data_;
178     unsigned           chain_size_;
179     unsigned           nbuckets_;
180     vector<unsigned>   llevel_;
181     unsigned           glevel_;
182     unsigned           next_;
183
184     friend class dictionary_hash_iter<K,V>;
185
186 }
187 ;
188
189 template<class K, class V>
190 DO_INLINE_F
191 dictionary_hash<K,V>::dictionary_hash(unsigned (*hf)(const K &))
192     : hashf_(hf), data_(1), chain_size_(DEFAULT_CHAIN_SIZE),
193     nbuckets_(data_.size()), llevel_(data_.size(), 0),
194     glevel_(0), next_(0) {
195 }
196
197 template<class K, class V>
198 DO_INLINE_F
199 dictionary_hash<K,V>::dictionary_hash(unsigned (*hf)(const K &), unsigned s1)
200     : hashf_(hf), data_(s1), chain_size_(s1), nbuckets_(data_.size()),
201     llevel_(data_.size(), 0), glevel_(0), next_(0) {
202     assert(s1 != 0);
203 }
204
205 template<class K, class V>
206 DO_INLINE_F
207 dictionary_hash<K,V>::dictionary_hash(const dictionary_hash<K,V>& d)
208     : hashf_(d.hashf_), data_(d.data_), chain_size_(d.chain_size_),
209     nbuckets_(d.nbuckets_), llevel_(d.llevel_), glevel_(d.glevel_),
210     next_(d.next_) {
211 }
212
213 template<class K, class V>
214 DO_INLINE_F
215 dictionary_hash<K,V>::~dictionary_hash() {
216 }
217
218 template<class K, class V>
219 DO_INLINE_F
220 dictionary_hash<K,V>&
221 dictionary_hash<K,V>::operator=(const dictionary_hash<K,V>& d) {
222     if (this == &d) {
223         return *this;
224     }
225
226     hashf_      = d.hashf_;
227     data_       = d.data_;
228     chain_size_ = d.chain_size_;
229     nbuckets_   = d.nbuckets_;
230     llevel_     = d.llevel_;
231     glevel_     = d.glevel_;
232     next_       = d.next_;
233
234     return *this;
235 }
236
237 template<class K, class V>
238 DO_INLINE_F
239 unsigned
240 dictionary_hash<K,V>::size() const {
241     unsigned sz = 0;
242     for (unsigned chain = 0; chain < data_.size(); chain++) {
243         sz += data_[chain].size();
244     }
245     return sz;
246 }
247
248 template<class K, class V>
249 DO_INLINE_F
250 V&
251 dictionary_hash<K,V>::operator[](const K& key) {
252     unsigned hash, chain, i;
253     if (locate(key, hash, chain, i)) {
254         return data_[chain][i].value;
255     }
256     return insert(key, hash, chain);
257 }
258
259 template<class K, class V>
260 DO_INLINE_F
261 bool                      
262 dictionary_hash<K,V>::find (const K& key, V& el) const
263 {
264   unsigned hash, chain, i;
265   if (locate(key, hash, chain, i)) {
266     el = data_[chain][i].value;
267     return true;
268   } else {
269     return false;
270   }
271 }
272
273 template<class K, class V>
274 DO_INLINE_F
275 bool
276 dictionary_hash<K,V>::defines(const K& key) const {
277     unsigned hash, chain, i;
278     return locate(key, hash, chain, i);
279 }
280
281 template<class K, class V>
282 DO_INLINE_F
283 void
284 dictionary_hash<K,V>::undef(const K& key) {
285     unsigned hash, chain, i;
286     if (locate(key, hash, chain, i)) {
287         remove(chain, i);
288     }
289 }
290
291 template<class K, class V>
292 DO_INLINE_F
293 void
294 dictionary_hash<K,V>::clear() {
295     for (unsigned i = 0; i < data_.size(); i++) {
296         data_[i].resize(0);
297     }
298 }
299
300 template<class K, class V>
301 DO_INLINE_F
302 vector<K>
303 dictionary_hash<K,V>::keys() const {
304     vector<K> k;
305     for (unsigned i = 0; i < data_.size(); i++) {
306         for (unsigned j = 0; j < data_[i].size(); j++) {
307             k += data_[i][j].key;
308         }
309     }
310     return k;
311 }
312
313 template<class K, class V>
314 DO_INLINE_F
315 vector<V>
316 dictionary_hash<K,V>::values() const {
317     vector<V> v;
318     for (unsigned i = 0; i < data_.size(); i++) {
319         for (unsigned j = 0; j < data_[i].size(); j++) {
320             v += data_[i][j].value;
321         }
322     }
323     return v;
324 }
325
326 template<class K, class V>
327 DO_INLINE_F
328 vector< pair<K,V> >
329 dictionary_hash<K,V>::items() const {
330     vector< pair<K,V> > p;
331     for (unsigned i = 0; i < data_.size(); i++) {
332         for (unsigned j = 0; j < data_[i].size(); j++) {
333             p += pair<K,V>(data_[i][j].key, data_[i][j].value);
334         }
335     }
336     return p;
337 }
338
339 template<class K, class V>
340 DO_INLINE_F
341 void
342 dictionary_hash<K,V>::app(void (*f)(const K &, V &)) {
343     for (unsigned i = 0; i < data_.size(); i++) {
344         for (unsigned j = 0; j < data_[i].size(); j++) {
345             f(data_[i][j].key, data_[i][j].value);
346         }
347     }
348 }
349
350 template<class K, class V>
351 DO_INLINE_F
352 void
353 dictionary_hash<K,V>::revapp(void (*f)(const K &, V &)) {
354     app(f);
355 }
356
357 template<class K, class V>
358 DO_INLINE_F
359 V
360 dictionary_hash<K,V>::fold(V (*f)(const K &, const V &, const V &),
361     const V& arg0) const {
362     V ret = arg0;
363     for (unsigned i = 0; i < data_.size(); i++) {
364         for (unsigned j = 0; j < data_[i].size(); j++) {
365             ret = f(data_[i][j].key, data_[i][j].value, ret);
366         }
367     }
368     return ret;
369 }
370
371 template<class K, class V>
372 DO_INLINE_F
373 V
374 dictionary_hash<K,V>::revfold(V (*f)(const K &, const V &, const V &),
375     const V& arg0) const {
376     return fold(f, arg0);
377 }
378
379 template<class K, class V>
380 DO_INLINE_F
381 unsigned
382 (*dictionary_hash<K,V>::hashf() const)(const K &) {
383     return hashf_;
384 }
385
386 template<class K, class V>
387 DO_INLINE_P
388 unsigned
389 dictionary_hash<K,V>::chain_of(unsigned hash) const {
390     unsigned chain = hash % nbuckets_;
391     if (llevel_[chain] > glevel_) {
392         chain = hash % (nbuckets_*2);
393         assert(chain < data_.size());
394     }
395     return chain;
396 }
397
398 template<class K, class V>
399 DO_INLINE_P
400 bool
401 dictionary_hash<K,V>::locate(const K& key, unsigned& hash,
402     unsigned& chain, unsigned& i) const {
403     hash           = hashf_(key);
404     chain          = chain_of(hash);
405     hash_chain& ch = data_[chain];
406
407     for (i = 0; i < ch.size(); i++) {
408         if ((hash == ch[i].hash_) && (key == ch[i].key)) {
409             return true;
410         }
411     }
412     return false;
413 }
414
415 template<class K, class V>
416 DO_INLINE_P
417 V&
418 dictionary_hash<K,V>::insert(const K& key, unsigned hash, unsigned chain) {
419     ((dictionary_hash<K,V> *) this)->data_[chain] += hash_pair(key, hash);
420     unsigned i      = data_[chain].size()-1;
421     unsigned nchain = chain;
422
423     if (data_[chain].size() > chain_size_) {
424         unsigned onext = next_;
425         split();
426         if (chain == onext) {
427             unsigned nhash;
428             assert(locate(key, nhash, nchain, i));
429             assert(hash == nhash);
430         }
431     }
432     return data_[nchain][i].value;
433 }
434
435 template<class K, class V>
436 DO_INLINE_P
437 void
438 dictionary_hash<K,V>::remove(unsigned chain, unsigned i) {
439     hash_chain&   ch   = data_[chain];
440     unsigned last = ch.size()-1;
441     if (i != last) {
442         ch[i] = ch[last];
443     }
444     ch.resize(last);
445 }
446
447 template<class K, class V>
448 DO_INLINE_P
449 void
450 dictionary_hash<K,V>::split() {
451     unsigned nch = data_.size();
452     unsigned nsz = nch+1;
453
454     data_.resize(nsz);
455     llevel_.resize(nsz); llevel_[nch] = ++llevel_[next_];
456
457     hash_chain& ch = data_[next_];
458     unsigned i = 0;
459     while (i < ch.size()) {
460         if (chain_of(ch[i].hash_) != next_) {
461             data_[nch] += ch[i];
462             remove(next_, i);
463         }
464         else {
465             i++;
466         }
467     }
468
469     next_++;
470     if (next_ == nbuckets_) {
471         next_ = 0;
472         nbuckets_ *= 2;
473         glevel_++;
474     }
475 }
476
477
478 \f
479
480
481 /************************************************************************
482  * template<class K, class V> class dictionary_iter
483 ************************************************************************/
484
485 template<class K, class V>
486 class dictionary_iter {
487 public:
488     DO_INLINE_F          dictionary_iter ();
489     DO_INLINE_F virtual ~dictionary_iter ();
490
491     virtual bool  next (K &, V &) =0;
492     virtual void reset ()         =0;
493
494 private:
495     DO_INLINE_P dictionary_iter                 (const dictionary_iter<K,V> &); // not allowed
496     DO_INLINE_P dictionary_iter<K,V>& operator= (const dictionary_iter<K,V> &); // not allowed
497 };
498
499 template<class K, class V>
500 DO_INLINE_F
501 dictionary_iter<K,V>::dictionary_iter() {
502 }
503
504 template<class K, class V>
505 DO_INLINE_F
506 dictionary_iter<K,V>::~dictionary_iter() {
507 }
508
509
510 \f
511
512
513 /************************************************************************
514  * template<class K, class V> class dictionary_hash_iter
515 ************************************************************************/
516
517 template<class K, class V>
518 class dictionary_hash_iter : public dictionary_iter<K,V> {
519 public:
520     DO_INLINE_F          dictionary_hash_iter (const dictionary_hash<K,V> &);
521     DO_INLINE_F virtual ~dictionary_hash_iter ();
522
523     DO_INLINE_F bool  next (K &, V &);
524     DO_INLINE_F void reset ();
525
526 private:
527     const dictionary_hash<K,V>& dict_;
528     unsigned                    chain_;
529     unsigned                    curr_;
530
531     DO_INLINE_P dictionary_hash_iter                 (const dictionary_hash_iter<K,V> &); // not allowed
532     DO_INLINE_P dictionary_hash_iter<K,V>& operator= (const dictionary_hash_iter<K,V> &); // not allowed
533 };
534
535 template<class K, class V>
536 DO_INLINE_F
537 bool
538 dictionary_hash_iter<K,V>::next(K& a, V& b) {
539     while (chain_ < dict_.data_.size()) {
540         if (curr_ < dict_.data_[chain_].size()) {
541             a = dict_.data_[chain_][curr_].key;
542             b = dict_.data_[chain_][curr_].value;
543             curr_++;
544             return true;
545         }
546
547         chain_++;
548         curr_ = 0;
549     }
550
551     return false;
552 }
553
554 template<class K, class V>
555 DO_INLINE_F
556 void
557 dictionary_hash_iter<K,V>::reset() {
558     chain_ = curr_ = 0;
559 }
560
561 template<class K, class V>
562 DO_INLINE_F
563 dictionary_hash_iter<K,V>::dictionary_hash_iter(const dictionary_hash<K,V>& d)
564     : dict_(d), chain_(0), curr_(0) {
565 }
566
567 template<class K, class V>
568 DO_INLINE_F
569 dictionary_hash_iter<K,V>::~dictionary_hash_iter() {
570 }
571
572
573 \f
574
575
576 /************************************************************************
577  * Iteration functions.
578 ************************************************************************/
579
580 template<class K, class V1, class V2>
581 DO_INLINE_F
582 dictionary_hash<K,V2>
583 map(V2 (*f)(const V1 &), const dictionary_hash<K,V1>& d) {
584     dictionary_hash<K,V2>      nd(d.hashf());
585     dictionary_hash_iter<K,V1> di(d);
586     K  k;
587     V1 v1;
588     while (di.next(k, v1)) {
589         nd[k] = f(v1);
590     }
591     return nd;
592 }
593
594 template<class K, class V1, class V2>
595 DO_INLINE_F
596 V2
597 fold(V2 (*f)(const K &, const V1 &, const V2 &), const dictionary_hash<K,V1>& d, const V2& arg0) {
598     dictionary_hash_iter<K,V1> di(d);
599     K  k;
600     V1 v1;
601     V2 v2 = arg0;
602     while (di.next(k, v1)) {
603         v2 = f(k, v1, v2);
604     }
605     return v2;
606 }
607
608 template<class K, class V1, class V2>
609 DO_INLINE_F
610 V2
611 revfold(V2 (*f)(const K &, const V1 &, const V2 &), const dictionary_hash<K,V1>& d, const V2& arg0) {
612     return fold(f, d, arg0);
613 }
614
615
616 \f
617
618
619 #endif /* !defined(_Dictionary_h_) */