Source/WTF/wtf/DoublyLinkedList.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 #ifndef DoublyLinkedList_h
  27 #define DoublyLinkedList_h
  28
  29 namespace WTF {
  30
  31 // This class allows nodes to share code without dictating data member layout.
  32 template<typename T> class DoublyLinkedListNode {
  33 public:
  34     DoublyLinkedListNode();
  35
  36     void setPrev(T*);
  37     void setNext(T*);
  38
  39     T* prev() const;
  40     T* next() const;
  41 };
  42
  43 template<typename T> inline DoublyLinkedListNode<T>::DoublyLinkedListNode()
  44 {
  45     setPrev(0);
  46     setNext(0);
  47 }
  48
  49 template<typename T> inline void DoublyLinkedListNode<T>::setPrev(T* prev)
  50 {
  51     static_cast<T*>(this)->m_prev = prev;
  52 }
  53
  54 template<typename T> inline void DoublyLinkedListNode<T>::setNext(T* next)
  55 {
  56     static_cast<T*>(this)->m_next = next;
  57 }
  58
  59 template<typename T> inline T* DoublyLinkedListNode<T>::prev() const
  60 {
  61     return static_cast<const T*>(this)->m_prev;
  62 }
  63
  64 template<typename T> inline T* DoublyLinkedListNode<T>::next() const
  65 {
  66     return static_cast<const T*>(this)->m_next;
  67 }
  68
  69 template<typename T> class DoublyLinkedList {
  70 public:
  71     DoublyLinkedList();
  72
  73     bool isEmpty() const;
  74     size_t size() const; // This is O(n).
  75     void clear();
  76
  77     T* head() const;
  78     T* removeHead();
  79
  80     T* tail() const;
  81
  82     void push(T*);
  83     void append(T*);
  84     void remove(T*);
  85
  86 private:
  87     T* m_head;
  88     T* m_tail;
  89 };
  90
  91 template<typename T> inline DoublyLinkedList<T>::DoublyLinkedList()
  92     : m_head(0)
  93     , m_tail(0)
  94 {
  95 }
  96
  97 template<typename T> inline bool DoublyLinkedList<T>::isEmpty() const
  98 {
  99     return !m_head;
 100 }
 101
 102 template<typename T> inline size_t DoublyLinkedList<T>::size() const
 103 {
 104     size_t size = 0;
 105     for (T* node = m_head; node; node = node->next())
 106         ++size;
 107     return size;
 108 }
 109
 110 template<typename T> inline void DoublyLinkedList<T>::clear()
 111 {
 112     m_head = 0;
 113     m_tail = 0;
 114 }
 115
 116 template<typename T> inline T* DoublyLinkedList<T>::head() const
 117 {
 118     return m_head;
 119 }
 120
 121 template<typename T> inline T* DoublyLinkedList<T>::tail() const
 122 {
 123     return m_tail;
 124 }
 125
 126 template<typename T> inline void DoublyLinkedList<T>::push(T* node)
 127 {
 128     if (!m_head) {
 129         ASSERT(!m_tail);
 130         m_head = node;
 131         m_tail = node;
 132         node->setPrev(0);
 133         node->setNext(0);
 134         return;
 135     }
 136
 137     ASSERT(m_tail);
 138     m_head->setPrev(node);
 139     node->setNext(m_head);
 140     node->setPrev(0);
 141     m_head = node;
 142 }
 143
 144 template<typename T> inline void DoublyLinkedList<T>::append(T* node)
 145 {
 146     if (!m_tail) {
 147         ASSERT(!m_head);
 148         m_head = node;
 149         m_tail = node;
 150         node->setPrev(0);
 151         node->setNext(0);
 152         return;
 153     }
 154
 155     ASSERT(m_head);
 156     m_tail->setNext(node);
 157     node->setPrev(m_tail);
 158     node->setNext(0);
 159     m_tail = node;
 160 }
 161
 162 template<typename T> inline void DoublyLinkedList<T>::remove(T* node)
 163 {
 164     if (node->prev()) {
 165         ASSERT(node != m_head);
 166         node->prev()->setNext(node->next());
 167     } else {
 168         ASSERT(node == m_head);
 169         m_head = node->next();
 170     }
 171
 172     if (node->next()) {
 173         ASSERT(node != m_tail);
 174         node->next()->setPrev(node->prev());
 175     } else {
 176         ASSERT(node == m_tail);
 177         m_tail = node->prev();
 178     }
 179 }
 180
 181 template<typename T> inline T* DoublyLinkedList<T>::removeHead()
 182 {
 183     T* node = head();
 184     if (node)
 185         remove(node);
 186     return node;
 187 }
 188
 189 } // namespace WTF
 190
 191 using WTF::DoublyLinkedListNode;
 192 using WTF::DoublyLinkedList;
 193
 194 #endif