b2IntrusiveList.h

/*
* Copyright (c) 2014 Google, Inc.
*
* This software is provided 'as-is', without any express or implied
* warranty.  In no event will the authors be held liable for any damages
* arising from the use of this software.
* Permission is granted to anyone to use this software for any purpose,
* including commercial applications, and to alter it and redistribute it
* freely, subject to the following restrictions:
* 1. The origin of this software must not be misrepresented; you must not
* claim that you wrote the original software. If you use this software
* in a product, an acknowledgment in the product documentation would be
* appreciated but is not required.
* 2. Altered source versions must be plainly marked as such, and must not be
* misrepresented as being the original software.
* 3. This notice may not be removed or altered from any source distribution.
*/
#ifndef B2_INTRUSIVE_LIST
#define B2_INTRUSIVE_LIST

#include <Box2D/Common/b2Settings.h>

// Whether to enable b2IntrusiveList::ValidateList().
// Be careful when enabling this since this changes the size of
// b2IntrusiveListNode so make sure *all* projects that include Box2D.h
// also define this value in the same way to avoid data corruption.
#ifndef B2_INTRUSIVE_LIST_VALIDATE
#define B2_INTRUSIVE_LIST_VALIDATE 0
#endif  // B2_INTRUSIVE_LIST_VALIDATE

class b2IntrusiveListNode
{
public:
    b2IntrusiveListNode()
    {
        Initialize();
#if B2_INTRUSIVE_LIST_VALIDATE
        m_magic = k_magic;
#endif // B2_INTRUSIVE_LIST_VALIDATE
    }

    ~b2IntrusiveListNode()
    {
        Remove();
#if B2_INTRUSIVE_LIST_VALIDATE
        m_magic = 0;
#endif // B2_INTRUSIVE_LIST_VALIDATE
    }

    void InsertAfter(b2IntrusiveListNode* const node)
    {
        b2Assert(!node->InList());
        node->m_next = m_next;
        node->m_prev = this;
        m_next->m_prev = node;
        m_next = node;
    }

    void InsertBefore(b2IntrusiveListNode* const node)
    {
        b2Assert(!node->InList());
        node->m_next = this;
        node->m_prev = m_prev;
        m_prev->m_next = node;
        m_prev = node;
    }

    const b2IntrusiveListNode* GetTerminator() const
    {
        return this;
    }

    b2IntrusiveListNode* Remove()
    {
        m_prev->m_next = m_next;
        m_next->m_prev = m_prev;
        Initialize();
        return this;
    }

    bool IsEmpty() const
    {
      return GetNext() == this;
    }

    bool InList() const
    {
      return !IsEmpty();
    }

    uint32 GetLength() const
    {
        uint32 length = 0;
        const b2IntrusiveListNode * const terminator = GetTerminator();
        for (const b2IntrusiveListNode* node = GetNext();
             node != terminator; node = node->GetNext())
        {
            length++;
        }
        return length;
    }

    b2IntrusiveListNode* GetNext() const
    {
        return m_next;
    }

    b2IntrusiveListNode* GetPrevious() const
    {
        return m_prev;
    }

    bool ValidateList() const
    {
#if B2_INTRUSIVE_LIST_VALIDATE
      if (m_magic != k_magic) return false;
      const b2IntrusiveListNode * const terminator = GetTerminator();
      for (b2IntrusiveListNode *node = GetNext(); node != terminator;
           node = node->GetNext()) {
        if (node->m_magic != k_magic) return false;
      }
#endif  // B2_INTRUSIVE_LIST_VALIDATE
      return true;
    }

