Source

pyGAP / game / engine / common / intrusive_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 {


class ListNode {
public:
        ListNode();
        ~ListNode();

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

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

        void insert_after(ListNode* node);
        void insert_before(ListNode* node);

private:
    ListNode(const ListNode&);
    ListNode& operator= (const ListNode&);

    ListNode*   prev_;
    ListNode*   next_;
};



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

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

    T* first();
    T* last();
    T* next(T* object);
    T* prev(T* object);
    ListNode* get_node(T* object) const;
    T* get_object(ListNode* node) const;

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

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

    size_t      offset_;
    ListNode    root_;

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


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


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


template <class T>
T* List<T>::last() {
    return root_.is_linked() ? get_object(root_.prev()) : NULL;
}


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


template <class T>
T* List<T>::prev(T* object) {
    ListNode* node = get_node(object);
    if (node->prev() == &root_)
        return NULL;
    else
        return get_object(node->prev());
}


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


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


template <class T>
void List<T>::push_back(T* object) {
    get_node(object)->insert_before(&root_);
}


template <class T>
void List<T>::push_front(T* object) {
    get_node(object)->insert_after(&root_);
}


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


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


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


} /* namespace common */


#endif