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 ) {
        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.hpp"
#include "intrusive_node.hpp"