Home | History | Annotate | Download | only in wtf 
      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
    195