Source/WTF/wtf/SentinelLinkedList.h

   1 /*
   2  * Copyright (C) 2011 Apple Inc. All rights reserved.
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions
   6  * are met:
   7  * 1. Redistributions of source code must retain the above copyright
   8  *    notice, this list of conditions and the following disclaimer.
   9  * 2. Redistributions in binary form must reproduce the above copyright
  10  *    notice, this list of conditions and the following disclaimer in the
  11  *    documentation and/or other materials provided with the distribution.
  12  *
  13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
  14  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
  15  * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  16  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
  17  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  18  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  19  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  20  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  21  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  22  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
  23  * THE POSSIBILITY OF SUCH DAMAGE.
  24  */
  25
  26 //    A SentinelLinkedList is a linked list with dummy head and tail sentinels,
  27 //    which allow for branch-less insertion and removal, and removal without a
  28 //    pointer to the list.
  29 //
  30 //    Requires: Node is a concrete class with:
  31 //        Node(SentinelTag);
  32 //        void setPrev(Node*);
  33 //        Node* prev();
  34 //        void setNext(Node*);
  35 //        Node* next();
  36
  37 #ifndef SentinelLinkedList_h
  38 #define SentinelLinkedList_h
  39
  40 namespace WTF {
  41
  42 enum SentinelTag { Sentinel };
  43
  44 template<typename T>
  45 class BasicRawSentinelNode {
  46 public:
  47     BasicRawSentinelNode(SentinelTag)
  48         : m_next(0)
  49         , m_prev(0)
  50     {
  51     }
  52
  53     BasicRawSentinelNode()
  54         : m_next(0)
  55         , m_prev(0)
  56     {
  57     }
  58
  59     void setPrev(BasicRawSentinelNode* prev) { m_prev = prev; }
  60     void setNext(BasicRawSentinelNode* next) { m_next = next; }
  61
  62     T* prev() { return static_cast<T*>(m_prev); }
  63     T* next() { return static_cast<T*>(m_next); }
  64
  65     bool isOnList() const
  66     {
  67         ASSERT(!!m_prev == !!m_next);
  68         return !!m_prev;
  69     }
  70
  71     void remove();
  72
  73 private:
  74     BasicRawSentinelNode* m_next;
  75     BasicRawSentinelNode* m_prev;
  76 };
  77
  78 template <typename T, typename RawNode = T> class SentinelLinkedList {
  79 public:
  80     typedef T* iterator;
  81
  82     SentinelLinkedList();
  83
  84     void push(T*);
  85     static void remove(T*);
  86
  87     iterator begin();
  88     iterator end();
  89
  90     bool isEmpty() { return begin() == end(); }
  91
  92 private:
  93     RawNode m_headSentinel;
  94     RawNode m_tailSentinel;
  95 };
  96
  97 template <typename T> void BasicRawSentinelNode<T>::remove()
  98 {
  99     SentinelLinkedList<T, BasicRawSentinelNode<T> >::remove(static_cast<T*>(this));
 100 }
 101
 102 template <typename T, typename RawNode> inline SentinelLinkedList<T, RawNode>::SentinelLinkedList()
 103     : m_headSentinel(Sentinel)
 104     , m_tailSentinel(Sentinel)
 105 {
 106     m_headSentinel.setNext(&m_tailSentinel);
 107     m_headSentinel.setPrev(0);
 108
 109     m_tailSentinel.setPrev(&m_headSentinel);
 110     m_tailSentinel.setNext(0);
 111 }
 112
 113 template <typename T, typename RawNode> inline typename SentinelLinkedList<T, RawNode>::iterator SentinelLinkedList<T, RawNode>::begin()
 114 {
 115     return static_cast<T*>(m_headSentinel.next());
 116 }
 117
 118 template <typename T, typename RawNode> inline typename SentinelLinkedList<T, RawNode>::iterator SentinelLinkedList<T, RawNode>::end()
 119 {
 120     return static_cast<T*>(&m_tailSentinel);
 121 }
 122
 123 template <typename T, typename RawNode> inline void SentinelLinkedList<T, RawNode>::push(T* node)
 124 {
 125     ASSERT(node);
 126     ASSERT(!node->prev());
 127     ASSERT(!node->next());
 128
 129     RawNode* prev = &m_headSentinel;
 130     RawNode* next = m_headSentinel.next();
 131
 132     node->setPrev(prev);
 133     node->setNext(next);
 134
 135     prev->setNext(node);
 136     next->setPrev(node);
 137 }
 138
 139 template <typename T, typename RawNode> inline void SentinelLinkedList<T, RawNode>::remove(T* node)
 140 {
 141     ASSERT(node);
 142     ASSERT(!!node->prev());
 143     ASSERT(!!node->next());
 144
 145     RawNode* prev = node->prev();
 146     RawNode* next = node->next();
 147
 148     prev->setNext(next);
 149     next->setPrev(prev);
 150
 151     node->setPrev(0);
 152     node->setNext(0);
 153 }
 154
 155 }
 156
 157 using WTF::BasicRawSentinelNode;
 158 using WTF::SentinelLinkedList;
 159
 160 #endif
 161