1 /*++
2 Copyright (c) 2006 Microsoft Corporation
3 
4 Module Name:
5 
6     obj_pair_hashtable.h
7 
8 Abstract:
9 
10     <abstract>
11 
12 Author:
13 
14     Leonardo de Moura (leonardo) 2008-02-19.
15 
16 Revision History:
17 
18 --*/
19 #pragma once
20 
21 #include "util/hash.h"
22 #include "util/hashtable.h"
23 
24 /**
25    \brief Special entry for a hashtable of pairs of obj pointers (i.e.,
26    objects that have a hash() method).
27    This entry uses 0x0 and 0x1 to represent HT_FREE and HT_DELETED.
28 */
29 template<typename T1, typename T2>
30 class obj_pair_hash_entry {
31     unsigned            m_hash; // cached hash code
32     std::pair<T1*, T2*> m_data { nullptr, nullptr };
33 
34 public:
35     typedef std::pair<T1*, T2*> data;
get_hash()36     unsigned get_hash() const { return m_hash; }
is_free()37     bool is_free() const { return m_data.first == 0; }
is_deleted()38     bool is_deleted() const { return m_data.first == reinterpret_cast<T1 *>(1); }
is_used()39     bool is_used() const { return m_data.first != reinterpret_cast<T1 *>(0) && m_data.first != reinterpret_cast<T1 *>(1); }
get_data()40     data const & get_data() const { return m_data; }
get_data()41     data & get_data() { return m_data; }
set_data(data const d)42     void set_data(data const d) { m_data = d; }
set_hash(unsigned h)43     void set_hash(unsigned h) { m_hash = h; }
mark_as_deleted()44     void mark_as_deleted() { m_data.first = reinterpret_cast<T1 *>(1); }
mark_as_free()45     void mark_as_free() { m_data.first = 0; }
46 };
47 
48 template<typename T1, typename T2>
49 class obj_pair_hashtable : public core_hashtable<obj_pair_hash_entry<T1, T2>, obj_ptr_pair_hash<T1, T2>, default_eq<std::pair<T1*, T2*> > > {
50 public:
51     obj_pair_hashtable(unsigned initial_capacity = DEFAULT_HASHTABLE_INITIAL_CAPACITY):
52         core_hashtable<obj_pair_hash_entry<T1, T2>, obj_ptr_pair_hash<T1, T2>, default_eq<std::pair<T1*, T2*> > >(initial_capacity) {
53     }
54 };
55 
56 template<typename Key1, typename Key2, typename Value>
57 class obj_pair_map {
58 protected:
59     class entry;
60 public:
61     class key_data {
62         Key1 *   m_key1;
63         Key2 *   m_key2;
64         Value    m_value;
65         unsigned m_hash;
66         friend class entry;
67     public:
key_data()68         key_data():
69             m_key1(nullptr),
70             m_key2(nullptr),
71             m_hash(0) {
72         }
key_data(Key1 * k1,Key2 * k2)73         key_data(Key1 * k1, Key2 * k2):
74             m_key1(k1),
75             m_key2(k2) {
76             m_hash = combine_hash(m_key1->hash(), m_key2->hash());
77         }
key_data(Key1 * k1,Key2 * k2,const Value & v)78         key_data(Key1 * k1, Key2 * k2, const Value & v):
79             m_key1(k1),
80             m_key2(k2),
81             m_value(v) {
82             m_hash = combine_hash(m_key1->hash(), m_key2->hash());
83         }
hash()84         unsigned hash() const { return m_hash; }
85         bool operator==(key_data const & other) const { return m_key1 == other.m_key1 && m_key2 == other.m_key2; }
get_key1()86         Key1 * get_key1() const { return m_key1; }
get_key2()87         Key2 * get_key2() const { return m_key2; }
get_value()88         Value const & get_value() const { return m_value; }
get_value()89         Value & get_value() { return m_value; }
90     };
91 protected:
92     class entry {
93         key_data m_data;
94     public:
95         typedef key_data data;
get_hash()96         unsigned get_hash() const { return m_data.hash(); }
is_free()97         bool is_free() const { return m_data.m_key1 == nullptr; }
is_deleted()98         bool is_deleted() const { return m_data.m_key1 == reinterpret_cast<Key1 *>(1); }
is_used()99         bool is_used() const { return m_data.m_key1 != reinterpret_cast<Key1 *>(0) && m_data.m_key1 != reinterpret_cast<Key1 *>(1); }
get_data()100         key_data const & get_data() const { return m_data; }
get_data()101         key_data & get_data() { return m_data; }
set_data(key_data const & d)102         void set_data(key_data const & d) { m_data = d; }
set_hash(unsigned h)103         void set_hash(unsigned h) { SASSERT(h == m_data.hash()); }
mark_as_deleted()104         void mark_as_deleted() { m_data.m_key1 = reinterpret_cast<Key1 *>(1); }
mark_as_free()105         void mark_as_free() { m_data.m_key1 = nullptr; }
106     };
107 
108     typedef core_hashtable<entry, obj_hash<key_data>, default_eq<key_data> > table;
109 
110     table m_table;
111 
find_core(Key1 * k1,Key2 * k2)112     entry * find_core(Key1 * k1, Key2 * k2) const {
113         return m_table.find_core(key_data(k1, k2));
114     }
115 
116 public:
obj_pair_map()117     obj_pair_map():
118         m_table(DEFAULT_HASHTABLE_INITIAL_CAPACITY) {}
119 
120     typedef typename table::iterator iterator;
121 
reset()122     void reset() {
123         m_table.reset();
124     }
125 
empty()126     bool empty() const {
127         return m_table.empty();
128     }
129 
size()130     unsigned size() const {
131         return m_table.size();
132     }
133 
capacity()134     unsigned capacity() const {
135         return m_table.capacity();
136     }
137 
begin()138     iterator begin() const {
139         return m_table.begin();
140     }
141 
end()142     iterator end() const {
143         return m_table.end();
144     }
145 
insert(Key1 * k1,Key2 * k2,Value const & v)146     void insert(Key1 * k1, Key2 * k2, Value const & v) {
147         m_table.insert(key_data(k1, k2, v));
148     }
149 
insert_if_not_there(Key1 * k1,Key2 * k2,Value const & v)150     Value& insert_if_not_there(Key1 * k1, Key2 * k2, Value const & v) {
151         return m_table.insert_if_not_there2(key_data(k1, k2, v))->get_data().get_value();
152     }
153 
find(Key1 * k1,Key2 * k2,Value & v)154     bool find(Key1 * k1, Key2 * k2, Value & v) const {
155         entry * e = find_core(k1, k2);
156         if (e) {
157             v = e->get_data().get_value();
158         }
159         return (nullptr != e);
160     }
161 
find(Key1 * k1,Key2 * k2)162     Value const & find(Key1 * k1, Key2 * k2) const {
163         entry * e = find_core(k1, k2);
164         return e->get_data().get_value();
165     }
166 
167     Value const& operator[](std::pair<Key1 *, Key2 *> const& key) const {
168         return find(key.first, key.second);
169     }
170 
contains(Key1 * k1,Key2 * k2)171     bool contains(Key1 * k1, Key2 * k2) const {
172         return find_core(k1, k2) != nullptr;
173     }
174 
contains(std::pair<Key1 *,Key2 * > const & key)175     bool contains(std::pair<Key1 *, Key2 *> const& key) const {
176         return contains(key.first, key.second);
177     }
178 
erase(Key1 * k1,Key2 * k2)179     void erase(Key1 * k1, Key2 * k2) {
180         m_table.remove(key_data(k1, k2));
181     }
182 };
183 
184 
185