cpp-intrusive-list/intrusive_list.tpp

//
//  intrusive_list.tpp.h
//  intrusive_list
//
//  Created by Sam Jaffe on 1/7/17.
//

#pragma once


template <typename T>
constexpr intrusive_list<T>::intrusive_list( node_type T::*node ) :
node_(node) {
  
}

template <typename T>
intrusive_list<T>::intrusive_list( std::initializer_list<pointer> ilist, node_type T::*node ) :
node_(node) {
  assign(ilist);
}

template <typename T>
intrusive_list<T>::~intrusive_list() {
  clear();
}

template <typename T>
intrusive_list<T>& intrusive_list<T>::operator=( intrusive_list&& other ) {
  if ( this == & other ) return *this;
  clear(); // other than this, default
  node_ = other.node_;
  size_ = other.size_;
  head_ = other.head_;
  other.head_ = &other.end_;
}

template <typename T>
inline intrusive_list<T>& intrusive_list<T>::operator=( std::initializer_list<pointer> ilist ) {
  assign(ilist);
}

template <typename T>
void intrusive_list<T>::assign( std::initializer_list<pointer> ilist ) {
  clear();
  for (pointer p : ilist) {
    push_back(p);
  }
}

template <typename T>
inline typename intrusive_list<T>::pointer intrusive_list<T>::front() {
  return head_->get();
}

template <typename T>
inline typename intrusive_list<T>::const_pointer intrusive_list<T>::front() const {
  return head_->get();
}

template <typename T>
inline typename intrusive_list<T>::pointer intrusive_list<T>::back() {
  return end_.prev_->get();
}

template <typename T>
inline typename intrusive_list<T>::const_pointer intrusive_list<T>::back() const {
  return end_.prev_->get();
}

template <typename T>
inline typename intrusive_list<T>::iterator intrusive_list<T>::begin() noexcept {
  return iterator{head_};
}

template <typename T>
inline typename intrusive_list<T>::const_iterator intrusive_list<T>::begin() const noexcept {
  return const_iterator{head_};
}

template <typename T>
inline typename intrusive_list<T>::const_iterator intrusive_list<T>::cbegin() const noexcept {
  return const_iterator{head_};
}

template <typename T>
inline typename intrusive_list<T>::iterator intrusive_list<T>::end() noexcept {
  return iterator{tail_};
}

template <typename T>
inline typename intrusive_list<T>::const_iterator intrusive_list<T>::end() const noexcept {
  return const_iterator{tail_};
}

template <typename T>
inline typename intrusive_list<T>::const_iterator intrusive_list<T>::cend() const noexcept {
  return const_iterator{tail_};
}

template <typename T>
inline typename intrusive_list<T>::reverse_iterator intrusive_list<T>::rbegin() {
  return reverse_iterator{end()};
}

template <typename T>
inline typename intrusive_list<T>::const_reverse_iterator intrusive_list<T>::rbegin() const noexcept {
  return const_reverse_iterator{end()};
}

template <typename T>
inline typename intrusive_list<T>::const_reverse_iterator intrusive_list<T>::crbegin() const noexcept {
  return const_reverse_iterator{cend()};
}

template <typename T>
inline typename intrusive_list<T>::reverse_iterator intrusive_list<T>::rend() noexcept {
  return reverse_iterator{begin()};
}

template <typename T>
inline typename intrusive_list<T>::const_reverse_iterator intrusive_list<T>::rend() const noexcept {
  return const_reverse_iterator{begin()};
}

template <typename T>
inline typename intrusive_list<T>::const_reverse_iterator intrusive_list<T>::crend() const noexcept{
  return const_reverse_iterator{cbegin()};
}

template <typename T>
inline bool intrusive_list<T>::empty() const noexcept {
  return size() == 0;
}

template <typename T>
inline typename intrusive_list<T>::size_type intrusive_list<T>::size() const noexcept {
  return size_;
}

template <typename T>
inline typename intrusive_list<T>::size_type intrusive_list<T>::max_size() const noexcept {
  return std::numeric_limits<size_type>::max();
}

template <typename T>
inline void intrusive_list<T>::clear() noexcept {
  erase(begin(), end());
}

template <typename T>
typename intrusive_list<T>::iterator
intrusive_list<T>::insert(const_iterator pos, pointer value) {
  node_type* n = &(value->*node_);
  if ( n->list_ == nullptr ) {
    insert_impl( pos, n );
  } else {
    throw std::logic_error{ "cannot use intrusive_list<T>::insert to perform a splice" };
  }
  return iterator{n};
}

template <typename T>
typename intrusive_list<T>::iterator
intrusive_list<T>::transfer(const_iterator pos, pointer value) {
  node_type* n = &(value->*node_);
  n->unlink( );
  insert_impl( pos, n );
  return iterator{n};
}

template <typename T>
void intrusive_list<T>::insert_impl( const_iterator pos, node_type * n ) {
  link(pos.get()->prev_, n);
  link(n, pos.get());
  n->list_ = this;
  ++size_;
}

template <typename T>
typename intrusive_list<T>::iterator
  intrusive_list<T>::insert(const_iterator pos, std::initializer_list<pointer> ilist) {
  for (pointer p : ilist) {
    insert( pos, p );
  }
  return iterator{pos.get()};
}

template <typename T>
typename intrusive_list<T>::iterator intrusive_list<T>::erase(iterator pos) {
  unlink(pos.get());
  pos.get()->list_ = nullptr;
  --size_;
  return iterator{pos.get()->next_};
}

template <typename T>
typename intrusive_list<T>::iterator intrusive_list<T>::erase(iterator first, iterator last) {
  while (first != last) {
    first = erase(first);
  }
  return last;
}

template <typename T>
inline void intrusive_list<T>::push_back(pointer value) {
  insert(cend(), value);
}

template <typename T>
void intrusive_list<T>::pop_back() {
  intrusive_node<T> *old = end_.prev_;
  end_.prev_ = old->prev_;
  unlink(old);
  --size_;
}

template <typename T>
inline void intrusive_list<T>::push_front(pointer value) {
  insert(begin(), value);
}

template <typename T>
inline void intrusive_list<T>::pop_front() {
  erase(begin());
}

template <typename T>
void intrusive_list<T>::remove( pointer value ) {
  node_type* n = &(value->*node_);
  if (n->list_ == this) {
    unlink(n);
    --size_;
  }
}

template <typename T>
template< class UnaryPredicate >
void intrusive_list<T>::remove_if( UnaryPredicate pred ) {
  auto it = begin();
  while (it != end()) {
    pointer p = it.get()->ptr_;
    ++it;
    if (pred(p)) {
      remove(p);
    }
  }
}

template <typename T>
inline void intrusive_list<T>::link(node_type* lhs, node_type* rhs) {
  if ( lhs ) { lhs->next_ = rhs; }
  rhs->prev_ = lhs;
}

template <typename T>
inline void intrusive_list<T>::unlink(node_type* node) {
  if (node->next_) {
    node->next_->prev_ = node->prev_;
  }
  if (node->prev_) {
    node->prev_->next_ = node->next_;
  }
}