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/07/10 18:09:12 UTC
[trafficserver] branch master updated: IntrusiveDList: Refreshed
for C++ eleventy, added const_iterator.
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 <am...@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]);