text: //
  // detail/hash_map.hpp
  // ~~~~~~~~~~~~~~~~~~~
  //
  // Copyright (c) 2003-2011 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 <boost/asio/detail/config.hpp>
  #include <boost/assert.hpp>
  #include <list>
  #include <utility>
  #include <boost/asio/detail/noncopyable.hpp>
  
  #if defined(BOOST_WINDOWS) || defined(__CYGWIN__)
  # include <boost/asio/detail/socket_types.hpp>
  #endif // defined(BOOST_WINDOWS) || defined(__CYGWIN__)
  
  #include <boost/asio/detail/push_options.hpp>
  
  namespace boost {
  namespace asio {
  namespace detail {
  
  inline std::size_t calculate_hash_value(int i)
  {
    return static_cast<std::size_t>(i);
  }
  
  inline std::size_t calculate_hash_value(void* p)
  {
    return reinterpret_cast<std::size_t>(p)
      + (reinterpret_cast<std::size_t>(p) >> 3);
  }
  
  #if defined(BOOST_WINDOWS) || defined(__CYGWIN__)
  inline std::size_t calculate_hash_value(SOCKET s)
  {
    return static_cast<std::size_t>(s);
  }
  #endif // defined(BOOST_WINDOWS) || defined(__CYGWIN__)
  
  // Note: assumes K and V are POD types.
  template <typename K, typename V>
  class hash_map
    : private noncopyable
  {
  public:
    // The type of a value in the map.
    typedef std::pair<K, V> value_type;
  
    // The type of a non-const iterator over the hash map.
    typedef typename std::list<value_type>::iterator iterator;
  
    // The type of a const iterator over the hash map.
    typedef typename std::list<value_type>::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<iterator, bool> 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<iterator, bool>(buckets_[bucket].last, true);
      }
      iterator end_it = buckets_[bucket].last;
      ++end_it;
      while (it != end_it)
      {
        if (it->first == v.first)
          return std::pair<iterator, bool>(it, false);
        ++it;
      }
      buckets_[bucket].last = values_insert(end_it, v);
      ++size_;
      return std::pair<iterator, bool>(buckets_[bucket].last, true);
    }
  
    // Erase an entry from the map.
    void erase(iterator it)
    {
      BOOST_ASSERT(it != values_.end());
  
      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;
      num_buckets_ = num_buckets;
  
      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;
      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<value_type> values_;
  
    // The list of spare nodes waiting to be recycled. Assumes that POD types only
    // are stored in the hash map.
    std::list<value_type> 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 <boost/asio/detail/pop_options.hpp>
  
  #endif // BOOST_ASIO_DETAIL_HASH_MAP_HPP
  