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