Home | History | Annotate | Download | only in wtf 
      1 /*
      2  * Copyright (C) 2013 Google 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 are
      6  * met:
      7  *
      8  *     * Redistributions of source code must retain the above copyright
      9  * notice, this list of conditions and the following disclaimer.
     10  *     * Redistributions in binary form must reproduce the above
     11  * copyright notice, this list of conditions and the following disclaimer
     12  * in the documentation and/or other materials provided with the
     13  * distribution.
     14  *     * Neither the name of Google Inc. nor the names of its
     15  * contributors may be used to endorse or promote products derived from
     16  * this software without specific prior written permission.
     17  *
     18  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
     19  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
     20  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
     21  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
     22  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
     23  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
     24  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
     25  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
     26  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
     27  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
     28  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
     29  */
     30 
     31 #ifndef LinkedStack_h
     32 #define LinkedStack_h
     33 
     34 #include "wtf/FastAllocBase.h"
     35 #include "wtf/OwnPtr.h"
     36 
     37 namespace WTF {
     38 
     39 template <typename T>
     40 class LinkedStack {
     41     WTF_MAKE_FAST_ALLOCATED;
     42 public:
     43     LinkedStack() : m_size(0) { }
     44 
     45     bool isEmpty();
     46 
     47     void push(const T&);
     48     const T& peek();
     49     void pop();
     50 
     51     size_t size();
     52 
     53     // This inner class used to be private but is now public on account of a
     54     // possible MSVC bug. It can be made private again if we get rid of
     55     // WTF_MAKE_FAST_ALLOCATED ever.
     56     class Node {
     57         WTF_MAKE_FAST_ALLOCATED;
     58     public:
     59         Node(const T&, PassOwnPtr<Node> next);
     60 
     61         T m_data;
     62         OwnPtr<Node> m_next;
     63     };
     64 
     65 private:
     66     OwnPtr<Node> m_head;
     67     size_t m_size;
     68 };
     69 
     70 template <typename T>
     71 LinkedStack<T>::Node::Node(const T& data, PassOwnPtr<Node> next)
     72     : m_data(data)
     73     , m_next(next)
     74 {
     75 }
     76 
     77 template <typename T>
     78 inline bool LinkedStack<T>::isEmpty()
     79 {
     80     return !m_head;
     81 }
     82 
     83 template <typename T>
     84 inline void LinkedStack<T>::push(const T& data)
     85 {
     86     m_head = adoptPtr(new Node(data, m_head.release()));
     87     ++m_size;
     88 }
     89 
     90 template <typename T>
     91 inline const T& LinkedStack<T>::peek()
     92 {
     93     return m_head->m_data;
     94 }
     95 
     96 template <typename T>
     97 inline void LinkedStack<T>::pop()
     98 {
     99     ASSERT(m_head && m_size);
    100     m_head = m_head->m_next.release();
    101     --m_size;
    102 }
    103 
    104 template <typename T>
    105 inline size_t LinkedStack<T>::size()
    106 {
    107     return m_size;
    108 }
    109 
    110 }
    111 
    112 using WTF::LinkedStack;
    113 
    114 #endif
    115