[trafficserver] 02/08: IntrusiveDList: Update erase methods.

[am...@apache.org]

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

commit c157bdcb38d719b3413f19ed1f6f8fc3246ccf34
Author: Alan M. Carroll <am...@apache.org>
AuthorDate: Sun Jul 22 21:24:02 2018 -0500

    IntrusiveDList: Update erase methods.
---
 .../internal-libraries/intrusive-list.en.rst       | 35 ++++++++++++-
 lib/ts/IntrusiveDList.h                            | 57 ++++++++++++++++++++--
 2 files changed, 86 insertions(+), 6 deletions(-)

diff --git a/doc/developer-guide/internal-libraries/intrusive-list.en.rst b/doc/developer-guide/internal-libraries/intrusive-list.en.rst
index 7a9c3b6..32e78c7 100644
--- a/doc/developer-guide/internal-libraries/intrusive-list.en.rst
+++ b/doc/developer-guide/internal-libraries/intrusive-list.en.rst
@@ -23,7 +23,9 @@ 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.
+handled outside the class. This class supports an STL compliant bidirectional iteration. The
+iterators automatically convert to pointer as in normal use of this class the contained elements
+will be referenced by pointers.
 
 Definition
 **********
@@ -52,6 +54,16 @@ Definition
 
          Return a reference to the previous element pointer embedded in the element :arg:`elt`.
 
+   .. type:: iterator
+
+      An STL compliant bidirectional iterator on elements in the list. :type:`iterator` has a user
+      defined conversion to :code:`value_type *` for convenience in use.
+
+   .. type:: const_iterator
+
+      An STL compliant bidirectional constant iterator on elements in the list. :type:`const_iterator` has a user
+      defined conversion to :code:`const value_type *` for convenience in use.
+
    .. function:: value_type * head()
 
       Return a pointer to the head element in the list. This may be :code:`nullptr` if the list is empty.
@@ -84,6 +96,27 @@ Definition
 
       Remove the tail element and return a pointer to it. May be :code:`nullptr` if the list is empty.
 
+   .. function:: iterator erase(const iterator & loc)
+
+      Remove the element at :arg:`loc`. Return the element after :arg:`loc`.
+
+   .. function:: iterator erase(const iterator & start, const iterator & limit)
+
+      Remove the elements in the half open range from and including :arg:`start`
+      to but not including :arg:`limit`.
+
+   .. function:: iterator iterator_for(value_type * value)
+
+      Return an :type:`iterator` that refers to :arg:`value`. :arg:`value` is checked for being in a
+      list but there is no guarantee it is in this list. If :arg:`value` is not in a list then the
+      end iterator is returned.
+
+   .. function:: const_iterator iterator_for(const value_type * value)
+
+      Return a :type:`const_iterator` that refers to :arg:`value`. :arg:`value` is checked for being
+      in a list but there is no guarantee it is in this list. If :arg:`value` is not in a list then
+      the end iterator is returned.
+
 Usage
 *****
 
diff --git a/lib/ts/IntrusiveDList.h b/lib/ts/IntrusiveDList.h
index 98f92d4..44fa8c5 100644
--- a/lib/ts/IntrusiveDList.h
+++ b/lib/ts/IntrusiveDList.h
@@ -265,9 +265,18 @@ public:
   /// @return This list.
   self_type &insert_before(iterator const &target, value_type *v);
 
-  /// Take @a elt out of this list.
-  /// @return This list.
-  self_type &erase(value_type *v);
+  /// Take @a v out of this list.
+  /// @return The element after @a v.
+  value_type *erase(value_type *v);
+
+  /// Take the element at @a loc out of this list.
+  /// @return Iterator for the next element.
+  iterator erase(const iterator &loc);
+
+  /// Take elements out of the list.
+  /// Remove elements start with @a start up to but not including @a limit.
+  /// @return @a limit
+  iterator erase(const iterator &start, const iterator &limit);
 
   /// Remove all elements.
   /// @note @b No memory management is done!
@@ -577,12 +586,15 @@ IntrusiveDList<L>::insert_before(iterator const &target, value_type *v) -> self_
 
 template <typename L>
 auto
-IntrusiveDList<L>::erase(value_type *v) -> self_type &
+IntrusiveDList<L>::erase(value_type *v) -> value_type *
 {
+  value_type *zret{nullptr};
+
   if (L::prev_ptr(v)) {
     L::next_ptr(L::prev_ptr(v)) = L::next_ptr(v);
   }
   if (L::next_ptr(v)) {
+    zret                        = L::next_ptr(v);
     L::prev_ptr(L::next_ptr(v)) = L::prev_ptr(v);
   }
   if (v == _head) {
@@ -594,10 +606,45 @@ IntrusiveDList<L>::erase(value_type *v) -> self_type &
   L::prev_ptr(v) = L::next_ptr(v) = nullptr;
   --_count;
 
-  return *this;
+  return zret;
 }
 
 template <typename L>
+auto
+IntrusiveDList<L>::erase(const iterator &loc) -> iterator
+{
+  return this->iterator_for(this->erase(loc._v));
+};
+
+template <typename L>
+auto
+IntrusiveDList<L>::erase(const iterator &first, const iterator &limit) -> iterator
+{
+  value_type *spot = first;
+  value_type *prev{L::prev_ptr(spot)};
+  if (prev) {
+    L::next_ptr(prev) = limit;
+  }
+  if (spot == _head) {
+    _head = limit;
+  }
+  // tail is only updated if @a limit is @a end (e.g., @c nullptr).
+  if (nullptr == limit) {
+    _tail = prev;
+  } else {
+    L::prev_ptr(limit) = prev;
+  }
+  // Clear links in removed elements.
+  while (spot != limit) {
+    value_type *target{spot};
+    spot                = L::next_ptr(spot);
+    L::prev_ptr(target) = L::next_ptr(target) = nullptr;
+  };
+
+  return {limit._v, this};
+};
+
+template <typename L>
 size_t
 IntrusiveDList<L>::count() const
 {