source: mainline/uspace/lib/cpp/include/internal/hash_table_iterators.hpp@ 0d221d2

lfn serial ticket/834-toolchain-update topic/msim-upgrade topic/simplify-dev-export
Last change on this file since 0d221d2 was d6bb78b, checked in by Dzejrou <dzejrou@…>, 7 years ago

cpp: fixed conversions from non-const iterators to const iterators
  • Property mode set to 100644
File size: 16.1 KB
Line 
1/*
2 * Copyright (c) 2018 Jaroslav Jindrak
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 *
9 * - Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 * - Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in the
13 * documentation and/or other materials provided with the distribution.
14 * - The name of the author may not be used to endorse or promote products
15 * derived from this software without specific prior written permission.
16 *
17 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
18 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
19 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
20 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
21 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
22 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 */
28
29#ifndef LIBCPP_INTERNAL_HASH_TABLE_ITERATORS
30#define LIBCPP_INTERNAL_HASH_TABLE_ITERATORS
31
32#include <internal/iterator.hpp>
33#include <internal/list.hpp>
34#include <internal/hash_table_bucket.hpp>
35#include <iterator>
36
37namespace std::aux
38{
39 template<class Value, class Reference, class Pointer, class Size>
40 class hash_table_iterator
41 {
42 public:
43 using value_type = Value;
44 using size_type = Size;
45 using reference = Reference;
46 using pointer = Pointer;
47 using difference_type = ptrdiff_t;
48
49 using iterator_category = forward_iterator_tag;
50
51 hash_table_iterator(hash_table_bucket<value_type, size_type>* table = nullptr,
52 size_type idx = size_type{}, size_type max_idx = size_type{},
53 list_node<value_type>* current = nullptr)
54 : table_{table}, idx_{idx}, max_idx_{max_idx}, current_{current}
55 { /* DUMMY BODY */ }
56
57 hash_table_iterator(const hash_table_iterator&) = default;
58 hash_table_iterator& operator=(const hash_table_iterator&) = default;
59
60 reference operator*()
61 {
62 return current_->value;
63 }
64
65 pointer operator->()
66 {
67 return &current_->value;
68 }
69
70 hash_table_iterator& operator++()
71 {
72 current_ = current_->next;
73 if (current_ == table_[idx_].head)
74 {
75 if (idx_ < max_idx_)
76 {
77 while (!table_[++idx_].head && idx_ < max_idx_)
78 { /* DUMMY BODY */ }
79
80 if (idx_ < max_idx_)
81 current_ = table_[idx_].head;
82 else
83 current_ = nullptr;
84 }
85 else
86 current_ = nullptr;
87 }
88
89 return *this;
90 }
91
92 hash_table_iterator operator++(int)
93 {
94 auto tmp = *this;
95 ++(*this);
96
97 return tmp;
98 }
99
100 list_node<value_type>* node()
101 {
102 return current_;
103 }
104
105 const list_node<value_type>* node() const
106 {
107 return current_;
108 }
109
110 size_type idx() const
111 {
112 return idx_;
113 }
114
115 private:
116 hash_table_bucket<value_type, size_type>* table_;
117 size_type idx_;
118 size_type max_idx_;
119 list_node<value_type>* current_;
120
121 template<class V, class CR, class CP, class S>
122 friend class hash_table_const_iterator;
123 };
124
125 template<class Value, class Ref, class Ptr, class Size>
126 bool operator==(const hash_table_iterator<Value, Ref, Ptr, Size>& lhs,
127 const hash_table_iterator<Value, Ref, Ptr, Size>& rhs)
128 {
129 return lhs.node() == rhs.node();
130 }
131
132 template<class Value, class Ref, class Ptr, class Size>
133 bool operator!=(const hash_table_iterator<Value, Ref, Ptr, Size>& lhs,
134 const hash_table_iterator<Value, Ref, Ptr, Size>& rhs)
135 {
136 return !(lhs == rhs);
137 }
138
139 template<class Value, class ConstReference, class ConstPointer, class Size>
140 class hash_table_const_iterator
141 {
142 using non_const_iterator_type = hash_table_iterator<
143 Value, get_non_const_ref_t<ConstReference>,
144 get_non_const_ptr<ConstPointer>, Size
145 >;
146
147 public:
148 using value_type = Value;
149 using size_type = Size;
150 using const_reference = ConstReference;
151 using const_pointer = ConstPointer;
152 using difference_type = ptrdiff_t;
153
154 using iterator_category = forward_iterator_tag;
155
156 hash_table_const_iterator(const hash_table_bucket<value_type, size_type>* table = nullptr,
157 size_type idx = size_type{}, size_type max_idx = size_type{},
158 const list_node<value_type>* current = nullptr)
159 : table_{table}, idx_{idx}, max_idx_{max_idx}, current_{current}
160 { /* DUMMY BODY */ }
161
162 hash_table_const_iterator(const hash_table_const_iterator&) = default;
163 hash_table_const_iterator& operator=(const hash_table_const_iterator&) = default;
164
165 hash_table_const_iterator(const non_const_iterator_type& other)
166 : table_{other.table_}, idx_{other.idx_}, max_idx_{other.max_idx_},
167 current_{other.current_}
168 { /* DUMMY BODY */ }
169
170 hash_table_const_iterator& operator=(const non_const_iterator_type& other)
171 {
172 table_ = other.table_;
173 idx_ = other.idx_;
174 max_idx_ = other.max_idx_;
175 current_ = other.current_;
176
177 return *this;
178 }
179
180 const_reference operator*() const
181 {
182 return current_->value;
183 }
184
185 const_pointer operator->() const
186 {
187 return &current_->value;
188 }
189
190 hash_table_const_iterator& operator++()
191 {
192 current_ = current_->next;
193 if (current_ == table_[idx_].head)
194 {
195 if (idx_ < max_idx_)
196 {
197 while (!table_[++idx_].head && idx_ < max_idx_)
198 { /* DUMMY BODY */ }
199
200 if (idx_ < max_idx_)
201 current_ = table_[idx_].head;
202 else
203 current_ = nullptr;
204 }
205 else
206 current_ = nullptr;
207 }
208
209 return *this;
210 }
211
212 hash_table_const_iterator operator++(int)
213 {
214 auto tmp = *this;
215 ++(*this);
216
217 return tmp;
218 }
219
220 list_node<value_type>* node()
221 {
222 return const_cast<list_node<value_type>*>(current_);
223 }
224
225 const list_node<value_type>* node() const
226 {
227 return current_;
228 }
229
230 size_type idx() const
231 {
232 return idx_;
233 }
234
235 private:
236 const hash_table_bucket<value_type, size_type>* table_;
237 size_type idx_;
238 size_type max_idx_;
239 const list_node<value_type>* current_;
240 };
241
242 template<class Value, class CRef, class CPtr, class Size>
243 bool operator==(const hash_table_const_iterator<Value, CRef, CPtr, Size>& lhs,
244 const hash_table_const_iterator<Value, CRef, CPtr, Size>& rhs)
245 {
246 return lhs.node() == rhs.node();
247 }
248
249 template<class Value, class CRef, class CPtr, class Size>
250 bool operator!=(const hash_table_const_iterator<Value, CRef, CPtr, Size>& lhs,
251 const hash_table_const_iterator<Value, CRef, CPtr, Size>& rhs)
252 {
253 return !(lhs == rhs);
254 }
255
256 template<class Value, class Ref, class Ptr, class CRef, class CPtr, class Size>
257 bool operator==(const hash_table_iterator<Value, Ref, Ptr, Size>& lhs,
258 const hash_table_const_iterator<Value, CRef, CPtr, Size>& rhs)
259 {
260 return lhs.node() == rhs.node();
261 }
262
263 template<class Value, class Ref, class Ptr, class CRef, class CPtr, class Size>
264 bool operator!=(const hash_table_iterator<Value, Ref, Ptr, Size>& lhs,
265 const hash_table_const_iterator<Value, CRef, CPtr, Size>& rhs)
266 {
267 return !(lhs == rhs);
268 }
269
270 template<class Value, class CRef, class CPtr, class Ref, class Ptr, class Size>
271 bool operator==(const hash_table_const_iterator<Value, CRef, CPtr, Size>& lhs,
272 const hash_table_iterator<Value, Ref, Ptr, Size>& rhs)
273 {
274 return lhs.node() == rhs.node();
275 }
276
277 template<class Value, class CRef, class CPtr, class Ref, class Ptr, class Size>
278 bool operator!=(const hash_table_const_iterator<Value, CRef, CPtr, Size>& lhs,
279 const hash_table_iterator<Value, Ref, Ptr, Size>& rhs)
280 {
281 return !(lhs == rhs);
282 }
283
284 template<class Value, class Reference, class Pointer>
285 class hash_table_local_iterator
286 {
287 public:
288 using value_type = Value;
289 using reference = Reference;
290 using pointer = Pointer;
291 using difference_type = ptrdiff_t;
292
293 using iterator_category = forward_iterator_tag;
294
295 hash_table_local_iterator(list_node<value_type>* head = nullptr,
296 list_node<value_type>* current = nullptr)
297 : head_{head}, current_{current}
298 { /* DUMMY BODY */ }
299
300 hash_table_local_iterator(const hash_table_local_iterator&) = default;
301 hash_table_local_iterator& operator=(const hash_table_local_iterator&) = default;
302
303 reference operator*()
304 {
305 return current_->value;
306 }
307
308 pointer operator->()
309 {
310 return &current_->value;
311 }
312
313 hash_table_local_iterator& operator++()
314 {
315 current_ = current_->next;
316 if (current_ == head_)
317 current_ = nullptr;
318
319 return *this;
320 }
321
322 hash_table_local_iterator operator++(int)
323 {
324 auto tmp = *this;
325 ++(*this);
326
327 return tmp;
328 }
329
330 list_node<value_type>* node()
331 {
332 return current_;
333 }
334
335 const list_node<value_type>* node() const
336 {
337 return current_;
338 }
339
340 private:
341 list_node<value_type>* head_;
342 list_node<value_type>* current_;
343
344 template<class V, class CR, class CP>
345 friend class hash_table_const_local_iterator;
346 };
347
348 template<class Value, class Ref, class Ptr>
349 bool operator==(const hash_table_local_iterator<Value, Ref, Ptr>& lhs,
350 const hash_table_local_iterator<Value, Ref, Ptr>& rhs)
351 {
352 return lhs.node() == rhs.node();
353 }
354
355 template<class Value, class Ref, class Ptr>
356 bool operator!=(const hash_table_local_iterator<Value, Ref, Ptr>& lhs,
357 const hash_table_local_iterator<Value, Ref, Ptr>& rhs)
358 {
359 return !(lhs == rhs);
360 }
361
362 template<class Value, class ConstReference, class ConstPointer>
363 class hash_table_const_local_iterator
364 {
365 using non_const_iterator_type = hash_table_local_iterator<
366 Value, get_non_const_ref_t<ConstReference>,
367 get_non_const_ptr_t<ConstPointer>
368 >;
369
370 public:
371 using value_type = Value;
372 using const_reference = ConstReference;
373 using const_pointer = ConstPointer;
374 using difference_type = ptrdiff_t;
375
376 using iterator_category = forward_iterator_tag;
377
378 // TODO: requirement for forward iterator is default constructibility, fix others!
379 hash_table_const_local_iterator(const list_node<value_type>* head = nullptr,
380 const list_node<value_type>* current = nullptr)
381 : head_{head}, current_{current}
382 { /* DUMMY BODY */ }
383
384 hash_table_const_local_iterator(const hash_table_const_local_iterator&) = default;
385 hash_table_const_local_iterator& operator=(const hash_table_const_local_iterator&) = default;
386
387 hash_table_const_local_iterator(const non_const_iterator_type& other)
388 : head_{other.head_}, current_{other.current_}
389 { /* DUMMY BODY */ }
390
391 hash_table_const_local_iterator& operator=(const non_const_iterator_type& other)
392 {
393 head_ = other.head_;
394 current_ = other.current_;
395
396 return *this;
397 }
398
399 const_reference operator*() const
400 {
401 return current_->value;
402 }
403
404 const_pointer operator->() const
405 {
406 return &current_->value;
407 }
408
409 hash_table_const_local_iterator& operator++()
410 {
411 current_ = current_->next;
412 if (current_ == head_)
413 current_ = nullptr;
414
415 return *this;
416 }
417
418 hash_table_const_local_iterator operator++(int)
419 {
420 auto tmp = *this;
421 ++(*this);
422
423 return tmp;
424 }
425
426
427 list_node<value_type>* node()
428 {
429 return const_cast<list_node<value_type>*>(current_);
430 }
431
432 const list_node<value_type>* node() const
433 {
434 return current_;
435 }
436
437 private:
438 const list_node<value_type>* head_;
439 const list_node<value_type>* current_;
440 };
441
442 template<class Value, class CRef, class CPtr>
443 bool operator==(const hash_table_const_local_iterator<Value, CRef, CPtr>& lhs,
444 const hash_table_const_local_iterator<Value, CRef, CPtr>& rhs)
445 {
446 return lhs.node() == rhs.node();
447 }
448
449 template<class Value, class CRef, class CPtr>
450 bool operator!=(const hash_table_const_local_iterator<Value, CRef, CPtr>& lhs,
451 const hash_table_const_local_iterator<Value, CRef, CPtr>& rhs)
452 {
453 return !(lhs == rhs);
454 }
455
456 template<class Value, class Ref, class Ptr, class CRef, class CPtr>
457 bool operator==(const hash_table_local_iterator<Value, Ref, Ptr>& lhs,
458 const hash_table_const_local_iterator<Value, CRef, CPtr>& rhs)
459 {
460 return lhs.node() == rhs.node();
461 }
462
463 template<class Value, class Ref, class Ptr, class CRef, class CPtr>
464 bool operator!=(const hash_table_local_iterator<Value, Ref, Ptr>& lhs,
465 const hash_table_const_local_iterator<Value, CRef, CPtr>& rhs)
466 {
467 return !(lhs == rhs);
468 }
469
470 template<class Value, class CRef, class CPtr, class Ref, class Ptr>
471 bool operator==(const hash_table_const_local_iterator<Value, CRef, CPtr>& lhs,
472 const hash_table_local_iterator<Value, Ref, Ptr>& rhs)
473 {
474 return lhs.node() == rhs.node();
475 }
476
477 template<class Value, class CRef, class CPtr, class Ref, class Ptr>
478 bool operator!=(const hash_table_const_local_iterator<Value, CRef, CPtr>& lhs,
479 const hash_table_local_iterator<Value, Ref, Ptr>& rhs)
480 {
481 return !(lhs == rhs);
482 }
483}
484
485#endif
Note: See TracBrowser for help on using the repository browser.