iterator_map.h

Go to the documentation of this file.

/***************************************************************************
 * include/stxxl/bits/containers/hash_map/iterator_map.h
 *
 * Part of the STXXL. See http://stxxl.sourceforge.net
 *
 * Copyright (C) 2007 Markus Westphal <[email protected]>
 * Copyright (C) 2014 Timo Bingmann <[email protected]>
 *
 * Distributed under the Boost Software License, Version 1.0.
 * (See accompanying file LICENSE_1_0.txt or copy at
 * http://www.boost.org/LICENSE_1_0.txt)
 **************************************************************************/

#ifndef STXXL_CONTAINERS_HASH_MAP_ITERATOR_MAP_HEADER
#define STXXL_CONTAINERS_HASH_MAP_ITERATOR_MAP_HEADER

#include <map>

#include <stxxl/bits/noncopyable.h>
#include <stxxl/bits/compat/hash_map.h>
#include <stxxl/bits/containers/hash_map/iterator.h>

STXXL_BEGIN_NAMESPACE

namespace hash_map {

template <class HashMap>
class iterator_map : private noncopyable
{
public:
 typedef HashMap hash_map_type;
 typedef typename hash_map_type::node_type node_type;
 typedef typename hash_map_type::source_type source_type;
 typedef typename hash_map_type::key_type key_type;

 typedef typename hash_map_type::internal_size_type internal_size_type;
 typedef typename hash_map_type::external_size_type external_size_type;

 typedef hash_map_iterator_base<hash_map_type> iterator_base;

private:
#if 0
 typedef std::multimap<internal_size_type, iterator_base*> multimap_type;
#else
 struct hasher
 {
 size_t operator () (const internal_size_type& key) const
 {
 return longhash1(key);
 }
#if STXXL_MSVC
 bool operator () (const internal_size_type& a, const internal_size_type& b) const
 {
 return (a < b);
 }
 enum
 { // parameters for hash table
 bucket_size = 4, // 0 < bucket_size
 min_buckets = 8 // min_buckets = 2 ^^ N, 0 < N
 };
#endif
 };
 // store iterators by bucket-index
 typedef typename compat_hash_multimap<
 internal_size_type, iterator_base*, hasher
 >::result multimap_type;
#endif

 //! bucket-index and pointer to iterator_base
 typedef typename multimap_type::value_type pair_type;
 typedef typename multimap_type::iterator mmiterator_type;
 typedef typename multimap_type::const_iterator const_mmiterator_type;

 hash_map_type* map_;
 multimap_type it_map_;

public:
 iterator_map(hash_map_type* map)
 : map_(map)
 { }

 ~iterator_map()
 {
 it_map_.clear();
 }

 void register_iterator(iterator_base& it)
 {
 register_iterator(it, it.i_bucket_);
 }

 void register_iterator(iterator_base& it, internal_size_type i_bucket)
 {
 STXXL_VERBOSE2("hash_map::iterator_map register_iterator addr=" << &it << " bucket=" << i_bucket);
 it_map_.insert(pair_type(i_bucket, &it));
 }

 void unregister_iterator(iterator_base& it)
 {
 unregister_iterator(it, it.i_bucket_);
 }

 void unregister_iterator(iterator_base& it, internal_size_type i_bucket)
 {
 STXXL_VERBOSE2("hash_map::iterator_map unregister_iterator addr=" << &it << " bucket=" << i_bucket);

 std::pair<mmiterator_type, mmiterator_type> range
 = it_map_.equal_range(i_bucket);

 assert(range.first != range.second);

 for (mmiterator_type i = range.first; i != range.second; ++i)
 {
 if (i->second == &it)
 {
 it_map_.erase(i);
 return;
 }
 }

 throw std::runtime_error("unregister_iterator Panic in hash_map::iterator_map, can not find and unregister iterator");
 }

 //! Update iterators with given key and bucket and make them point to the
 //! specified location in external memory (will be called during
 //! re-hashing)
 void fix_iterators_2ext(internal_size_type i_bucket_old, const key_type& key,
 internal_size_type i_bucket_new, external_size_type i_ext)
 {
 STXXL_VERBOSE2("hash_map::iterator_map fix_iterators_2ext i_bucket=" << i_bucket_old << " new_i_ext=" << i_ext);

 std::vector<iterator_base*> its2fix;
 _find(i_bucket_old, its2fix);

 for (typename std::vector<iterator_base*>::iterator
 it2fix = its2fix.begin(); it2fix != its2fix.end(); ++it2fix)
 {
 if (!map_->_eq(key, (**it2fix).key_))
 continue;

 if (i_bucket_old != i_bucket_new)
 {
 unregister_iterator(**it2fix);
 register_iterator(**it2fix, i_bucket_new);
 }

 (**it2fix).i_bucket_ = i_bucket_new;
 (**it2fix).node_ = NULL;
 (**it2fix).i_external_ = i_ext;
 (**it2fix).source_ = hash_map_type::src_external;
 // external position is now known (i_ext) and therefore valid
 (**it2fix).ext_valid_ = true;
 (**it2fix).reset_reader();
 (**it2fix).reader_ = NULL;
 }
 }

