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