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