 //! Update iterators with given key and bucket and make them point to the
 //! specified node in internal memory (will be called by insert_oblivious)
 void fix_iterators_2int(internal_size_type i_bucket, const key_type& key, node_type* node)
 {
 STXXL_VERBOSE2("hash_map::iterator_map fix_iterators_2int i_bucket=" << i_bucket << " node=" << node);

 std::vector<iterator_base*> its2fix;
 _find(i_bucket, its2fix);

 for (typename std::vector<iterator_base*>::iterator
 it2fix = its2fix.begin(); it2fix != its2fix.end(); ++it2fix)
 {
 if (!map_->_eq((**it2fix).key_, key))
 continue;

 assert((**it2fix).source_ == hash_map_type::src_external);

 (**it2fix).source_ = hash_map_type::src_internal;
 (**it2fix).node_ = node;
 (**it2fix).i_external_++;
 if ((** it2fix).reader_)
 (** it2fix).reader_->operator ++ ();
 }
 }

 //! Update iterators with given key and bucket and make them point to the
 //! end of the hash-map (called by erase and erase_oblivious)
 void fix_iterators_2end(internal_size_type i_bucket, const key_type& key)
 {
 STXXL_VERBOSE2("hash_map::iterator_map fix_iterators_2end i_bucket=" << i_bucket);

 std::vector<iterator_base*> its2fix;
 _find(i_bucket, its2fix);

 for (typename std::vector<iterator_base*>::iterator
 it2fix = its2fix.begin(); it2fix != its2fix.end(); ++it2fix)
 {
 if (!map_->_eq(key, (**it2fix).key_))
 continue;

 (**it2fix).end_ = true;
 (**it2fix).reset_reader();
 unregister_iterator(**it2fix);
 }
 }

 //! Update all iterators and make them point to the end of the hash-map
 //! (used by clear())
 void fix_iterators_all2end()
 {
 for (mmiterator_type it2fix = it_map_.begin();
 it2fix != it_map_.end(); ++it2fix)
 {
 (*it2fix).second->end_ = true;
 (*it2fix).second->reset_reader();
 }
 it_map_.clear();
 }

private:
 //! Find all iterators registered with given bucket and add them to outc
 template <class OutputContainer>
 void _find(internal_size_type i_bucket, OutputContainer& outc)
 {
 std::pair<mmiterator_type, mmiterator_type> range
 = it_map_.equal_range(i_bucket);

 for (mmiterator_type i = range.first; i != range.second; ++i)
 outc.push_back((*i).second);
 }

 // changes hash_map pointer in all contained iterators
 void change_hash_map_pointers(hash_map_type* map)
 {
 for (mmiterator_type it = it_map_.begin(); it != it_map_.end(); ++it)
 ((*it).second)->map_ = map;
 }

public:
 void swap(iterator_map<HashMap>& obj)
 {
 std::swap(it_map_, obj.it_map_);
 std::swap(map_, obj.map_);

 change_hash_map_pointers(map_);
 obj.change_hash_map_pointers(obj.map_);
 }

 void print_statistics(std::ostream& o = std::cout) const
 {
 o << "Registered iterators: " << it_map_.size() << "\n";

 for (const_mmiterator_type i = it_map_.begin(); i != it_map_.end(); ++i)
 {
 o << " Address=" << i->second
 << ", Bucket=" << i->second->i_bucket_
 << ", Node=" << i->second->node_
 << ", i_ext=" << i->second->i_external_
 << ", "
 << ((i->second->source_ == hash_map_type::src_external)
 ? "external" : "internal") << std::endl;
 }
 }
};

} // namespace hash_map

STXXL_END_NAMESPACE

namespace std {

template <class HashMapType>
void swap(stxxl::hash_map::iterator_map<HashMapType>& a,
 stxxl::hash_map::iterator_map<HashMapType>& b)
{
 if (&a != &b)
 a.swap(b);
}

} // namespace std

#endif // !STXXL_CONTAINERS_HASH_MAP_ITERATOR_MAP_HEADER