181bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch/* 281bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch * Copyright (C) 2011 Apple Inc. All rights reserved. 381bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch * 481bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch * Redistribution and use in source and binary forms, with or without 581bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch * modification, are permitted provided that the following conditions 681bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch * are met: 781bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch * 1. Redistributions of source code must retain the above copyright 881bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch * notice, this list of conditions and the following disclaimer. 981bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch * 2. Redistributions in binary form must reproduce the above copyright 1081bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch * notice, this list of conditions and the following disclaimer in the 1181bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch * documentation and/or other materials provided with the distribution. 1281bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch * 1381bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS'' 1481bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, 1581bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 1681bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS 1781bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 1881bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 1981bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 2081bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 2181bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 2281bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF 2381bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch * THE POSSIBILITY OF SUCH DAMAGE. 2481bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch */ 2581bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch 2681bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch// A SentinelLinkedList is a linked list with dummy head and tail sentinels, 2781bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch// which allow for branch-less insertion and removal, and removal without a 2881bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch// pointer to the list. 2981bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch// 3081bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch// Requires: Node is a concrete class with: 3181bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch// Node(SentinelTag); 3281bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch// void setPrev(Node*); 3381bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch// Node* prev(); 3481bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch// void setNext(Node*); 3581bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch// Node* next(); 3681bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch 3781bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch#ifndef SentinelLinkedList_h 3881bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch#define SentinelLinkedList_h 3981bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch 4081bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdochnamespace WTF { 4181bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch 4281bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdochenum SentinelTag { Sentinel }; 4381bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch 4481bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdochtemplate <typename Node> class SentinelLinkedList { 4581bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdochpublic: 4681bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch typedef Node* iterator; 4781bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch 4881bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch SentinelLinkedList(); 4981bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch 5081bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch void push(Node*); 5181bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch static void remove(Node*); 5281bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch 5381bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch iterator begin(); 5481bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch iterator end(); 5581bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch 5681bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdochprivate: 5781bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch Node m_headSentinel; 5881bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch Node m_tailSentinel; 5981bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch}; 6081bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch 6181bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdochtemplate <typename Node> inline SentinelLinkedList<Node>::SentinelLinkedList() 6281bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch : m_headSentinel(Sentinel) 6381bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch , m_tailSentinel(Sentinel) 6481bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch{ 6581bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch m_headSentinel.setNext(&m_tailSentinel); 6681bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch m_headSentinel.setPrev(0); 6781bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch 6881bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch m_tailSentinel.setPrev(&m_headSentinel); 6981bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch m_tailSentinel.setNext(0); 7081bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch} 7181bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch 7281bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdochtemplate <typename Node> inline typename SentinelLinkedList<Node>::iterator SentinelLinkedList<Node>::begin() 7381bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch{ 7481bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch return m_headSentinel.next(); 7581bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch} 7681bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch 7781bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdochtemplate <typename Node> inline typename SentinelLinkedList<Node>::iterator SentinelLinkedList<Node>::end() 7881bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch{ 7981bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch return &m_tailSentinel; 8081bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch} 8181bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch 8281bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdochtemplate <typename Node> inline void SentinelLinkedList<Node>::push(Node* node) 8381bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch{ 8481bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch ASSERT(node); 8581bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch Node* prev = &m_headSentinel; 8681bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch Node* next = m_headSentinel.next(); 8781bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch 8881bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch node->setPrev(prev); 8981bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch node->setNext(next); 9081bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch 9181bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch prev->setNext(node); 9281bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch next->setPrev(node); 9381bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch} 9481bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch 9581bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdochtemplate <typename Node> inline void SentinelLinkedList<Node>::remove(Node* node) 9681bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch{ 9781bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch Node* prev = node->prev(); 9881bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch Node* next = node->next(); 9981bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch 10081bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch prev->setNext(next); 10181bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch next->setPrev(prev); 10281bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch} 10381bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch 10481bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch} 10581bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch 10681bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdochusing WTF::SentinelLinkedList; 10781bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch 10881bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch#endif 10981bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch 110