Line data Source code
1 : // Author(s): Bas Ploeger
2 : // Copyright: see the accompanying file COPYING or copy at
3 : // https://github.com/mCRL2org/mCRL2/blob/master/COPYING
4 : //
5 : // Distributed under the Boost Software License, Version 1.0.
6 : // (See accompanying file LICENSE_1_0.txt or copy at
7 : // http://www.boost.org/LICENSE_1_0.txt)
8 : //
9 : /// \file sim_hashtable.cpp
10 : #include "mcrl2/lts/detail/sim_hashtable.h"
11 :
12 : #define NOT_FOUND (std::size_t)(-1)
13 : #define END_OF_LIST (std::size_t)(-1)
14 : #define REMOVED (std::size_t)(-2)
15 :
16 : /* ---------------- hash_table_iterator ----------------------------- */
17 :
18 0 : hash_table2_iterator::hash_table2_iterator(hash_table2* ht)
19 0 : : hash_table(ht)
20 : {
21 0 : bucket_it = hash_table->buckets.begin();
22 0 : while (bucket_it != hash_table->buckets.end()
23 0 : && (bucket_it->next == REMOVED))
24 : {
25 0 : ++bucket_it;
26 : }
27 0 : }
28 :
29 0 : void hash_table2_iterator::operator ++()
30 : {
31 0 : if (bucket_it != hash_table->buckets.end())
32 : {
33 0 : ++bucket_it;
34 0 : while (bucket_it != hash_table->buckets.end()
35 0 : && (bucket_it->next == REMOVED))
36 : {
37 0 : ++bucket_it;
38 : }
39 : }
40 0 : }
41 :
42 430 : hash_table3_iterator::hash_table3_iterator(hash_table3* ht)
43 430 : : hash_table(ht)
44 : {
45 430 : bucket_it = hash_table->buckets.begin();
46 430 : end = hash_table->buckets.end();
47 430 : while (bucket_it != end && bucket_it->next == REMOVED)
48 : {
49 0 : ++bucket_it;
50 : }
51 430 : }
52 :
53 3057 : void hash_table3_iterator::operator ++()
54 : {
55 3057 : if (bucket_it != end)
56 : {
57 3057 : ++bucket_it;
58 3057 : while (bucket_it != end && bucket_it->next == REMOVED)
59 : {
60 0 : ++bucket_it;
61 : }
62 : }
63 3057 : }
64 :
65 : /* ---------------- hash_table -------------------------------------- */
66 :
67 32 : hash_table2::hash_table2(std::size_t initsize)
68 : {
69 32 : mask = 1;
70 352 : while (mask < initsize)
71 : {
72 320 : mask = mask << 1;
73 : }
74 32 : --mask;
75 32 : clear();
76 32 : }
77 :
78 32 : hash_table2::~hash_table2()
79 32 : {}
80 :
81 64 : void hash_table2::clear()
82 : {
83 64 : table.assign(mask+1,END_OF_LIST);
84 64 : buckets.clear();
85 64 : removed_count = 0;
86 64 : }
87 :
88 148 : void hash_table2::add(std::size_t x,std::size_t y)
89 : {
90 148 : std::size_t h = hash(x,y);
91 148 : if (hfind(h,x,y) == NOT_FOUND)
92 : {
93 148 : if (check_table())
94 : {
95 0 : h = hash(x,y);
96 : }
97 : bucket2 new_bucket;
98 148 : new_bucket.x = x;
99 148 : new_bucket.y = y;
100 148 : new_bucket.next = table[h];
101 148 : table[h] = buckets.size();
102 148 : buckets.push_back(new_bucket);
103 : }
104 148 : }
105 :
106 597 : bool hash_table2::find(std::size_t x,std::size_t y)
107 : {
108 597 : return (hfind(hash(x,y),x,y) != NOT_FOUND);
109 : }
110 :
111 0 : void hash_table2::remove(std::size_t x,std::size_t y)
112 : {
113 : bucket2 b;
114 : std::size_t i, prev_i;
115 0 : std::size_t h = hash(x,y);
116 0 : i = table[h];
117 0 : if (i != END_OF_LIST)
118 : {
119 0 : b = buckets[i];
120 0 : if (b.x == x && b.y == y)
121 : {
122 0 : table[h] = b.next;
123 0 : buckets[i].next = REMOVED;
124 0 : ++removed_count;
125 0 : return;
126 : }
127 0 : prev_i = i;
128 0 : i = b.next;
129 : }
130 0 : while (i != END_OF_LIST)
131 : {
132 0 : b = buckets[i];
133 0 : if (b.x == x && b.y == y)
134 : {
135 0 : buckets[prev_i].next = buckets[i].next;
136 0 : buckets[i].next = REMOVED;
137 0 : ++removed_count;
138 0 : return;
139 : }
140 0 : prev_i = i;
141 0 : i = b.next;
142 : }
143 : }
144 :
145 745 : std::size_t hash_table2::hfind(std::size_t h,std::size_t x,std::size_t y)
146 : {
147 745 : std::size_t i = table[h];
148 : bucket2 b;
149 745 : while (i != END_OF_LIST)
150 : {
151 184 : b = buckets[i];
152 184 : if (b.x == x && b.y == y)
153 : {
154 184 : return i;
155 : }
156 0 : i = b.next;
157 : }
158 561 : return NOT_FOUND;
159 : }
160 :
161 148 : bool hash_table2::check_table()
162 : {
163 148 : if (4*(buckets.size() - removed_count) >= 3*table.size())
164 : {
165 : /* table is filled for at least 75%, so let's rehash! */
166 0 : mask = (2*mask) + 1;
167 0 : table.assign(mask+1,END_OF_LIST);
168 : std::size_t h;
169 0 : for (std::size_t i = 0; i < buckets.size(); ++i)
170 : {
171 0 : if (buckets[i].next != REMOVED)
172 : {
173 0 : h = hash(buckets[i].x,buckets[i].y);
174 0 : buckets[i].next = table[h];
175 0 : table[h] = i;
176 : }
177 : }
178 0 : return true;
179 : }
180 148 : return false;
181 : }
182 :
183 745 : std::size_t hash_table2::hash(std::size_t x, std::size_t y)
184 : {
185 745 : return ((159403*x + 389651*y) & mask);
186 : }
187 :
188 162 : hash_table3::hash_table3(std::size_t initsize)
189 : {
190 162 : mask = 1;
191 1782 : while (mask < initsize)
192 : {
193 1620 : mask = mask << 1;
194 : }
195 162 : --mask;
196 162 : clear();
197 162 : }
198 :
199 162 : hash_table3::~hash_table3()
200 162 : {}
201 :
202 708 : void hash_table3::clear()
203 : {
204 708 : table.assign(mask+1,END_OF_LIST);
205 708 : buckets.clear();
206 708 : removed_count = 0;
207 708 : }
208 :
209 5425 : void hash_table3::add(std::size_t x,std::size_t y,std::size_t z)
210 : {
211 5425 : std::size_t h = hash(x,y,z);
212 5425 : if (hfind(h,x,y,z) == NOT_FOUND)
213 : {
214 5254 : if (check_table())
215 : {
216 0 : h = hash(x,y,z);
217 : }
218 : bucket3 new_bucket;
219 5254 : new_bucket.x = x;
220 5254 : new_bucket.y = y;
221 5254 : new_bucket.z = z;
222 5254 : new_bucket.next = table[h];
223 5254 : table[h] = buckets.size();
224 5254 : buckets.push_back(new_bucket);
225 : }
226 5425 : }
227 :
228 3716 : bool hash_table3::find(std::size_t x,std::size_t y,std::size_t z)
229 : {
230 3716 : return (hfind(hash(x,y,z),x,y,z) != NOT_FOUND);
231 : }
232 :
233 28 : void hash_table3::remove(std::size_t x,std::size_t y,std::size_t z)
234 : {
235 : bucket3 b;
236 : std::size_t i, prev_i;
237 28 : std::size_t h = hash(x,y,z);
238 28 : i = table[h];
239 28 : if (i != END_OF_LIST)
240 : {
241 28 : b = buckets[i];
242 28 : if (b.x == x && b.y == y && b.z == z)
243 : {
244 26 : table[h] = b.next;
245 26 : buckets[i].next = REMOVED;
246 26 : ++removed_count;
247 28 : return;
248 : }
249 2 : prev_i = i;
250 2 : i = b.next;
251 : }
252 2 : while (i != END_OF_LIST)
253 : {
254 2 : b = buckets[i];
255 2 : if (b.x == x && b.y == y && b.z == z)
256 : {
257 2 : buckets[prev_i].next = buckets[i].next;
258 2 : buckets[i].next = REMOVED;
259 2 : ++removed_count;
260 2 : return;
261 : }
262 0 : prev_i = i;
263 0 : i = b.next;
264 : }
265 : }
266 :
267 9141 : std::size_t hash_table3::hfind(std::size_t h,std::size_t x,std::size_t y,std::size_t z)
268 : {
269 9141 : std::size_t i = table[h];
270 : bucket3 b;
271 9337 : while (i != END_OF_LIST)
272 : {
273 2256 : b = buckets[i];
274 2256 : if (b.x == x && b.y == y && b.z == z)
275 : {
276 2060 : return i;
277 : }
278 196 : i = b.next;
279 : }
280 7081 : return NOT_FOUND;
281 : }
282 :
283 5254 : bool hash_table3::check_table()
284 : {
285 5254 : if (4*(buckets.size() - removed_count) >= 3*table.size())
286 : {
287 : /* table is filled for at least 75%, so let's rehash! */
288 0 : mask = (2*mask) + 1;
289 0 : table.assign(mask+1,END_OF_LIST);
290 : std::size_t h;
291 0 : for (std::size_t i = 0; i < buckets.size(); ++i)
292 : {
293 0 : if (buckets[i].next != REMOVED)
294 : {
295 0 : h = hash(buckets[i].x,buckets[i].y,buckets[i].z);
296 0 : buckets[i].next = table[h];
297 0 : table[h] = i;
298 : }
299 : }
300 0 : return true;
301 : }
302 5254 : return false;
303 : }
304 :
305 9169 : std::size_t hash_table3::hash(std::size_t x, std::size_t y, std::size_t z)
306 : {
307 9169 : return ((159403*x + 389651*y + 521503*z) & mask);
308 : }
|