SentinelLinkedList.h [plain text]
#ifndef SentinelLinkedList_h
#define SentinelLinkedList_h
namespace WTF {
enum SentinelTag { Sentinel };
template<typename T>
class BasicRawSentinelNode {
public:
BasicRawSentinelNode(SentinelTag)
: m_next(0)
, m_prev(0)
{
}
BasicRawSentinelNode()
: m_next(0)
, m_prev(0)
{
}
void setPrev(BasicRawSentinelNode* prev) { m_prev = prev; }
void setNext(BasicRawSentinelNode* next) { m_next = next; }
T* prev() { return static_cast<T*>(m_prev); }
T* next() { return static_cast<T*>(m_next); }
bool isOnList() const
{
ASSERT(!!m_prev == !!m_next);
return !!m_prev;
}
void remove();
private:
BasicRawSentinelNode* m_next;
BasicRawSentinelNode* m_prev;
};
template <typename T, typename RawNode = T> class SentinelLinkedList {
public:
typedef T* iterator;
SentinelLinkedList();
void push(T*);
static void remove(T*);
iterator begin();
iterator end();
private:
RawNode m_headSentinel;
RawNode m_tailSentinel;
};
template <typename T> void BasicRawSentinelNode<T>::remove()
{
SentinelLinkedList<T, BasicRawSentinelNode<T> >::remove(static_cast<T*>(this));
}
template <typename T, typename RawNode> inline SentinelLinkedList<T, RawNode>::SentinelLinkedList()
: m_headSentinel(Sentinel)
, m_tailSentinel(Sentinel)
{
m_headSentinel.setNext(&m_tailSentinel);
m_headSentinel.setPrev(0);
m_tailSentinel.setPrev(&m_headSentinel);
m_tailSentinel.setNext(0);
}
template <typename T, typename RawNode> inline typename SentinelLinkedList<T, RawNode>::iterator SentinelLinkedList<T, RawNode>::begin()
{
return static_cast<T*>(m_headSentinel.next());
}
template <typename T, typename RawNode> inline typename SentinelLinkedList<T, RawNode>::iterator SentinelLinkedList<T, RawNode>::end()
{
return static_cast<T*>(&m_tailSentinel);
}
template <typename T, typename RawNode> inline void SentinelLinkedList<T, RawNode>::push(T* node)
{
ASSERT(node);
ASSERT(!node->prev());
ASSERT(!node->next());
RawNode* prev = &m_headSentinel;
RawNode* next = m_headSentinel.next();
node->setPrev(prev);
node->setNext(next);
prev->setNext(node);
next->setPrev(node);
}
template <typename T, typename RawNode> inline void SentinelLinkedList<T, RawNode>::remove(T* node)
{
ASSERT(node);
ASSERT(!!node->prev());
ASSERT(!!node->next());
RawNode* prev = node->prev();
RawNode* next = node->next();
prev->setNext(next);
next->setPrev(prev);
node->setPrev(0);
node->setNext(0);
}
}
using WTF::BasicRawSentinelNode;
using WTF::SentinelLinkedList;
#endif