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 //    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 Node> class SentinelLinkedList {
     45 public:
     46     typedef Node* iterator;
     47 
     48     SentinelLinkedList();
     49 
     50     void push(Node*);
     51     static void remove(Node*);
     52 
     53     iterator begin();
     54     iterator end();
     55 
     56 private:
     57     Node m_headSentinel;
     58     Node m_tailSentinel;
     59 };
     60 
     61 template <typename Node> inline SentinelLinkedList<Node>::SentinelLinkedList()
     62     : m_headSentinel(Sentinel)
     63     , m_tailSentinel(Sentinel)
     64 {
     65     m_headSentinel.setNext(&m_tailSentinel);
     66     m_headSentinel.setPrev(0);
     67 
     68     m_tailSentinel.setPrev(&m_headSentinel);
     69     m_tailSentinel.setNext(0);
     70 }
     71 
     72 template <typename Node> inline typename SentinelLinkedList<Node>::iterator SentinelLinkedList<Node>::begin()
     73 {
     74     return m_headSentinel.next();
     75 }
     76 
     77 template <typename Node> inline typename SentinelLinkedList<Node>::iterator SentinelLinkedList<Node>::end()
     78 {
     79     return &m_tailSentinel;
     80 }
     81 
     82 template <typename Node> inline void SentinelLinkedList<Node>::push(Node* node)
     83 {
     84     ASSERT(node);
     85     Node* prev = &m_headSentinel;
     86     Node* next = m_headSentinel.next();
     87 
     88     node->setPrev(prev);
     89     node->setNext(next);
     90 
     91     prev->setNext(node);
     92     next->setPrev(node);
     93 }
     94 
     95 template <typename Node> inline void SentinelLinkedList<Node>::remove(Node* node)
     96 {
     97     Node* prev = node->prev();
     98     Node* next = node->next();
     99 
    100     prev->setNext(next);
    101     next->setPrev(prev);
    102 }
    103 
    104 }
    105 
    106 using WTF::SentinelLinkedList;
    107 
    108 #endif
    109 
    110