Source

pyGAP / game / inc / common / list.h

Full commit
#ifndef __COMMON_LIST_H__
#define __COMMON_LIST_H__


#include <stddef.h>


#define INTRUSIVE_LIST(T, node)       common::ListDeclare<T, offsetof(T, node)>()


namespace common {


template <class T>
class ListNode {
public:
        ListNode();
        ~ListNode();

        ListNode<T>* next() { return next_; }
        ListNode<T>* prev() { return prev_; }

        bool is_linked() const { return next_ != prev_; }
        void unlink();

        void insert_after(ListNode<T>* node, ListNode<T>* prev_node);
        void insert_before(ListNode<T>* node, ListNode<T>* next_node);

private:
    ListNode(const ListNode&);
    ListNode<T>& operator= (const ListNode&);

    ListNode<T>*   prev_;
    ListNode<T>*   next_;
};


template <class T>
class List {
public:
    ~List();

    T* first();
    T* next(T* object);
    ListNode<T>* get_node(T* object) const;
    T* get_object(ListNode<T>* node) const;

    bool is_empty() const;
    void push_back(T* object);
    void push_front(T* object);

private:
    List(size_t offset) : offset_(offset) {}

    ListNode<T>     root_;
    size_t          offset_;

    template<class, size_t> friend class ListDeclare;
};



template <class T, size_t offset>
class ListDeclare : public List<T> {
public:
    ListDeclare();
};


// -----------------------------------------------------------------------------


template <class T>
ListNode<T>::ListNode() {
    prev_ = this;
    next_ = this;
}


template <class T>
ListNode<T>::~ListNode()
{
    unlink();
}


template <class T>
void ListNode<T>::unlink() {
    if (!is_linked())
        return;

    prev_->next_ = next_;
    next_->prev_ = prev_;
    prev_ = next_ = this;
}


template <class T>
void ListNode<T>::insert_after(ListNode<T>* node, ListNode<T>* prev_node) {
    unlink();

    prev_ = prev_node;
    next_ = prev_node->next_;

    prev_node->next_->prev_ = this;
    prev_node->next_ = node;
}


template <class T>
void ListNode<T>::insert_before(ListNode<T>* node, ListNode<T>* next_node) {
    unlink();

    prev_ = next_node->prev_;
    next_ = prev_->next_;

    next_node->prev_->next_ = node;
    next_node->prev_ = this;
}


// -----------------------------------------------------------------------------


template <class T>
T* List<T>::first() {
    return root_->is_linked() ? get_object(root_->next()) : NULL;
}


template <class T>
List<T>::~List() {
    while (root_.is_linked())
        root_.next()->unlink();
}


template <class T>
T* List<T>::next(T* object) {
    ListNode<T>* node = get_node(object);
    return node->next() == root_ ? NULL : node->next();
}


template <class T>
ListNode<T>* List<T>::get_node(T* object) const {
    return (ListNode<T>*)((size_t)object + offset_);
}


template <class T>
T* List<T>::get_object(ListNode<T>* node) const {
    return (T*)((size_t)node - offset_);
}


template <class T>
void List<T>::push_back(T* object) {
    ListNode<T>* node = get_node(object);
    root_.insert_before(node, node->next());
}


template <class T>
void List<T>::push_front(T* object) {
    ListNode<T>* node = get_node(object);
    root_.insert_after(node, node->prev());
}


// -----------------------------------------------------------------------------


template <class T, size_t offset>
ListDeclare<T, offset>::ListDeclare() : List<T>(offset)
{}


} /* namespace common */


#endif