14 #ifndef STXXL_CONTAINERS_HASH_MAP_ITERATOR_HEADER
15 #define STXXL_CONTAINERS_HASH_MAP_ITERATOR_HEADER
26 template <
class HashMap>
28 template <
class HashMap>
30 template <
class HashMap>
32 template <
class HashMap>
35 template <
class HashMap>
46 typedef typename hash_map_type::key_type
key_type;
47 typedef typename hash_map_type::reference
reference;
49 typedef typename hash_map_type::node_type
node_type;
101 i_external_(i_external),
103 ext_valid_(ext_valid),
106 STXXL_VERBOSE3(
"hash_map_iterator_base parameter construct addr=" <<
this);
107 map_->iterator_map_.register_iterator(*
this);
127 prefetch_(obj.prefetch_),
128 i_bucket_(obj.i_bucket_),
129 source_(obj.source_),
131 i_external_(obj.i_external_),
133 ext_valid_(obj.ext_valid_),
136 STXXL_VERBOSE3(
"hash_map_iterator_base constr from" << (&obj) <<
" to " <<
this);
139 map_->iterator_map_.register_iterator(*
this);
145 STXXL_VERBOSE3(
"hash_map_iterator_base copy from" << (&obj) <<
" to " <<
this);
150 map_->iterator_map_.unregister_iterator(*
this);
165 map_->iterator_map_.register_iterator(*
this);
173 if (end_ && obj.
end_)
176 if (map_ != obj.
map_ ||
181 if (source_ == hash_map_type::src_internal)
182 return node_ == obj.
node_;
201 reader_ =
new reader_type(begin, end, map_->block_cache_,
202 bucket.i_subblock_, prefetch_);
213 else if (node_ == NULL)
222 while (i_external_ < bucket.n_external_)
224 if (map_->_gt(reader_->const_value().first, node_->value_.first))
264 if (start_prefetching && !prefetch_)
266 reader_->enable_prefetching();
273 node_type* tmp_node = (node_) ? node_ : bucket.list_;
274 if (source_ == hash_map_type::src_external)
276 while (tmp_node && map_->_leq(tmp_node->value_.first, key_))
277 tmp_node = tmp_node->next();
282 else if (source_ == hash_map_type::src_internal)
283 tmp_node = node_->next();
289 while (tmp_node && i_external_ < bucket.n_external_)
292 if (map_->_leq(tmp_node->value_.first, reader_->const_value().first))
295 if (map_->_eq(node_->value_.first, reader_->const_value().first))
301 if (!node_->deleted())
303 key_ = node_->value_.first;
304 source_ = hash_map_type::src_internal;
309 tmp_node = tmp_node->next();
314 key_ = reader_->const_value().first;
315 source_ = hash_map_type::src_external;
320 if (i_external_ < bucket.n_external_)
322 key_ = reader_->const_value().first;
323 source_ = hash_map_type::src_external;
330 if (!node_->deleted())
332 key_ = node_->value_.first;
333 source_ = hash_map_type::src_internal;
337 tmp_node = tmp_node->next();
343 if (i_bucket_ == map_->buckets_.size())
351 bucket = map_->buckets_[i_bucket_];
353 tmp_node = bucket.list_;
355 reader_->skip_to(map_->bids_.begin() + bucket.i_block_, bucket.i_subblock_);
362 this->map_->iterator_map_.unregister_iterator(*
this, i_bucket_old);
364 else if (i_bucket_old != i_bucket_)
366 this->map_->iterator_map_.unregister_iterator(*
this, i_bucket_old);
367 this->map_->iterator_map_.register_iterator(*
this, i_bucket_);
376 map_->iterator_map_.unregister_iterator(*
this);
381 template <
class HashMap>
382 class hash_map_iterator :
public hash_map_iterator_base<HashMap>
392 typedef typename hash_map_type::pointer
pointer;
411 :
base_type(map, i_bucket, node, i_external, source, ext_valid, key)
428 base_type::operator = (obj);
456 if (this->source_ == hash_map_type::src_internal)
458 return this->node_->value_;
462 if (this->reader_ == NULL)
463 base_type::init_reader();
465 return this->reader_->value();
473 return &operator * ();
479 base_type::find_next(
true);
484 template <
class HashMap>
485 class hash_map_const_iterator :
public hash_map_iterator_base<HashMap>
495 typedef typename hash_map_type::pointer
pointer;
514 :
base_type(map, i_bucket, node, i_external, source, ext_valid, key)
535 base_type::operator = (obj);
562 if (this->source_ == hash_map_type::src_internal)
564 return this->node_->value_;
568 if (this->reader_ == NULL)
569 base_type::init_reader();
571 return this->reader_->const_value();
578 base_type::find_next(
true);
587 #endif // !STXXL_CONTAINERS_HASH_MAP_ITERATOR_HEADER
hash_map_type::internal_size_type internal_size_type
hash_map_type::bid_iterator_type bid_iterator_type
bool ext_valid_
true if i_external points to the current or next external value
internal_size_type i_bucket_
index of current bucket
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)
hash_map_type::key_type key_type
hash_map_const_iterator(const hash_map_const_iterator &obj)
hash_map_type::const_pointer const_pointer
bool prefetch_
true if prefetching enabled; false by default, will be set to true when incrementing (see find_next()...
hash_map_type::bucket_type bucket_type
hash_map_type::bid_iterator_type bid_iterator_type
hash_map_iterator_base(hash_map_type *map)
Construct a new iterator pointing to the end of the given hash-map.
void reset_reader()
Reset reader-object.
hash_map_iterator_base(const hash_map_iterator_base &obj)
Construct a new iterator from an existing one.
stxxl::hash_map::hash_map_iterator_base< hash_map_type > base_type
virtual ~hash_map_iterator_base()
hash_map_type::source_type source_type
stxxl::hash_map::hash_map_const_iterator< hash_map_type > hash_map_const_iterator
hash_map_const_iterator()
void find_next(bool start_prefetching=false)
Advance iterator to the next value The next value is determined in the following way.
uint_pair & operator++()
prefix increment operator (directly manipulates the integer parts)
buffered_reader< typename hash_map_type::block_cache_type, bid_iterator_type > reader_type
hash_map_type::key_type key_type
external_size_type i_external_
position of current (source=external) or next (source=internal) external value (see _ext_valid) ...
buffered_reader< typename hash_map_type::block_cache_type, bid_iterator_type > reader_type
hash_map_type::internal_size_type internal_size_type
hash_map_iterator(const hash_map_iterator &obj)
hash_map_type::const_reference const_reference
hash_map_type::const_reference const_reference
hash_map_iterator(hash_map_type *map)
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.
hash_map_type::source_type source_type
hash_map_type::external_size_type external_size_type
bool operator!=(const uint_pair &b) const
inequality checking operator
#define STXXL_VERBOSE3(x)
unsigned_type internal_size_type
stxxl::hash_map::hash_map_iterator_base< hash_map_type > base_type
hash_map_type::external_size_type external_size_type
internal_size_type i_block_
index of first block's bid (to be used as index for hash_map's bids_-array
#define STXXL_BEGIN_NAMESPACE
hash_map_type::value_type value_type
hash_map_type::external_size_type external_size_type
hash_map_type::pointer pointer
hash_map_type::reference reference
std::forward_iterator_tag iterator_category
hash_map_type::key_type key_type
hash_map_type::value_type value_type
std::forward_iterator_tag iterator_category
hash_map_type::bucket_type bucket_type
bool end_
true if iterator equals end()
hash_map_const_iterator(const hash_map_iterator &obj)
hash_map_type::const_pointer const_pointer
hash_map_type::bid_iterator_type bid_iterator_type
Cache of blocks contained in an external memory hash map. Uses the stxxl::lru_pager as eviction algor...
uint64 external_size_type
hash_map_type::reference reference
Used to scan external memory with prefetching.
buffered_reader< typename hash_map_type::block_cache_type, bid_iterator_type > reader_type
hash_map_type::const_reference const_reference
stxxl::hash_map::hash_map_iterator< hash_map_type > hash_map_iterator
hash_map_type::node_type node_type
source_type source_
source of current value: external or internal
hash_map_type::reference reference
hash_map_type::value_type value_type
External associative container (map). Introduction to map container: see STXXL Map (B+-tree) tutor...
void init_reader()
Initialize reader object to scan external values.
hash_map_type::source_type source_type
node_type * node_
current (source=internal) or old (src=external) internal node
hash_map_type::node_type node_type
std::forward_iterator_tag iterator_category
hash_map_type::bucket_type bucket_type
hash_map_type::pointer pointer
key_type key_
key of current value
hash_map_type::node_type node_type
hash_map_type::internal_size_type internal_size_type
bool operator==(const uint_pair &b) const
equality checking operator
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)
#define STXXL_END_NAMESPACE
hash_map_const_iterator(hash_map_type *map)