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