15c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/* 209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) * Copyright (C) 2014 Google Inc. All rights reserved. 35c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 45c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Redistribution and use in source and binary forms, with or without 55c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * modification, are permitted provided that the following conditions are 65c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * met: 75c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 85c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * * Redistributions of source code must retain the above copyright 95c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * notice, this list of conditions and the following disclaimer. 105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * * Redistributions in binary form must reproduce the above 115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * copyright notice, this list of conditions and the following disclaimer 125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * in the documentation and/or other materials provided with the 135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * distribution. 145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * * Neither the name of Google Inc. nor the names of its 155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * contributors may be used to endorse or promote products derived from 165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * this software without specific prior written permission. 175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */ 305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 31d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles)#ifndef HeapLinkedStack_h 32d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles)#define HeapLinkedStack_h 338abfc5808a4e34d6e03867af8bc440dee641886fTorne (Richard Coles) 34a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch#include "platform/heap/Heap.h" 35a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch#include "platform/heap/Visitor.h" 368abfc5808a4e34d6e03867af8bc440dee641886fTorne (Richard Coles) 37c1847b1379d12d0e05df27436bf19a9b1bf12deaTorne (Richard Coles)namespace blink { 388abfc5808a4e34d6e03867af8bc440dee641886fTorne (Richard Coles) 39d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles)template <typename T> 40d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles)class HeapLinkedStack : public GarbageCollected<HeapLinkedStack<T> > { 418abfc5808a4e34d6e03867af8bc440dee641886fTorne (Richard Coles)public: 42d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) HeapLinkedStack() : m_size(0) { } 43d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) 44d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) bool isEmpty(); 458abfc5808a4e34d6e03867af8bc440dee641886fTorne (Richard Coles) 46d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) void push(const T&); 47d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) const T& peek(); 48d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) void pop(); 498abfc5808a4e34d6e03867af8bc440dee641886fTorne (Richard Coles) 50d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) size_t size(); 518abfc5808a4e34d6e03867af8bc440dee641886fTorne (Richard Coles) 52d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) void trace(Visitor* visitor) 53d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) { 54d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) for (Node* current = m_head; current; current = current->m_next) 55d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) visitor->trace(current); 56d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) } 578abfc5808a4e34d6e03867af8bc440dee641886fTorne (Richard Coles) 5809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)private: 59d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) class Node : public GarbageCollected<Node> { 60d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) public: 61d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) Node(const T&, Node* next); 62d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) 63d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) void trace(Visitor* visitor) { visitor->trace(m_data); } 64d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) 65d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) T m_data; 66d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) Member<Node> m_next; 67d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) }; 68d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) 69d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) Member<Node> m_head; 70d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) size_t m_size; 718abfc5808a4e34d6e03867af8bc440dee641886fTorne (Richard Coles)}; 728abfc5808a4e34d6e03867af8bc440dee641886fTorne (Richard Coles) 73d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles)template <typename T> 74d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles)HeapLinkedStack<T>::Node::Node(const T& data, Node* next) 75d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) : m_data(data) 76d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) , m_next(next) 77d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles){ 78d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles)} 79d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) 80d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles)template <typename T> 81d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles)inline bool HeapLinkedStack<T>::isEmpty() 82d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles){ 83d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) return !m_head; 84d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles)} 85d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) 86d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles)template <typename T> 87d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles)inline void HeapLinkedStack<T>::push(const T& data) 88d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles){ 89d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) m_head = new Node(data, m_head); 90d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) ++m_size; 91d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles)} 92d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) 93d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles)template <typename T> 94d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles)inline const T& HeapLinkedStack<T>::peek() 95d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles){ 96d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) return m_head->m_data; 97d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles)} 98d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) 99d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles)template <typename T> 100d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles)inline void HeapLinkedStack<T>::pop() 101d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles){ 102d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) ASSERT(m_head && m_size); 103d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) m_head = m_head->m_next; 104d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) --m_size; 105d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles)} 106d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) 107d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles)template <typename T> 108d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles)inline size_t HeapLinkedStack<T>::size() 10909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles){ 110d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) return m_size; 11109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)} 1128abfc5808a4e34d6e03867af8bc440dee641886fTorne (Richard Coles) 1138abfc5808a4e34d6e03867af8bc440dee641886fTorne (Richard Coles)} 1148abfc5808a4e34d6e03867af8bc440dee641886fTorne (Richard Coles) 115d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles)#endif // HeapLinkedStack_h 116