trafficserver-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From a..@apache.org
Subject [trafficserver] branch master updated: IntrusiveDList: Refreshed for C++ eleventy, added const_iterator.
Date Tue, 10 Jul 2018 18:09:12 GMT
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 1893dbb  IntrusiveDList: Refreshed for C++ eleventy, added const_iterator.
1893dbb is described below

commit 1893dbb7895893b3393b57984cf34fb516cfb277
Author: Alan M. Carroll <amc@apache.org>
AuthorDate: Fri Jun 29 06:56:40 2018 -0500

    IntrusiveDList: Refreshed for C++ eleventy, added const_iterator.
---
 CMakeLists.txt                                     |   1 +
 .../internal-libraries/index.en.rst                |   1 +
 .../internal-libraries/intrusive-list.en.rst       | 153 ++++
 iocore/net/P_SNIActionPerformer.h                  |   2 +-
 lib/ts/IntrusiveDList.h                            | 801 ++++++++++++++-------
 lib/ts/IpMap.cc                                    |  99 +--
 lib/ts/IpMap.h                                     |   2 +-
 lib/ts/Makefile.am                                 |   1 +
 lib/ts/unit-tests/test_IntrusiveDList.cc           | 274 +++++++
 lib/ts/unit-tests/test_IpMap.cc                    |  26 +-
 proxy/ControlMatcher.cc                            |   2 +-
 proxy/IPAllow.cc                                   |   6 +-
 proxy/logging/LogFilter.cc                         |   4 +-
 13 files changed, 1042 insertions(+), 330 deletions(-)

