aboutsummaryrefslogtreecommitdiffstats
path: root/lib/asio/detail/hash_map.hpp
diff options
context:
space:
mode:
Diffstat (limited to 'lib/asio/detail/hash_map.hpp')
-rw-r--r--lib/asio/detail/hash_map.hpp331
1 files changed, 331 insertions, 0 deletions
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 <list>
+#include <utility>
+#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<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(ASIO_WINDOWS) || defined(__CYGWIN__)
+inline std::size_t calculate_hash_value(SOCKET s)
+{
+ return static_cast<std::size_t>(s);
+}
+#endif // defined(ASIO_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)
+ {
+ 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<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
+
+#include "asio/detail/pop_options.hpp"
+
+#endif // ASIO_DETAIL_HASH_MAP_HPP