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 <[email protected]> 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 {
