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