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 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