    bool FindNodeInList(b2IntrusiveListNode* const nodeToFind) const
    {
        const b2IntrusiveListNode * const terminator = GetTerminator();
        for (b2IntrusiveListNode *node = GetNext(); node != terminator;
             node = node->GetNext())
        {
            if (nodeToFind == node) return true;
        }
        return false;
    }

private:
    void Initialize()
    {
        m_next = this;
        m_prev = this;
    }

private:
#if B2_INTRUSIVE_LIST_VALIDATE
    uint32 m_magic;
#endif  // B2_INTRUSIVE_LIST_VALIDATE
    b2IntrusiveListNode *m_prev;
    b2IntrusiveListNode *m_next;

private:
#if B2_INTRUSIVE_LIST_VALIDATE
    static const uint32 k_magic = 0x7157ac01;
#endif  // B2_INTRUSIVE_LIST_VALIDATE
};

#define B2_INTRUSIVE_LIST_GET_NODE(NodeMemberName) \
    b2IntrusiveListNode* GetListNode() { return &NodeMemberName; } \
    const b2IntrusiveListNode* GetListNode() const { return &NodeMemberName; }

#define B2_INTRUSIVE_LIST_NODE_GET_CLASS_ACCESSOR( \
    Class, NodeMemberName, FunctionName) \
    static Class* FunctionName(b2IntrusiveListNode *node) \
    { \
        Class *cls = NULL; \
        /* This effectively performs offsetof(Class, NodeMemberName) */ \
        /* which ends up in the undefined behavior realm of C++ but in */ \
        /* practice this works with most compilers. */ \
        return reinterpret_cast<Class*>((uint8*)(node) - \
                                        (uint8*)(&cls->NodeMemberName)); \
    } \
    \
    static const Class* FunctionName(const b2IntrusiveListNode *node) \
    { \
        return FunctionName(const_cast<b2IntrusiveListNode*>(node)); \
    }

#define B2_INTRUSIVE_LIST_NODE_GET_CLASS(Class, NodeMemberName) \
    B2_INTRUSIVE_LIST_NODE_GET_CLASS_ACCESSOR(Class, NodeMemberName, \
                                              GetInstanceFromListNode)

template<typename T>
class b2TypedIntrusiveListNode
{
public:
    b2TypedIntrusiveListNode() { }
    ~b2TypedIntrusiveListNode() { }

    void InsertAfter(T* const obj)
    {
        b2Assert(obj);
        GetListNode()->InsertAfter(obj->GetListNode());
    }

    void InsertBefore(T* const obj)
    {
        b2Assert(obj);
        GetListNode()->InsertBefore(obj->GetListNode());
    }

    T* GetNext() const
    {
        return GetInstanceFromListNode(GetListNode()->GetNext());
    }

    T* GetPrevious() const
    {
        return GetInstanceFromListNode(GetListNode()->GetPrevious());
    }

    T* GetTerminator() const
    {
        return (T*)GetListNode();
    }

    T* Remove()
    {
        GetListNode()->Remove();
        return GetInstanceFromListNode(GetListNode());
    }

    bool InList() const
    {
        return GetListNode()->InList();
    }

    // Determine whether this list is empty.
    bool IsEmpty() const
    {
        return GetListNode()->IsEmpty();
    }

    uint32 GetLength() const
    {
        return GetListNode()->GetLength();
    }

    B2_INTRUSIVE_LIST_GET_NODE(m_node);

private:
    // Node within an intrusive list.
    b2IntrusiveListNode m_node;

public:
    static T* GetInstanceFromListNode(b2IntrusiveListNode* const node)
    {
        b2Assert(node);
        // Calculate the pointer to T from the offset.
        return (T*)((uint8*)node - GetNodeOffset(node));
    }

private:
    // Get the offset of m_node within this class.
    static int32 GetNodeOffset(b2IntrusiveListNode* const node)
    {
        b2Assert(node);
        // Perform some type punning to calculate the offset of m_node in T.
        // WARNING: This could result in undefined behavior with some C++
        // compilers.
        T* obj = (T*)node;
        int32 nodeOffset = (int32)((uint8*)&obj->m_node - (uint8*)obj);
        return nodeOffset;
    }
};

#endif // B2_INTRUSIVE_LIST