cpp-intrusive-list/intrusive_list.hpp

//
//  intrusive_iterator.h
//  utilities
//
//  Created by Sam Jaffe on 9/26/14.
//  Copyright (c) 2014 Sam Jaffe. All rights reserved.
//

#pragma once

#include <iterator>
#include <limits>
#include <cstddef>

template <typename T>
class intrusive_node;

template <typename T>
class intrusive_list;

template <typename T>
class intrusive_iterator;

template <typename T>
class const_intrusive_iterator;

template <typename T>
class intrusive_node {
public:
  typedef T value_type;
  typedef T& reference;
  typedef const T& const_reference;
  typedef T* pointer;
  typedef const T* const_pointer;
private:
  typedef intrusive_node<T>* self;
public:
  intrusive_node() = delete;
  intrusive_node(const intrusive_node&) = delete;
  intrusive_node(intrusive_node&&) = delete;
  intrusive_node& operator=(const intrusive_node&) = delete;
  intrusive_node& operator=(intrusive_node&&) = delete;
  
  intrusive_node(pointer ptr);
  ~intrusive_node();
  
private:
  friend intrusive_list<T>;
  friend intrusive_iterator<intrusive_node<T> >;
  friend const_intrusive_iterator<intrusive_node<T> >;
  
  pointer ptr_ = nullptr;
  intrusive_list<T>* list_ = nullptr;
  self next_ = nullptr;
  self prev_ = nullptr;
};

template <typename N>
class intrusive_iterator : public std::iterator<std::bidirectional_iterator_tag, typename N::value_type> {
public:
  typedef std::bidirectional_iterator_tag iterator_category;
  typedef typename N::value_type value_type;
  typedef typename N::reference reference;
  typedef typename N::const_reference const_reference;
  typedef typename N::pointer pointer;
  typedef typename N::const_pointer const_pointer;
public:
  intrusive_iterator(N* node);
  
  reference operator*();
  const_reference operator*() const;
  
  pointer operator->();
  const_pointer operator->() const;
  
  intrusive_iterator operator++(int);
  intrusive_iterator& operator++();
  
  intrusive_iterator operator--(int);
  intrusive_iterator& operator--();
  
  bool operator==(const intrusive_iterator& other) const;
  bool operator!=(const intrusive_iterator& other) const;
  
private:
  friend intrusive_list<value_type>;
  
  N* get();
  const N* get() const;
  
  N* node_;
};

template <typename N>
class const_intrusive_iterator : public std::iterator<std::bidirectional_iterator_tag, typename N::value_type> {
public:
  typedef std::bidirectional_iterator_tag iterator_category;
  typedef typename N::value_type value_type;
  typedef typename N::reference reference;
  typedef typename N::const_reference const_reference;
  typedef typename N::pointer pointer;
  typedef typename N::const_pointer const_pointer;
public:
  const_intrusive_iterator(const N* node);
  
  const_reference operator*() const;
  
  const_pointer operator->() const;
  
  const_intrusive_iterator operator++(int);
  const_intrusive_iterator& operator++();
  
  const_intrusive_iterator operator--(int);
  const_intrusive_iterator& operator--();
  
  bool operator==(const const_intrusive_iterator& other) const;
  bool operator!=(const const_intrusive_iterator& other) const;
  
private:
  friend intrusive_list<value_type>;
  
  const N* get() const;
  
  const N* node_;
};

template <typename T>
class intrusive_list {
public:
  typedef T value_type;
  typedef intrusive_node<value_type> node_type;
  typedef std::size_t size_type;
  typedef std::ptrdiff_t difference_type;
  typedef T* pointer;
  typedef const T* const_pointer;
  typedef intrusive_iterator<node_type> iterator;
  typedef const_intrusive_iterator<node_type> const_iterator;
  typedef typename std::reverse_iterator<iterator> reverse_iterator;
  typedef typename std::reverse_iterator<const_iterator> const_reverse_iterator;
public:
  constexpr intrusive_list( node_type T::*node ) :
  node_(node) {
    
  }
  intrusive_list( const intrusive_list& ) = delete;
  intrusive_list( intrusive_list&& other ) = default;
  intrusive_list( std::initializer_list<pointer> ilist, node_type T::*node ) :
  node_(node) {
    assign(ilist);
  }
  ~intrusive_list() {
    clear();
  }
  
