1/* 2 * Copyright (C) 2011 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 BlockStack_h 27#define BlockStack_h 28 29#include <wtf/Assertions.h> 30#include <wtf/FastMalloc.h> 31#include <wtf/Vector.h> 32 33namespace WTF { 34 35template <typename T> class BlockStack { 36public: 37 static const size_t blockSize = 4096; 38 static const size_t blockLength = blockSize / sizeof(T); 39 40 BlockStack(); 41 ~BlockStack(); 42 43 T* grow(); 44 void shrink(T*); 45 46 const Vector<T*>& blocks(); 47 48private: 49 Vector<T*> m_blocks; 50 T* m_spareBlock; // Used to avoid thrash at block boundaries. 51}; 52 53template <typename T> BlockStack<T>::BlockStack() 54 : m_spareBlock(0) 55{ 56} 57 58template <typename T> BlockStack<T>::~BlockStack() 59{ 60 if (m_spareBlock) 61 fastFree(m_spareBlock); 62 for (size_t i = 0; i < m_blocks.size(); ++i) 63 fastFree(m_blocks[i]); 64} 65 66template <typename T> inline const Vector<T*>& BlockStack<T>::blocks() 67{ 68 return m_blocks; 69} 70 71template <typename T> T* BlockStack<T>::grow() 72{ 73 T* block = m_spareBlock ? m_spareBlock : static_cast<T*>(fastMalloc(blockSize)); 74 m_spareBlock = 0; 75 76 m_blocks.append(block); 77 return block; 78} 79 80template <typename T> void BlockStack<T>::shrink(T* newEnd) 81{ 82 ASSERT(newEnd != m_blocks.last() + blockLength); 83 m_spareBlock = m_blocks.last(); 84 m_blocks.removeLast(); 85 86 while (m_blocks.last() + blockLength != newEnd) { 87 fastFree(m_blocks.last()); 88 m_blocks.removeLast(); 89 } 90} 91 92} 93 94using WTF::BlockStack; 95 96#endif 97