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