You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@trafficserver.apache.org by am...@apache.org on 2018/08/20 15:40:18 UTC
[trafficserver] branch master updated: IntrusiveHashMap: Refresh
TSHashTable for C++ eleventy.
This is an automated email from the ASF dual-hosted git repository.
amc pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/trafficserver.git
The following commit(s) were added to refs/heads/master by this push:
new d6099b3 IntrusiveHashMap: Refresh TSHashTable for C++ eleventy.
d6099b3 is described below
commit d6099b3661b60fe002221d561d3e5f7f3575cf6f
Author: Alan M. Carroll <am...@apache.org>
AuthorDate: Sun Jul 1 19:46:00 2018 -0500
IntrusiveHashMap: Refresh TSHashTable for C++ eleventy.
---
CMakeLists.txt | 2 +
doc/conf.py | 6 +-
.../internal-libraries/index.en.rst | 1 +
.../internal-libraries/intrusive-hash-map.en.rst | 197 ++++++
lib/ts/IntrusiveHashMap.h | 662 +++++++++++++++++++++
lib/ts/Makefile.am | 1 +
lib/ts/unit-tests/test_IntrusiveHashMap.cc | 148 +++++
7 files changed, 1015 insertions(+), 2 deletions(-)
diff --git a/CMakeLists.txt b/CMakeLists.txt
index 07dffb2..6207c2a 100644
--- a/CMakeLists.txt
+++ b/CMakeLists.txt
@@ -1083,6 +1083,7 @@ add_library(libtsutil SHARED
lib/ts/InkErrno.cc
lib/ts/InkErrno.h
lib/ts/IntrusiveDList.h
+ lib/ts/IntrusiveHashMap.h
lib/ts/IntrusivePtrTest.cc
lib/ts/IpMap.cc
lib/ts/IpMap.h
@@ -1157,6 +1158,7 @@ add_executable(test_tslib
lib/ts/unit-tests/test_History.cc
lib/ts/unit-tests/test_ink_inet.cc
lib/ts/unit-tests/test_IntrusiveDList.cc
+ lib/ts/unit-tests/test_IntrusiveHashMap.cc
lib/ts/unit-tests/test_IntrusivePtr.cc
lib/ts/unit-tests/test_IpMap.cc
lib/ts/unit-tests/test_layout.cc
diff --git a/doc/conf.py b/doc/conf.py
index 54e7b10..3e3040e 100644
--- a/doc/conf.py
+++ b/doc/conf.py
@@ -167,8 +167,10 @@ pygments_style = 'sphinx'
#modindex_common_prefix = []
nitpicky = True
-nitpick_ignore = [ ('cpp:typeOrConcept', 'T')
- , ('cpp:typeOrConcept', 'Args')
+nitpick_ignore = [ ('cpp:typeOrConcept', 'T') # template arg
+ , ('cpp:typeOrConcept', 'F') # template arg
+ , ('cpp:typeOrConcept', 'Args') # variadic template arg
+ , ('cpp:typeOrConcept', 'Rest') # variadic template arg
]
# Autolink issue references.
diff --git a/doc/developer-guide/internal-libraries/index.en.rst b/doc/developer-guide/internal-libraries/index.en.rst
index fd9d3af..0800562 100644
--- a/doc/developer-guide/internal-libraries/index.en.rst
+++ b/doc/developer-guide/internal-libraries/index.en.rst
@@ -33,6 +33,7 @@ development team.
scalar.en
buffer-writer.en
intrusive-list.en
+ intrusive-hash-map.en
MemArena.en
AcidPtr.en
Extendible.en
diff --git a/doc/developer-guide/internal-libraries/intrusive-hash-map.en.rst b/doc/developer-guide/internal-libraries/intrusive-hash-map.en.rst
new file mode 100644
index 0000000..6ee1413
--- /dev/null
+++ b/doc/developer-guide/internal-libraries/intrusive-hash-map.en.rst
@@ -0,0 +1,197 @@
+.. Licensed to the Apache Software Foundation (ASF) under one
+ or more contributor license agreements. See the NOTICE file distributed with this work for
+ additional information regarding copyright ownership. The ASF licenses this file to you under the
+ Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with
+ the License. You may obtain a copy of the License at
+
+ http://www.apache.org/licenses/LICENSE-2.0
+
+ Unless required by applicable law or agreed to in writing, software distributed under the License
+ is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
+ or implied. See the License for the specific language governing permissions and limitations under
+ the License.
+
+.. include:: ../../common.defs
+
+.. _lib-intrusive-hash-map:
+.. highlight:: cpp
+.. default-domain:: cpp
+
+IntrusiveHashMap
+****************
+
+:class:`IntrusiveHashMap` provides a "hash" or "unordered" set, using intrusive links. It provides a
+container for elements, each of which has a :arg:`key`. A hash function is applied to a key to
+generate a :arg:`hash id` which is used to group the elements in to buckets for fast lookup. This
+container is a mix of :code:`std::unordered_set` and :code:`std::unordered_map`. There is no
+separation between elements and keys, but each element can contain non-key data.
+
+Iteration over elements is provided and is constant time.
+
+In order to optimize lookup, the container can increase the number of buckets used. This is called
+the "expansion policy" of the container and it can be automatic or controlled externally.
+
+Usage
+*****
+
+To use an :class:`IntrusiveHashMap` the element must provide support for the container. This is done
+through an associated descriptor class which provides the operations needed to manipulate the elements
+in the container.
+
+Examples
+========
+
+Details
+*******
+
+.. class:: template < typename H > IntrusiveHashMap
+
+ :tparam H: Element operations.
+
+ An unordered map using a hash function. The properties of the map are determined by types and
+ operations provided by the descriptor type :arg:`H`. The following types are derived from :arg:`H`
+ and defined in the container type.
+
+ .. type:: value_type
+
+ The type of elements in the container, deduced from the return types of the link accessor methods
+ in :arg:`H`.
+
+ .. type:: key_type
+
+ The type of the key used for hash computations. Deduced from the return type of the key
+ accessor. An instance of this type is never default constructed nor modified, therefore it can
+ be a reference if the key type is expensive to copy.
+
+ .. type:: hash_id
+
+ The type of the hash of a :type:`key_type`. Deduced from the return type of the hash function.
+ This must be a numeric type.
+
+ :arg:`H`
+ This describes the hash map, primarily via the operations required for the map. The related types are deduced
+ from the function return types. This is designed to be compatible with :class:`IntrusiveDList`.
+
+ .. function:: static key_type key_of(value_type * v)
+
+ Key accessor - return the key of the element :arg:`v`.
+
+ .. function:: static hash_id hash_of(key_type key)
+
+ Hash function - compute the hash value of the :arg:`key`.
+
+ .. function:: static bool equal(key_type lhs, key_type rhs)
+
+ Key comparison - two keys are equal if this function returns :code:`true`.
+
+ .. function:: static IntrusiveHashMap::value_type * & next_ptr(IntrusiveHashMap::value_type * v)
+
+ Return a reference to the next element pointer embedded in the element :arg:`v`.
+
+ .. function:: static IntrusiveHashMap::value_type * & prev_ptr(IntrusiveHashMap::value_type * v)
+
+ Return a reference to the previous element pointer embedded in the element :arg:`v`.
+
+ .. type:: iterator
+
+ An STL compliant iterator over elements in the container.
+
+ .. function:: IntrusiveHashMap & insert(value_type * v)
+
+ Insert the element :arg:`v` into the container.
+
+ .. function:: iterator begin()
+
+ Return an iterator to the first element in the container.
+
+ .. function:: iterator end()
+
+ Return an iterator to past the last element in the container.
+
+ .. function:: iterator find(value_type * v)
+
+ Search for :arg:`v` in the container. If found, return an iterator refering to :arg:`v`. If not
+ return the end iterator. This validates :arg:`v` is in the container.
+
+ .. function:: IntrusiveHashMap & erase(iterator spot)
+
+ Remove the element referred to by :arg:`spot` from the container.
+
+ .. function:: iterator iterator_for(value_type * v)
+
+ Return an iterator for :arg:`v`. This is very fast, faster than :func:`IntrusiveHashMap::find`
+ but less safe because no validation done on :arg:`v`. If it not in the container (either in no
+ container or a different one) further iteration on the returned iterator will go badly. It is
+ useful inside range :code:`for` loops when it is guaranteed the element is in the container.
+
+ .. function:: template <typename F> IntrusiveHashMap & apply(F && f)
+
+ :tparam F: A functional type with the signature :code:`void (value_type*)`.
+
+ This applies the function :arg:`f` to every element in the container in such a way that
+ modification of the element does not interfere with the iteration. The most common use is to
+ :code:`delete` the elements during cleanup. The common idiom ::
+
+ for ( auto & elt : container) delete &elt;
+
+ is problematic because the iteration links are in the deleted element causing the computation
+ of the next element to be a use after free. Using :func:`IntrusiveHashMap::apply` enables safe
+ cleanup. ::
+
+ container.apply([](value_type & v) { delete & v; });
+
+ Because the links are intrusive it is possible for other classes or the element class to
+ modify them. In such cases this method provides a safe way to invoke such mechanisms.
+
+Design Notes
+************
+
+This is a refresh of an previously existing class, :code:`TSHahTable`. The switch to C++ 11 and then
+C++ 17 made it possible to do much better in terms of the internal implementation and API. The
+overall functionality is the roughly the same but with an easier API, compatiblity with
+:class:`IntrusiveDList`, and better internal implementation.
+
+The biggest change is that elements are stored in a single global list rather than per hash bucket.
+The buckets server only as entry points in to the global list and to count the number of elements
+per bucket. This simplifies the implementation of iteration, so that the old :code:`Location` nested
+class can be removed. Elements with equal keys can be handled in the same way as with STL
+containers, via iterator ranges, instead of a custom psuedo-iterator class.
+
+Notes on :func:`IntrusiveHashMap::apply`
+========================================
+
+This was added after some experience with use of the container. Initially it was added to make
+cleaning up the container easier. Without it, cleanup looks like ::
+
+ for ( auto spot = map.begin(), limit = map.end() ; spot != limit ; delete &( * spot++)) {
+ ; // empty
+ }
+
+Instead one can do ::
+
+ map.apply([](value_type& v) { delete &v; });
+
+The post increment operator guarantees that :arg:`spot` has been updated before the current element is destroyed.
+However, it turns out to be handy in other map modifying operations. In the unit tests there is
+this code
+
+.. literalinclude:: ../../../lib/ts/unit-tests/test_IntrusiveHashMap.cc
+ :lines: 129-132
+
+This removes all elements that do not have the payload "dup". As another design note,
+:func:`IntrusiveHashMap::iterator_for` here serves to bypass validation checking on the target for
+:func:`IntrusiveHashMap::erase`, which is proper because :func:`IntrusiveHashMap::apply` guarantees
+:arg:`thing` is in the map.
+
+Without :code:`apply` this is needed ::
+
+ auto idx = map.begin();
+ while (idx != map.end()) {
+ auto x{idx++};
+ if ("dup"sv != x->_payload) {
+ map.erase(x);
+ }
+ }
+
+The latter is more verbose and more importantly less obvious, depending on a subtle interaction with
+post increment.
diff --git a/lib/ts/IntrusiveHashMap.h b/lib/ts/IntrusiveHashMap.h
new file mode 100644
index 0000000..b39514c
--- /dev/null
+++ b/lib/ts/IntrusiveHashMap.h
@@ -0,0 +1,662 @@
+/** @file
+
+ Instrusive hash map.
+
+ @section license License
+
+ Licensed to the Apache Software Foundation (ASF) under one
+ or more contributor license agreements. See the NOTICE file
+ distributed with this work for additional information
+ regarding copyright ownership. The ASF licenses this file
+ to you under the Apache License, Version 2.0 (the
+ "License"); you may not use this file except in compliance
+ with the License. You may obtain a copy of the License at
+
+ http://www.apache.org/licenses/LICENSE-2.0
+
+ Unless required by applicable law or agreed to in writing, software
+ distributed under the License is distributed on an "AS IS" BASIS,
+ WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ See the License for the specific language governing permissions and
+ limitations under the License.
+*/
+
+#pragma once
+
+#include <vector>
+#include <array>
+#include <algorithm>
+#include <ts/IntrusiveDList.h>
+
+namespace ts
+{
+/** Intrusive Hash Table.
+
+ Values stored in this container are not destroyed when the container is destroyed or removed from the container.
+ They must be released by the client.
+
+ Duplicate keys are allowed. Clients must walk the list for multiple entries.
+ @see @c Location::operator++()
+
+ By default the table automatically expands to limit the average chain length. This can be tuned. If set
+ to @c MANUAL then the table will expand @b only when explicitly requested to do so by the client.
+ @see @c ExpansionPolicy
+ @see @c setExpansionPolicy()
+ @see @c setExpansionLimit()
+ @see @c expand()
+
+ The hash table is configured by a descriptor class. This must contain the following members
+
+ - The static method <tt>key_type key_of(value_type *)</tt> which returns the key for an instance of @c value_type.
+
+ - The static method <tt>bool equal(key_type lhs, key_type rhs)</tt> which checks if two instances of @c Key are the same.
+
+ - The static method <tt>hash_id hash_of(key_type)</tt> which computes the hash value of the key. @c ID must a numeric type.
+
+ - The static method <tt>value_type *& next_ptr(value_type *)</tt> which returns a reference to a forward pointer.
+
+ - The static method <tt>value_type *& prev_ptr(value_type *)</tt> which returns a reference to a backwards pointer.
+
+ These are the required members, it is permitted to have other methods (if the descriptor is used for other purposes)
+ or to provide overloads of the methods. Note this is compatible with @c IntrusiveDList.
+
+ Several internal types are deduced from these arguments.
+
+ @a Key is the return type of @a key_of and represents the key that distinguishes instances of @a value_type. Two
+ instances of @c value_type are considered the same if their respective @c Key values are @c equal. @c Key is
+ presumed cheap to copy. If the underlying key is not a simple type then @a Key should be a constant pointer or a
+ constant reference. The hash table will never attempt to modify a key.
+
+ @a ID The numeric type that is the hash value for an instance of @a Key.
+
+ Example for @c HttpServerSession keyed by the origin server IP address.
+
+ @code
+ struct Descriptor {
+ static sockaddr const* key_of(HttpServerSession const* value) { return &value->ip.sa }
+ static bool equal(sockaddr const* lhs, sockaddr const* rhs) { return ats_ip_eq(lhs, rhs); }
+ static uint32_t hash_of(sockaddr const* key) { return ats_ip_hash(key); }
+ static HttpServerSession *& next_ptr(HttpServerSession * ssn) { return ssn->_next; }
+ static HttpServerSession *& prev_ptr(HttpServerSession * ssn) { return ssn->_prev; }
+ };
+ using Table = IntrusiveHashMap<Descriptor>;
+ @endcode
+
+ */
+template <typename H> class IntrusiveHashMap
+{
+ using self_type = IntrusiveHashMap;
+
+public:
+ /// Type of elements in the map.
+ using value_type = typename std::remove_pointer<typename std::remove_reference<decltype(H::next_ptr(nullptr))>::type>::type;
+ /// Key type for the elements.
+ using key_type = decltype(H::key_of(static_cast<value_type *>(nullptr)));
+ /// The numeric hash ID computed from a key.
+ using hash_id = decltype(H::hash_of(H::key_of(static_cast<value_type *>(nullptr))));
+
+ /// When the hash table is expanded.
+ enum ExpansionPolicy {
+ MANUAL, ///< Client must explicitly expand the table.
+ AVERAGE, ///< Table expands if average chain length exceeds limit. [default]
+ MAXIMUM ///< Table expands if any chain length exceeds limit.
+ };
+
+protected:
+ /** List of elements.
+ * All table elements are in this list. The buckets reference their starting element in the list, or nothing if
+ * no elements are in that bucket.
+ */
+ using List = IntrusiveDList<H>;
+
+ /// A bucket for the hash map.
+ struct Bucket {
+ /// Support for IntrusiveDList<Bucket::Linkage>, definitions and link storage.
+ struct Linkage {
+ static Bucket *&next_ptr(Bucket *b); ///< Access next pointer.
+ static Bucket *&prev_ptr(Bucket *b); ///< Access prev pointer.
+ Bucket *_prev{nullptr}; ///< Prev pointer.
+ Bucket *_next{nullptr}; ///< Next pointer.
+ } _link;
+
+ value_type *_v{nullptr}; ///< First element in the bucket.
+ size_t _count{0}; ///< Number of elements in the bucket.
+
+ /** Marker for the chain having different keys.
+
+ This is used to determine if expanding the hash map would be useful - buckets that are not mixed
+ will not be changed by an expansion.
+ */
+ bool _mixed_p{false};
+
+ /// Compute the limit value for iteration in this bucket.
+ /// This is the value of the next bucket, or @c nullptr if no next bucket.
+ value_type *limit() const;
+
+ /// Verify @a v is in this bucket.
+ bool contains(value_type *v) const;
+
+ void clear(); ///< Reset to initial state.
+ };
+
+public:
+ /// The default starting number of buckets.
+ static size_t constexpr DEFAULT_BUCKET_COUNT = 7; ///< POOMA.
+ /// The default expansion policy limit.
+ static size_t constexpr DEFAULT_EXPANSION_LIMIT = 4; ///< Value from previous version.
+ /// Expansion policy if not specified in constructor.
+ static ExpansionPolicy constexpr DEFAULT_EXPANSION_POLICY = AVERAGE;
+
+ using iterator = typename List::iterator;
+ using const_iterator = typename List::const_iterator;
+
+ /// A range of elements in the map.
+ /// It is a half open range, [first, last) in the usual STL style.
+ /// @internal I tried @c std::pair as a base for this but was unable to get STL container operations to work.
+ struct range {
+ iterator first; ///< First element.
+ iterator last; ///< Past last element.
+
+ /// Construct from two iterators.
+ range(iterator const &lhs, iterator const &rhs);
+
+ // These methods enable treating the range as a view in to the hash map.
+
+ /// Return @a first
+ iterator const &begin() const;
+ /// Return @a last
+ iterator const &end() const;
+ };
+
+ /// A range of constant elements in the map.
+ struct const_range {
+ const_iterator first; ///< First element.
+ const_iterator last; ///< Past last element.
+
+ /// Construct from two iterators.
+ const_range(const_iterator const &lhs, const_iterator const &rhs);
+
+ // These methods enable treating the range as a view in to the hash map.
+
+ /// Return @a first
+ const_iterator const &begin() const;
+ /// Return @a last
+ const_iterator const &end() const;
+ };
+
+ /// Construct, starting with @n buckets.
+ /// This doubles as the default constructor.
+ IntrusiveHashMap(size_t n = DEFAULT_BUCKET_COUNT);
+
+ /** Remove all values from the table.
+
+ The values are not cleaned up. The values are not touched in this method, therefore it is safe
+ to destroy them first and then @c clear this table.
+ */
+ self_type &clear();
+
+ iterator begin(); ///< First element.
+ const_iterator begin() const; ///< First element.
+ iterator end(); ///< Past last element.
+ const_iterator end() const; ///< Past last element.
+
+ /** Insert a value in to the table.
+ The @a value must @b NOT already be in a table of this type.
+ @note The value itself is put in the table, @b not a copy.
+ */
+ void insert(value_type *v);
+
+ /** Find an element with a key equal to @a key.
+
+ @return A element with a matching key, or the end iterator if not found.
+ */
+ const_iterator find(key_type key) const;
+ iterator find(key_type key);
+
+ /** Get an iterator for an existing value @a v.
+
+ @return An iterator that references @a v, or the end iterator if @a v is not in the table.
+ */
+ const_iterator find(value_type const *v) const;
+ iterator find(value_type *v);
+
+ /** Find the range of objects with keys equal to @a key.
+
+ @return A iterator pair of [first, last) items with equal keys.
+ */
+ const_range equal_range(key_type key) const;
+ range equal_range(key_type key);
+
+ /** Get an @c iterator for the value @a v.
+
+ This is a bit obscure but needed in certain cases. It should only be used on a @a value that
+ is already known to be in the table.
+ */
+ iterator iterator_for(value_type *v);
+
+ /** Remove the value at @a loc from the table.
+
+ @note This does @b not clean up the removed elements. Use carefully to avoid leaks.
+
+ @return @c true if the value was removed, @c false otherwise.
+ */
+ bool erase(iterator const &loc);
+
+ /// Remove all elements in the @c range @a r.
+ bool erase(range const &r);
+ /// Remove all elements in the range (first, last]
+ bool erase(iterator const &first, iterator const &last);
+
+ /** Apply @a F(value_type&) to every element in the hash map.
+ *
+ * This is similar to a range for loop except the iteration is done in a way where destruction or alternation of
+ * the element does @b not affect the iterator. Primarily this is useful for @c delete to clean up the elements
+ * but it can have other uses.
+ *
+ * @tparam F A functional object of the form <tt>void F(value_type&)</tt>
+ * @param f The function to apply.
+ * @return
+ */
+ template <typename F> self_type &apply(F &&f);
+
+ /** Expand the hash if needed.
+
+ Useful primarily when the expansion policy is set to @c MANUAL.
+ */
+ void expand();
+
+ /// Number of elements in the map.
+ size_t count() const;
+
+ /// Number of buckets in the array.
+ size_t bucket_count() const;
+
+ /// Set the expansion policy to @a policy.
+ self_type &set_expansion_policy(ExpansionPolicy policy);
+
+ /// Get the current expansion policy
+ ExpansionPolicy get_expansion_policy() const;
+
+ /// Set the limit value for the expansion policy.
+ self_type &set_expansion_limit(size_t n);
+
+ /// Set the limit value for the expansion policy.
+ size_t get_expansion_limit() const;
+
+protected:
+ /// The type of storage for the buckets.
+ using Table = std::vector<Bucket>;
+
+ List _list; ///< Elements in the table.
+ Table _table; ///< Array of buckets.
+
+ /// List of non-empty buckets.
+ IntrusiveDList<typename Bucket::Linkage> _active_buckets;
+
+ Bucket *bucket_for(key_type key);
+
+ ExpansionPolicy _expansion_policy{DEFAULT_EXPANSION_POLICY}; ///< When to exand the table.
+ size_t _expansion_limit{DEFAULT_EXPANSION_LIMIT}; ///< Limit value for expansion.
+
+ // noncopyable
+ IntrusiveHashMap(const IntrusiveHashMap &) = delete;
+ IntrusiveHashMap &operator=(const IntrusiveHashMap &) = delete;
+
+ // Hash table size prime list.
+ static constexpr std::array<size_t, 29> PRIME = {{1, 3, 7, 13, 31, 61, 127, 251,
+ 509, 1021, 2039, 4093, 8191, 16381, 32749, 65521,
+ 131071, 262139, 524287, 1048573, 2097143, 4194301, 8388593, 16777213,
+ 33554393, 67108859, 134217689, 268435399, 536870909}};
+};
+
+template <typename H>
+auto
+IntrusiveHashMap<H>::Bucket::Linkage::next_ptr(Bucket *b) -> Bucket *&
+{
+ return b->_link._next;
+}
+
+template <typename H>
+auto
+IntrusiveHashMap<H>::Bucket::Linkage::prev_ptr(Bucket *b) -> Bucket *&
+{
+ return b->_link._prev;
+}
+
+// This is designed so that if the bucket is empty, then @c nullptr is returned, which will immediately terminate
+// a search loop on an empty bucket because that will start with a nullptr candidate, matching the limit.
+template <typename H>
+auto
+IntrusiveHashMap<H>::Bucket::limit() const -> value_type *
+{
+ Bucket *n{_link._next};
+ return n ? n->_v : nullptr;
+};
+
+template <typename H>
+void
+IntrusiveHashMap<H>::Bucket::clear()
+{
+ _v = nullptr;
+ _count = 0;
+ _mixed_p = false;
+}
+
+template <typename H>
+bool
+IntrusiveHashMap<H>::Bucket::contains(value_type *v) const
+{
+ value_type *x = _v;
+ value_type *limit = this->limit();
+ while (x != limit && x != v) {
+ x = H::next_ptr(x);
+ }
+ return x == v;
+}
+
+// ---------------------
+template <typename H> IntrusiveHashMap<H>::range::range(iterator const &lhs, iterator const &rhs) : first(lhs), last(rhs) {}
+
+template <typename H>
+auto
+IntrusiveHashMap<H>::range::begin() const -> iterator const &
+{
+ return first;
+}
+template <typename H>
+auto
+IntrusiveHashMap<H>::range::end() const -> iterator const &
+{
+ return last;
+}
+
+template <typename H>
+IntrusiveHashMap<H>::const_range::const_range(const_iterator const &lhs, const_iterator const &rhs) : first(lhs), last(rhs)
+{
+}
+
+template <typename H>
+auto
+IntrusiveHashMap<H>::const_range::begin() const -> const_iterator const &
+{
+ return first;
+}
+
+template <typename H>
+auto
+IntrusiveHashMap<H>::const_range::end() const -> const_iterator const &
+{
+ return last;
+}
+
+// ---------------------
+
+template <typename H> IntrusiveHashMap<H>::IntrusiveHashMap(size_t n)
+{
+ if (n) {
+ _table.resize(*std::lower_bound(PRIME.begin(), PRIME.end(), n));
+ }
+}
+
+template <typename H>
+auto
+IntrusiveHashMap<H>::bucket_for(key_type key) -> Bucket *
+{
+ return &_table[H::hash_of(key) % _table.size()];
+}
+
+template <typename H>
+auto
+IntrusiveHashMap<H>::begin() -> iterator
+{
+ return _list.begin();
+}
+
+template <typename H>
+auto
+IntrusiveHashMap<H>::begin() const -> const_iterator
+{
+ return _list.begin();
+}
+
+template <typename H>
+auto
+IntrusiveHashMap<H>::end() -> iterator
+{
+ return _list.end();
+}
+
+template <typename H>
+auto
+IntrusiveHashMap<H>::end() const -> const_iterator
+{
+ return _list.end();
+}
+
+template <typename H>
+auto
+IntrusiveHashMap<H>::clear() -> self_type &
+{
+ for (auto &b : _table) {
+ b.clear();
+ }
+ // Clear container data.
+ _list.clear();
+ _active_buckets.clear();
+ return *this;
+}
+
+template <typename H>
+auto
+IntrusiveHashMap<H>::find(key_type key) -> iterator
+{
+ Bucket *b = this->bucket_for(key);
+ value_type *v = b->_v;
+ value_type *limit = b->limit();
+ while (v != limit && !H::equal(key, H::key_of(v))) {
+ v = H::next_ptr(v);
+ }
+ return _list.iterator_for(v);
+}
+
+template <typename H>
+auto
+IntrusiveHashMap<H>::find(key_type key) const -> const_iterator
+{
+ return const_cast<self_type *>(this)->find(key);
+}
+
+template <typename H>
+auto
+IntrusiveHashMap<H>::equal_range(key_type key) -> range
+{
+ iterator first{this->find(key)};
+ iterator last{first};
+ iterator limit{this->end()};
+
+ while (last != limit && H::equal(key, H::key_of(&*last))) {
+ ++last;
+ }
+
+ return {first, last};
+}
+
+template <typename H>
+auto
+IntrusiveHashMap<H>::equal_range(key_type key) const -> const_range
+{
+ return const_cast<self_type *>(this)->equal_range(key);
+}
+
+template <typename H>
+auto
+IntrusiveHashMap<H>::iterator_for(value_type *v) -> iterator
+{
+ return _list.iterator_for(v);
+}
+
+template <typename H>
+auto
+IntrusiveHashMap<H>::find(value_type *v) -> iterator
+{
+ Bucket *b = this->bucket_for(H::key_of(v));
+ return b->contains(v) ? _list.iterator_for(v) : this->end();
+}
+
+template <typename H>
+auto
+IntrusiveHashMap<H>::find(value_type const *v) const -> const_iterator
+{
+ return const_cast<self_type *>(this)->find(const_cast<value_type *>(v));
+}
+
+template <typename H>
+void
+IntrusiveHashMap<H>::insert(value_type *v)
+{
+ auto key = H::key_of(v);
+ Bucket *bucket = this->bucket_for(key);
+ value_type *spot = bucket->_v;
+
+ if (nullptr == spot) { // currently empty bucket, set it and add to active list.
+ _list.append(v);
+ bucket->_v = v;
+ _active_buckets.append(bucket);
+ } else {
+ value_type *limit = bucket->limit();
+
+ while (spot != limit && !H::equal(key, H::key_of(spot))) {
+ spot = H::next_ptr(spot);
+ }
+
+ if (spot == limit) { // this key is not in the bucket, add it at the end and note this is now a mixed bucket.
+ _list.insert_before(bucket->_v, v);
+ bucket->_v = v;
+ bucket->_mixed_p = true;
+ } else { // insert before the first matching key.
+ _list.insert_before(spot, v);
+ if (spot == bucket->_v) { // added before the bucket start, update the start.
+ bucket->_v = v;
+ } else { // if the matching key wasn't first, there is some other key in the bucket, mark it mixed.
+ bucket->_mixed_p = true;
+ }
+ }
+ }
+ ++bucket->_count;
+
+ // auto expand if appropriate.
+ if ((AVERAGE == _expansion_policy && (_list.count() / _table.size()) > _expansion_limit) ||
+ (MAXIMUM == _expansion_policy && bucket->_count > _expansion_limit && bucket->_mixed_p)) {
+ this->expand();
+ }
+}
+
+template <typename H>
+bool
+IntrusiveHashMap<H>::erase(iterator const &loc)
+{
+ bool zret = false;
+
+ if (loc != this->end()) {
+ value_type *v = &*loc;
+ Bucket *b = this->bucket_for(H::key_of(v));
+ if (b->contains(v)) {
+ value_type *nv = H::next_ptr(v);
+ value_type *limit = b->limit();
+ if (b->_v == v) { // removed first element in bucket, update bucket
+ if (limit == nv) { // that was also the only element, deactivate bucket
+ _active_buckets.erase(b);
+ b->clear();
+ } else {
+ b->_v = nv;
+ --b->_count;
+ }
+ }
+ zret = true;
+ _list.erase(v);
+ }
+ }
+ return zret;
+}
+
+template <typename H>
+template <typename F>
+auto
+IntrusiveHashMap<H>::apply(F &&f) -> self_type &
+{
+ iterator spot{this->begin()};
+ iterator limit{this->end()};
+ while (spot != limit) {
+ f(*spot++); // post increment means @a spot is updated before @a f is applied.
+ }
+ return *this;
+};
+
+template <typename H>
+void
+IntrusiveHashMap<H>::expand()
+{
+ ExpansionPolicy org_expansion_policy = _expansion_policy; // save for restore.
+ value_type *old = _list.head(); // save for repopulating.
+ auto old_size = _table.size();
+
+ // Reset to empty state.
+ this->clear();
+ _table.resize(*std::lower_bound(PRIME.begin(), PRIME.end(), old_size + 1));
+
+ _expansion_policy = MANUAL; // disable any auto expand while we're expanding.
+ while (old) {
+ value_type *v = old;
+ old = H::next_ptr(old);
+ this->insert(v);
+ }
+ // stashed array gets cleaned up when @a tmp goes out of scope.
+ _expansion_policy = org_expansion_policy; // reset to original value.
+}
+
+template <typename H>
+size_t
+IntrusiveHashMap<H>::count() const
+{
+ return _list.count();
+}
+
+template <typename H>
+size_t
+IntrusiveHashMap<H>::bucket_count() const
+{
+ return _table.size();
+}
+
+template <typename H>
+auto
+IntrusiveHashMap<H>::set_expansion_policy(ExpansionPolicy policy) -> self_type &
+{
+ _expansion_policy = policy;
+ return *this;
+}
+
+template <typename H>
+auto
+IntrusiveHashMap<H>::get_expansion_policy() const -> ExpansionPolicy
+{
+ return _expansion_policy;
+}
+
+template <typename H>
+auto
+IntrusiveHashMap<H>::set_expansion_limit(size_t n) -> self_type &
+{
+ _expansion_limit = n;
+ return *this;
+}
+
+template <typename H>
+size_t
+IntrusiveHashMap<H>::get_expansion_limit() const
+{
+ return _expansion_limit;
+}
+/* ---------------------------------------------------------------------------------------------- */
+
+} // namespace ts
diff --git a/lib/ts/Makefile.am b/lib/ts/Makefile.am
index e6d574c..56cdd2d 100644
--- a/lib/ts/Makefile.am
+++ b/lib/ts/Makefile.am
@@ -273,6 +273,7 @@ test_tslib_SOURCES = \
unit-tests/test_History.cc \
unit-tests/test_ink_inet.cc \
unit-tests/test_IntrusiveDList.cc \
+ unit-tests/test_IntrusiveHashMap.cc \
unit-tests/test_IntrusivePtr.cc \
unit-tests/test_IpMap.cc \
unit-tests/test_layout.cc \
diff --git a/lib/ts/unit-tests/test_IntrusiveHashMap.cc b/lib/ts/unit-tests/test_IntrusiveHashMap.cc
new file mode 100644
index 0000000..ba30e97
--- /dev/null
+++ b/lib/ts/unit-tests/test_IntrusiveHashMap.cc
@@ -0,0 +1,148 @@
+/** @file
+
+ IntrusiveHashMap unit tests.
+
+ @section license License
+
+ Licensed to the Apache Software Foundation (ASF) under one
+ or more contributor license agreements. See the NOTICE file
+ distributed with this work for additional information
+ regarding copyright ownership. The ASF licenses this file
+ to you under the Apache License, Version 2.0 (the
+ "License"); you may not use this file except in compliance
+ with the License. You may obtain a copy of the License at
+
+ http://www.apache.org/licenses/LICENSE-2.0
+
+ Unless required by applicable law or agreed to in writing, software
+ distributed under the License is distributed on an "AS IS" BASIS,
+ WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ See the License for the specific language governing permissions and
+ limitations under the License.
+*/
+
+#include <iostream>
+#include <string_view>
+#include <string>
+#include <bitset>
+#include <ts/IntrusiveHashMap.h>
+#include <ts/BufferWriter.h>
+#include <catch.hpp>
+#include "../../../tests/include/catch.hpp"
+
+// -------------
+// --- TESTS ---
+// -------------
+
+using namespace std::literals;
+
+namespace
+{
+struct Thing {
+ std::string _payload;
+ int _n{0};
+
+ Thing(std::string_view text) : _payload(text) {}
+ Thing(std::string_view text, int x) : _payload(text), _n(x) {}
+
+ Thing *_next{nullptr};
+ Thing *_prev{nullptr};
+};
+
+struct ThingMapDescriptor {
+ static Thing *&
+ next_ptr(Thing *thing)
+ {
+ return thing->_next;
+ }
+ static Thing *&
+ prev_ptr(Thing *thing)
+ {
+ return thing->_prev;
+ }
+ static std::string_view
+ key_of(Thing *thing)
+ {
+ return thing->_payload;
+ }
+ static constexpr std::hash<std::string_view> hasher{};
+ static auto
+ hash_of(std::string_view s) -> decltype(hasher(s))
+ {
+ return hasher(s);
+ }
+ static bool
+ equal(std::string_view const &lhs, std::string_view const &rhs)
+ {
+ return lhs == rhs;
+ }
+};
+
+using Map = ts::IntrusiveHashMap<ThingMapDescriptor>;
+
+} // namespace
+
+TEST_CASE("IntrusiveHashMap", "[libts][IntrusiveHashMap]")
+{
+ Map map;
+ map.insert(new Thing("bob"));
+ REQUIRE(map.count() == 1);
+ map.insert(new Thing("dave"));
+ map.insert(new Thing("persia"));
+ REQUIRE(map.count() == 3);
+ for (auto &thing : map) {
+ delete &thing;
+ }
+ map.clear();
+ REQUIRE(map.count() == 0);
+
+ size_t nb = map.bucket_count();
+ std::bitset<64> marks;
+ for (int i = 1; i <= 63; ++i) {
+ std::string name;
+ ts::bwprint(name, "{} squared is {}", i, i * i);
+ Thing *thing = new Thing(name);
+ thing->_n = i;
+ map.insert(thing);
+ REQUIRE(map.count() == i);
+ REQUIRE(map.find(name) != map.end());
+ }
+ REQUIRE(map.count() == 63);
+ REQUIRE(map.bucket_count() > nb);
+ for (auto &thing : map) {
+ REQUIRE(0 == marks[thing._n]);
+ marks[thing._n] = 1;
+ }
+ marks[0] = 1;
+ REQUIRE(marks.all());
+ map.insert(new Thing("dup"sv, 79));
+ map.insert(new Thing("dup"sv, 80));
+ map.insert(new Thing("dup"sv, 81));
+
+ auto r = map.equal_range("dup"sv);
+ REQUIRE(r.first != r.last);
+ REQUIRE(r.first->_payload == "dup"sv);
+
+ Map::iterator idx;
+
+ // Erase all the non-"dup" and see if the range is still correct.
+ map.apply([&map](Thing &thing) {
+ if (thing._payload != "dup"sv)
+ map.erase(map.iterator_for(&thing));
+ });
+ r = map.equal_range("dup"sv);
+ REQUIRE(r.first != r.last);
+ idx = r.first;
+ REQUIRE(idx->_payload == "dup"sv);
+ REQUIRE((++idx)->_payload == "dup"sv);
+ REQUIRE(idx->_n != r.first->_n);
+ REQUIRE((++idx)->_payload == "dup"sv);
+ REQUIRE(idx->_n != r.first->_n);
+ REQUIRE(++idx == map.end());
+ // Verify only the "dup" items are left.
+ for (auto &&elt : map) {
+ REQUIRE(elt._payload == "dup"sv);
+ }
+ // clean up the last bits.
+ map.apply([](Thing &thing) { delete &thing; });
+};