From e95946831f8ef53d29590735a2df661385edb008 Mon Sep 17 00:00:00 2001 From: "Matthias P. Braendli" Date: Mon, 6 Aug 2018 10:35:22 +0200 Subject: Replace boost by the standalone asio library --- lib/asio/detail/hash_map.hpp | 331 +++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 331 insertions(+) create mode 100644 lib/asio/detail/hash_map.hpp (limited to 'lib/asio/detail/hash_map.hpp') diff --git a/lib/asio/detail/hash_map.hpp b/lib/asio/detail/hash_map.hpp new file mode 100644 index 0000000..e70970d --- /dev/null +++ b/lib/asio/detail/hash_map.hpp @@ -0,0 +1,331 @@ +// +// detail/hash_map.hpp +// ~~~~~~~~~~~~~~~~~~~ +// +// Copyright (c) 2003-2018 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 ASIO_DETAIL_HASH_MAP_HPP +#define ASIO_DETAIL_HASH_MAP_HPP + +#if defined(_MSC_VER) && (_MSC_VER >= 1200) +# pragma once +#endif // defined(_MSC_VER) && (_MSC_VER >= 1200) + +#include "asio/detail/config.hpp" +#include +#include +#include "asio/detail/assert.hpp" +#include "asio/detail/noncopyable.hpp" + +#if defined(ASIO_WINDOWS) || defined(__CYGWIN__) +# include "asio/detail/socket_types.hpp" +#endif // defined(ASIO_WINDOWS) || defined(__CYGWIN__) + +#include "asio/detail/push_options.hpp" + +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(ASIO_WINDOWS) || defined(__CYGWIN__) +inline std::size_t calculate_hash_value(SOCKET s) +{ + return static_cast(s); +} +#endif // defined(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) + { + ASIO_ASSERT(it != values_.end()); + 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(ASIO_HASH_MAP_BUCKETS) + ASIO_HASH_MAP_BUCKETS +#else // 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 // 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; + 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 + +#include "asio/detail/pop_options.hpp" + +#endif // ASIO_DETAIL_HASH_MAP_HPP -- cgit v1.2.3