wtf/SentinelLinkedList.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 //    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