  intrusive_list& operator=( const intrusive_list& ) = delete;
  intrusive_list& 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_;
  }
  intrusive_list& operator=( std::initializer_list<pointer> ilist ) {
    assign(ilist);
  }
  
  void assign( std::initializer_list<pointer> ilist ) {
    clear();
    for (pointer p : ilist) {
      push_back(p);
    }
  }
  
  inline pointer front() {
    return head_->get();
  }
  inline const_pointer front() const {
    return head_->get();
  }
  
  inline pointer back() {
    return end_.prev_->get();
  }
  inline const_pointer back() const {
    return end_.prev_->get();
  }
  
  inline iterator begin() noexcept {
    return iterator{head_};
  }
  inline const_iterator begin() const noexcept {
    return const_iterator{head_};
  }
  inline const_iterator cbegin() const noexcept {
    return const_iterator{head_};
  }
  
  inline iterator end() noexcept {
    return iterator{&end_};
  }
  inline const_iterator end() const noexcept {
    return const_iterator{&end_};
  }
  inline const_iterator cend() const noexcept {
    return const_iterator{&end_};
  }
  
  inline reverse_iterator rbegin() {
    return reverse_iterator{end()};
  }
  inline const_reverse_iterator rbegin() const noexcept {
    return const_reverse_iterator{end()};
  }
  inline const_reverse_iterator crbegin() const noexcept {
    return const_reverse_iterator{cend()};
  }
  
  inline reverse_iterator rend() noexcept {
    return reverse_iterator{begin()};
  }
  inline const_reverse_iterator rend() const noexcept {
    return const_reverse_iterator{begin()};
  }
  inline const_reverse_iterator crend() const noexcept{
    return const_reverse_iterator{cbegin()};
  }
  
  inline bool empty() const noexcept {
    return size_ = 0;
  }
  inline size_type size() const noexcept {
    return size_;
  }
  inline size_type max_size() const noexcept {
    return std::numeric_limits<size_type>::max();
  }
  
  void clear() noexcept {
    erase(begin(), end());
  }
  
  iterator insert(const_iterator pos, pointer value) {
    node_type* n = &(value->*node_);
    link(pos.get()->prev_, n);
    link(n, pos.get());
    n->list_ = this;
    ++size_;
    return iterator{n};
  }
  iterator insert(const_iterator pos, std::initializer_list<pointer> ilist) {
    for (pointer p : ilist) {
      link(pos.get()->prev_, p->*node_);
      link(p->*node_, pos.get());
      p->*node_->list_ = this;
    }
    size_ += ilist.size();
    return iterator{pos.get()};
  }
  
  iterator erase(iterator pos) {
    unlink(pos.get());
    pos.get()->list_ = nullptr;
    --size_;
    return iterator{pos.get()->next_};
  }
  iterator erase(iterator first, iterator last) {
    while (first != last) {
      first = erase(first);
    }
    return last;
  }
  
  inline void push_back(pointer value) {
    link(end_.prev_, &(value->*node_));
    ++size_;
  }
  
  inline void pop_back() {
    intrusive_node<T> *old = end_.prev_;
    end_.prev_ = old->prev_;
    unlink(old);
    --size_;
  }
  
  inline void push_front(pointer value) {
    insert(begin(), value);
  }
  
  inline void pop_front() {
    erase(begin());
  }
  
  void remove( pointer value ) {
    node_type* n = &(value->*node_);
    if (n->list_ == this) {
      unlink(n);
      --size_;
    }
  }
  template< class UnaryPredicate >
  void remove_if( UnaryPredicate pred ) {
    auto it = begin();
    while (it != end()) {
      pointer p = it.get()->ptr_;
      ++it;
      if (pred(p)) {
        remove(p);
      }
    }
  }
private:
  inline void link(node_type* lhs, node_type* rhs) {
    lhs->next_ = rhs;
    rhs->prev_ = lhs;
  }
  inline void unlink(node_type* node) {
    if (node->next_) {
      node->next_->prev_ = node->prev_;
    }
    if (node->prev_) {
      node->prev_->next_ = node->next_;
    }
  }
  
  node_type T::*node_;
  node_type end_{nullptr}; // secretly const
  node_type *head_ = &end_;
  size_type size_;
};

#include "intrusive_iterator.tpp"
#include "intrusive_node.tpp"