Line data Source code
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 :
42 : namespace ug{
43 :
44 : template <class TKey, class TValue>
45 : Hash<TKey, TValue>::
46 : Hash() :
47 : m_numEntries(0),
48 : m_firstUnusedEntry(invalid_index())
49 : {
50 : resize_hash(1);
51 : }
52 :
53 :
54 : template <class TKey, class TValue>
55 4 : Hash<TKey, TValue>::
56 : Hash(size_t hashSize) :
57 4 : m_numEntries(0),
58 4 : m_firstUnusedEntry(invalid_index())
59 : {
60 4 : resize_hash(hashSize);
61 4 : }
62 :
63 :
64 : template <class TKey, class TValue>
65 4 : void Hash<TKey, TValue>::
66 : resize_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 8 : newHashList.resize(max<size_t>(1, size),
77 4 : pair<size_t, size_t>(invalid_index(), invalid_index()));
78 :
79 4 : if(m_numEntries > 0){
80 0 : for(size_t i = 0; i < m_hashList.size(); ++i){
81 0 : size_t curInd = m_hashList[i].first;
82 0 : while(curInd != invalid_index()){
83 : Entry& e = m_entries[curInd];
84 0 : size_t hi = hash_key(e.key) % size;
85 :
86 0 : if(newHashList[hi].first == invalid_index())
87 0 : newHashList[hi].first = newHashList[hi].second = curInd;
88 : else{
89 0 : m_entries[newHashList[hi].second].next = curInd;
90 0 : newHashList[hi].second = curInd;
91 : }
92 :
93 0 : curInd = e.next;
94 0 : e.next = invalid_index();
95 : }
96 : }
97 : }
98 :
99 : m_hashList.swap(newHashList);
100 4 : }
101 :
102 :
103 : template <class TKey, class TValue>
104 : size_t Hash<TKey, TValue>::
105 : hash_size() const
106 : {
107 : return m_hashList.size();
108 : }
109 :
110 :
111 : template <class TKey, class TValue>
112 : void Hash<TKey, TValue>::
113 : reserve(size_t size)
114 : {
115 0 : m_entries.reserve(size);
116 0 : }
117 :
118 :
119 : template <class TKey, class TValue>
120 : size_t Hash<TKey, TValue>::
121 : capacity() const
122 : {
123 : return m_entries.capacity();
124 : }
125 :
126 :
127 : template <class TKey, class TValue>
128 : void Hash<TKey, TValue>::
129 : clear()
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 :
140 : template <class TKey, class TValue>
141 : bool Hash<TKey, TValue>::
142 : empty() const
143 : {
144 : return m_numEntries == 0;
145 : }
146 :
147 :
148 : template <class TKey, class TValue>
149 : bool Hash<TKey, TValue>::
150 : has_entry(const key_t& key) const
151 : {
152 0 : return find_entry(key) != invalid_index();
153 : }
154 :
155 :
156 : template <class TKey, class TValue>
157 7 : TValue& Hash<TKey, TValue>::
158 : get_entry(const key_t& key)
159 : {
160 : size_t eind = find_entry(key);
161 :
162 7 : if(eind == invalid_index()){
163 0 : 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 7 : return m_entries[eind].value;
167 : }
168 :
169 :
170 : template <class TKey, class TValue>
171 : const TValue& Hash<TKey, TValue>::
172 : get_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 :
183 : template <class TKey, class TValue>
184 11 : bool Hash<TKey, TValue>::
185 : get_entry(TValue& valOut, const key_t& key) const
186 : {
187 0 : size_t eind = find_entry(key);
188 :
189 11 : if(eind == invalid_index())
190 : return false;
191 :
192 11 : valOut = m_entries[eind].value;
193 11 : return true;
194 : }
195 :
196 :
197 : template <class TKey, class TValue>
198 11 : void Hash<TKey, TValue>::
199 : insert(const key_t& key, const value_t& val)
200 : {
201 11 : size_t eind = m_firstUnusedEntry;
202 11 : if(eind == invalid_index()){
203 : eind = m_entries.size();
204 8 : m_entries.push_back(Entry(key, val));
205 : }
206 : else{
207 3 : m_firstUnusedEntry = m_entries[eind].next;
208 3 : m_entries[eind] = Entry(key, val);
209 : }
210 :
211 : size_t hi = hash_index(key);
212 :
213 11 : if(m_hashList[hi].first == invalid_index()){
214 11 : m_hashList[hi].first = m_hashList[hi].second = eind;
215 : }
216 : else{
217 0 : m_entries[m_hashList[hi].second].next = eind;
218 0 : m_hashList[hi].second = eind;
219 : }
220 :
221 11 : ++m_numEntries;
222 11 : }
223 :
224 :
225 : template <class TKey, class TValue>
226 7 : void Hash<TKey, TValue>::
227 : erase(const key_t& key)
228 : {
229 : size_t hi = hash_index(key);
230 : size_t prevInd = invalid_index();
231 7 : size_t curInd = m_hashList[hi].first;
232 7 : while(curInd != invalid_index()){
233 7 : if(m_entries[curInd].key == key)
234 : break;
235 : prevInd = curInd;
236 0 : curInd = m_entries[curInd].next;
237 : }
238 :
239 7 : 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 7 : if(prevInd == invalid_index())
244 7 : m_hashList[hi].first = m_entries[curInd].next;
245 : else
246 0 : 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 7 : if(m_entries[curInd].next == invalid_index())
251 7 : m_hashList[hi].second = prevInd;
252 : }
253 :
254 : // curInd has to be added to the list of unused entries:
255 7 : m_entries[curInd].next = m_firstUnusedEntry;
256 7 : m_firstUnusedEntry = curInd;
257 7 : --m_numEntries;
258 7 : }
259 :
260 :
261 : template <class TKey, class TValue>
262 : typename Hash<TKey, TValue>::iterator Hash<TKey, TValue>::
263 : begin(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 :
271 : template <class TKey, class TValue>
272 : typename Hash<TKey, TValue>::iterator Hash<TKey, TValue>::
273 : end(const key_t& key)
274 : {
275 : return iterator(key, NULL, invalid_index());
276 : }
277 :
278 : template <class TKey, class TValue>
279 : size_t Hash<TKey, TValue>::
280 : hash_index(const key_t& key) const
281 : {
282 68 : return hash_key(key) % m_hashList.size();
283 : }
284 :
285 : template <class TKey, class TValue>
286 0 : size_t Hash<TKey, TValue>::
287 : find_entry(const key_t& key) const
288 : {
289 : size_t hi = hash_index(key);
290 50 : size_t curInd = m_hashList[hi].first;
291 50 : while(curInd != invalid_index()){
292 35 : if(m_entries[curInd].key == key)
293 0 : return curInd;
294 0 : curInd = m_entries[curInd].next;
295 : }
296 : return invalid_index();
297 : }
298 :
299 : }// end of namespace
300 :
301 : #endif
|
