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 template <typename Node> class DoublyLinkedList {
     32 public:
     33     DoublyLinkedList();
     34 
     35     bool isEmpty();
     36 
     37     Node* head();
     38 
     39     void append(Node*);
     40     void remove(Node*);
     41 
     42 private:
     43     Node* m_head;
     44     Node* m_tail;
     45 };
     46 
     47 template <typename Node> inline DoublyLinkedList<Node>::DoublyLinkedList()
     48     : m_head(0)
     49     , m_tail(0)
     50 {
     51 }
     52 
     53 template <typename Node> inline bool DoublyLinkedList<Node>::isEmpty()
     54 {
     55     return !m_head;
     56 }
     57 
     58 template <typename Node> inline Node* DoublyLinkedList<Node>::head()
     59 {
     60     return m_head;
     61 }
     62 
     63 template <typename Node> inline void DoublyLinkedList<Node>::append(Node* node)
     64 {
     65     if (!m_tail) {
     66         ASSERT(!m_head);
     67         m_head = node;
     68         m_tail = node;
     69         node->setPrev(0);
     70         node->setNext(0);
     71         return;
     72     }
     73 
     74     ASSERT(m_head);
     75     m_tail->setNext(node);
     76     node->setPrev(m_tail);
     77     node->setNext(0);
     78     m_tail = node;
     79 }
     80 
     81 template <typename Node> inline void DoublyLinkedList<Node>::remove(Node* node)
     82 {
     83     if (node->prev()) {
     84         ASSERT(node != m_head);
     85         node->prev()->setNext(node->next());
     86     } else {
     87         ASSERT(node == m_head);
     88         m_head = node->next();
     89     }
     90 
     91     if (node->next()) {
     92         ASSERT(node != m_tail);
     93         node->next()->setPrev(node->prev());
     94     } else {
     95         ASSERT(node == m_tail);
     96         m_tail = node->prev();
     97     }
     98 }
     99 
    100 } // namespace WTF
    101 
    102 using WTF::DoublyLinkedList;
    103 
    104 #endif
    105