/usr/include/boost/asio/detail
Edit: /usr/include/boost/asio/detail/hash_map.hpp (8343B)
//
// detail/hash_map.hpp
// ~~~~~~~~~~~~~~~~~~~
//
// Copyright (c) 2003-2020 Christopher M. Kohlhoff (chris at kohlhoff dot com)
//
// 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 BOOST_ASIO_DETAIL_HASH_MAP_HPP
#define BOOST_ASIO_DETAIL_HASH_MAP_HPP
#if defined(_MSC_VER) && (_MSC_VER >= 1200)
# pragma once
#endif // defined(_MSC_VER) && (_MSC_VER >= 1200)
#include
#include
#include
#include
#include
#if defined(BOOST_ASIO_WINDOWS) || defined(__CYGWIN__)
# include
#endif // defined(BOOST_ASIO_WINDOWS) || defined(__CYGWIN__)
#include
namespace boost {
namespace asio {
namespace detail {
inline std::size_t calculate_hash_value(int i)
{
return static_cast(i);
}
inline std::size_t calculate_hash_value(void* p)
{
return reinterpret_cast(p)
+ (reinterpret_cast(p) >> 3);
}
#if defined(BOOST_ASIO_WINDOWS) || defined(__CYGWIN__)
inline std::size_t calculate_hash_value(SOCKET s)
{
return static_cast(s);
}
#endif // defined(BOOST_ASIO_WINDOWS) || defined(__CYGWIN__)
// Note: assumes K and V are POD types.
template
class hash_map
: private noncopyable
{
public:
// The type of a value in the map.
typedef std::pair value_type;
// The type of a non-const iterator over the hash map.
typedef typename std::list::iterator iterator;
// The type of a const iterator over the hash map.
typedef typename std::list::const_iterator const_iterator;
// Constructor.
hash_map()
: size_(0),
buckets_(0),
num_buckets_(0)
{
}
// Destructor.
~hash_map()
{
delete[] buckets_;
}
// Get an iterator for the beginning of the map.
iterator begin()
{
return values_.begin();
}
// Get an iterator for the beginning of the map.
const_iterator begin() const
{
return values_.begin();
}
// Get an iterator for the end of the map.
iterator end()
{
return values_.end();
}
// Get an iterator for the end of the map.
const_iterator end() const
{
return values_.end();
}
// Check whether the map is empty.
bool empty() const
{
return values_.empty();
}
// Find an entry in the map.
iterator find(const K& k)
{
if (num_buckets_)
{
size_t bucket = calculate_hash_value(k) % num_buckets_;
iterator it = buckets_[bucket].first;
if (it == values_.end())
return values_.end();
iterator end_it = buckets_[bucket].last;
++end_it;
while (it != end_it)
{
if (it->first == k)
return it;
++it;
}
}
return values_.end();
}
// Find an entry in the map.
const_iterator find(const K& k) const
{
if (num_buckets_)
{
size_t bucket = calculate_hash_value(k) % num_buckets_;
const_iterator it = buckets_[bucket].first;
if (it == values_.end())
return it;
const_iterator end_it = buckets_[bucket].last;
++end_it;
while (it != end_it)
{
if (it->first == k)
return it;
++it;
}
}
return values_.end();
}
// Insert a new entry into the map.
std::pair insert(const value_type& v)
{
if (size_ + 1 >= num_buckets_)
rehash(hash_size(size_ + 1));
size_t bucket = calculate_hash_value(v.first) % num_buckets_;
iterator it = buckets_[bucket].first;
if (it == values_.end())
{
buckets_[bucket].first = buckets_[bucket].last =
values_insert(values_.end(), v);
++size_;
return std::pair(buckets_[bucket].last, true);
}
iterator end_it = buckets_[bucket].last;
++end_it;
while (it != end_it)
{
if (it->first == v.first)
return std::pair(it, false);
++it;
}
buckets_[bucket].last = values_insert(end_it, v);
++size_;
return std::pair(buckets_[bucket].last, true);
}
// Erase an entry from the map.
void erase(iterator it)
{
BOOST_ASIO_ASSERT(it != values_.end());
BOOST_ASIO_ASSERT(num_buckets_ != 0);
size_t bucket = calculate_hash_value(it->first) % num_buckets_;
bool is_first = (it == buckets_[bucket].first);
bool is_last = (it == buckets_[bucket].last);
if (is_first && is_last)
buckets_[bucket].first = buckets_[bucket].last = values_.end();
else if (is_first)
++buckets_[bucket].first;
else if (is_last)
--buckets_[bucket].last;
values_erase(it);
--size_;
}
// Erase a key from the map.
void erase(const K& k)
{
iterator it = find(k);
if (it != values_.end())
erase(it);
}
// Remove all entries from the map.
void clear()
{
// Clear the values.
values_.clear();
size_ = 0;
// Initialise all buckets to empty.
iterator end_it = values_.end();
for (size_t i = 0; i < num_buckets_; ++i)
buckets_[i].first = buckets_[i].last = end_it;
}
private:
// Calculate the hash size for the specified number of elements.
static std::size_t hash_size(std::size_t num_elems)
{
static std::size_t sizes[] =
{
#if defined(BOOST_ASIO_HASH_MAP_BUCKETS)
BOOST_ASIO_HASH_MAP_BUCKETS
#else // BOOST_ASIO_HASH_MAP_BUCKETS
3, 13, 23, 53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593,
49157, 98317, 196613, 393241, 786433, 1572869, 3145739, 6291469,
12582917, 25165843
#endif // BOOST_ASIO_HASH_MAP_BUCKETS
};
const std::size_t nth_size = sizeof(sizes) / sizeof(std::size_t) - 1;
for (std::size_t i = 0; i < nth_size; ++i)
if (num_elems < sizes[i])
return sizes[i];
return sizes[nth_size];
}
// Re-initialise the hash from the values already contained in the list.
void rehash(std::size_t num_buckets)
{
if (num_buckets == num_buckets_)
return;
BOOST_ASIO_ASSERT(num_buckets != 0);
iterator end_iter = values_.end();
// Update number of buckets and initialise all buckets to empty.
bucket_type* tmp = new bucket_type[num_buckets];
delete[] buckets_;
buckets_ = tmp;
num_buckets_ = num_buckets;
for (std::size_t i = 0; i < num_buckets_; ++i)
buckets_[i].first = buckets_[i].last = end_iter;
// Put all values back into the hash.
iterator iter = values_.begin();
while (iter != end_iter)
{
std::size_t bucket = calculate_hash_value(iter->first) % num_buckets_;
if (buckets_[bucket].last == end_iter)
{
buckets_[bucket].first = buckets_[bucket].last = iter++;
}
else if (++buckets_[bucket].last == iter)
{
++iter;
}
else
{
values_.splice(buckets_[bucket].last, values_, iter++);
--buckets_[bucket].last;
}
}
}
// Insert an element into the values list by splicing from the spares list,
// if a spare is available, and otherwise by inserting a new element.
iterator values_insert(iterator it, const value_type& v)
{
if (spares_.empty())
{
return values_.insert(it, v);
}
else
{
spares_.front() = v;
values_.splice(it, spares_, spares_.begin());
return --it;
}
}
// Erase an element from the values list by splicing it to the spares list.
void values_erase(iterator it)
{
*it = value_type();
spares_.splice(spares_.begin(), values_, it);
}
// The number of elements in the hash.
std::size_t size_;
// The list of all values in the hash map.
std::list values_;
// The list of spare nodes waiting to be recycled. Assumes that POD types only
// are stored in the hash map.
std::list spares_;
// The type for a bucket in the hash table.
struct bucket_type
{
iterator first;
iterator last;
};
// The buckets in the hash.
bucket_type* buckets_;
// The number of buckets in the hash.
std::size_t num_buckets_;
};
} // namespace detail
} // namespace asio
} // namespace boost
#include
#endif // BOOST_ASIO_DETAIL_HASH_MAP_HPP