| // |
| // detail/hash_map.hpp |
| // ~~~~~~~~~~~~~~~~~~~ |
| // |
| // Copyright (c) 2003-2010 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 <cassert> |
| #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 = buckets_[bucket].last; |
| ++end; |
| while (it != end) |
| { |
| 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 = buckets_[bucket].last; |
| ++end; |
| while (it != end) |
| { |
| 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 = buckets_[bucket].last; |
| ++end; |
| while (it != end) |
| { |
| if (it->first == v.first) |
| return std::pair<iterator, bool>(it, false); |
| ++it; |
| } |
| buckets_[bucket].last = values_insert(end, v); |
| ++size_; |
| return std::pair<iterator, bool>(buckets_[bucket].last, true); |
| } |
| |
| // Erase an entry from the map. |
| void erase(iterator it) |
| { |
| 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 = values_.end(); |
| for (size_t i = 0; i < num_buckets_; ++i) |
| buckets_[i].first = buckets_[i].last = end; |
| } |
| |
| 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 = 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; |
| |
| // Put all values back into the hash. |
| iterator iter = values_.begin(); |
| while (iter != end) |
| { |
| std::size_t bucket = calculate_hash_value(iter->first) % num_buckets_; |
| if (buckets_[bucket].last == end) |
| { |
| 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 |