IntrusiveDList.h

Go to the documentation of this file.

// SPDX-License-Identifier: Apache-2.0
// Copyright Apach Software Foundation 2019
 
#pragma once

#include <iterator>
#include <type_traits>
 
#include "swoc/swoc_version.h"
 
namespace swoc { inline namespace SWOC_VERSION_NS {
template <typename L> class IntrusiveDList {
  friend class iterator;
 
public:
  using self_type = IntrusiveDList; 
  // Get the result of calling the pointer access function, then strip off reference and pointer
  // qualifiers. @c nullptr is used instead of the pointer type because this is done precisely
  // to find that type.
  using value_type = typename std::remove_pointer<
    typename std::remove_reference<typename std::invoke_result<decltype(L::next_ptr), std::nullptr_t>::type>::type>::type;

  class const_iterator {
    using self_type = const_iterator; 
    friend class IntrusiveDList;
 
  public:
    using list_type  = IntrusiveDList;                       
    using value_type = const typename list_type::value_type; 
    // STL algorithm compliance.
    using iterator_category = std::bidirectional_iterator_tag;
    using pointer           = value_type *;
    using reference         = value_type &;
    using difference_type   = int;

    const_iterator();

    self_type &operator++();

    self_type &operator--();

    self_type operator++(int);

    self_type operator--(int);

    value_type &operator*() const;

    value_type *operator->() const;

    operator value_type *() const;

    bool operator==(self_type const &that) const;

    bool operator!=(self_type const &that) const;

    bool has_prev() const;

    bool has_next() const;

    bool has_predecessor() const;

    bool has_successor() const;
 
  protected:
    // These are stored non-const to make implementing @c iterator easier. This class provides the required @c const
    // protection.
    list_type *_list{nullptr};                   
    typename list_type::value_type *_v{nullptr}; 

    const_iterator(const list_type *list, value_type *v);
  };

  class iterator : public const_iterator {
    using self_type  = iterator;       
    using super_type = const_iterator; 
 
    friend class IntrusiveDList;
 
  public:
    using list_type  = IntrusiveDList;                 
    using value_type = typename list_type::value_type; 
    // STL algorithm compliance.
    using iterator_category = std::bidirectional_iterator_tag;
    using pointer           = value_type *;
    using reference         = value_type &;

    iterator();

    self_type &operator++();

    self_type &operator--();

    self_type operator++(int);

    self_type operator--(int);

    value_type &operator*() const;

    value_type *operator->() const;

    operator value_type *() const;
 
  protected:
    iterator(list_type *list, value_type *v);
  };

  IntrusiveDList() = default;
 
  IntrusiveDList(self_type const &that) = delete;

  IntrusiveDList(self_type &&that);

  self_type &operator=(const self_type &that) = delete;

  self_type &operator=(self_type &&that);

  bool empty() const;

  bool contains(const value_type *v) const;

  self_type &prepend(value_type *v);

  self_type &append(value_type *v);

  value_type *take_head();

  value_type *take_tail();

  self_type &insert_after(value_type *target, value_type *v);

  self_type &insert_before(value_type *target, value_type *v);

  self_type &insert_after(iterator const &target, value_type *v);

  self_type &insert_before(iterator const &target, value_type *v);

  value_type *erase(value_type *v);

  iterator erase(const iterator &loc);

  iterator erase(const iterator &start, const iterator &limit);

  iterator nth(unsigned n);

  self_type take_prefix(unsigned n);

  self_type split_prefix(unsigned n);

  self_type take_suffix(unsigned n);

  self_type split_suffix(unsigned n);

  self_type &append(self_type &src);

  self_type &prepend(self_type &src);

  self_type &insert_after(value_type *target, self_type &src);

  self_type &insert_before(value_type *target, self_type &src);

  self_type &insert_after(iterator const &target, self_type &src);

  self_type &insert_before(iterator const &target, self_type &src);

  self_type &clear();

  size_t count() const;

  iterator begin();

  const_iterator begin() const;

  iterator end();

  const_iterator end() const;

  iterator iterator_for(value_type *v);
 
  const_iterator iterator_for(const value_type *v) const;

  value_type *head();
 
  const value_type *head() const;

  value_type *tail();
 
  const value_type *tail() const;

  template <typename F> self_type &apply(F &&f);
 
protected:
  value_type *_head{nullptr}; 
  value_type *_tail{nullptr}; 
  size_t _count{0};           
};

template <typename T, T *(T::*NEXT) = &T::_next, T *(T::*PREV) = &T::_prev> struct IntrusiveLinkage {
  static T *&next_ptr(T *thing); 
  static T *&prev_ptr(T *thing); 
};
 
template <typename T, T *(T::*NEXT), T *(T::*PREV)>
T *&
IntrusiveLinkage<T, NEXT, PREV>::next_ptr(T *thing) {
  return thing->*NEXT;
}
 
template <typename T, T *(T::*NEXT), T *(T::*PREV)>
T *&
IntrusiveLinkage<T, NEXT, PREV>::prev_ptr(T *thing) {
  return thing->*PREV;
}

template <typename T, typename P>
T *&
ptr_ref_cast(P *&p) {
  union {
    P **_p;
    T **_t;
  } u{&p};
  return *(u._t);
}

template <typename T, typename L> struct IntrusiveLinkageRebind {
  static T *&next_ptr(T *thing); 
  static T *&prev_ptr(T *thing); 
};
 
template <typename T, typename L>
T *&
IntrusiveLinkageRebind<T, L>::next_ptr(T *thing) {
  return ptr_ref_cast<T>(L::next_ptr(thing));
}
 
template <typename T, typename L>
T *&
IntrusiveLinkageRebind<T, L>::prev_ptr(T *thing) {
  return ptr_ref_cast<T>(L::prev_ptr(thing));
}
 
template <typename T> struct IntrusiveLinks {
  T *_next = nullptr;
  T *_prev = nullptr;
};
 
template <typename T, IntrusiveLinks<T>(T::*links)> struct IntrusiveLinkDescriptor {
  static T *&next_ptr(T *thing); 
  static T *&prev_ptr(T *thing); 
};
 
// --- Implementation ---
 
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(list_type *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;
  }
  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> IntrusiveDList<L>::const_iterator::operator value_type *() const {
  return _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> IntrusiveDList<L>::iterator::operator value_type *() const {
  return super_type::_v;
}

 
template <typename L>
IntrusiveDList<L>::IntrusiveDList(self_type &&that) : _head(that._head), _tail(that._tail), _count(that._count) {
  that.clear();
}
 
template <typename L>
bool
IntrusiveDList<L>::empty() const {
  return _head == nullptr;
}
 
template <typename L>
bool
IntrusiveDList<L>::contains(const value_type *v) const {
  for (auto thing = _head; thing; thing = L::next_ptr(thing)) {
    if (thing == v)
      return true;
  }
  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>
bool
IntrusiveDList<L>::const_iterator::has_predecessor() const {
  return _v ? nullptr != L::prev_ptr(_v) : !_list->empty();
}
 
template <typename L>
bool
IntrusiveDList<L>::const_iterator::has_prev() const {
  return _v ? nullptr != L::prev_ptr(_v) : !_list->empty();
}
 
template <typename L>
bool
IntrusiveDList<L>::const_iterator::has_successor() const {
  return _v && nullptr != L::next_ptr(_v);
}
 
template <typename L>
bool
IntrusiveDList<L>::const_iterator::has_next() const {
  return nullptr != _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
  }
  _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;
}
 
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>::insert_after(value_type *target, self_type &src) -> self_type & {
  if (target && src._count > 0) {
    if (_tail == target) {
      this->append(src);
    } else {                                                     // invariant - @a target is not tail therefore has a successor.
      L::next_ptr(src._tail)              = L::next_ptr(target); // link @a src tail to @a target successor
      L::prev_ptr(L::next_ptr(src._tail)) = src._tail;
 
      L::prev_ptr(src._head) = target; // link @a src head to @target
      L::next_ptr(target)    = src._head;
 
      _count += src._count;
      src.clear();
    }
  }
  return *this;
}
 
template <typename L>
auto
IntrusiveDList<L>::insert_after(iterator const &target, self_type &src) -> self_type & {
  return this->insert_after(target._v, src);
}
 
template <typename L>
auto
IntrusiveDList<L>::insert_before(value_type *target, self_type &src) -> self_type & {
  if (target && src._count > 0) {
    if (_head == target) {
      this->prepend(src);
    } else {                                                  // invariant - @a target is not head and therefore has a predecessor.
      L::prev_ptr(src._head)           = L::prev_ptr(target); // link @a src head to @a target predecessor
      L::next_ptr(L::prev_ptr(target)) = src._head;
 
      L::next_ptr(src._tail) = target; // link @a src tail to @a target
      L::prev_ptr(target)    = src._tail;
 
      _count += src._count;
      src.clear();
    }
  }
  return *this;
}
 
template <typename L>
auto
IntrusiveDList<L>::insert_before(iterator const &target, self_type &src) -> self_type & {
  return this->insert_before(target._v, src);
}
 
template <typename L>
auto
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) {
    _head = L::next_ptr(v);
  }
  if (v == _tail) {
    _tail = L::prev_ptr(v);
  }
  L::prev_ptr(v) = L::next_ptr(v) = nullptr;
  --_count;
 
  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>
auto
IntrusiveDList<L>::operator=(self_type &&that) -> self_type & {
  if (this != &that) {
    this->_head  = that._head;
    this->_tail  = that._tail;
    this->_count = that._count;
    that.clear();
  }
  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>::tail() const -> const value_type * {
  return _tail;
}
 
template <typename L>
auto
IntrusiveDList<L>::head() -> value_type * {
  return _head;
}
 
template <typename L>
auto
IntrusiveDList<L>::head() const -> const value_type * {
  return _head;
}
 
template <typename L>
auto
IntrusiveDList<L>::clear() -> self_type & {
  _head = _tail = nullptr;
  _count        = 0;
  return *this;
}
 
template <typename L>
auto
IntrusiveDList<L>::nth(unsigned int n) -> iterator {
  if (n >= _count) {
    return {};
  }
 
  value_type *spot;
  if (n < _count / 2) { // closer to head, count from there..
    spot = _head;
    while (n-- > 0) {
      spot = L::next_ptr(spot);
    }
  } else { // count from tail
    spot         = _tail;
    unsigned idx = _count - 1;
    while (idx-- > n) {
      spot = L::prev_ptr(spot);
    }
  }
  return iterator_for(spot);
}
 
template <typename L>
auto
IntrusiveDList<L>::take_prefix(unsigned int n) -> self_type {
  if (n == 0) {
    return {};
  }
 
  if (_count <= n) {
    return std::move(*this);
  }
 
  // Invariant - there is at least one element that will not be taken.
 
  self_type zret;
  value_type *spot = this->nth(n); // new @a head for @a this
 
  zret._count             = n;
  zret._head              = _head;
  zret._tail              = L::prev_ptr(spot);
  L::next_ptr(zret._tail) = nullptr;
 
  _count             -= n;
  _head               = spot;
  L::prev_ptr(_head)  = nullptr;
 
  return zret;
}
 
template <typename L>
auto
IntrusiveDList<L>::split_prefix(unsigned int n) -> self_type {
  if (n <= _count) {
    return this->take_prefix(n);
  }
  return {};
}
 
template <typename L>
auto
IntrusiveDList<L>::take_suffix(unsigned int n) -> self_type {
  if (n == 0) {
    return {};
  }
 
  if (_count <= n) {
    return std::move(*this);
  }
 
  // Invariant - there is at least one element that will not be taken.
 
  self_type zret;
  value_type *spot = this->nth(_count - n - 1); // new @a tail for @a this
 
  zret._count             = n;
  zret._head              = L::next_ptr(spot);
  L::prev_ptr(zret._head) = nullptr;
  zret._tail              = _tail;
 
  _count             -= n;
  _tail               = spot;
  L::next_ptr(_tail)  = nullptr;
 
  return zret;
}
 
template <typename L>
auto
IntrusiveDList<L>::split_suffix(unsigned int n) -> self_type {
  if (n <= _count) {
    return this->take_suffix(n);
  }
  return {};
}
 
template <typename L>
auto
IntrusiveDList<L>::prepend(IntrusiveDList::self_type &src) -> self_type & {
  if (src._count > 0) {
    if (_count == 0) {
      *this = std::move(src);
    } else {
      L::prev_ptr(_head)      = src._tail;
      L::next_ptr(src._tail)  = _head;
      _count                 += src._count;
      _head                   = src._head;
      src.clear();
    }
  }
  return *this;
}
 
template <typename L>
auto
IntrusiveDList<L>::append(IntrusiveDList::self_type &src) -> self_type & {
  if (src._count > 0) {
    if (_count == 0) {
      *this = std::move(src);
    } else {
      L::next_ptr(_tail)      = src._head;
      L::prev_ptr(src._head)  = _tail;
      _count                 += src._count;
      _tail                   = src._tail;
      src.clear();
    }
  }
  return *this;
}
 
namespace detail {
// Make @c apply more convenient by allowing the function to take a reference type or pointer type
// to the container elements. The pointer type is the base, plus a shim to convert from a reference
// type functor to a pointer type. The complex return type definition forces only one, but
// not both, to be valid for a particular functor. This also must be done via free functions and not
// method overloads because the compiler forces a match up of method definitions and declarations
// before any template instantiation.
 
template <typename L, typename F>
auto
Intrusive_DList_Apply(IntrusiveDList<L> &list, F &&f)
  -> decltype(f(*static_cast<typename IntrusiveDList<L>::value_type *>(nullptr)), list) {
  return list.apply([&f](typename IntrusiveDList<L>::value_type *v) { return f(*v); });
}
 
template <typename L, typename F>
auto
Intrusive_DList_Apply(IntrusiveDList<L> &list, F &&f)
  -> decltype(f(static_cast<typename IntrusiveDList<L>::value_type *>(nullptr)), list) {
  auto spot{list.begin()};
  auto limit{list.end()};
  while (spot != limit) {
    f(spot++); // post increment means @a spot is updated before @a f is applied.
  }
  return list;
}
} // namespace detail
 
template <typename L>
template <typename F>
auto
IntrusiveDList<L>::apply(F &&f) -> self_type & {
  return detail::Intrusive_DList_Apply(*this, f);
}
}} // namespace swoc::SWOC_VERSION_NS