/usr/include/stxxl/bits/containers/hash_map
Edit: /usr/include/stxxl/bits/containers/hash_map/hash_map.h (58030B)
/***************************************************************************
* include/stxxl/bits/containers/hash_map/hash_map.h
*
* Part of the STXXL. See http://stxxl.sourceforge.net
*
* Copyright (C) 2007 Markus Westphal
* Copyright (C) 2014 Timo Bingmann
*
* 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_HASH_MAP_HEADER
#define STXXL_CONTAINERS_HASH_MAP_HASH_MAP_HEADER
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
STXXL_BEGIN_NAMESPACE
#define STXXL_VERBOSE_HASH_MAP(m) \
STXXL_VERBOSE1("hash_map[" << static_cast(this) << "]::" << m)
//! External memory hash-map
namespace hash_map {
/*!
* Main implementation of external memory hash map.
*
* \tparam KeyType the key type
* \tparam MappedType the mapped type associated with a key
* \tparam HashType a hash functional
* \tparam CompareType a less comparison relation for KeyType
* \tparam SubBlockSize the raw size of a subblock (caching granularity)
* (default: 8192)
* \tparam SubBlocksPerBlock the number of subblocks per external block
* (default: 256 -> 2MB blocks)
* \tparam AllocType allocator for internal-memory buffer
*/
template >
>
class hash_map : private noncopyable
{
protected:
typedef hash_map self_type;
public:
//! type of the keys being used
typedef KeyType key_type;
//! type of the data to be stored
typedef MappedType mapped_type;
//! actually store (key-data)-pairs
typedef std::pair value_type;
//! type for value-references
typedef value_type& reference;
//! type for constant value-references
typedef const value_type& const_reference;
//! pointer to type of keys
typedef value_type* pointer;
//! const pointer to type of keys
typedef value_type const* const_pointer;
typedef stxxl::external_size_type external_size_type;
typedef stxxl::internal_size_type internal_size_type;
typedef stxxl::int64 difference_type;
//! type of (mother) hash-function
typedef HashType hasher;
//! functor that imposes a ordering on keys (but see _lt())
typedef KeyCompareType key_compare;
//! allocator template type
typedef AllocatorType allocator_type;
typedef hash_map_iterator iterator;
typedef hash_map_const_iterator const_iterator;
//! subblock- and block-size in bytes
enum {
block_raw_size = SubBlocksPerBlock * SubBlockSize,
subblock_raw_size = SubBlockSize
};
//! Subblock-size as number of elements, block-size as number of subblocks
enum {
subblocks_per_block = SubBlocksPerBlock,
subblock_size = SubBlockSize / sizeof(value_type)
};
//! a subblock consists of subblock_size values
typedef typed_block subblock_type;
//! a block consists of block_size subblocks
typedef typed_block block_type;
//! block-identifier for subblocks
typedef typename subblock_type::bid_type subblock_bid_type;
//! block-identifier for blocks
typedef typename block_type::bid_type bid_type;
//! container for block-bids
typedef std::vector bid_container_type;
//! iterator for block-bids
typedef typename bid_container_type::iterator bid_iterator_type;
enum source_type { src_internal, src_external, src_unknown };
//! nodes for internal-memory buffer
typedef node node_type;
//! buckets
typedef bucket bucket_type;
typedef std::vector buckets_container_type;
//! for tracking active iterators
typedef iterator_map iterator_map_type;
typedef block_cache block_cache_type;
typedef buffered_reader reader_type;
typedef typename allocator_type::template rebind::other node_allocator_type;
protected:
//! user supplied mother hash-function
hasher hash_;
//! user supplied strict-weak-ordering for keys
key_compare cmp_;
//! array of bucket
buckets_container_type buckets_;
//! blocks-ids of allocated blocks
bid_container_type bids_;
//! size of internal-memory buffer in number of entries
internal_size_type buffer_size_;
//! maximum size for internal-memory buffer
internal_size_type max_buffer_size_;
//! keeps track of all active iterators
iterator_map_type iterator_map_;
mutable block_cache_type block_cache_;
//! used to allocate new nodes for internal buffer
node_allocator_type node_allocator_;
//! false if the total-number of values is correct (false) or true if
//! estimated (true); see *oblivious_-methods
mutable bool oblivious_;
//! (estimated) number of values
mutable external_size_type num_total_;
//! desired load factor after rehashing
float opt_load_factor_;
public:
/*!
* Construct a new hash-map
* \param n initial number of buckets
* \param hf hash-function
* \param cmp comparator-object
* \param buffer_size size of internal-memory buffer in bytes
* \param a allocation-strategory for internal-memory buffer
*/
hash_map(internal_size_type n = 0,
const hasher& hf = hasher(),
const key_compare& cmp = key_compare(),
internal_size_type buffer_size = 128*1024*1024,
const allocator_type& a = allocator_type())
: hash_(hf),
cmp_(cmp),
buckets_(n),
bids_(0),
buffer_size_(0),
iterator_map_(this),
block_cache_(tuning::get_instance()->blockcache_size),
node_allocator_(a),
oblivious_(false),
num_total_(0),
opt_load_factor_(0.875)
{
max_buffer_size_ = buffer_size / sizeof(node_type);
}
/*!
* Construct a new hash-map and insert all values in the range [f,l)
*
* \param begin beginning of the range
* \param end end of the range
* \param mem_to_sort internal memory that may be used for bulk-construction (not
* to be confused with the buffer-memory)
* \param n initial number of buckets
* \param hf hash-function
* \param cmp comparator-object
* \param buffer_size size of internal-memory buffer in bytes
* \param a allocation-strategory for internal-memory buffer
*/
template
hash_map(InputIterator begin, InputIterator end,
internal_size_type mem_to_sort = 256*1024*1024,
internal_size_type n = 0,
const hasher& hf = hasher(),
const key_compare& cmp = key_compare(),
internal_size_type buffer_size = 128*1024*1024,
const allocator_type& a = allocator_type())
: hash_(hf),
cmp_(cmp),
buckets_(n), // insert will determine a good size
bids_(0),
buffer_size_(0),
iterator_map_(this),
block_cache_(tuning::get_instance()->blockcache_size),
node_allocator_(a),
oblivious_(false),
num_total_(0),
opt_load_factor_(0.875)
{
max_buffer_size_ = buffer_size / sizeof(node_type);
insert(begin, end, mem_to_sort);
}
~hash_map()
{
clear();
}
public:
//! Hash-function used by this hash-map
hasher hash_function() const
{ return hash_; }
//! Strict-weak-ordering used by this hash-map
key_compare key_cmp() const
{ return cmp_; }
//! Get node memory allocator
allocator_type get_allocator() const
{ return node_allocator_; }
protected:
/*!
* After using *oblivious_-methods only an estimate for the total number of
* elements can be given. This method accesses external memory to
* calculate the exact number.
*/
void _make_conscious()
{ /* const */ //! TODO: make const again
if (!oblivious_)
return;
typedef HashedValuesStream values_stream_type;
// this will start prefetching automatically
reader_type reader(bids_.begin(), bids_.end(), block_cache_);
values_stream_type values(buckets_.begin(), buckets_.end(),
reader, bids_.begin(), *this);
num_total_ = 0;
while (!values.empty())
{
++num_total_;
++values;
}
oblivious_ = false;
}
public:
//! Number of values currently stored. Note: If the correct number is
//! currently unknown (because *_oblivous-methods were used), external
//! memory will be scanned.
external_size_type size() const
{
if (oblivious_)
((self_type*)this)->_make_conscious();
return num_total_;
}
//! The hash-map may store up to this number of values
external_size_type max_size() const
{
return std::numeric_limits::max();
}
//! Check if container is empty.
bool empty() const
{
return size() != 0;
}
/*!
* Insert a new value if no value with the same key is already present;
* external memory must therefore be accessed
*
* \param value what to insert
* \return a tuple whose second part is true iff the value was actually
* added (no value with the same key present); the first part is an
* iterator pointing to the newly inserted or already stored value
*/
std::pair insert(const value_type& value)
{
if (buckets_.size() == 0)
_rebuild_buckets(128);
internal_size_type i_bucket = _bkt_num(value.first);
bucket_type& bucket = buckets_[i_bucket];
node_type* node = _find_key_internal(bucket, value.first);
// found value in internal memory
if (node && _eq(node->value_.first, value.first))
{
bool old_deleted = node->deleted();
if (old_deleted)
{
node->set_deleted(false);
node->value_ = value;
++num_total_;
}
return std::pair(
iterator(this, i_bucket, node,
0, src_internal, false, value.first), old_deleted);
}
// search external memory ...
else
{
tuple result
= _find_key_external(bucket, value.first);
external_size_type i_external = result.first;
value_type ext_value = result.second;
// ... if found, return iterator pointing to external position ...
if (i_external < bucket.n_external_ && _eq(ext_value.first, value.first))
{
return std::pair(
iterator(this, i_bucket, node,
i_external, src_external, true, value.first), false);
}
// ... otherwise create a new buffer-node to add the value
else
{
++num_total_;
node_type* new_node =
node
? node->set_next(_new_node(value, node->next(), false))
: (bucket.list_ = _new_node(value, bucket.list_, false));
iterator it(this, i_bucket, new_node,
0, src_internal, false, value.first);
++buffer_size_;
if (buffer_size_ >= max_buffer_size_)
_rebuild_buckets(); // will fix it as well
return std::pair(it, true);
}
}
}
//! Insert a value; external memory is not accessed so that another value
//! with the same key may be overwritten
//! \param value what to insert
//! \return iterator pointing to the inserted value
iterator insert_oblivious(const value_type& value)
{
internal_size_type i_bucket = _bkt_num(value.first);
bucket_type& bucket = buckets_[i_bucket];
node_type* node = _find_key_internal(bucket, value.first);
// found value in internal memory
if (node && _eq(node->value_.first, value.first))
{
if (node->deleted())
++num_total_;
node->set_deleted(false);
node->value_ = value;
return iterator(this, i_bucket, node,
0, src_internal, false, value.first);
}
// not found; ignore external memory and add a new node to the
// internal-memory buffer
else
{
oblivious_ = true;
++num_total_;
node_type* new_node =
node
? node->set_next(_new_node(value, node->next(), false))
: (bucket.list_ = _new_node(value, bucket.list_, false));
// there may be some iterators that reference the newly inserted
// value in external memory these need to be fixed (make them point
// to new_node)
iterator_map_.fix_iterators_2int(i_bucket, value.first, new_node);
iterator it(this, i_bucket, new_node,
0, src_internal, false, value.first);
++buffer_size_;
if (buffer_size_ >= max_buffer_size_)
_rebuild_buckets();
return it;
}
}
//! Erase value by iterator
//! \param it iterator pointing to the value to erase
void erase(const_iterator it)
{
--num_total_;
bucket_type& bucket = buckets_[it.i_bucket_];
if (it.source_ == src_internal)
{
it.node_->set_deleted(true);
iterator_map_.fix_iterators_2end(it.i_bucket_, it.key_);
}
else {
// find biggest value < iterator's value
node_type* node = _find_key_internal(bucket, it.key_);
assert(!node || !_eq(node->value_.first, it.key_));
// add delete-node to buffer
if (node)
node->set_next(_new_node(value_type(it.key_, mapped_type()), node->next(), true));
else
bucket.list_ = _new_node(value_type(it.key_, mapped_type()), bucket.list_, true);
iterator_map_.fix_iterators_2end(it.i_bucket_, it.key_);
++buffer_size_;
if (buffer_size_ >= max_buffer_size_)
_rebuild_buckets();
}
}
//! Erase value by key; check external memory
//! \param key key of value to erase
//! \return number of values actually erased (0 or 1)
external_size_type erase(const key_type& key)
{
internal_size_type i_bucket = _bkt_num(key);
bucket_type& bucket = buckets_[i_bucket];
node_type* node = _find_key_internal(bucket, key);
// found in internal memory
if (node && _eq(node->value_.first, key))
{
if (!node->deleted())
{
node->set_deleted(true);
--num_total_;
iterator_map_.fix_iterators_2end(i_bucket, key);
return 1;
}
else
return 0; // already deleted
}
// check external memory
else
{
tuple result
= _find_key_external(bucket, key);
external_size_type i_external = result.first;
value_type ext_value = result.second;
// found in external memory; add delete-node
if (i_external < bucket.n_external_ && _eq(ext_value.first, key))
{
--num_total_;
if (node)
node->set_next(_new_node(value_type(key, mapped_type()), node->next(), true));
else
bucket.list_ = _new_node(value_type(key, mapped_type()), bucket.list_, true);
iterator_map_.fix_iterators_2end(i_bucket, key);
++buffer_size_;
if (buffer_size_ >= max_buffer_size_)
_rebuild_buckets();
return 1;
}
// no value with given key
else
return 0;
}
}
//! Erase value by key but without looking at external memory
//! \param key key for value to release
void erase_oblivious(const key_type& key)
{
internal_size_type i_bucket = _bkt_num(key);
bucket_type& bucket = buckets_[i_bucket];
node_type* node = _find_key_internal(bucket, key);
// found value in internal-memory
if (node && _eq(node->value_.first, key))
{
if (!node->deleted())
{
--num_total_;
node->set_deleted(true);
iterator_map_.fix_iterators_2end(i_bucket, key);
}
}
// not found; ignore external memory and add delete-node
else
{
oblivious_ = true;
--num_total_;
if (node)
node->set_next(_new_node(value_type(key, mapped_type()), node->next(), true));
else
bucket.list_ = _new_node(value_type(key, mapped_type()), bucket.list_, true);
iterator_map_.fix_iterators_2end(i_bucket, key);
++buffer_size_;
if (buffer_size_ >= max_buffer_size_)
_rebuild_buckets();
}
}
//! Reset hash-map: erase all values, invalidate all iterators
void clear()
{
STXXL_VERBOSE_HASH_MAP("clear()");
iterator_map_.fix_iterators_all2end();
block_cache_.flush();
block_cache_.clear();
// reset buckets and release buffer-memory
for (internal_size_type i_bucket = 0;
i_bucket < buckets_.size(); i_bucket++)
{
_erase_nodes(buckets_[i_bucket].list_, NULL);
buckets_[i_bucket] = bucket_type();
}
oblivious_ = false;
num_total_ = 0;
buffer_size_ = 0;
// free external memory
block_manager* bm = block_manager::get_instance();
bm->delete_blocks(bids_.begin(), bids_.end());
bids_.clear();
}
//! Exchange stored values with another hash-map
//! \param obj hash-map to swap values with
void swap(self_type& obj)
{
std::swap(buckets_, obj.buckets_);
std::swap(bids_, obj.bids_);
std::swap(oblivious_, obj.oblivious_);
std::swap(num_total_, obj.num_total_);
std::swap(node_allocator_, obj.node_allocator_);
std::swap(hash_, obj.hash_);
std::swap(cmp_, obj.cmp_);
std::swap(buffer_size_, obj.buffer_size_);
std::swap(max_buffer_size_, obj.max_buffer_size_);
std::swap(opt_load_factor_, obj.opt_load_factor_);
std::swap(iterator_map_, obj.iterator_map_);
std::swap(block_cache_, obj.block_cache_);
}
protected:
// find statistics
mutable external_size_type n_subblocks_loaded;
mutable external_size_type n_found_internal;
mutable external_size_type n_found_external;
mutable external_size_type n_not_found;
public:
//! Reset hash-map statistics
void reset_statistics()
{
block_cache_.reset_statistics();
n_subblocks_loaded = n_found_external = n_found_internal = n_not_found = 0;
}
//! Print short general statistics to output stream
void print_statistics(std::ostream& o = std::cout) const
{
o << "Find-statistics:" << std::endl;
o << " Found internal : " << n_found_internal << std::endl;
o << " Found external : " << n_found_external << std::endl;
o << " Not found : " << n_not_found << std::endl;
o << " Subblocks searched : " << n_subblocks_loaded << std::endl;
iterator_map_.print_statistics(o);
block_cache_.print_statistics(o);
}
//! Look up value by key. Non-const access.
//! \param key key for value to look up
iterator find(const key_type& key)
{
if (buffer_size_ + 1 >= max_buffer_size_) // (*)
_rebuild_buckets();
internal_size_type i_bucket = _bkt_num(key);
bucket_type& bucket = buckets_[i_bucket];
node_type* node = _find_key_internal(bucket, key);
// found in internal-memory buffer
if (node && _eq(node->value_.first, key)) {
n_found_internal++;
if (node->deleted())
return this->_end();
else
return iterator(this, i_bucket, node, 0, src_internal, false, key);
}
// search external elements
else {
tuple result
= _find_key_external(bucket, key);
external_size_type i_external = result.first;
value_type value = result.second;
// found in external memory
if (i_external < bucket.n_external_ && _eq(value.first, key)) {
n_found_external++;
// we ultimately expect the user to de-reference the returned
// iterator to change its value (non-const!). to prevent an
// additional disk-access, we create a new node in the
// internal-memory buffer overwriting the external value.
// note: by checking and rebuilding (if neccessary) in (*) we
// made sure that the new node will fit into the buffer and no
// rebuild is neccessary here.
node_type* new_node =
node
? node->set_next(_new_node(value, node->next(), false))
: (bucket.list_ = _new_node(value, bucket.list_, false));
++buffer_size_;
iterator_map_.fix_iterators_2int(i_bucket, value.first, new_node);
return iterator(this, i_bucket, new_node, i_external + 1, src_internal, true, key);
}
// not found in external memory
else {
n_not_found++;
return this->_end();
}
}
}
//! Look up value by key. Const access.
//! \param key key for value to look up
const_iterator find(const key_type& key) const
{
internal_size_type i_bucket = _bkt_num(key);
const bucket_type& bucket = buckets_[i_bucket];
node_type* node = _find_key_internal(bucket, key);
// found in internal-memory buffer
if (node && _eq(node->value_.first, key)) {
n_found_internal++;
if (node->deleted())
return this->_end();
else
return const_iterator((self_type*)this, i_bucket, node, 0, src_internal, false, key);
}
// search external elements
else {
tuple result
= _find_key_external(bucket, key);
external_size_type i_external = result.first;
value_type value = result.second;
// found in external memory
if (i_external < bucket.n_external_ && _eq(value.first, key)) {
n_found_external++;
return const_iterator((self_type*)this, i_bucket, node, i_external, src_external, true, key);
}
// not found in external memory
else {
n_not_found++;
return this->_end();
}
}
}
//! Number of values with given key
//! \param k key for value to look up
//! \return 0 or 1 depending on the presence of a value with the given key
external_size_type count(const key_type& k) const
{
const_iterator cit = find(k);
return (cit == end()) ? 0 : 1;
}
//! Finds a range containing all values with given key. Non-const access
//! \param key key to look for#
//! \return range may be empty or contains exactly one value
std::pair equal_range(const key_type& key)
{
iterator it = find(key);
return std::pair(it, it);
}
//! Finds a range containing all values with given key. Const access
//! \param key key to look for#
//! \return range may be empty or contains exactly one value
std::pair equal_range(const key_type& key) const
{
const_iterator cit = find(key);
return std::pair(cit, cit);
}
//! Convenience operator to quickly insert or find values. Use with caution
//! since using this operator will check external-memory.
mapped_type& operator [] (const key_type& key)
{
if (buffer_size_ + 1 >= max_buffer_size_) // (*)
_rebuild_buckets();
internal_size_type i_bucket = _bkt_num(key);
bucket_type& bucket = buckets_[i_bucket];
node_type* node = _find_key_internal(bucket, key);
// found in internal-memory buffer
if (node && _eq(node->value_.first, key)) {
if (node->deleted()) {
node->set_deleted(false);
node->value_.second = mapped_type();
++num_total_;
}
return node->value_.second;
}
// search external elements
else {
tuple result
= _find_key_external(bucket, key);
external_size_type i_external = result.first;
value_type found_value = result.second;
value_type buffer_value =
(i_external < bucket.n_external_ && _eq(found_value.first, key))
? found_value
: value_type(key, mapped_type());
// add a new node to the buffer. this new node's value overwrites
// the external value if it was found and otherwise is set to (key,
// mapped_type())
node_type* new_node =
node
? node->set_next(_new_node(buffer_value, node->next(), false))
: (bucket.list_ = _new_node(buffer_value, bucket.list_, false));
++buffer_size_;
// note that we already checked the buffer-size in (*)
return new_node->value_.second;
}
}
//! Number of buckets
internal_size_type bucket_count() const
{ return buckets_.size(); }
//! Maximum number of buckets
internal_size_type max_bucket_count() const
{ return (internal_size_type)(max_size() / subblock_size); }
//! Bucket-index for values with given key.
internal_size_type bucket_index(const key_type& k) const
{ return _bkt_num(k); }
public:
//! Average number of (sub)blocks occupied by a bucket.
float load_factor() const
{ return (float)num_total_ / ((float)subblock_size * (float)buckets_.size()); }
//! Get desired load-factor
float opt_load_factor() const { return opt_load_factor_; }
//! Set desired load-factor
void opt_load_factor(float z)
{
opt_load_factor_ = z;
if (load_factor() > opt_load_factor_)
_rebuild_buckets();
}
//! Rehash with (at least) n buckets
void rehash(internal_size_type n = 0)
{
_rebuild_buckets(n);
}
//! Number of bytes occupied by buffer
internal_size_type buffer_size() const
{
// buffer-size internally stored as number of nodes
return buffer_size_ * sizeof(node_type);
}
//! Maximum buffer size in byte
internal_size_type max_buffer_size() const
{
return max_buffer_size_ * sizeof(node_type);
}
//! Set maximum buffer size
//! \param buffer_size new size in byte
void max_buffer_size(internal_size_type buffer_size)
{
max_buffer_size_ = buffer_size / sizeof(node_type);
if (buffer_size_ >= max_buffer_size_)
_rebuild_buckets();
}
protected:
//! iterator pointing to the beginnning of the hash-map
template
Iterator _begin() const
{
self_type* non_const_this = (self_type*)this;
if (buckets_.size() == 0)
return _end();
// correct key will be set by find_next()
Iterator it(non_const_this, 0, buckets_[0].list_,
0, src_unknown, true, key_type());
it.find_next();
return it;
}
//! iterator pointing to the end of the hash-map (iterator-type as
//! template-parameter)
template
Iterator _end() const
{
self_type* non_const_this = (self_type*)this;
return Iterator(non_const_this);
}
public:
//! Returns an iterator pointing to the beginning of the hash-map
iterator begin() { return _begin(); }
//! Returns a const_interator pointing to the beginning of the hash-map
const_iterator begin() const { return _begin(); }
//! Returns an iterator pointing to the end of the hash-map
iterator end() { return _end(); }
//! Returns a const_iterator pointing to the end of the hash-map
const_iterator end() const { return _end(); }
protected:
//! Allocate a new buffer-node
node_type * _get_node()
{
return node_allocator_.allocate(1);
}
//! Free given node
void _put_node(node_type* node)
{
node_allocator_.deallocate(node, 1);
}
//! Allocate a new buffer-node and initialize with given value, node and
//! deleted-flag
node_type * _new_node(const value_type& value, node_type* nxt, bool del)
{
node_type* node = _get_node();
node->value_ = value;
node->set_next(nxt);
node->set_deleted(del);
return node;
}
//! Free nodes in range [first, last). If last is NULL all nodes will be
//! freed.
void _erase_nodes(node_type* first, node_type* last)
{
node_type* curr = first;
while (curr != last)
{
node_type* next = curr->next();
_put_node(curr);
curr = next;
}
}
//! Bucket-index for values with given key
internal_size_type _bkt_num(const key_type& key) const
{
return _bkt_num(key, buckets_.size());
}
/*!
* Bucket-index for values with given key. The total number of buckets has
* to be specified as well. The bucket number is determined by \f$
* bucket_num = (hash/max_hash)*n_buckets \f$ max_hash is in fact 2^63-1
* (internal_size_type=uint64 (or uint32)) but we rather divide by 2^64, so
* we can use plain integer arithmetic easily (there should be only a small
* difference): this way we must only calculate the upper 64 bits of the
* product hash*n_buckets and we're done. See
* http://www.cs.uaf.edu/~cs301/notes/Chapter5/node5.html
*/
internal_size_type _bkt_num(const key_type& key, internal_size_type n) const
{
//! TODO maybe specialize double arithmetic to integer. the old code
//! was faulty -tb.
return (internal_size_type)(
(double)n * ((double)hash_(key) / (double)std::numeric_limits::max())
);
}
/*!
* Locate the given key in the internal-memory chained list. If the key is
* not present, the node with the biggest key smaller than the given key is
* returned. Note that the returned value may be zero: either because the
* chained list is empty or because the given key is smaller than all other
* keys in the chained list.
*/
node_type*
_find_key_internal(const bucket_type& bucket, const key_type& key) const
{
node_type* old = NULL;
for (node_type* curr = bucket.list_;
curr && _leq(curr->value_.first, key);
curr = curr->next())
{
old = curr;
}
return old;
}
/*!
* Search for key in external part of bucket. Return value is (i_external,
* value), where i_ext = bucket._num_external if key could not be found.
*/
tuple
_find_key_external(const bucket_type& bucket, const key_type& key) const
{
subblock_type* subblock;
// number of subblocks occupied by bucket
internal_size_type n_subblocks = (internal_size_type)(
bucket.n_external_ / subblock_size
);
if (bucket.n_external_ % subblock_size != 0)
n_subblocks++;
for (internal_size_type i_subblock = 0;
i_subblock < n_subblocks; i_subblock++)
{
subblock = _load_subblock(bucket, i_subblock);
// number of values in i-th subblock
internal_size_type n_values =
(i_subblock + 1 < n_subblocks)
? (internal_size_type)subblock_size
: (internal_size_type)(
bucket.n_external_ - i_subblock * subblock_size
);
//! TODO: replace with bucket.n_external_ % subblock_size
// biggest key in current subblock still too small => next subblock
if (_lt((*subblock)[n_values - 1].first, key))
continue;
// binary search in current subblock
internal_size_type i_lower = 0, i_upper = n_values;
while (i_lower + 1 != i_upper)
{
internal_size_type i_middle = (i_lower + i_upper) / 2;
if (_leq((*subblock)[i_middle].first, key))
i_lower = i_middle;
else
i_upper = i_middle;
}
value_type value = (*subblock)[i_lower];
if (_eq(value.first, key))
return tuple
(i_subblock * subblock_size + i_lower, value);
else
return tuple
(bucket.n_external_, value_type());
}
return tuple
(bucket.n_external_, value_type());
}
/*!
* Load the given bucket's i-th subblock.
* Since a bucket may be spread over several blocks, we must
* 1. determine in which block the requested subblock is located
* 2. at which position within the obove-mentioned block the questioned subblock is located
*/
subblock_type*
_load_subblock(const bucket_type& bucket, internal_size_type which_subblock) const
{
n_subblocks_loaded++;
// index of the requested subblock counted from the very beginning of
// the bucket's first block
external_size_type i_abs_subblock = bucket.i_subblock_ + which_subblock;
/* 1. */
bid_type bid = bids_[bucket.i_block_ + (internal_size_type)(i_abs_subblock / subblocks_per_block)];
/* 2. */
internal_size_type i_subblock_within = (internal_size_type)(i_abs_subblock % subblocks_per_block);
return block_cache_.get_subblock(bid, i_subblock_within);
}
typedef HashedValue hashed_value_type;
//! Functor to extracts the actual value from a HashedValue-struct
struct HashedValueExtractor
{
value_type& operator () (hashed_value_type& hvalue)
{ return hvalue.value_; }
};
/*!
* Will return from its input-stream all values that are to be stored in
* the given bucket. Those values must appear in consecutive order
* beginning with the input-stream's current value.
*/
template
struct HashingStream
{
typedef typename InputStream::value_type value_type;
self_type* map_;
InputStream& input_;
internal_size_type i_bucket_;
external_size_type bucket_size_;
value_type value_;
bool empty_;
ValueExtractor vextract_;
HashingStream(InputStream& input, internal_size_type i_bucket,
ValueExtractor vextract, self_type* map)
: map_(map),
input_(input),
i_bucket_(i_bucket),
bucket_size_(0),
vextract_(vextract)
{
empty_ = find_next();
}
const value_type& operator * () { return value_; }
bool empty() const { return empty_; }
void operator ++ ()
{
++input_;
empty_ = find_next();
}
bool find_next()
{
if (input_.empty())
return true;
value_ = *input_;
if (map_->_bkt_num(vextract_(value_).first) != i_bucket_)
return true;
++bucket_size_;
return false;
}
};
/* Rebuild hash-map. The desired number of buckets may be supplied. */
void _rebuild_buckets(internal_size_type n_desired = 0)
{
STXXL_VERBOSE_HASH_MAP("_rebuild_buckets()");
typedef buffered_writer writer_type;
typedef HashedValuesStream values_stream_type;
typedef HashingStream hashing_stream_type;
const int_type write_buffer_size = config::get_instance()->disks_number() * 4;
// determine new number of buckets from desired load_factor ...
internal_size_type n_new;
n_new = (internal_size_type)ceil((double)num_total_ / ((double)subblock_size * (double)opt_load_factor()));
// ... but give the user the chance to request even more buckets
if (n_desired > n_new)
n_new = std::min(n_desired, max_bucket_count());
// allocate new buckets and bids
buckets_container_type old_buckets(n_new);
std::swap(buckets_, old_buckets);
bid_container_type old_bids;
std::swap(bids_, old_bids);
// read stored values in consecutive order
// use new to control point of destruction (see below)
reader_type* reader
= new reader_type(old_bids.begin(), old_bids.end(), block_cache_);
values_stream_type values_stream(old_buckets.begin(), old_buckets.end(),
*reader, old_bids.begin(), *this);
writer_type writer(&bids_, write_buffer_size, write_buffer_size / 2);
// re-distribute values among new buckets.
// this makes use of the fact that if value1 preceeds value2 before
// resizing, value1 will preceed value2 after resizing as well (uniform
// rehashing)
num_total_ = 0;
for (internal_size_type i_bucket = 0;
i_bucket < buckets_.size(); i_bucket++)
{
buckets_[i_bucket] = bucket_type();
buckets_[i_bucket].i_block_ = writer.i_block();
buckets_[i_bucket].i_subblock_ = writer.i_subblock();
hashing_stream_type hasher(values_stream, i_bucket, HashedValueExtractor(), this);
external_size_type i_ext = 0;
while (!hasher.empty())
{
const hashed_value_type& hvalue = *hasher;
iterator_map_.fix_iterators_2ext(hvalue.i_bucket_, hvalue.value_.first, i_bucket, i_ext);
writer.append(hvalue.value_);
++hasher;
++i_ext;
}
writer.finish_subblock();
buckets_[i_bucket].n_external_ = hasher.bucket_size_;
num_total_ += hasher.bucket_size_;
}
writer.flush();
// reader must be deleted before deleting old_bids because its
// destructor will dereference the bid-iterator
delete reader;
block_cache_.clear();
// get rid of old blocks and buckets
block_manager* bm = stxxl::block_manager::get_instance();
bm->delete_blocks(old_bids.begin(), old_bids.end());
for (internal_size_type i_bucket = 0;
i_bucket < old_buckets.size(); i_bucket++)
{
_erase_nodes(old_buckets[i_bucket].list_, NULL);
old_buckets[i_bucket] = bucket_type();
}
buffer_size_ = 0;
oblivious_ = false;
}
/*!
* Stream for filtering duplicates. Used to eliminate duplicated values
* when bulk-inserting Note: input has to be sorted, so that duplicates
* will occure in row
*/
template
struct UniqueValueStream
{
typedef typename InputStream::value_type value_type;
self_type& map_;
InputStream& in_;
UniqueValueStream(InputStream& input, self_type& map)
: map_(map), in_(input)
{ }
bool empty() const { return in_.empty(); }
const value_type& operator * () { return *in_; }
void operator ++ ()
{
value_type v_old = *in_;
++in_;
while (!in_.empty() && v_old.first == (*in_).first)
++in_;
}
};
template
struct AddHashStream
{
//! (hash,value)
typedef std::pair value_type;
self_type& map_;
InputStream& in_;
AddHashStream(InputStream& input, self_type& map)
: map_(map), in_(input)
{ }
bool empty() const { return in_.empty(); }
value_type operator * ()
{ return value_type(map_.hash_((*in_).first), *in_); }
void operator ++ () { ++in_; }
};
/*!
* Extracts the value-part (ignoring the hashvalue); required by
* HashingStream (see above)
*/
struct StripHashFunctor
{
const value_type& operator () (std::pair& v)
{ return v.second; }
};
/*!
* Comparator object for values as required by stxxl::sort. Sorting is done
* lexicographically by Note: the hash-value has already
* been computed.
*/
struct Cmp : public std::binary_function<
std::pair,
std::pair, bool
>
{
self_type& map_;
Cmp(self_type& map) : map_(map) { }
bool operator () (const std::pair& a,
const std::pair& b) const
{
return (a.first < b.first) ||
((a.first == b.first) && map_.cmp_(a.second.first, b.second.first));
}
std::pair min_value() const
{
return std::pair(
std::numeric_limits::min(),
value_type(map_.cmp_.min_value(), mapped_type())
);
}
std::pair max_value() const
{
return std::pair(
std::numeric_limits::max(),
value_type(map_.cmp_.max_value(), mapped_type())
);
}
};
public:
//! Bulk-insert of values in the range [f, l)
//! \param f beginning of the range
//! \param l end of the range
//! \param mem internal memory that may be used (note: this memory will be used additionally to the buffer). The more the better
template
void insert(InputIterator f, InputIterator l, internal_size_type mem)
{
//! values already stored in the hashtable ("old values")
typedef HashedValuesStream old_values_stream;
//! old values, that are to be stored in a certain (new) bucket
typedef HashingStream old_hashing_stream;
//! values to insert ("new values")
typedef typename stxxl::stream::streamify_traits::stream_type input_stream;
//! new values with added hash: (hash, (key, mapped))
typedef AddHashStream new_values_stream;
//! new values sorted by
typedef stxxl::stream::sort new_sorted_values_stream;
//! new values sorted by with duplicates eliminated
typedef UniqueValueStream new_unique_values_stream;
//! new values, that are to be stored in a certain bucket
typedef HashingStream new_hashing_stream;
typedef buffered_writer writer_type;
int_type write_buffer_size = config::get_instance()->disks_number() * 2;
// calculate new number of buckets
external_size_type num_total_new = num_total_ + (l - f); // estimated number of elements
external_size_type n_buckets_new = (external_size_type)ceil((double)num_total_new / ((double)subblock_size * (double)opt_load_factor()));
if (n_buckets_new > max_bucket_count())
n_buckets_new = max_bucket_count();
STXXL_VERBOSE_HASH_MAP("insert() items=" << (l - f) << " buckets_new=" << n_buckets_new);
// prepare new buckets and bids
buckets_container_type old_buckets((internal_size_type)n_buckets_new);
std::swap(buckets_, old_buckets);
// writer will allocate new blocks as necessary
bid_container_type old_bids;
std::swap(bids_, old_bids);
// already stored values ("old values")
reader_type* reader = new reader_type(old_bids.begin(), old_bids.end(),
block_cache_);
old_values_stream old_values(old_buckets.begin(), old_buckets.end(),
*reader, old_bids.begin(), *this);
// values to insert ("new values")
input_stream input = stxxl::stream::streamify(f, l);
new_values_stream new_values(input, *this);
new_sorted_values_stream new_sorted_values(new_values, Cmp(*this), mem);
new_unique_values_stream new_unique_values(new_sorted_values, *this);
writer_type writer(&bids_, write_buffer_size, write_buffer_size / 2);
num_total_ = 0;
for (internal_size_type i_bucket = 0; i_bucket < buckets_.size(); i_bucket++)
{
buckets_[i_bucket] = bucket_type();
buckets_[i_bucket].i_block_ = writer.i_block();
buckets_[i_bucket].i_subblock_ = writer.i_subblock();
old_hashing_stream old_hasher(old_values, i_bucket, HashedValueExtractor(), this);
new_hashing_stream new_hasher(new_unique_values, i_bucket, StripHashFunctor(), this);
internal_size_type bucket_size = 0;
// more old and new values for the current bucket => choose smallest
while (!old_hasher.empty() && !new_hasher.empty())
{
internal_size_type old_hash = hash_((*old_hasher).value_.first);
internal_size_type new_hash = (*new_hasher).first;
key_type old_key = (*old_hasher).value_.first;
key_type new_key = (*new_hasher).second.first;
// old value wins
if ((old_hash < new_hash) || (old_hash == new_hash && cmp_(old_key, new_key))) // (_lt((*old_hasher)._value.first, (*new_hasher).second.first))
{
const hashed_value_type& hvalue = *old_hasher;
iterator_map_.fix_iterators_2ext(hvalue.i_bucket_, hvalue.value_.first, i_bucket, bucket_size);
writer.append(hvalue.value_);
++old_hasher;
}
// new value smaller or equal => new value wins
else
{
if (_eq(old_key, new_key))
{
const hashed_value_type& hvalue = *old_hasher;
iterator_map_.fix_iterators_2ext(hvalue.i_bucket_, hvalue.value_.first, i_bucket, bucket_size);
++old_hasher;
}
writer.append((*new_hasher).second);
++new_hasher;
}
++bucket_size;
}
// no more new values for the current bucket
while (!old_hasher.empty())
{
const hashed_value_type& hvalue = *old_hasher;
iterator_map_.fix_iterators_2ext(hvalue.i_bucket_, hvalue.value_.first, i_bucket, bucket_size);
writer.append(hvalue.value_);
++old_hasher;
++bucket_size;
}
// no more old values for the current bucket
while (!new_hasher.empty())
{
writer.append((*new_hasher).second);
++new_hasher;
++bucket_size;
}
writer.finish_subblock();
buckets_[i_bucket].n_external_ = bucket_size;
num_total_ += bucket_size;
}
writer.flush();
delete reader;
block_cache_.clear();
// release old blocks
block_manager* bm = stxxl::block_manager::get_instance();
bm->delete_blocks(old_bids.begin(), old_bids.end());
// free nodes in old bucket lists
for (internal_size_type i_bucket = 0;
i_bucket < old_buckets.size(); i_bucket++)
{
_erase_nodes(old_buckets[i_bucket].list_, NULL);
old_buckets[i_bucket] = bucket_type();
}
buffer_size_ = 0;
oblivious_ = false;
}
protected:
/* 1 iff a < b
The comparison is done lexicographically by (hash-value, key)
*/
bool _lt(const key_type& a, const key_type& b) const
{
internal_size_type hash_a = hash_(a);
internal_size_type hash_b = hash_(b);
return (hash_a < hash_b) ||
((hash_a == hash_b) && cmp_(a, b));
}
//! true iff a > b
bool _gt(const key_type& a, const key_type& b) const { return _lt(b, a); }
//! true iff a <= b
bool _leq(const key_type& a, const key_type& b) const { return !_gt(a, b); }
//! true iff a >= b
bool _geq(const key_type& a, const key_type& b) const { return !_lt(a, b); }
//! true iff a == b. note: it is mandatory that equal keys yield equal
//! hash-values => hashing not neccessary for equality-testing.
bool _eq(const key_type& a, const key_type& b) const
{ return !cmp_(a, b) && !cmp_(b, a); }
friend class hash_map_iterator_base;
friend class hash_map_iterator;
friend class hash_map_const_iterator;
friend class iterator_map;
friend class block_cache;
friend struct HashedValuesStream;
#if 1
void _dump_external()
{
reader_type reader(bids_.begin(), bids_.end(), &block_cache_);
for (internal_size_type i_block = 0; i_block < bids_.size(); i_block++) {
std::cout << "block " << i_block << ":\n";
for (internal_size_type i_subblock = 0; i_subblock < subblocks_per_block; i_subblock++) {
std::cout << " subblock " << i_subblock << ":\n ";
for (external_size_type i_element = 0; i_element < subblocks_per_block; i_element++) {
std::cout << reader.const_value().first << ", ";
++reader;
}
std::cout << std::endl;
}
}
}
void _dump_buckets()
{
reader_type reader(bids_.begin(), bids_.end(), &block_cache_);
std::cout << "number of buckets: " << buckets_.size() << std::endl;
for (internal_size_type i_bucket = 0; i_bucket < buckets_.size(); i_bucket++) {
const bucket_type& bucket = buckets_[i_bucket];
reader.skip_to(bids_.begin() + bucket.i_block_, bucket.i_subblock_);
std::cout << " bucket " << i_bucket << ": block=" << bucket.i_block_ << ", subblock=" << bucket.i_subblock_ << ", external=" << bucket.n_external_ << std::endl;
node_type* node = bucket.list_;
std::cout << " internal_list=";
while (node) {
std::cout << node->value_.first << " (del=" << node->deleted() << "), ";
node = node->next();
}
std::cout << std::endl;
std::cout << " external=";
for (external_size_type i_element = 0; i_element < bucket.n_external_; i_element++) {
std::cout << reader.const_value().first << ", ";
++reader;
}
std::cout << std::endl;
}
}
void _dump_bucket_statistics()
{
std::cout << "number of buckets: " << buckets_.size() << std::endl;
for (internal_size_type i_bucket = 0; i_bucket < buckets_.size(); i_bucket++) {
const bucket_type& bucket = buckets_[i_bucket];
std::cout << " bucket " << i_bucket << ": block=" << bucket.i_block_ << ", subblock=" << bucket.i_subblock_ << ", external=" << bucket.n_external_ << ", list=" << bucket.list_ << std::endl;
}
}
#endif
public:
//! Construct an equality predicate from the comparison operator
struct equal_to : public std::binary_function
{
//! reference to hash_map
const self_type& m_map;
//! constructor requires reference to hash_map
equal_to(const self_type& map) : m_map(map) { }
//! return whether the arguments compare equal (x==y).
bool operator () (const key_type& x, const key_type& y) const
{
return m_map._eq(x, y);
}
//! C++11 required type
typedef key_type first_argument_type;
//! C++11 required type
typedef key_type second_argument_type;
//! C++11 required type
typedef bool result_type;
};
//! Type of constructed equality predicate
typedef equal_to key_equal;
//! Constructed equality predicate used by this hash-map
key_equal key_eq() const
{
return equal_to(*this);
}
public:
//! Even more statistics: Number of buckets, number of values, buffer-size,
//! values per bucket
void print_load_statistics(std::ostream& o = std::cout) const
{
external_size_type sum_external = 0;
external_size_type square_sum_external = 0;
external_size_type max_external = 0;
for (internal_size_type i_bucket = 0; i_bucket < buckets_.size(); i_bucket++)
{
const bucket_type& b = buckets_[i_bucket];
sum_external += b.n_external_;
square_sum_external += b.n_external_ * b.n_external_;
if (b.n_external_ > max_external)
max_external = b.n_external_;
}
double avg_external = (double)sum_external / (double)buckets_.size();
double std_external = sqrt(((double)square_sum_external / (double)buckets_.size()) - (avg_external * avg_external));
o << "Bucket count : " << buckets_.size() << std::endl;
o << "Values total : " << num_total_ << std::endl;
o << "Values buffered : " << buffer_size_ << std::endl;
o << "Max Buffer-Size : " << max_buffer_size_ << std::endl;
o << "Max external/bucket : " << max_external << std::endl;
o << "Avg external/bucket : " << avg_external << std::endl;
o << "Std external/bucket : " << std_external << std::endl;
o << "Load-factor : " << load_factor() << std::endl;
o << "Blocks allocated : " << bids_.size() << " => " << (bids_.size() * block_type::raw_size) << " bytes" << std::endl;
o << "Bytes per value : " << ((double)(bids_.size() * block_type::raw_size) / (double)num_total_) << std::endl;
}
}; /* end of class hash_map */
} // namespace hash_map
STXXL_END_NAMESPACE
namespace std {
template
void swap(stxxl::hash_map::hash_map& a,
stxxl::hash_map::hash_map& b)
{
if (&a != &b)
a.swap(b);
}
} // namespace std
#endif // !STXXL_CONTAINERS_HASH_MAP_HASH_MAP_HEADER