1/* 2 * Copyright (C) 2013 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#ifndef Bag_h 27#define Bag_h 28 29namespace WTF { 30 31template<typename T> 32class Bag { 33private: 34 class Node { 35 WTF_MAKE_FAST_ALLOCATED; 36 public: 37 T m_item; 38 Node* m_next; 39 }; 40 41public: 42 Bag() 43 : m_head(0) 44 { 45 } 46 47 ~Bag() 48 { 49 while (m_head) { 50 Node* current = m_head; 51 m_head = current->m_next; 52 delete current; 53 } 54 } 55 56 T* add() 57 { 58 Node* newNode = new Node; 59 newNode->m_next = m_head; 60 m_head = newNode; 61 return &newNode->m_item; 62 } 63 64 class iterator { 65 public: 66 iterator() 67 : m_node(0) 68 { 69 } 70 71 // This is sort of cheating; it's equivalent to iter == end(). 72 bool operator!() const { return !m_node; } 73 74 T* operator*() const { return &m_node->m_item; } 75 76 iterator& operator++() 77 { 78 m_node = m_node->m_next; 79 return *this; 80 } 81 82 bool operator==(const iterator& other) const 83 { 84 return m_node == other.m_node; 85 } 86 87 bool operator!=(const iterator& other) const 88 { 89 return !(*this == other); 90 } 91 92 private: 93 template<typename U> friend class WTF::Bag; 94 Node* m_node; 95 }; 96 97 iterator begin() 98 { 99 iterator result; 100 result.m_node = m_head; 101 return result; 102 } 103 104 iterator end() { return iterator(); } 105 106 bool isEmpty() const { return !m_head; } 107 108private: 109 Node* m_head; 110}; 111 112} // namespace WTF 113 114using WTF::Bag; 115 116#endif // Bag_h 117 118