33#ifndef __H__UG__hash_impl__
34#define __H__UG__hash_impl__
44template <
class TKey,
class TValue>
48 m_firstUnusedEntry(invalid_index())
54template <
class TKey,
class TValue>
56Hash(
size_t hashSize) :
58 m_firstUnusedEntry(invalid_index())
60 resize_hash(hashSize);
64template <
class TKey,
class TValue>
75 vector<pair<size_t, size_t> > newHashList;
76 newHashList.resize(max<size_t>(1, size),
77 pair<size_t, size_t>(invalid_index(), invalid_index()));
80 for(
size_t i = 0; i < m_hashList.size(); ++i){
81 size_t curInd = m_hashList[i].first;
82 while(curInd != invalid_index()){
83 Entry& e = m_entries[curInd];
86 if(newHashList[hi].first == invalid_index())
87 newHashList[hi].first = newHashList[hi].second = curInd;
89 m_entries[newHashList[hi].second].next = curInd;
90 newHashList[hi].second = curInd;
94 e.next = invalid_index();
99 m_hashList.swap(newHashList);
103template <
class TKey,
class TValue>
107 return m_hashList.size();
111template <
class TKey,
class TValue>
115 m_entries.reserve(size);
119template <
class TKey,
class TValue>
123 return m_entries.capacity();
127template <
class TKey,
class TValue>
134 m_firstUnusedEntry = invalid_index();
135 m_hashList.assign(m_hashList.size(),
136 make_pair<size_t, size_t>(invalid_index(), invalid_index()));
140template <
class TKey,
class TValue>
144 return m_numEntries == 0;
148template <
class TKey,
class TValue>
152 return find_entry(key) != invalid_index();
156template <
class TKey,
class TValue>
160 size_t eind = find_entry(key);
162 if(eind == invalid_index()){
163 UG_THROW(
"No entry exists for the specified key. Please call 'has_entry' first"
164 " or use the alternate version of 'get_entry', which returns a bool.");
166 return m_entries[eind].value;
170template <
class TKey,
class TValue>
174 size_t eind = find_entry(key);
176 if(eind == invalid_index()){
177 UG_THROW(
"No entry exists for the specified key. Please call 'has_entry' first"
178 " or use the alternate version of 'get_entry', which returns a bool.");
180 return m_entries[eind].value;
183template <
class TKey,
class TValue>
187 size_t eind = find_entry(key);
189 if(eind == invalid_index())
192 valOut = m_entries[eind].value;
197template <
class TKey,
class TValue>
201 size_t eind = m_firstUnusedEntry;
202 if(eind == invalid_index()){
203 eind = m_entries.size();
204 m_entries.push_back(
Entry(key, val));
207 m_firstUnusedEntry = m_entries[eind].next;
208 m_entries[eind] =
Entry(key, val);
211 size_t hi = hash_index(key);
213 if(m_hashList[hi].first == invalid_index()){
214 m_hashList[hi].first = m_hashList[hi].second = eind;
217 m_entries[m_hashList[hi].second].next = eind;
218 m_hashList[hi].second = eind;
225template <
class TKey,
class TValue>
229 size_t hi = hash_index(key);
230 size_t prevInd = invalid_index();
231 size_t curInd = m_hashList[hi].first;
232 while(curInd != invalid_index()){
233 if(m_entries[curInd].key == key)
236 curInd = m_entries[curInd].next;
239 if(curInd != invalid_index()){
243 if(prevInd == invalid_index())
244 m_hashList[hi].first = m_entries[curInd].next;
246 m_entries[prevInd].next = m_entries[curInd].next;
250 if(m_entries[curInd].next == invalid_index())
251 m_hashList[hi].second = prevInd;
255 m_entries[curInd].next = m_firstUnusedEntry;
256 m_firstUnusedEntry = curInd;
261template <
class TKey,
class TValue>
267 return iterator(key, &m_entries.front(), m_hashList[hash_index(key)].first);
271template <
class TKey,
class TValue>
275 return iterator(key, NULL, invalid_index());
278template <
class TKey,
class TValue>
282 return hash_key(key) % m_hashList.size();
285template <
class TKey,
class TValue>
289 size_t hi = hash_index(key);
290 size_t curInd = m_hashList[hi].first;
291 while(curInd != invalid_index()){
292 if(m_entries[curInd].key == key)
294 curInd = m_entries[curInd].next;
296 return invalid_index();
103template <
class TKey,
class TValue> {
…}
90 newHashList[hi].second = curInd; {
…}
89 m_entries[newHashList[hi].second].next = curInd; {
…}
86 if(newHashList[hi].first == invalid_index()) {
…}
83 Entry& e = m_entries[curInd]; {
…}
58 m_firstUnusedEntry(invalid_index()) {
…}
void insert(const key_t &key, const value_t &val)
Definition hash_impl.hpp:199
TValue value_t
Definition hash.h:54
value_t & get_entry(const key_t &key)
Definition hash_impl.hpp:158
size_t capacity() const
returns the capacity of the container in which key-value-pairs are stored.
Definition hash_impl.hpp:121
bool has_entry(const key_t &key) const
Definition hash_impl.hpp:150
iterator begin(const key_t &key)
Definition hash_impl.hpp:263
bool empty() const
Definition hash_impl.hpp:142
TKey key_t
Definition hash.h:53
size_t hash_size() const
Definition hash_impl.hpp:105
void erase(const key_t &key)
Definition hash_impl.hpp:227
size_t hash_index(const key_t &key) const
Definition hash_impl.hpp:280
iterator end(const key_t &key)
Definition hash_impl.hpp:273
size_t find_entry(const key_t &key) const
Definition hash_impl.hpp:287
void reserve(size_t size)
Reserves memory for key-value-pair storage.
Definition hash_impl.hpp:113
void resize_hash(size_t size)
Definition hash_impl.hpp:66
void clear()
Definition hash_impl.hpp:129
Hash()
Definition hash_impl.hpp:46
hash_iterator< key_t, value_t, Entry > iterator
Definition hash.h:55
size_t hash_key(const TKey &key)
The hashing method can be specialized for different types.
Definition hash_function.h:50
#define UG_THROW(msg)
Definition error.h:57
Definition smart_pointer.h:814