Loading [MathJax]/extensions/tex2jax.js
ug4
All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules Pages
hash_impl.hpp
Go to the documentation of this file.
1/*
2 * Copyright (c) 2013-2015: G-CSC, Goethe University Frankfurt
3 * Author: Sebastian Reiter
4 *
5 * This file is part of UG4.
6 *
7 * UG4 is free software: you can redistribute it and/or modify it under the
8 * terms of the GNU Lesser General Public License version 3 (as published by the
9 * Free Software Foundation) with the following additional attribution
10 * requirements (according to LGPL/GPL v3 §7):
11 *
12 * (1) The following notice must be displayed in the Appropriate Legal Notices
13 * of covered and combined works: "Based on UG4 (www.ug4.org/license)".
14 *
15 * (2) The following notice must be displayed at a prominent place in the
16 * terminal output of covered works: "Based on UG4 (www.ug4.org/license)".
17 *
18 * (3) The following bibliography is recommended for citation and must be
19 * preserved in all covered files:
20 * "Reiter, S., Vogel, A., Heppner, I., Rupp, M., and Wittum, G. A massively
21 * parallel geometric multigrid solver on hierarchically distributed grids.
22 * Computing and visualization in science 16, 4 (2013), 151-164"
23 * "Vogel, A., Reiter, S., Rupp, M., Nägel, A., and Wittum, G. UG4 -- a novel
24 * flexible software system for simulating pde based models on high performance
25 * computers. Computing and visualization in science 16, 4 (2013), 165-179"
26 *
27 * This program is distributed in the hope that it will be useful,
28 * but WITHOUT ANY WARRANTY; without even the implied warranty of
29 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
30 * GNU Lesser General Public License for more details.
31 */
32
33#ifndef __H__UG__hash_impl__
34#define __H__UG__hash_impl__
35
36#include <cassert>
37#include <algorithm>
38#include <limits>
39#include "common/error.h"
40#include "hash.h"
41
42namespace ug{
43
44template <class TKey, class TValue>
46Hash() :
47 m_numEntries(0),
48 m_firstUnusedEntry(invalid_index())
49{
50 resize_hash(1);
51}
52
53
54template <class TKey, class TValue>
56Hash(size_t hashSize) :
57 m_numEntries(0),
58 m_firstUnusedEntry(invalid_index())
60 resize_hash(hashSize);
63
64template <class TKey, class TValue>
66resize_hash(size_t size)
67{
68//todo: This method could be more efficient by reusing memory in m_hashList...
69
70// create a new hash and insert all existing items into it
71// when creating the hash-list, we'll reserve some additional memory to
72// avoid frequent reallocations.
73// note: during the first resize no additional memory will be allocated.
74 using namespace std;
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()));
79 if(m_numEntries > 0){
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];
84 size_t hi = hash_key(e.key) % size;
86 if(newHashList[hi].first == invalid_index())
87 newHashList[hi].first = newHashList[hi].second = curInd;
88 else{
89 m_entries[newHashList[hi].second].next = curInd;
90 newHashList[hi].second = curInd;
91 }
93 curInd = e.next;
94 e.next = invalid_index();
95 }
96 }
97 }
98
99 m_hashList.swap(newHashList);
100}
101
103template <class TKey, class TValue>
105hash_size() const
106{
107 return m_hashList.size();
108}
109
110
111template <class TKey, class TValue>
113reserve(size_t size)
114{
115 m_entries.reserve(size);
116}
117
118
119template <class TKey, class TValue>
121capacity() const
122{
123 return m_entries.capacity();
124}
125
126
127template <class TKey, class TValue>
129clear()
130{
131 using namespace std;
132 m_entries.clear();
133 m_numEntries = 0;
134 m_firstUnusedEntry = invalid_index();
135 m_hashList.assign(m_hashList.size(),
136 make_pair<size_t, size_t>(invalid_index(), invalid_index()));
137}
138
139
140template <class TKey, class TValue>
142empty() const
143{
144 return m_numEntries == 0;
145}
146
147
148template <class TKey, class TValue>
150has_entry(const key_t& key) const
151{
152 return find_entry(key) != invalid_index();
153}
154
155
156template <class TKey, class TValue>
158get_entry(const key_t& key)
159{
160 size_t eind = find_entry(key);
161
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.");
165 }
166 return m_entries[eind].value;
167}
168
169
170template <class TKey, class TValue>
172get_entry(const key_t& key) const
173{
174 size_t eind = find_entry(key);
175
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.");
179 }
180 return m_entries[eind].value;
181}
182
183template <class TKey, class TValue>
185get_entry(TValue& valOut, const key_t& key) const
186{
187 size_t eind = find_entry(key);
188
189 if(eind == invalid_index())
190 return false;
191
192 valOut = m_entries[eind].value;
193 return true;
194}
195
196
197template <class TKey, class TValue>
199insert(const key_t& key, const value_t& val)
200{
201 size_t eind = m_firstUnusedEntry;
202 if(eind == invalid_index()){
203 eind = m_entries.size();
204 m_entries.push_back(Entry(key, val));
205 }
206 else{
207 m_firstUnusedEntry = m_entries[eind].next;
208 m_entries[eind] = Entry(key, val);
209 }
210
211 size_t hi = hash_index(key);
212
213 if(m_hashList[hi].first == invalid_index()){
214 m_hashList[hi].first = m_hashList[hi].second = eind;
215 }
216 else{
217 m_entries[m_hashList[hi].second].next = eind;
218 m_hashList[hi].second = eind;
219 }
220
221 ++m_numEntries;
222}
223
224
225template <class TKey, class TValue>
227erase(const key_t& key)
228{
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)
234 break;
235 prevInd = curInd;
236 curInd = m_entries[curInd].next;
237 }
238
239 if(curInd != invalid_index()){
240 // if curInd was the first entry for this hash-index, we have to adjust
241 // the beginning of the sequence. If not, we have to adjust the next pointer
242 // of the previous entry.
243 if(prevInd == invalid_index())
244 m_hashList[hi].first = m_entries[curInd].next;
245 else
246 m_entries[prevInd].next = m_entries[curInd].next;
247
248 // if curInd was the last entry for this hash-index, we have to adjust
249 // the end of the sequence.
250 if(m_entries[curInd].next == invalid_index())
251 m_hashList[hi].second = prevInd;
252 }
253
254// curInd has to be added to the list of unused entries:
255 m_entries[curInd].next = m_firstUnusedEntry;
256 m_firstUnusedEntry = curInd;
257 --m_numEntries;
258}
259
260
261template <class TKey, class TValue>
263begin(const key_t& key)
264{
265 if(empty())
266 return end(key);
267 return iterator(key, &m_entries.front(), m_hashList[hash_index(key)].first);
268}
269
270
271template <class TKey, class TValue>
273end(const key_t& key)
274{
275 return iterator(key, NULL, invalid_index());
276}
277
278template <class TKey, class TValue>
280hash_index(const key_t& key) const
281{
282 return hash_key(key) % m_hashList.size();
283}
284
285template <class TKey, class TValue>
287find_entry(const key_t& key) const
288{
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)
293 return curInd;
294 curInd = m_entries[curInd].next;
295 }
296 return invalid_index();
297}
298
299}// end of namespace
300
301#endif
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
the ug namespace
Definition hash.h:106