15c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/* 2926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) * Copyright (C) 2013 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) 31591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch#ifndef LinkedStack_h 32591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch#define LinkedStack_h 335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 34591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch#include "wtf/FastAllocBase.h" 35591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch#include "wtf/OwnPtr.h" 3653e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles) 37591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdochnamespace WTF { 385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 39591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdochtemplate <typename T> 40591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdochclass LinkedStack { 41591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch WTF_MAKE_FAST_ALLOCATED; 42591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdochpublic: 43591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch LinkedStack() : m_size(0) { } 445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 45591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch bool isEmpty(); 46591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch 47591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch void push(const T&); 48591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch const T& peek(); 49591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch void pop(); 50591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch 51591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch size_t size(); 52591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch 53f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles) // This inner class used to be private but is now public on account of a 54f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles) // possible MSVC bug. It can be made private again if we get rid of 55f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles) // WTF_MAKE_FAST_ALLOCATED ever. 56591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch class Node { 57591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch WTF_MAKE_FAST_ALLOCATED; 58591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch public: 59591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch Node(const T&, PassOwnPtr<Node> next); 60591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch 61591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch T m_data; 62591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch OwnPtr<Node> m_next; 63591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch }; 64591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch 65f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles)private: 66591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch OwnPtr<Node> m_head; 67591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch size_t m_size; 68591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch}; 69591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch 70591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdochtemplate <typename T> 71591b958dee2cf159d33a0b931e6231072eaf38d5Ben MurdochLinkedStack<T>::Node::Node(const T& data, PassOwnPtr<Node> next) 72591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch : m_data(data) 73591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch , m_next(next) 74521d96ec04ace82590870fb04353ec4f82bb150fTorne (Richard Coles){ 75926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)} 765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 77591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdochtemplate <typename T> 78591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdochinline bool LinkedStack<T>::isEmpty() 79926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles){ 80591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch return !m_head; 81926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)} 82926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) 83591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdochtemplate <typename T> 84591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdochinline void LinkedStack<T>::push(const T& data) 85521d96ec04ace82590870fb04353ec4f82bb150fTorne (Richard Coles){ 86591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch m_head = adoptPtr(new Node(data, m_head.release())); 87591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch ++m_size; 88926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)} 89926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) 90591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdochtemplate <typename T> 91591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdochinline const T& LinkedStack<T>::peek() 92521d96ec04ace82590870fb04353ec4f82bb150fTorne (Richard Coles){ 93591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch return m_head->m_data; 94521d96ec04ace82590870fb04353ec4f82bb150fTorne (Richard Coles)} 95521d96ec04ace82590870fb04353ec4f82bb150fTorne (Richard Coles) 96591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdochtemplate <typename T> 97591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdochinline void LinkedStack<T>::pop() 98521d96ec04ace82590870fb04353ec4f82bb150fTorne (Richard Coles){ 99591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch ASSERT(m_head && m_size); 100591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch m_head = m_head->m_next.release(); 101591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch --m_size; 102926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)} 1035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 104591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdochtemplate <typename T> 105591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdochinline size_t LinkedStack<T>::size() 106521d96ec04ace82590870fb04353ec4f82bb150fTorne (Richard Coles){ 107591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch return m_size; 108591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch} 109591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch 1105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 111521d96ec04ace82590870fb04353ec4f82bb150fTorne (Richard Coles) 112591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdochusing WTF::LinkedStack; 113591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch 114591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch#endif 115