added new function find() to classes dictionary_hash and dictionary_lite
[dyninst.git] / common / h / DictionaryLite.h
1 // DictionaryLite.h
2
3 /*
4  * $Log: DictionaryLite.h,v $
5  * Revision 1.4  1996/05/06 04:38:40  karavan
6  * added new function find() to classes dictionary_hash and dictionary_lite
7  *
8  * Revision 1.3  1995/12/26 19:57:05  tamches
9  * made (empty) destructor inline.
10  * removed unused member function clear()
11  *
12  * Revision 1.2  1995/12/16 00:23:37  tamches
13  * removed keys() member function which in turn removes the need for vector<KEY>
14  * template instantiation.
15  * Removed inheritance of pair<K,V> which in turn removes the need for
16  * pair<K,V> template.
17  *
18  * Revision 1.1  1995/11/06 19:19:15  tamches
19  * first version of DictionaryLite
20  *
21  */
22
23 /************************************************************************
24  * DictionaryLite.h: same as Dictionary.h, but with some template baggage
25  * removed.  Should lead to smaller binaries. --ari
26  * example: no class Dictionary, which wasn't being used anyway.
27  * example: no class Dictionary_Iter, which wasn't being used.
28  * example: don't need to instantiate vector< pair<K,V> >, because the
29  *          seldom-if-ever used routine items() is gone.
30  * example: no more iteration class
31  * example: no virtual functions anywhere anymore
32  * example: no keys() or values() members anymore so no need for vector<K>
33  *             or for vector<V> to be instantiated.
34  *             (this is still being worked on; so far, values() is needed in TC)
35  * example: no map(), app, revapp() etc. fluff member functions anymore
36 ************************************************************************/
37
38 #if defined(external_templates)
39 #pragma interface
40 #endif
41
42 #ifndef _DICTIONARY_LITE_H_
43 #define _DICTIONARY_LITE_H_
44
45 #include "util/h/Pair.h"
46 #include "util/h/Vector.h"
47
48 #if !defined(DO_INLINE_P)
49 #define DO_INLINE_P 
50 #endif
51
52 #if !defined(DO_INLINE_F)
53 #define DO_INLINE_F
54 #endif
55
56
57 /************************************************************************
58  * template<class K, class V> class dictionary_lite
59 ************************************************************************/
60
61 static const unsigned DEFAULT_LITE_CHAIN_SIZE = 32;
62
63 template<class K, class V>
64 class dictionary_lite {
65
66 public:
67     DO_INLINE_F  dictionary_lite (unsigned (*)(const K &));
68     DO_INLINE_F  dictionary_lite (unsigned (*)(const K &), unsigned);
69     DO_INLINE_F  dictionary_lite (const dictionary_lite<K,V> &);
70     DO_INLINE_F ~dictionary_lite () {}
71
72     DO_INLINE_F dictionary_lite<K,V>&  operator= (const dictionary_lite<K,V> &);
73     DO_INLINE_F unsigned                    size ()                       const;
74     DO_INLINE_F V&                    operator[] (const K &);
75     DO_INLINE_F bool                        find (const K &, V &);
76     DO_INLINE_F bool                     defines (const K &)              const;
77     DO_INLINE_F void                       undef (const K &);
78 //    DO_INLINE_F void                       clear ();
79 //    DO_INLINE_F vector<K>                   keys ()                       const;
80     DO_INLINE_F vector<V>                 values ()                       const;
81
82     unsigned (*hashf () const) (const K &);
83
84 private:
85     DO_INLINE_P unsigned chain_of (unsigned)                                      const;
86     DO_INLINE_P bool       locate (const K &, unsigned &, unsigned &, unsigned &) const;
87     DO_INLINE_P V&         insert (const K &, unsigned, unsigned);
88     DO_INLINE_P void       remove (unsigned, unsigned);
89     DO_INLINE_P void        split ();
90
91     struct hash_pair {
92        K key;
93        V value;
94        unsigned hash_;
95
96        hash_pair() {}
97        hash_pair(const K &theKey, unsigned theHash) : key(theKey), hash_(theHash) {}
98        hash_pair(const K &theKey, const V &theValue, unsigned theHash) : key(theKey), value(theValue), hash_(theHash) {}
99  
100        bool operator==(const hash_pair &other) const {
101           return (hash_ == other.hash_ && key == other.key && value == other.value);
102        }
103     };
104     typedef vector<hash_pair> hash_chain;
105
106     unsigned           (*hashf_)(const K &);
107     vector<hash_chain> data_;
108     unsigned           chain_size_;
109     unsigned           nbuckets_;
110     vector<unsigned>   llevel_;
111     unsigned           glevel_;
112     unsigned           next_;
113 };
114
115 #endif /* !defined(_Dictionary_h_) */