diff --git a/CMakeLists.txt b/CMakeLists.txt
index f88c463..2ae9ce3 100644
--- a/CMakeLists.txt
+++ b/CMakeLists.txt
@@ -1161,6 +1161,7 @@ add_executable(test_tslib
 	lib/ts/unit-tests/test_BufferWriter.cc
 	lib/ts/unit-tests/test_BufferWriterFormat.cc
 	lib/ts/unit-tests/test_ink_inet.cc
+	lib/ts/unit-tests/test_IntrusiveDList.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/developer-guide/internal-libraries/index.en.rst b/doc/developer-guide/internal-libraries/index.en.rst
index f6e8391..aae63c8 100644
--- a/doc/developer-guide/internal-libraries/index.en.rst
+++ b/doc/developer-guide/internal-libraries/index.en.rst
@@ -32,4 +32,5 @@ development team.
    MemSpan.en
    scalar.en
    buffer-writer.en
+   intrusive-list.en
    MemArena.en
diff --git a/doc/developer-guide/internal-libraries/intrusive-list.en.rst b/doc/developer-guide/internal-libraries/intrusive-list.en.rst
new file mode 100644
index 0000000..c8527f5
--- /dev/null
+++ b/doc/developer-guide/internal-libraries/intrusive-list.en.rst
@@ -0,0 +1,153 @@
+.. 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-list:
+.. highlight:: cpp
+.. default-domain:: cpp
+
+IntrusiveDList
+**************
+
+:class:`IntrusiveDList` is a class that provides a double linked list using pointers embeded in the
+object. :class:`IntrusiveDList` also acts as a queue. No memory management is done - objects can be
+added to and removed from the list but the allocation and deallocation of the objects must be
+handled outside the class. This class supports an STL compliant bidirectional iteration.
+
+Definition
+**********
+
+.. class:: template < typename L > IntrusiveDList
+
+   A double linked list / queue based on links inside the objects. The element type, :code:`T`, is
+   deduced from the return type of the link accessor methods in :arg:`L`.
+
+   :tparam L: List item descriptor
+
+   The descriptor, :arg:`L`, is a type that provides the operations on list elements required by
+   the container.
+
+   .. type:: value_type
+
+      The class for elements in the container, deduced from the return types of the link accessor methods
+      in :class:`L`.
+
+   .. class:: L
+
+      .. function:: static IntrusiveDList::value_type*& next_ptr(IntrusiveDList::value_type* elt)
+
+         Return a reference to the next element pointer embedded in the element :arg:`elt`.
+
+      .. function:: static IntrusiveDList::value_type*& prev_ptr(IntrusiveDList::value_type* elt)
+
+         Return a reference to the previous element pointer embedded in the element :arg:`elt`.
+
+   .. function:: value_type* head()
+
+      Return a pointer to the head element in the list. This may be :code:`nullptr` if the list is empty.
+
+   .. function:: value_type* tail()
+
+      Return a pointer to the tail element in the list. This may be :code:`nullptr` if the list is empty.
+
+   .. function:: IntrusiveDList& clear()
+
+      Remove all elements from the list. This only removes, no deallocation nor destruction is performed.
+
+   .. function:: size_t count() const
+
+      Return the number of elements in the list.
+
+   .. function:: IntrusiveDList& append(value_type * elt)
+
+      Append :arg:`elt` to the list.
+
+   .. function:: IntrusiveDList& prepend(value_type * elt)
+
+      Prepend :arg:`elt` to the list.
+
+Usage
+*****
+
+An instance of :class:`IntrusiveDList` acts as a container for items, maintaining a doubly linked
+list / queue of the objects and tracking the number of objects in the container. There are methods
+for appending, prepending, and inserting (both before and after a specific element already in the
+list). Some care must be taken because it is too expensive to check for an element already being in
+the list or in another list. The internal links are set to :code:`nullptr`, therefore one simple check
+for being in a list is if either internal link is not :code:`nullptr`. This requires initializing the
+internal links to :code:`nullptr`.
+
+Examples
+========
+
+In this example the goal is to have a list of :code:`Message` objects. First the class is declared
+along with the internal linkage support.
+
+.. literalinclude:: ../../../lib/ts/unit-tests/test_IntrusiveDList.cc
+   :lines: 37-62
+
+The struct :code:`Linkage` is used both to provide the descriptor to :class:`IntrusiveDList` but to
+contain the link pointers as well. This isn't necessary - the links could have been direct members
+and the implementation of the link accessor methods adjusted. Because the links are intended to be
+used only by a specific container class (:code:`Container`) the struct is made protected.
+
+The implementation of the link accessor methods.
+
+.. literalinclude:: ../../../lib/ts/unit-tests/test_IntrusiveDList.cc
+   :lines: 64-73
+
+An example method to check if the message is in a list.
+
+.. literalinclude:: ../../../lib/ts/unit-tests/test_IntrusiveDList.cc
+   :lines: 75-79
+
+The container class for the messages could be implemented as
+
+.. literalinclude:: ../../../lib/ts/unit-tests/test_IntrusiveDList.cc
+   :lines: 81-96
+
+The :code:`debug` method takes a format string (:arg:`fmt`) and an arbitrary set of arguments, formats
+the arguments in to the string, and adds the new message to the list.
+
+.. literalinclude:: ../../../lib/ts/unit-tests/test_IntrusiveDList.cc
+   :lines: 119-128
+
+Other methods for the various severity levels would be implemented in a similar fashion. Because the
+intrusive list does not do memory management, the container must clean that up itself, as in the
+:code:`clear` method. The STL iteration support makes this easy.
+
+.. literalinclude:: ../../../lib/ts/unit-tests/test_IntrusiveDList.cc
+   :lines: 103-111
+
+Design Notes
+************
+
+The historic goal of this class is to replace the :code:`DLL` list support. The benefits of this are
+
+*  Remove dependency on the C preprocessor.
+
+*  Provide greater flexibility in the internal link members. Because of the use of the descriptor
+   and its static methods, the links can be anywhere in the object, including in nested structures
+   or super classes. The links are declared like normal members and do not require specific macros.
+
+*  Provide STL compliant iteration. This makes the class easier to use in general and particularly
+   in the case of range :code:`for` loops.
+
+*  Track the number of items in the list.
+
+*  Provide queue support, which is of such low marginal expense there is, IMHO, no point in
+   providing a separate class for it.
+
+
+
diff --git a/iocore/net/P_SNIActionPerformer.h b/iocore/net/P_SNIActionPerformer.h
index c40091e..586910a 100644
--- a/iocore/net/P_SNIActionPerformer.h
+++ b/iocore/net/P_SNIActionPerformer.h
@@ -123,7 +123,7 @@ public:
   SNIAction(Continuation *cont) override
   {
     // i.e, ip filtering is not required
-    if (ip_map.getCount() == 0) {
+    if (ip_map.count() == 0) {
       return SSL_TLSEXT_ERR_OK;
     }
 
diff --git a/lib/ts/IntrusiveDList.h b/lib/ts/IntrusiveDList.h
index 5906d0b..320be15 100644
--- a/lib/ts/IntrusiveDList.h
+++ b/lib/ts/IntrusiveDList.h
@@ -43,339 +43,608 @@
 
 /// FreeBSD doesn't like just declaring the tag struct we need so we have to include the file.
 #include <iterator>
+#include <type_traits>
 
 /** Intrusive doubly linked list container.
 
-    This holds items in a doubly linked list using members of the
-    items.  Elements are copied in to the list. No memory management
-    is done by the list implementation.
+    This holds items in a doubly linked list using links in the items. Items are placed in the list by changing the
+    pointers. An item can be in only one list for a set of links, but an item can contain multiple sets of links. This
+    requires different specializations of this template because link access is part of the type specification. Memory
+    for items is not managed by this class - instances must be allocated and released elsewhere. In particular removing
+    an item from the list does not destruct or free the item.
 
-    To use this class a client should create the structure for
-    elements of the list and ensure that it has two self pointers to
-    be used by the list. For example,
+    Access to the links is described by a linkage class which is required to contain the following members:
+
+    - The static method @c next_ptr which returns a reference to the pointer to the next item.
+
+    - The static method @c prev_ptr which returns a reference to the pointer to the previous item.
+
+    The pointer methods take a single argument of @c Item* and must return a reference to a pointer instance. This
+    type is deduced from the methods and is not explicitly specified. It must be cheaply copyable and stateless.
+
+    An example declaration woudl be
 
     @code
-      struct Elt {
-        int _payload;
-        Elt* _next;
-        Elt* _prev;
+      // Item in the list.
+      struct Thing {
+        Thing* _next;
+        Thing* _prev;
+        Data _payload;
+
+        // Linkage descriptor.
+        struct Linkage {
+          static Thing*& next_ptr(Thing* Thing) { return Thing->_next; }
+          static Thing*& prev_ptr(Thing* Thing) { return Thing->_prev; }
+        };
       };
-    @endcode
 
-    The list is declared as
-    @code
-      typedef IntrusiveDList<Elt, &Elt::_next, &Elt::_prev> EltList;
+      using ThingList = IntrusiveDList<Thing::Linkage>;
     @endcode
 
-    An element can be in multiple types of lists simultaneously as
-    long as each list type uses distinct members. It is not possible
-    for an element to be in more than one list of the same type
-    simultaneously.  This is intrinsic to intrusive list support.
-
-    Element access is done by using either STL style iteration, or
-    direct access to the member pointers. A client can have its own
-    mechanism for getting an element to start, or use the @c getHead
-    and/or @c getTail methods to get the first and last elements in
-    the list respectively.
-
-    @note Due to bugs in various compilers or the C++ specification
-    (or both) it is not possible in general to declare the element
-    pointers in a super class. The template argument @c T must be
-    exactly the same @c T as for the element pointers, even though a
-    pointer to member of a superclass should be trivially coerced to a
-    pointer to member of subclass. MSVC permits an explicit cast in
-    this case, but gcc does not and therefore there is no way to do
-    this. It is most vexing.
-
-    P.S. I think it's a compiler bug personally with regard to the
-    type of an expression of the form @c &T::M is not @c T::* if @c M
-    is declared in a superclass S. In that case the type is @c S::*
-    which seems very wrong to me.
+    Element access is done by using either STL style iteration, or direct access to the member pointers. A client can
+    have its own mechanism for getting an element to start, or use the @c head and/or @c tail methods to get the
+    first and last elements in the list respectively. Note if the list is empty then @c Linkage::NIL will be returned.
 
   */
-template <typename T, ///< Type of list element.
-          T *(T::*N), ///< Member to use for pointer to next element.
-          T *(T::*P)  ///< Member to use for pointer to previous element.
-          >
-class IntrusiveDList
+template <typename L> class IntrusiveDList
 {
   friend class iterator;
 
 public:
-  typedef IntrusiveDList self; ///< Self reference type.
-  typedef T element_type;      ///< Type of list element.
-                               /** STL style iterator for access to elements.
-                                */
-  class iterator
+  using self_type = IntrusiveDList; ///< Self reference type.
+  /// The list item type.
+  using value_type = typename std::remove_pointer<typename std::remove_reference<decltype(L::next_ptr(nullptr))>::type>::type;
+
+  /** Const iterator for the list.
+   */
+  class const_iterator
   {
+    using self_type = const_iterator; ///< Self reference type.
     friend class IntrusiveDList;
 
   public:
-    typedef iterator self;       ///< Self reference type.
-    typedef T value_type;        ///< Referenced type for iterator.
-    typedef int difference_type; ///< Distance type.
-    typedef T *pointer;          ///< Pointer to referent.
-    typedef T &reference;        ///< Reference to referent.
-    typedef std::bidirectional_iterator_tag iterator_category;
+    using list_type  = IntrusiveDList;                       ///< Container type.
+    using value_type = const typename list_type::value_type; /// Import for API compliance.
+    // STL algorithm compliance.
+    using iterator_category = std::bidirectional_iterator_tag;
+    using pointer           = value_type *;
+    using reference         = value_type &;
+    using difference_type   = int;
 
     /// Default constructor.
-    iterator() : _list(0), _elt(0) {}
-    /// Equality test.
-    /// @return @c true if @c this and @a that refer to the same object.
-    bool
-    operator==(self const &that) const
-    {
-      return _list == that._list && _elt == that._elt;
-    }
+    const_iterator();
+
     /// Pre-increment.
     /// Move to the next element in the list.
     /// @return The iterator.
-    self &
-    operator++()
-    {
-      if (_elt)
-        _elt = _elt->*N;
-      return *this;
-    }
+    self_type &operator++();
+
     /// Pre-decrement.
     /// Move to the previous element in the list.
     /// @return The iterator.
-    self &
-    operator--()
-    {
-      if (_elt)
-        _elt = _elt->*P;
-      else if (_list)
-        _elt = _list->_tail;
-      return *this;
-    }
+    self_type &operator--();
+
     /// Post-increment.
     /// Move to the next element in the list.
     /// @return The iterator value before the increment.
-    self
-    operator++(int)
-    {
-      self tmp(*this);
-      ++*this;
-      return tmp;
-    }
+    self_type operator++(int);
+
     /// Post-decrement.
     /// Move to the previous element in the list.
     /// @return The iterator value before the decrement.
-    self
-    operator--(int)
-    {
-      self tmp(*this);
-      --*this;
-      return tmp;
-    }
-    /// Inequality test.
-    /// @return @c true if @c this and @a do not refer to the same object.
-    bool
-    operator!=(self const &that) const
-    {
-      return !(*this == that);
-    }
+    self_type operator--(int);
+
     /// Dereference.
     /// @return A reference to the referent.
-    reference operator*() { return *_elt; }
+    value_type &operator*() const;
+
     /// Dereference.
     /// @return A pointer to the referent.
-    pointer operator->() { return _elt; }
+    value_type *operator->() const;
+
+    /// Equality
+    bool operator==(self_type const &that) const;
+
+    /// Inequality
+    bool operator!=(self_type const &that) const;
 
   protected:
-    IntrusiveDList *_list; ///< List for this iterator.
-    T *_elt;               ///< Referenced element.
+    // These are stored non-const to make implementing @c iterator easier. This class provides the required @c const
+    // protection.
+    list_type *_list{nullptr};                   ///< Needed to descrement from @c end() position.
+    typename list_type::value_type *_v{nullptr}; ///< Referenced element.
+
     /// Internal constructor for containers.
-    iterator(IntrusiveDList *container, ///< Container for iteration.
-             T *elt                     ///< Initial referent
-             )
-      : _list(container), _elt(elt)
-    {
-    }
+    const_iterator(const list_type *list, value_type *v);
+  };
+
+  /** Iterator for the list.
+   */
+  class iterator : public const_iterator
+  {
+    using self_type  = iterator;       ///< Self reference type.
+    using super_type = const_iterator; ///< Super class type.
+
+    friend class IntrusiveDList;
+
+  public:
+    using list_type  = IntrusiveDList;                 /// Must hoist this for direct use.
+    using value_type = typename list_type::value_type; /// Import for API compliance.
+    // STL algorithm compliance.
+    using iterator_category = std::bidirectional_iterator_tag;
+    using pointer           = value_type *;
+    using reference         = value_type &;
+
+    /// Default constructor.
+    iterator();
+
+    /// Pre-increment.
+    /// Move to the next element in the list.
+    /// @return The iterator.
+    self_type &operator++();
+
+    /// Pre-decrement.
+    /// Move to the previous element in the list.
+    /// @return The iterator.
+    self_type &operator--();
+
+    /// Post-increment.
+    /// Move to the next element in the list.
+    /// @return The iterator value before the increment.
+    self_type operator++(int);
+
+    /// Post-decrement.
+    /// Move to the previous element in the list.
+    /// @return The iterator value before the decrement.
+    self_type operator--(int);
+
+    /// Dereference.
+    /// @return A reference to the referent.
+    value_type &operator*() const;
+
+    /// Dereference.
+    /// @return A pointer to the referent.
+    value_type *operator->() const;
+
+  protected:
+    /// Internal constructor for containers.
+    iterator(list_type *list, value_type *v);
   };
 
-  /// Default constructor (empty list).
-  IntrusiveDList() : _head(nullptr), _tail(nullptr), _count(0) {}
   /// Empty check.
   /// @return @c true if the list is empty.
-  bool
-  isEmpty() const
-  {
-    return 0 == _head;
-  }
+  bool empty() const;
+
+  /// Presence check (linear time).
+  /// @return @c true if @a v is in the list, @c false if not.
+  bool contains(value_type *v) const;
+
   /// Add @a elt as the first element in the list.
   /// @return This container.
-  self &
-  prepend(T *elt ///< Element to add.
-  )
-  {
-    elt->*N = _head;
-    elt->*P = nullptr;
-    if (_head)
-      _head->*P = elt;
-    _head = elt;
-    if (!_tail)
-      _tail = _head; // empty to non-empty transition
-    ++_count;
-    return *this;
-  }
+  self_type &prepend(value_type *v);
+
   /// Add @elt as the last element in the list.
   /// @return This container.
-  self &
-  append(T *elt ///< Element to add.
-  )
-  {
-    elt->*N = nullptr;
-    elt->*P = _tail;
-    if (_tail)
-      _tail->*N = elt;
-    _tail = elt;
-    if (!_head)
-      _head = _tail; // empty to non-empty transition
-    ++_count;
-    return *this;
-  }
+  self_type &append(value_type *v);
+
   /// Remove the first element of the list.
   /// @return A poiner to the removed item, or @c nullptr if the list was empty.
-  T *
-  takeHead()
-  {
-    T *zret = 0;
-    if (_head) {
-      zret  = _head;
-      _head = _head->*N;
-      if (_head)
-        _head->*P = 0;
-      else
-        _tail = 0;  // non-empty to empty transition.
-      zret->*N = 0; // erase traces of list.
-      zret->*P = 0;
-      --_count;
-    }
-    return zret;
-  }
+  value_type *take_head();
+
   /// Remove the last element of the list.
   /// @return A poiner to the removed item, or @c nullptr if the list was empty.
-  T *
-  takeTail()
-  {
-    T *zret = 0;
-    if (_tail) {
-      zret  = _tail;
-      _tail = _tail->*P = 0;
-      if (_tail)
-        _tail->*N = 0;
-      else
-        _head = 0;  // non-empty to empty transition.
-      zret->*N = 0; // erase traces of list.
-      zret->*P = 0;
-      --_count;
-    }
-    return zret;
-  }
+  value_type *take_tail();
+
   /// Insert a new element @a elt after @a target.
-  /// The caller is responsible for ensuring @a target is in this list
-  /// and @a elt is not in a list.
+  /// The caller is responsible for ensuring @a target is in this list and @a elt is not in a list.
   /// @return This list.
-  self &
-  insertAfter(T *target, ///< Target element in list.
-              T *elt     ///< Element to insert.
-  )
-  {
-    // Should assert that !(elt->*N || elt->*P)
-    elt->*N    = target->*N;
-    elt->*P    = target;
-    target->*N = elt;
-    if (elt->*N)
-      elt->*N->*P = elt;
-    if (target == _tail)
-      _tail = elt;
-    ++_count;
-    return *this;
-  }
-  /// Insert a new element @a elt before @a target.
-  /// The caller is responsible for ensuring @a target is in this list
-  /// and @a elt is not in a list.
+  self_type &insert_after(value_type *target, value_type *v);
+
+  /// Insert a new element @a v before @a target.
+  /// The caller is responsible for ensuring @a target is in this list and @a elt is not in a list.
   /// @return This list.
-  self &
-  insertBefore(T *target, ///< Target element in list.
-               T *elt     ///< Element to insert.
-  )
-  {
-    // Should assert that !(elt->*N || elt->*P)
-    elt->*P    = target->*P;
-    elt->*N    = target;
-    target->*P = elt;
-    if (elt->*P)
-      elt->*P->*N = elt;
-    if (target == _head)
-      _head = elt;
-    ++_count;
-    return *this;
-  }
+  self_type &insert_before(value_type *target, value_type *v);
+
+  /// Insert a new element @a elt after @a target.
+  /// If @a target is the end iterator, @a v is appended to the list.
+  /// @return This list.
+  self_type &insert_after(iterator const &target, value_type *v);
+
+  /// Insert a new element @a v before @a target.
+  /// If @a target is the end iterator, @a v is appended to the list.
+  /// @return This list.
+  self_type &insert_before(iterator const &target, value_type *v);
+
   /// Take @a elt out of this list.
   /// @return This list.
-  self &
-  take(T *elt ///< Element to remove.
-  )
-  {
-    if (elt->*P)
-      elt->*P->*N = elt->*N;
-    if (elt->*N)
-      elt->*N->*P = elt->*P;
-    if (elt == _head)
-      _head = elt->*N;
-    if (elt == _tail)
-      _tail = elt->*P;
-    elt->*P = elt->*N = nullptr;
-    --_count;
-    return *this;
-  }
+  self_type &erase(value_type *v);
+
   /// Remove all elements.
   /// @note @b No memory management is done!
   /// @return This container.
-  self &
-  clear()
-  {
-    _head = _tail = nullptr;
-    _count        = 0;
-    return *this;
-  }
+  self_type &clear();
+
   /// @return Number of elements in the list.
-  size_t
-  getCount() const
-  {
-    return _count;
-  }
+  size_t count() const;
 
   /// Get an iterator to the first element.
-  iterator
-  begin()
-  {
-    return iterator(this, _head);
+  iterator begin();
+
+  /// Get an iterator to the first element.
+  const_iterator begin() const;
+
+  /// Get an iterator past the last element.
+  iterator end();
+
+  /// Get an iterator past the last element.
+  const_iterator end() const;
+
+  /** Get an iterator for the item @a v.
+   *
+   * It is the responsibility of the caller that @a v is in the list. The purpose is to make iteration starting
+   * at a specific element easier (i.e. all of the link manipulation and checking is done by the iterator).
+   *
+   * @return An @c iterator that refers to @a v.
+   */
+  iterator iterator_for(value_type *v);
+  const_iterator iterator_for(const value_type *v) const;
+
+  /// Get the first element.
+  value_type *head();
+
+  /// Get the last element.
+  value_type *tail();
+
+protected:
+  value_type *_head{nullptr}; ///< First element in list.
+  value_type *_tail{nullptr}; ///< Last element in list.
+  size_t _count{0};           ///< # of elements in list.
+};
+
+template <typename L> IntrusiveDList<L>::const_iterator::const_iterator() {}
+
+template <typename L>
+IntrusiveDList<L>::const_iterator::const_iterator(const list_type *list, value_type *v)
+  : _list(const_cast<list_type *>(list)), _v(const_cast<typename list_type::value_type *>(v))
+{
+}
+
+template <typename L> IntrusiveDList<L>::iterator::iterator() {}
+
+template <typename L> IntrusiveDList<L>::iterator::iterator(IntrusiveDList *list, value_type *v) : super_type(list, v) {}
+
+template <typename L>
+auto
+IntrusiveDList<L>::const_iterator::operator++() -> self_type &
+{
+  _v = L::next_ptr(_v);
+  return *this;
+}
+
+template <typename L>
+auto
+IntrusiveDList<L>::iterator::operator++() -> self_type &
+{
+  this->super_type::operator++();
+  return *this;
+}
+
+template <typename L>
+auto
+IntrusiveDList<L>::const_iterator::operator++(int) -> self_type
+{
+  self_type tmp(*this);
+  ++*this;
+  return tmp;
+}
+
+template <typename L>
+auto
+IntrusiveDList<L>::iterator::operator++(int) -> self_type
+{
+  self_type tmp(*this);
+  ++*this;
+  return tmp;
+}
+
+template <typename L>
+auto
+IntrusiveDList<L>::const_iterator::operator--() -> self_type &
+{
+  if (_v) {
+    _v = L::prev_ptr(_v);
+  } else if (_list) {
+    _v = _list->_tail;
   }
-  /// Get an iterator to past the last element.
-  iterator
-  end()
-  {
-    return iterator(this, 0);
+  return *this;
+}
+
+template <typename L>
+auto
+IntrusiveDList<L>::iterator::operator--() -> self_type &
+{
+  this->super_type::operator--();
+  return *this;
+}
+
+template <typename L>
+auto
+IntrusiveDList<L>::const_iterator::operator--(int) -> self_type
+{
+  self_type tmp(*this);
+  --*this;
+  return tmp;
+}
+
+template <typename L>
+auto
+IntrusiveDList<L>::iterator::operator--(int) -> self_type
+{
+  self_type tmp(*this);
+  --*this;
+  return tmp;
+}
+
+template <typename L> auto IntrusiveDList<L>::const_iterator::operator-> () const -> value_type *
+{
+  return _v;
+}
+
+template <typename L> auto IntrusiveDList<L>::iterator::operator-> () const -> value_type *
+{
+  return super_type::_v;
+}
+
+template <typename L> auto IntrusiveDList<L>::const_iterator::operator*() const -> value_type &
+{
+  return *_v;
+}
+
+template <typename L> auto IntrusiveDList<L>::iterator::operator*() const -> value_type &
+{
+  return *super_type::_v;
+}
+
+template <typename L>
+bool
+IntrusiveDList<L>::empty() const
+{
+  return _head == nullptr;
+}
+
+template <typename L>
+bool
+IntrusiveDList<L>::contains(value_type *v) const
+{
+  for (auto thing = _head; thing; thing = L::next_ptr(thing)) {
+    if (thing == v)
+      return true;
   }
-  /// Get the first element.
-  T *
-  getHead()
-  {
-    return _head;
+  return false;
+}
+
+template <typename L>
+bool
+IntrusiveDList<L>::const_iterator::operator==(self_type const &that) const
+{
+  return this->_v == that._v;
+}
+
+template <typename L>
+bool
+IntrusiveDList<L>::const_iterator::operator!=(self_type const &that) const
+{
+  return this->_v != that._v;
+}
+
+template <typename L>
+auto
+IntrusiveDList<L>::prepend(value_type *v) -> self_type &
+{
+  L::prev_ptr(v) = nullptr;
+  if (nullptr != (L::next_ptr(v) = _head)) {
+    L::prev_ptr(_head) = v;
+  } else {
+    _tail = v; // transition empty -> non-empty
   }
-  /// Get the last element.
-  T *
-  getTail()
-  {
-    return _tail;
+  _head = v;
+  ++_count;
+  return *this;
+}
+
+template <typename L>
+auto
+IntrusiveDList<L>::append(value_type *v) -> self_type &
+{
+  L::next_ptr(v) = nullptr;
+  if (nullptr != (L::prev_ptr(v) = _tail)) {
+    L::next_ptr(_tail) = v;
+  } else {
+    _head = v; // transition empty -> non-empty
   }
+  _tail = v;
+  ++_count;
+  return *this;
+}
 
-protected:
-  T *_head;      ///< First element in list.
-  T *_tail;      ///< Last element in list.
-  size_t _count; ///< # of elements in list.
+template <typename L>
+auto
+IntrusiveDList<L>::take_head() -> value_type *
+{
+  value_type *zret = _head;
+  if (_head) {
+    if (nullptr == (_head = L::next_ptr(_head))) {
+      _tail = nullptr; // transition non-empty -> empty
+    } else {
+      L::prev_ptr(_head) = nullptr;
+    }
+    L::next_ptr(zret) = L::prev_ptr(zret) = nullptr;
+    --_count;
+  }
+  return zret;
+}
+
+template <typename L>
+auto
+IntrusiveDList<L>::take_tail() -> value_type *
+{
+  value_type *zret = _tail;
+  if (_tail) {
+    if (nullptr == (_tail = L::prev_ptr(_tail))) {
+      _head = nullptr; // transition non-empty -> empty
+    } else {
+      L::next_ptr(_tail) = nullptr;
+    }
+    L::next_ptr(zret) = L::prev_ptr(zret) = nullptr;
+    --_count;
+  }
+  return zret;
+}
+
+template <typename L>
+auto
+IntrusiveDList<L>::insert_after(value_type *target, value_type *v) -> self_type &
+{
+  if (target) {
+    if (nullptr != (L::next_ptr(v) = L::next_ptr(target))) {
+      L::prev_ptr(L::next_ptr(v)) = v;
+    } else if (_tail == target) {
+      _tail = v;
+    }
+    L::prev_ptr(v)      = target;
+    L::next_ptr(target) = v;
+
+    ++_count;
+  } else {
+    this->append(v);
+  }
+  return *this;
+}
+
+template <typename L>
+auto
+IntrusiveDList<L>::insert_after(iterator const &target, value_type *v) -> self_type &
+{
+  return this->insert_after(target._v, v);
+}
+
+template <typename L>
+auto
+IntrusiveDList<L>::insert_before(value_type *target, value_type *v) -> self_type &
+{
+  if (target) {
+    if (nullptr != (L::prev_ptr(v) = L::prev_ptr(target))) {
+      L::next_ptr(L::prev_ptr(v)) = v;
+    } else if (target == _head) {
+      _head = v;
+    }
+    L::next_ptr(v)      = target;
+    L::prev_ptr(target) = v;
+
+    ++_count;
+  } else {
+    this->append(v);
+  }
+  return *this;
+}
+
+template <typename L>
+auto
+IntrusiveDList<L>::insert_before(iterator const &target, value_type *v) -> self_type &
+{
+  return this->insert_before(target._v, v);
+}
+
+template <typename L>
+auto
+IntrusiveDList<L>::erase(value_type *v) -> self_type &
+{
+  if (L::prev_ptr(v)) {
+    L::next_ptr(L::prev_ptr(v)) = L::next_ptr(v);
+  }
+  if (L::next_ptr(v)) {
+    L::prev_ptr(L::next_ptr(v)) = L::prev_ptr(v);
+  }
+  if (v == _head) {
+    _head = L::next_ptr(v);
+  }
+  if (v == _tail) {
+    _tail = L::prev_ptr(v);
+  }
+  L::prev_ptr(v) = L::next_ptr(v) = nullptr;
+  --_count;
+
+  return *this;
+}
+
+template <typename L>
+size_t
+IntrusiveDList<L>::count() const
+{
+  return _count;
+};
+
+template <typename L>
+auto
+IntrusiveDList<L>::begin() const -> const_iterator
+{
+  return const_iterator{this, _head};
+};
+
+template <typename L>
+auto
+IntrusiveDList<L>::begin() -> iterator
+{
+  return iterator{this, _head};
+};
+
+template <typename L>
+auto
+IntrusiveDList<L>::end() const -> const_iterator
+{
+  return const_iterator{this, nullptr};
+};
+
+template <typename L>
+auto
+IntrusiveDList<L>::end() -> iterator
+{
+  return iterator{this, nullptr};
+};
+
+template <typename L>
+auto
+IntrusiveDList<L>::iterator_for(value_type *v) -> iterator
+{
+  return iterator{this, v};
+};
+
+template <typename L>
+auto
+IntrusiveDList<L>::iterator_for(const value_type *v) const -> const_iterator
+{
+  return const_iterator{this, v};
+};
+
+template <typename L>
+auto
+IntrusiveDList<L>::tail() -> value_type *
+{
+  return _tail;
+}
+
+template <typename L>
+auto
+IntrusiveDList<L>::head() -> value_type *
+{
+  return _head;
+}
+
+template <typename L>
+auto
+IntrusiveDList<L>::clear() -> self_type &
+{
+  _head = _tail = nullptr;
+  _count        = 0;
+  return *this;
 };
diff --git a/lib/ts/IpMap.cc b/lib/ts/IpMap.cc
index b61c98c..5d5ca3c 100644
--- a/lib/ts/IpMap.cc
+++ b/lib/ts/IpMap.cc
@@ -199,15 +199,15 @@ namespace detail
         Caller is responsible for ensuring that @a spot is in this container
         and the proper location for @a n.
     */
-    void insertAfter(N *spot, ///< Node in list.
-                     N *n     ///< Node to insert.
+    void insert_after(N *spot, ///< Node in list.
+                      N *n     ///< Node to insert.
     );
     /** Insert @a n before @a spot.
         Caller is responsible for ensuring that @a spot is in this container
         and the proper location for @a n.
     */
-    void insertBefore(N *spot, ///< Node in list.
-                      N *n     ///< Node to insert.
+    void insert_before(N *spot, ///< Node in list.
+                       N *n     ///< Node to insert.
     );
     /// Add node @a n as the first node.
     void prepend(N *n);
@@ -223,7 +223,7 @@ namespace detail
     void validate();
 
     /// @return The number of distinct ranges.
-    size_t getCount() const;
+    size_t count() const;
 
     /// Print all spans.
     /// @return This map.
@@ -256,21 +256,34 @@ namespace detail
       return static_cast<N *>(n->_right);
     }
     N *
-    getHead()
+    head()
     {
-      return static_cast<N *>(_list.getHead());
+      return static_cast<N *>(_list.head());
     }
     N *
-    getTail()
+    tail()
     {
-      return static_cast<N *>(_list.getTail());
+      return static_cast<N *>(_list.tail());
     }
 
     N *_root; ///< Root node.
     /// In order list of nodes.
     /// For ugly compiler reasons, this is a list of base class pointers
     /// even though we really store @a N instances on it.
-    typedef IntrusiveDList<RBNode, &RBNode::_next, &RBNode::_prev> NodeList;
+    struct NodeLinkage {
+      static RBNode *&
+      next_ptr(RBNode *n)
+      {
+        return n->_next;
+      }
+      static RBNode *&
+      prev_ptr(RBNode *n)
+      {
+        return n->_prev;
+      }
+    };
+    using NodeList = IntrusiveDList<NodeLinkage>;
+    //    typedef IntrusiveDList<RBNode, &RBNode::_next, &RBNode::_prev> NodeList;
     /// This keeps track of all allocated nodes in order.
     /// Iteration depends on this list being maintained.
     NodeList _list;
@@ -302,7 +315,7 @@ namespace detail
   IpMapBase<N>::clear()
   {
     // Delete everything.
-    N *n = static_cast<N *>(_list.getHead());
+    N *n = static_cast<N *>(_list.head());
     while (n) {
       N *x = n;
       n    = next(n);
@@ -344,7 +357,7 @@ namespace detail
         }
       }
     } else {
-      n = this->getHead();
+      n = this->head();
     }
 
     // Work through the rest of the nodes of interest.
@@ -386,7 +399,7 @@ namespace detail
             n->setMin(min);
             return *this;
           } else { // no overlap, space to complete range.
-            this->insertBefore(n, new N(min, max, payload));
+            this->insert_before(n, new N(min, max, payload));
             return *this;
           }
         }
@@ -407,13 +420,13 @@ namespace detail
           }
         } else {               // no carry node.
           if (max < n->_min) { // entirely before next span.
-            this->insertBefore(n, new N(min, max, payload));
+            this->insert_before(n, new N(min, max, payload));
             return *this;
           } else {
             if (min < n->_min) { // leading section, need node.
               N *y = new N(min, n->_min, payload);
               y->decrementMax();
-              this->insertBefore(n, y);
+              this->insert_before(n, y);
             }
             if (max <= n->_max) { // nothing past node
               return *this;
@@ -485,7 +498,7 @@ namespace detail
           // request span is covered by existing span.
           x = new N(min, max, payload); //
           n->setMin(max_plus);          // clip existing.
-          this->insertBefore(n, x);
+          this->insert_before(n, x);
           return *this;
         }
       } else if (n->_data == payload && n->_max >= min_1) {
@@ -517,20 +530,20 @@ namespace detail
         x = new N(min, max, payload);
         r = new N(max_plus, n->_max, n->_data);
         n->setMax(min_1);
-        this->insertAfter(n, x);
-        this->insertAfter(x, r);
+        this->insert_after(n, x);
+        this->insert_after(x, r);
         return *this; // done.
       }
       n = next(n); // lower bound span handled, move on.
       if (!x) {
         x = new N(min, max, payload);
         if (n) {
-          this->insertBefore(n, x);
+          this->insert_before(n, x);
         } else {
           this->append(x); // note that since n == 0 we'll just return.
         }
       }
-    } else if (nullptr != (n = this->getHead()) &&     // at least one node in tree.
+    } else if (nullptr != (n = this->head()) &&        // at least one node in tree.
                n->_data == payload &&                  // payload matches
                (n->_max <= max || n->_min <= max_plus) // overlap or adj.
     ) {
@@ -584,7 +597,7 @@ namespace detail
           x = new N(max, N::argue(n->_max), n->_data);
           x->incrementMin();
           n->setMaxMinusOne(N::deref(min));
-          this->insertAfter(n, x);
+          this->insert_after(n, x);
           return *this; // done.
         } else {
           n->setMaxMinusOne(N::deref(min)); // just clip overlap.
@@ -610,7 +623,7 @@ namespace detail
 
   template <typename N>
   void
-  IpMapBase<N>::insertAfter(N *spot, N *n)
+  IpMapBase<N>::insert_after(N *spot, N *n)
   {
     N *c = right(spot);
     if (!c) {
@@ -619,13 +632,13 @@ namespace detail
       spot->_next->setChild(n, N::LEFT);
     }
 
-    _list.insertAfter(spot, n);
+    _list.insert_after(spot, n);
     _root = static_cast<N *>(n->rebalanceAfterInsert());
   }
 
   template <typename N>
   void
-  IpMapBase<N>::insertBefore(N *spot, N *n)
+  IpMapBase<N>::insert_before(N *spot, N *n)
   {
     N *c = left(spot);
     if (!c) {
@@ -634,7 +647,7 @@ namespace detail
       spot->_prev->setChild(n, N::RIGHT);
     }
 
-    _list.insertBefore(spot, n);
+    _list.insert_before(spot, n);
     _root = static_cast<N *>(n->rebalanceAfterInsert());
   }
 
@@ -645,7 +658,7 @@ namespace detail
     if (!_root) {
       _root = n;
     } else {
-      _root = static_cast<N *>(_list.getHead()->setChild(n, N::LEFT)->rebalanceAfterInsert());
+      _root = static_cast<N *>(_list.head()->setChild(n, N::LEFT)->rebalanceAfterInsert());
     }
     _list.prepend(n);
   }
@@ -657,7 +670,7 @@ namespace detail
     if (!_root) {
       _root = n;
     } else {
-      _root = static_cast<N *>(_list.getTail()->setChild(n, N::RIGHT)->rebalanceAfterInsert());
+      _root = static_cast<N *>(_list.tail()->setChild(n, N::RIGHT)->rebalanceAfterInsert());
     }
     _list.append(n);
   }
@@ -667,7 +680,7 @@ namespace detail
   IpMapBase<N>::remove(N *n)
   {
     _root = static_cast<N *>(n->remove());
-    _list.take(n);
+    _list.erase(n);
     delete n;
   }
 
@@ -695,9 +708,9 @@ namespace detail
 
   template <typename N>
   size_t
-  IpMapBase<N>::getCount() const
+  IpMapBase<N>::count() const
   {
-    return _list.getCount();
+    return _list.count();
   }
   //----------------------------------------------------------------------------
   template <typename N>
@@ -706,7 +719,7 @@ namespace detail
   {
 #if 0
   if (_root) _root->validate();
-  for ( Node* n = _list.getHead() ; n ; n = n->_next ) {
+  for ( Node* n = _list.head() ; n ; n = n->_next ) {
     Node* x;
     if (0 != (x = n->_next)) {
       if (x->_prev != n)
@@ -725,7 +738,7 @@ namespace detail
   IpMapBase<N>::print()
   {
 #if 0
-  for ( Node* n = _list.getHead() ; n ; n = n->_next ) {
+  for ( Node* n = _list.head() ; n ; n = n->_next ) {
     std::cout
       << n << ": " << n->_min << '-' << n->_max << " [" << n->_data << "] "
       << (n->_color == Node::BLACK ? "Black " : "Red   ") << "P=" << n->_parent << " L=" << n->_left << " R=" << n->_right
@@ -1174,14 +1187,14 @@ IpMap::fill(in_addr_t min, in_addr_t max, void *data)
 }
 
 size_t
-IpMap::getCount() const
+IpMap::count() const
 {
   size_t zret = 0;
   if (_m4) {
-    zret += _m4->getCount();
+    zret += _m4->count();
   }
   if (_m6) {
-    zret += _m6->getCount();
+    zret += _m6->count();
   }
   return zret;
 }
@@ -1203,10 +1216,10 @@ IpMap::begin() const
 {
   Node *x = nullptr;
   if (_m4) {
-    x = _m4->getHead();
+    x = _m4->head();
   }
   if (!x && _m6) {
-    x = _m6->getHead();
+    x = _m6->head();
   }
   return iterator(this, x);
 }
@@ -1218,8 +1231,8 @@ IpMap::iterator::operator++()
     // If we go past the end of the list see if it was the v4 list
     // and if so, move to the v6 list (if it's there).
     Node *x = static_cast<Node *>(_node->_next);
-    if (!x && _tree->_m4 && _tree->_m6 && _node == _tree->_m4->getTail()) {
-      x = _tree->_m6->getHead();
+    if (!x && _tree->_m4 && _tree->_m6 && _node == _tree->_m4->tail()) {
+      x = _tree->_m6->head();
     }
     _node = x;
   }
@@ -1233,17 +1246,17 @@ IpMap::iterator::operator--()
     // At a node, try to back up. Handle the case where we back over the
     // start of the v6 addresses and switch to the v4, if there are any.
     Node *x = static_cast<Node *>(_node->_prev);
-    if (!x && _tree->_m4 && _tree->_m6 && _node == _tree->_m6->getHead()) {
-      x = _tree->_m4->getTail();
+    if (!x && _tree->_m4 && _tree->_m6 && _node == _tree->_m6->head()) {
+      x = _tree->_m4->tail();
     }
     _node = x;
   } else if (_tree) {
     // We were at the end. Back up to v6 if possible, v4 if not.
     if (_tree->_m6) {
-      _node = _tree->_m6->getTail();
+      _node = _tree->_m6->tail();
     }
     if (!_node && _tree->_m4) {
-      _node = _tree->_m4->getTail();
+      _node = _tree->_m4->tail();
     }
   }
   return *this;
diff --git a/lib/ts/IpMap.h b/lib/ts/IpMap.h
index cab828f..156da83 100644
--- a/lib/ts/IpMap.h
+++ b/lib/ts/IpMap.h
@@ -335,7 +335,7 @@ public:
   /// Iterator past last element.
   iterator end() const;
   /// @return Number of distinct ranges in the map.
-  size_t getCount() const;
+  size_t count() const;
 
   /** Validate internal data structures.
       @note Intended for debugging, not general client use.
diff --git a/lib/ts/Makefile.am b/lib/ts/Makefile.am
index 797c4e3..e0bebb8 100644
--- a/lib/ts/Makefile.am
+++ b/lib/ts/Makefile.am
@@ -269,6 +269,7 @@ test_tslib_SOURCES = \
 	unit-tests/test_BufferWriter.cc \
 	unit-tests/test_BufferWriterFormat.cc \
 	unit-tests/test_ink_inet.cc \
+	unit-tests/test_IntrusiveDList.cc \
 	unit-tests/test_IntrusivePtr.cc \
 	unit-tests/test_IpMap.cc \
 	unit-tests/test_layout.cc \
diff --git a/lib/ts/unit-tests/test_IntrusiveDList.cc b/lib/ts/unit-tests/test_IntrusiveDList.cc
new file mode 100644
index 0000000..afbf24f
--- /dev/null
+++ b/lib/ts/unit-tests/test_IntrusiveDList.cc
@@ -0,0 +1,274 @@
+/** @file
+
+    IntrusiveDList 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 <ts/IntrusiveDList.h>
+#include <ts/BufferWriter.h>
+
+#include <catch.hpp>
+
+// --------------------
+// Code for documentation - placed here to guarantee the examples at least compile.
+// First so that additional tests do not require updating the documentation source links.
+
+class Message
+{
+  using self_type = Message;
+
+public:
+  // Message severity level.
+  enum Severity { LVL_DEBUG, LVL_INFO, LVL_WARN, LVL_ERROR };
+
+protected:
+  std::string _text; // Text of the message.
+  Severity _severity{LVL_DEBUG};
+  int _indent{0}; // indentation level for display.
+
+  // Intrusive list support.
+  struct Linkage {
+    static self_type *&next_ptr(self_type *); // Link accessor.
+    static self_type *&prev_ptr(self_type *); // Link accessor.
+
+    self_type *_next{nullptr}; // Forward link.
+    self_type *_prev{nullptr}; // Backward link.
+  } _link;
+
+  bool is_in_list() const;
+
+  friend class Container;
+};
+
+auto
+Message::Linkage::next_ptr(self_type *that) -> self_type *&
+{
+  return that->_link._next;
+}
+auto
+Message::Linkage::prev_ptr(self_type *that) -> self_type *&
+{
+  return that->_link._prev;
+}
+
+bool
+Message::is_in_list() const
+{
+  return _link._next || _link._prev;
+}
+
+class Container
+{
+  using self_type   = Container;
+  using MessageList = IntrusiveDList<Message::Linkage>;
+
+public:
+  ~Container();
+
+  template <typename... Args> self_type &debug(std::string_view fmt, Args &&... args);
+
+  size_t count() const;
+  self_type &clear();
+
+protected:
+  MessageList _msgs;
+};
+
+Container::~Container()
+{
+  this->clear(); // clean up memory.
+}
+
+auto
+Container::clear() -> self_type &
+{
+  for (auto &&msg : _msgs) {
+    delete &msg;
+  }
+  _msgs.clear();
+  return *this;
+}
+
+size_t
+Container::count() const
+{
+  return _msgs.count();
+}
+
+template <typename... Args>
+auto
+Container::debug(std::string_view fmt, Args &&... args) -> self_type &
+{
+  Message *msg = new Message;
+  ts::bwprintv(msg->_text, fmt, std::forward_as_tuple(args...));
+  msg->_severity = Message::LVL_DEBUG;
+  _msgs.append(msg);
+  return *this;
+}
+
+TEST_CASE("IntrusiveDList Example", "[libts][IntrusiveDList]")
+{
+  Container container;
+
+  container.debug("This is message {}", 1);
+  REQUIRE(container.count() == 1);
+  // Destructor is checked for non-crashing as container goes out of scope.
+}
+
+// --------------------
+
+struct Thing {
+  Thing *_next{nullptr};
+  Thing *_prev{nullptr};
+  std::string _payload;
+
+  Thing(std::string_view text) : _payload(text) {}
+
+  struct Linkage {
+    static Thing *&
+    next_ptr(Thing *t)
+    {
+      return t->_next;
+    }
+    static Thing *&
+    prev_ptr(Thing *t)
+    {
+      return t->_prev;
+    }
+  };
+};
+
+// Just for you, @maskit ! Demonstrating non-public links and subclassing.
+class PrivateThing : protected Thing
+{
+  using self_type  = PrivateThing;
+  using super_type = Thing;
+
+public:
+  PrivateThing(std::string_view text) : super_type(text) {}
+
+  struct Linkage {
+    static self_type *&
+    next_ptr(self_type *t)
+    {
+      return *reinterpret_cast<self_type **>(&t->_next);
+    }
+    static self_type *&
+    prev_ptr(self_type *t)
+    {
+      return *reinterpret_cast<self_type **>(&t->_prev);
+    }
+  };
+
+  std::string const &
+  payload() const
+  {
+    return _payload;
+  }
+};
+
+using ThingList        = IntrusiveDList<Thing::Linkage>;
+using PrivateThingList = IntrusiveDList<PrivateThing::Linkage>;
+
+TEST_CASE("IntrusiveDList", "[libts][IntrusiveDList]")
+{
+  ThingList list;
+  int n;
+
+  REQUIRE(list.count() == 0);
+  REQUIRE(list.head() == nullptr);
+  REQUIRE(list.tail() == nullptr);
+  REQUIRE(list.begin() == list.end());
+  REQUIRE(list.empty());
+
+  n = 0;
+  for ([[maybe_unused]] auto &thing : list)
+    ++n;
+  REQUIRE(n == 0);
+  // Check const iteration (mostly compile checks here).
+  for ([[maybe_unused]] auto &thing : static_cast<ThingList const &>(list))
+    ++n;
+  REQUIRE(n == 0);
+
+  list.append(new Thing("one"));
+  REQUIRE(list.begin() != list.end());
+  REQUIRE(list.tail() == list.head());
+
+  list.prepend(new Thing("two"));
+  REQUIRE(list.count() == 2);
+  REQUIRE(list.head()->_payload == "two");
+  REQUIRE(list.tail()->_payload == "one");
+  list.prepend(list.take_tail());
+  REQUIRE(list.head()->_payload == "one");
+  REQUIRE(list.tail()->_payload == "two");
+  list.insert_after(list.head(), new Thing("middle"));
+  list.insert_before(list.tail(), new Thing("muddle"));
+  REQUIRE(list.count() == 4);
+  auto spot = list.begin();
+  REQUIRE((*spot++)._payload == "one");
+  REQUIRE((*spot++)._payload == "middle");
+  REQUIRE((*spot++)._payload == "muddle");
+  REQUIRE((*spot++)._payload == "two");
+  REQUIRE(spot == list.end());
+
+  Thing *thing = list.take_head();
+  REQUIRE(thing->_payload == "one");
+  REQUIRE(list.count() == 3);
+  REQUIRE(list.head() != nullptr);
+  REQUIRE(list.head()->_payload == "middle");
+
+  list.prepend(thing);
+  list.erase(list.head());
+  REQUIRE(list.count() == 3);
+  REQUIRE(list.head() != nullptr);
+  REQUIRE(list.head()->_payload == "middle");
+  list.prepend(thing);
+
+  thing = list.take_tail();
+  REQUIRE(thing->_payload == "two");
+  REQUIRE(list.count() == 3);
+  REQUIRE(list.tail() != nullptr);
+  REQUIRE(list.tail()->_payload == "muddle");
+
+  list.append(thing);
+  list.erase(list.tail());
+  REQUIRE(list.count() == 3);
+  REQUIRE(list.tail() != nullptr);
+  REQUIRE(list.tail()->_payload == "muddle");
+  REQUIRE(list.head()->_payload == "one");
+
+  list.insert_before(list.end(), new Thing("trailer"));
+  REQUIRE(list.count() == 4);
+  REQUIRE(list.tail()->_payload == "trailer");
+
+  PrivateThingList priv_list;
+  for (int i = 1; i <= 23; ++i) {
+    std::string name;
+    ts::bwprint(name, "Item {}", i);
+    priv_list.append(new PrivateThing(name));
+    REQUIRE(priv_list.count() == i);
+  }
+  REQUIRE(priv_list.head()->payload() == "Item 1");
+  REQUIRE(priv_list.tail()->payload() == "Item 23");
+}
diff --git a/lib/ts/unit-tests/test_IpMap.cc b/lib/ts/unit-tests/test_IpMap.cc
index 28fa5c0..05aa2da 100644
--- a/lib/ts/unit-tests/test_IpMap.cc
+++ b/lib/ts/unit-tests/test_IpMap.cc
@@ -135,7 +135,7 @@ TEST_CASE("IpMap Basic", "[libts][ipmap]")
   map.mark(ip5, ip9, markA);
   {
     INFO("Coalesce failed");
-    CHECK(map.getCount() == 1);
+    CHECK(map.count() == 1);
   }
   {
     INFO("Range max not found.");
@@ -153,7 +153,7 @@ TEST_CASE("IpMap Basic", "[libts][ipmap]")
   map.fill(ip15, ip100, markB);
   {
     INFO("Fill failed.");
-    CHECK(map.getCount() == 2);
+    CHECK(map.count() == 2);
   }
   {
     INFO("fill interior missing");
@@ -179,13 +179,13 @@ TEST_CASE("IpMap Basic", "[libts][ipmap]")
   map.clear();
   {
     INFO("Clear failed.");
-    CHECK(map.getCount() == 0);
+    CHECK(map.count() == 0);
   }
 
   map.mark(ip20, ip50, markA);
   map.mark(ip100, ip150, markB);
   map.fill(ip10, ip200, markC);
-  CHECK(map.getCount() == 5);
+  CHECK(map.count() == 5);
   {
     INFO("Left span missing");
     CHECK(map.contains(ip15, &mark));
@@ -214,7 +214,7 @@ TEST_CASE("IpMap Basic", "[libts][ipmap]")
   map.unmark(ip140, ip160);
   {
     INFO("unmark failed");
-    CHECK(map.getCount() == 5);
+    CHECK(map.count() == 5);
   }
   {
     INFO("unmark left edge still there.");
@@ -247,7 +247,7 @@ TEST_CASE("IpMap Basic", "[libts][ipmap]")
   map.mark(ip0, ipmax, markC);
   {
     INFO("IpMap: Full range fill left extra ranges.");
-    CHECK(map.getCount() == 1);
+    CHECK(map.count() == 1);
   }
 }
 
@@ -285,12 +285,12 @@ TEST_CASE("IpMap Unmark", "[libts][ipmap]")
   map.mark(&a_0, &a_max, markA);
   {
     INFO("IpMap Unmark: Full range not single.");
-    CHECK(map.getCount() == 1);
+    CHECK(map.count() == 1);
   }
   map.unmark(&a_10_28_56_0, &a_10_28_56_255);
   {
     INFO("IpMap Unmark: Range unmark failed.");
-    CHECK(map.getCount() == 2);
+    CHECK(map.count() == 2);
   }
   // Generic range check.
   {
@@ -420,7 +420,7 @@ TEST_CASE("IpMap Fill", "[libts][ipmap]")
     map.fill(&a0, &a_max, markC);
     {
       INFO("IpMap[2]: Fill failed.");
-      CHECK(map.getCount() == 5);
+      CHECK(map.count() == 5);
     }
     {
       INFO("invalid mark in range gap");
@@ -443,7 +443,7 @@ TEST_CASE("IpMap Fill", "[libts][ipmap]")
     map.fill(&a0, &a_max, deny);
     {
       INFO("range count incorrect");
-      CHECK(map.getCount() == 5);
+      CHECK(map.count() == 5);
     }
     {
       INFO("mark between ranges");
@@ -485,7 +485,7 @@ TEST_CASE("IpMap Fill", "[libts][ipmap]")
 
     {
       INFO("IpMap Fill[pre-refill]: Bad range count.");
-      CHECK(map.getCount() == 10);
+      CHECK(map.count() == 10);
     }
     // These should be ignored by the map as it is completely covered for IPv6.
     map.fill(&a_fe80_9d90, &a_fe80_9d9d, markA);
@@ -493,7 +493,7 @@ TEST_CASE("IpMap Fill", "[libts][ipmap]")
     map.fill(&a_0000_0000, &a_ffff_ffff, markB);
     {
       INFO("IpMap Fill[post-refill]: Bad range count.");
-      CHECK(map.getCount() == 10);
+      CHECK(map.count() == 10);
     }
   }
 
@@ -601,5 +601,5 @@ TEST_CASE("IpMap CloseIntersection", "[libts][ipmap]")
   map.mark(d_2_l, d_2_u, markD);
   CHECK_THAT(map, IsMarkedAt(a_1_m));
 
-  CHECK(map.getCount() == 13);
+  CHECK(map.count() == 13);
 }
diff --git a/proxy/ControlMatcher.cc b/proxy/ControlMatcher.cc
index d96f139..d717d1d 100644
--- a/proxy/ControlMatcher.cc
+++ b/proxy/ControlMatcher.cc
@@ -667,7 +667,7 @@ template <class Data, class MatchResult>
 void
 IpMatcher<Data, MatchResult>::Print()
 {
-  printf("\tIp Matcher with %d elements, %zu ranges.\n", num_el, ip_map.getCount());
+  printf("\tIp Matcher with %d elements, %zu ranges.\n", num_el, ip_map.count());
   for (IpMap::iterator spot(ip_map.begin()), limit(ip_map.end()); spot != limit; ++spot) {
     char b1[INET6_ADDRSTRLEN], b2[INET6_ADDRSTRLEN];
     printf("\tRange %s - %s ", ats_ip_ntop(spot->min(), b1, sizeof b1), ats_ip_ntop(spot->max(), b2, sizeof b2));
diff --git a/proxy/IPAllow.cc b/proxy/IPAllow.cc
index acb4281..09fe6f6 100644
--- a/proxy/IPAllow.cc
+++ b/proxy/IPAllow.cc
@@ -111,7 +111,7 @@ void
 IpAllow::PrintMap(IpMap *map)
 {
   std::ostringstream s;
-  s << map->getCount() << " ACL entries.";
+  s << map->count() << " ACL entries.";
   for (auto &spot : *map) {
     char text[INET6_ADDRSTRLEN];
     AclRecord const *ar = static_cast<AclRecord const *>(spot.data());
@@ -178,7 +178,7 @@ IpAllow::BuildTable()
   bool alarmAlready = false;
 
   // Table should be empty
-  ink_assert(_src_map.getCount() == 0 && _dest_map.getCount() == 0);
+  ink_assert(_src_map.count() == 0 && _dest_map.count() == 0);
 
   file_buf = readIntoBuffer(config_file_path, module_name, nullptr);
 
@@ -297,7 +297,7 @@ IpAllow::BuildTable()
     line = tokLine(nullptr, &tok_state);
   }
 
-  if (_src_map.getCount() == 0 && _dest_map.getCount() == 0) { // TODO: check
+  if (_src_map.count() == 0 && _dest_map.count() == 0) { // TODO: check
     Warning("%s No entries in %s. All IP Addresses will be blocked", module_name, config_file_path);
   } else {
     // convert the coloring from indices to pointers.
diff --git a/proxy/logging/LogFilter.cc b/proxy/logging/LogFilter.cc
index 8c60d82..35fa71d 100644
--- a/proxy/logging/LogFilter.cc
+++ b/proxy/logging/LogFilter.cc
@@ -767,7 +767,7 @@ void
 LogFilterIP::init()
 {
   m_type       = IP_FILTER;
-  m_num_values = m_map.getCount();
+  m_num_values = m_map.count();
 }
 
 /*-------------------------------------------------------------------------
@@ -886,7 +886,7 @@ LogFilterIP::display(FILE *fd)
 {
   ink_assert(fd != nullptr);
 
-  if (0 == m_map.getCount()) {
+  if (0 == m_map.count()) {
     fprintf(fd, "Filter \"%s\" is inactive, no values specified\n", m_name);
   } else {
     fprintf(fd, "Filter \"%s\" %sS records if %s %s ", m_name, ACTION_NAME[m_action], m_field->symbol(), OPERATOR_NAME[m_operator]);


Mime
View raw message