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