181bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch/* 281bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch * Copyright (C) 2011 Apple Inc. All rights reserved. 381bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch * 481bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch * Redistribution and use in source and binary forms, with or without 581bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch * modification, are permitted provided that the following conditions 681bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch * are met: 781bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch * 1. Redistributions of source code must retain the above copyright 881bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch * notice, this list of conditions and the following disclaimer. 981bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch * 2. Redistributions in binary form must reproduce the above copyright 1081bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch * notice, this list of conditions and the following disclaimer in the 1181bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch * documentation and/or other materials provided with the distribution. 1281bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch * 1381bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS'' 1481bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, 1581bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 1681bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS 1781bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 1881bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 1981bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 2081bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 2181bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 2281bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF 2381bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch * THE POSSIBILITY OF SUCH DAMAGE. 2481bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch */ 2581bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch 2681bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch#ifndef BlockStack_h 2781bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch#define BlockStack_h 2881bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch 2981bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch#include <wtf/Assertions.h> 3081bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch#include <wtf/Vector.h> 3181bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch 3281bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdochnamespace WTF { 3381bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch 3481bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdochtemplate <typename T> class BlockStack { 3581bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdochpublic: 3681bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch static const size_t blockSize = 4096; 3781bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch static const size_t blockLength = blockSize / sizeof(T); 3881bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch 3981bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch BlockStack(); 4081bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch ~BlockStack(); 4181bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch 4281bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch T* grow(); 4381bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch void shrink(T*); 4481bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch 4581bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch const Vector<T*>& blocks(); 4681bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch 4781bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdochprivate: 4881bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch Vector<T*> m_blocks; 4981bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch T* m_spareBlock; // Used to avoid thrash at block boundaries. 5081bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch}; 5181bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch 5281bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdochtemplate <typename T> BlockStack<T>::BlockStack() 5381bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch : m_spareBlock(0) 5481bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch{ 5581bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch} 5681bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch 5781bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdochtemplate <typename T> BlockStack<T>::~BlockStack() 5881bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch{ 5981bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch if (m_spareBlock) 6081bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch free(m_spareBlock); 6181bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch for (size_t i = 0; i < m_blocks.size(); ++i) 6281bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch free(m_blocks[i]); 6381bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch} 6481bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch 6581bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdochtemplate <typename T> inline const Vector<T*>& BlockStack<T>::blocks() 6681bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch{ 6781bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch return m_blocks; 6881bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch} 6981bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch 7081bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdochtemplate <typename T> T* BlockStack<T>::grow() 7181bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch{ 7281bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch T* block = m_spareBlock ? m_spareBlock : static_cast<T*>(malloc(blockSize)); 7381bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch m_spareBlock = 0; 7481bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch 7581bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch m_blocks.append(block); 7681bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch return block; 7781bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch} 7881bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch 7981bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdochtemplate <typename T> void BlockStack<T>::shrink(T* newEnd) 8081bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch{ 8181bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch ASSERT(newEnd != m_blocks.last() + blockLength); 8281bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch m_spareBlock = m_blocks.last(); 8381bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch m_blocks.removeLast(); 8481bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch 8581bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch while (m_blocks.last() + blockLength != newEnd) { 8681bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch free(m_blocks.last()); 8781bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch m_blocks.removeLast(); 8881bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch } 8981bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch} 9081bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch 9181bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch} 9281bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch 9381bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdochusing WTF::BlockStack; 9481bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch 9581bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch#endif 96