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