STXXL  1.4-dev
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
iterator.h
Go to the documentation of this file.
1 /***************************************************************************
2  * include/stxxl/bits/containers/hash_map/iterator.h
3  *
4  * Part of the STXXL. See http://stxxl.sourceforge.net
5  *
6  * Copyright (C) 2007 Markus Westphal <[email protected]>
7  * Copyright (C) 2014 Timo Bingmann <[email protected]>
8  *
9  * Distributed under the Boost Software License, Version 1.0.
10  * (See accompanying file LICENSE_1_0.txt or copy at
11  * http://www.boost.org/LICENSE_1_0.txt)
12  **************************************************************************/
13 
14 #ifndef STXXL_CONTAINERS_HASH_MAP_ITERATOR_HEADER
15 #define STXXL_CONTAINERS_HASH_MAP_ITERATOR_HEADER
16 
17 #include <stxxl/bits/namespace.h>
19 
21 
23 
24 namespace hash_map {
25 
26 template <class HashMap>
28 template <class HashMap>
30 template <class HashMap>
32 template <class HashMap>
33 class block_cache;
34 
35 template <class HashMap>
37 {
38 public:
39  friend class iterator_map<HashMap>;
40  friend void HashMap::erase(hash_map_const_iterator<HashMap> it);
41 
42  typedef HashMap hash_map_type;
45  typedef typename hash_map_type::value_type value_type;
46  typedef typename hash_map_type::key_type key_type;
47  typedef typename hash_map_type::reference reference;
48  typedef typename hash_map_type::const_reference const_reference;
49  typedef typename hash_map_type::node_type node_type;
50  typedef typename hash_map_type::bucket_type bucket_type;
51  typedef typename hash_map_type::bid_iterator_type bid_iterator_type;
52  typedef typename hash_map_type::source_type source_type;
53 
55 
56  typedef std::forward_iterator_tag iterator_category;
57 
58 protected:
59  HashMap* map_;
61  //! true if prefetching enabled; false by default, will be set to true when
62  //! incrementing (see find_next())
63  bool prefetch_;
64  //! index of current bucket
66  //! source of current value: external or internal
68  //! current (source=internal) or old (src=external) internal node
70  //! position of current (source=external) or next (source=internal)
71  //! external value (see _ext_valid)
73  //! key of current value
75  /*! true if i_external points to the current or next external value
76 
77  example: iterator was created by hash_map::find() and the value was found
78  in internal memory
79 
80  => iterator pointing to internal node is created and location of next
81  external value is unknown (_ext_valid == false)
82 
83  => when incrementing the iterator the external values will be scanned
84  from the beginning of the bucket to find the valid external index
85  */
86  bool ext_valid_;
87  //! true if iterator equals end()
88  bool end_;
89 
90 public:
91  //! Construct a new iterator
93  external_size_type i_external, source_type source,
94  bool ext_valid, key_type key)
95  : map_(map),
96  reader_(NULL),
97  prefetch_(false),
98  i_bucket_(i_bucket),
99  source_(source),
100  node_(node),
101  i_external_(i_external),
102  key_(key),
103  ext_valid_(ext_valid),
104  end_(false)
105  {
106  STXXL_VERBOSE3("hash_map_iterator_base parameter construct addr=" << this);
107  map_->iterator_map_.register_iterator(*this);
108  }
109 
110  //! Construct a new iterator pointing to the end of the given hash-map.
112  : map_(map),
113  reader_(NULL),
114  prefetch_(false),
115  i_bucket_(0),
116  source_(hash_map_type::src_unknown),
117  node_(NULL),
118  i_external_(0),
119  ext_valid_(false),
120  end_(true)
121  { }
122 
123  //! Construct a new iterator from an existing one
125  : map_(obj.map_),
126  reader_(NULL),
127  prefetch_(obj.prefetch_),
128  i_bucket_(obj.i_bucket_),
129  source_(obj.source_),
130  node_(obj.node_),
131  i_external_(obj.i_external_),
132  key_(obj.key_),
133  ext_valid_(obj.ext_valid_),
134  end_(obj.end_)
135  {
136  STXXL_VERBOSE3("hash_map_iterator_base constr from" << (&obj) << " to " << this);
137 
138  if (!end_ && map_)
139  map_->iterator_map_.register_iterator(*this);
140  }
141 
142  //! Assignment operator
144  {
145  STXXL_VERBOSE3("hash_map_iterator_base copy from" << (&obj) << " to " << this);
146 
147  if (&obj != this)
148  {
149  if (map_ && !end_)
150  map_->iterator_map_.unregister_iterator(*this);
151 
152  reset_reader();
153 
154  map_ = obj.map_;
155  i_bucket_ = obj.i_bucket_;
156  node_ = obj.node_;
157  source_ = obj.source_;
158  i_external_ = obj.i_external_;
159  ext_valid_ = obj.ext_valid_;
160  prefetch_ = obj.prefetch_;
161  end_ = obj.end_;
162  key_ = obj.key_;
163 
164  if (map_ && !end_)
165  map_->iterator_map_.register_iterator(*this);
166  }
167  return *this;
168  }
169 
170  //! Two iterators are equal if the point to the same value in the same map
171  bool operator == (const hash_map_iterator_base& obj) const
172  {
173  if (end_ && obj.end_)
174  return true;
175 
176  if (map_ != obj.map_ ||
177  i_bucket_ != obj.i_bucket_ ||
178  source_ != obj.source_)
179  return false;
180 
181  if (source_ == hash_map_type::src_internal)
182  return node_ == obj.node_;
183  else
184  return i_external_ == obj.i_external_;
185  }
186 
187  bool operator != (const hash_map_iterator_base& obj) const
188  {
189  return ! operator == (obj);
190  }
191 
192 protected:
193  //! Initialize reader object to scan external values
194  void init_reader()
195  {
196  const bucket_type& bucket = map_->buckets_[i_bucket_];
197 
198  bid_iterator_type begin = map_->bids_.begin() + bucket.i_block_;
199  bid_iterator_type end = map_->bids_.end();
200 
201  reader_ = new reader_type(begin, end, map_->block_cache_,
202  bucket.i_subblock_, prefetch_);
203 
204  // external value's index already known
205  if (ext_valid_)
206  {
207  // TODO: speed this up (go directly to i_external_
208  for (external_size_type i = 0; i < i_external_; i++)
209  ++(*reader_);
210  }
211  // otw lookup external value.
212  // case I: no internal value => first external value is the desired one
213  else if (node_ == NULL)
214  {
215  i_external_ = 0;
216  ext_valid_ = true;
217  }
218  // case II: search for smallest external value > internal value
219  else
220  {
221  i_external_ = 0;
222  while (i_external_ < bucket.n_external_)
223  {
224  if (map_->_gt(reader_->const_value().first, node_->value_.first))
225  break;
226 
227  ++(*reader_);
228  ++i_external_;
229  }
230  // note: i_external==num_external just means that there was no
231  // external value > internal value (which is perfectly OK)
232  ext_valid_ = true;
233  }
234  }
235 
236  //! Reset reader-object
238  {
239  if (reader_) {
240  delete reader_;
241  reader_ = NULL;
242  }
243  }
244 
245 public:
246  //! Advance iterator to the next value
247  //! The next value is determined in the following way
248  //! - if there are remaining internal or external values in the current
249  //! bucket, choose the smallest among them, that is not marked as deleted
250  //! - otherwise continue with the next bucket
251  void find_next(bool start_prefetching = false)
252  {
253  // invariant: current external value is always > current internal value
254  assert(!end_);
255 
256  internal_size_type i_bucket_old = i_bucket_;
257  bucket_type bucket = map_->buckets_[i_bucket_];
258 
259  if (reader_ == NULL)
260  init_reader();
261 
262  // when incremented once, more increments are likely to follow;
263  // therefore start prefetching
264  if (start_prefetching && !prefetch_)
265  {
266  reader_->enable_prefetching();
267  prefetch_ = true;
268  }
269 
270  // determine starting-points for comparision, which are given by:
271  // - tmp_node: smallest internal value > old value (tmp_node may be NULL)
272  // - reader_: smallest external value > old value (external value may not exists)
273  node_type* tmp_node = (node_) ? node_ : bucket.list_;
274  if (source_ == hash_map_type::src_external)
275  {
276  while (tmp_node && map_->_leq(tmp_node->value_.first, key_))
277  tmp_node = tmp_node->next();
278 
279  ++i_external_;
280  ++(*reader_);
281  }
282  else if (source_ == hash_map_type::src_internal)
283  tmp_node = node_->next();
284  // else (source unknown): tmp_node and reader_ already point to the
285  // correct values
286 
287  while (true) {
288  // internal and external values available
289  while (tmp_node && i_external_ < bucket.n_external_)
290  {
291  // internal value less or equal external value => internal wins
292  if (map_->_leq(tmp_node->value_.first, reader_->const_value().first))
293  {
294  node_ = tmp_node;
295  if (map_->_eq(node_->value_.first, reader_->const_value().first))
296  {
297  ++i_external_;
298  ++(*reader_);
299  }
300 
301  if (!node_->deleted())
302  {
303  key_ = node_->value_.first;
304  source_ = hash_map_type::src_internal;
305  goto end_search; // just this once - I promise...
306  }
307  else
308  // continue search if internal value flaged as deleted
309  tmp_node = tmp_node->next();
310  }
311  // otherwise external wins
312  else
313  {
314  key_ = reader_->const_value().first;
315  source_ = hash_map_type::src_external;
316  goto end_search;
317  }
318  }
319  // only external values left
320  if (i_external_ < bucket.n_external_)
321  {
322  key_ = reader_->const_value().first;
323  source_ = hash_map_type::src_external;
324  goto end_search;
325  }
326  // only internal values left
327  while (tmp_node)
328  {
329  node_ = tmp_node;
330  if (!node_->deleted())
331  {
332  key_ = node_->value_.first;
333  source_ = hash_map_type::src_internal;
334  goto end_search;
335  }
336  else
337  tmp_node = tmp_node->next(); // continue search
338  }
339 
340  // at this point there are obviously no more values in the current
341  // bucket let's try the next one (outer while-loop!)
342  i_bucket_++;
343  if (i_bucket_ == map_->buckets_.size())
344  {
345  end_ = true;
346  reset_reader();
347  goto end_search;
348  }
349  else
350  {
351  bucket = map_->buckets_[i_bucket_];
352  i_external_ = 0;
353  tmp_node = bucket.list_;
354  node_ = NULL;
355  reader_->skip_to(map_->bids_.begin() + bucket.i_block_, bucket.i_subblock_);
356  }
357  }
358 
359 end_search:
360  if (end_)
361  {
362  this->map_->iterator_map_.unregister_iterator(*this, i_bucket_old);
363  }
364  else if (i_bucket_old != i_bucket_)
365  {
366  this->map_->iterator_map_.unregister_iterator(*this, i_bucket_old);
367  this->map_->iterator_map_.register_iterator(*this, i_bucket_);
368  }
369  }
370 
372  {
373  STXXL_VERBOSE3("hash_map_iterator_base deconst " << this);
374 
375  if (map_ && !end_)
376  map_->iterator_map_.unregister_iterator(*this);
377  reset_reader();
378  }
379 };
380 
381 template <class HashMap>
382 class hash_map_iterator : public hash_map_iterator_base<HashMap>
383 {
384 public:
385  typedef HashMap hash_map_type;
388  typedef typename hash_map_type::value_type value_type;
389  typedef typename hash_map_type::key_type key_type;
390  typedef typename hash_map_type::reference reference;
391  typedef typename hash_map_type::const_reference const_reference;
392  typedef typename hash_map_type::pointer pointer;
393  typedef typename hash_map_type::const_pointer const_pointer;
394  typedef typename hash_map_type::node_type node_type;
395  typedef typename hash_map_type::bucket_type bucket_type;
396  typedef typename hash_map_type::bid_iterator_type bid_iterator_type;
397  typedef typename hash_map_type::source_type source_type;
398 
399  typedef buffered_reader<typename hash_map_type::block_cache_type,
401 
402  typedef std::forward_iterator_tag iterator_category;
403 
406 
407 public:
409  node_type* node, external_size_type i_external,
410  source_type source, bool ext_valid, key_type key)
411  : base_type(map, i_bucket, node, i_external, source, ext_valid, key)
412  { }
413 
415  : base_type(NULL)
416  { }
417 
419  : base_type(map)
420  { }
421 
423  : base_type(obj)
424  { }
425 
426  hash_map_iterator& operator = (const hash_map_iterator& obj)
427  {
428  base_type::operator = (obj);
429  return *this;
430  }
431 
432  bool operator == (const hash_map_iterator& obj) const
433  {
434  return base_type::operator == (obj);
435  }
436 
437  bool operator == (const hash_map_const_iterator& obj) const
438  {
439  return base_type::operator == (obj);
440  }
441 
442  bool operator != (const hash_map_iterator& obj) const
443  {
444  return base_type::operator != (obj);
445  }
446 
447  bool operator != (const hash_map_const_iterator& obj) const
448  {
449  return base_type::operator != (obj);
450  }
451 
452  //! Return reference to current value. If source is external, mark the
453  //! value's block as dirty
454  reference operator * ()
455  {
456  if (this->source_ == hash_map_type::src_internal)
457  {
458  return this->node_->value_;
459  }
460  else
461  {
462  if (this->reader_ == NULL)
463  base_type::init_reader();
464 
465  return this->reader_->value();
466  }
467  }
468 
469  //! Return reference to current value. If source is external, mark the
470  //! value's block as dirty
471  pointer operator -> ()
472  {
473  return &operator * ();
474  }
475 
476  //! Increment iterator
478  {
479  base_type::find_next(true);
480  return *this;
481  }
482 };
483 
484 template <class HashMap>
485 class hash_map_const_iterator : public hash_map_iterator_base<HashMap>
486 {
487 public:
488  typedef HashMap hash_map_type;
491  typedef typename hash_map_type::value_type value_type;
492  typedef typename hash_map_type::key_type key_type;
493  typedef typename hash_map_type::reference reference;
494  typedef typename hash_map_type::const_reference const_reference;
495  typedef typename hash_map_type::pointer pointer;
496  typedef typename hash_map_type::const_pointer const_pointer;
497  typedef typename hash_map_type::node_type node_type;
498  typedef typename hash_map_type::bucket_type bucket_type;
499  typedef typename hash_map_type::bid_iterator_type bid_iterator_type;
500  typedef typename hash_map_type::source_type source_type;
501 
502  typedef buffered_reader<typename hash_map_type::block_cache_type,
504 
505  typedef std::forward_iterator_tag iterator_category;
506 
509 
510 public:
512  node_type* node, external_size_type i_external,
513  source_type source, bool ext_valid, key_type key)
514  : base_type(map, i_bucket, node, i_external, source, ext_valid, key)
515  { }
516 
518  : base_type(NULL)
519  { }
520 
522  : base_type(map)
523  { }
524 
526  : base_type(obj)
527  { }
528 
530  : base_type(obj)
531  { }
532 
534  {
535  base_type::operator = (obj);
536  return *this;
537  }
538 
539  bool operator == (const hash_map_const_iterator& obj) const
540  {
541  return base_type::operator == (obj);
542  }
543 
544  bool operator == (const hash_map_iterator& obj) const
545  {
546  return base_type::operator == (obj);
547  }
548 
549  bool operator != (const hash_map_const_iterator& obj) const
550  {
551  return base_type::operator != (obj);
552  }
553 
554  bool operator != (const hash_map_iterator& obj) const
555  {
556  return base_type::operator != (obj);
557  }
558 
559  //! Return const-reference to current value
560  const_reference operator * ()
561  {
562  if (this->source_ == hash_map_type::src_internal)
563  {
564  return this->node_->value_;
565  }
566  else
567  {
568  if (this->reader_ == NULL)
569  base_type::init_reader();
570 
571  return this->reader_->const_value();
572  }
573  }
574 
575  //! Increment iterator
577  {
578  base_type::find_next(true);
579  return *this;
580  }
581 };
582 
583 } // namespace hash_map
584 
586 
587 #endif // !STXXL_CONTAINERS_HASH_MAP_ITERATOR_HEADER
hash_map_type::internal_size_type internal_size_type
Definition: iterator.h:489
hash_map_type::bid_iterator_type bid_iterator_type
Definition: iterator.h:396
bool ext_valid_
true if i_external points to the current or next external value
Definition: iterator.h:86
internal_size_type i_bucket_
index of current bucket
Definition: iterator.h:65
hash_map_const_iterator(hash_map_type *map, internal_size_type i_bucket, node_type *node, external_size_type i_external, source_type source, bool ext_valid, key_type key)
Definition: iterator.h:511
hash_map_type::key_type key_type
Definition: iterator.h:492
hash_map_const_iterator(const hash_map_const_iterator &obj)
Definition: iterator.h:529
hash_map_type::const_pointer const_pointer
Definition: iterator.h:393
bool prefetch_
true if prefetching enabled; false by default, will be set to true when incrementing (see find_next()...
Definition: iterator.h:63
hash_map_type::bucket_type bucket_type
Definition: iterator.h:50
hash_map_type::bid_iterator_type bid_iterator_type
Definition: iterator.h:51
hash_map_iterator_base(hash_map_type *map)
Construct a new iterator pointing to the end of the given hash-map.
Definition: iterator.h:111
void reset_reader()
Reset reader-object.
Definition: iterator.h:237
hash_map_iterator_base(const hash_map_iterator_base &obj)
Construct a new iterator from an existing one.
Definition: iterator.h:124
stxxl::hash_map::hash_map_iterator_base< hash_map_type > base_type
Definition: iterator.h:507
hash_map_type::source_type source_type
Definition: iterator.h:52
stxxl::hash_map::hash_map_const_iterator< hash_map_type > hash_map_const_iterator
Definition: iterator.h:405
void find_next(bool start_prefetching=false)
Advance iterator to the next value The next value is determined in the following way.
Definition: iterator.h:251
uint_pair & operator++()
prefix increment operator (directly manipulates the integer parts)
Definition: uint_types.h:163
buffered_reader< typename hash_map_type::block_cache_type, bid_iterator_type > reader_type
Definition: iterator.h:503
hash_map_type::key_type key_type
Definition: iterator.h:46
external_size_type i_external_
position of current (source=external) or next (source=internal) external value (see _ext_valid) ...
Definition: iterator.h:72
buffered_reader< typename hash_map_type::block_cache_type, bid_iterator_type > reader_type
Definition: iterator.h:400
hash_map_type::internal_size_type internal_size_type
Definition: iterator.h:43
hash_map_iterator(const hash_map_iterator &obj)
Definition: iterator.h:422
hash_map_type::const_reference const_reference
Definition: iterator.h:48
hash_map_type::const_reference const_reference
Definition: iterator.h:494
hash_map_iterator(hash_map_type *map)
Definition: iterator.h:418
hash_map_iterator_base(HashMap *map, internal_size_type i_bucket, node_type *node, external_size_type i_external, source_type source, bool ext_valid, key_type key)
Construct a new iterator.
Definition: iterator.h:92
hash_map_type::source_type source_type
Definition: iterator.h:397
hash_map_type::external_size_type external_size_type
Definition: iterator.h:44
bool operator!=(const uint_pair &b) const
inequality checking operator
Definition: uint_types.h:198
#define STXXL_VERBOSE3(x)
Definition: verbose.h:127
unsigned_type internal_size_type
Definition: types.h:66
stxxl::hash_map::hash_map_iterator_base< hash_map_type > base_type
Definition: iterator.h:404
hash_map_type::external_size_type external_size_type
Definition: iterator.h:490
internal_size_type i_block_
index of first block&#39;s bid (to be used as index for hash_map&#39;s bids_-array
Definition: util.h:72
#define STXXL_BEGIN_NAMESPACE
Definition: namespace.h:16
hash_map_type::value_type value_type
Definition: iterator.h:388
hash_map_type::external_size_type external_size_type
Definition: iterator.h:387
hash_map_type::pointer pointer
Definition: iterator.h:392
hash_map_type::reference reference
Definition: iterator.h:390
std::forward_iterator_tag iterator_category
Definition: iterator.h:505
hash_map_type::key_type key_type
Definition: iterator.h:389
hash_map_type::value_type value_type
Definition: iterator.h:45
std::forward_iterator_tag iterator_category
Definition: iterator.h:56
hash_map_type::bucket_type bucket_type
Definition: iterator.h:395
bool end_
true if iterator equals end()
Definition: iterator.h:88
hash_map_const_iterator(const hash_map_iterator &obj)
Definition: iterator.h:525
hash_map_type::const_pointer const_pointer
Definition: iterator.h:496
hash_map_type::bid_iterator_type bid_iterator_type
Definition: iterator.h:499
Cache of blocks contained in an external memory hash map. Uses the stxxl::lru_pager as eviction algor...
Definition: block_cache.h:118
uint64 external_size_type
Definition: types.h:67
hash_map_type::reference reference
Definition: iterator.h:493
Used to scan external memory with prefetching.
Definition: util.h:95
buffered_reader< typename hash_map_type::block_cache_type, bid_iterator_type > reader_type
Definition: iterator.h:54
hash_map_type::const_reference const_reference
Definition: iterator.h:391
stxxl::hash_map::hash_map_iterator< hash_map_type > hash_map_iterator
Definition: iterator.h:508
hash_map_type::node_type node_type
Definition: iterator.h:49
source_type source_
source of current value: external or internal
Definition: iterator.h:67
hash_map_type::reference reference
Definition: iterator.h:47
hash_map_type::value_type value_type
Definition: iterator.h:491
External associative container (map). Introduction to map container: see STXXL Map (B+-tree) tutor...
Definition: map.h:82
void init_reader()
Initialize reader object to scan external values.
Definition: iterator.h:194
hash_map_type::source_type source_type
Definition: iterator.h:500
node_type * node_
current (source=internal) or old (src=external) internal node
Definition: iterator.h:69
hash_map_type::node_type node_type
Definition: iterator.h:394
std::forward_iterator_tag iterator_category
Definition: iterator.h:402
hash_map_type::bucket_type bucket_type
Definition: iterator.h:498
hash_map_type::pointer pointer
Definition: iterator.h:495
key_type key_
key of current value
Definition: iterator.h:74
hash_map_type::node_type node_type
Definition: iterator.h:497
hash_map_type::internal_size_type internal_size_type
Definition: iterator.h:386
bool operator==(const uint_pair &b) const
equality checking operator
Definition: uint_types.h:192
hash_map_iterator(hash_map_type *map, internal_size_type i_bucket, node_type *node, external_size_type i_external, source_type source, bool ext_valid, key_type key)
Definition: iterator.h:408
#define STXXL_END_NAMESPACE
Definition: namespace.h:17
hash_map_const_iterator(hash_map_type *map)
Definition: iterator.h:521