+++ /dev/null
-/*
- * Copyright (C) 2010 Apple Inc. All rights reserved.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- * 1. Redistributions of source code must retain the above copyright
- * notice, this list of conditions and the following disclaimer.
- * 2. Redistributions in binary form must reproduce the above copyright
- * notice, this list of conditions and the following disclaimer in the
- * documentation and/or other materials provided with the distribution.
- *
- * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
- * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
- * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
- * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
- * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
- * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
- * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
- * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
- * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
- * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
- * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
- */
-
-#ifndef BumpPointerAllocator_h
-#define BumpPointerAllocator_h
-
-#include <wtf/PageAllocation.h>
-
-namespace WTF {
-
-#define MINIMUM_BUMP_POOL_SIZE 0x1000
-
-class BumpPointerPool {
-public:
- // ensureCapacity will check whether the current pool has capacity to
- // allocate 'size' bytes of memory If it does not, it will attempt to
- // allocate a new pool (which will be added to this one in a chain).
- //
- // If allocation fails (out of memory) this method will return null.
- // If the return value is non-null, then callers should update any
- // references they have to this current (possibly full) BumpPointerPool
- // to instead point to the newly returned BumpPointerPool.
- BumpPointerPool* ensureCapacity(size_t size)
- {
- void* allocationEnd = static_cast<char*>(m_current) + size;
- ASSERT(allocationEnd > m_current); // check for overflow
- if (allocationEnd <= static_cast<void*>(this))
- return this;
- return ensureCapacityCrossPool(this, size);
- }
-
- // alloc should only be called after calling ensureCapacity; as such
- // alloc will never fail.
- void* alloc(size_t size)
- {
- void* current = m_current;
- void* allocationEnd = static_cast<char*>(current) + size;
- ASSERT(allocationEnd > current); // check for overflow
- ASSERT(allocationEnd <= static_cast<void*>(this));
- m_current = allocationEnd;
- return current;
- }
-
- // The dealloc method releases memory allocated using alloc. Memory
- // must be released in a LIFO fashion, e.g. if the client calls alloc
- // four times, returning pointer A, B, C, D, then the only valid order
- // in which these may be deallocaed is D, C, B, A.
- //
- // The client may optionally skip some deallocations. In the example
- // above, it would be valid to only explicitly dealloc C, A (D being
- // dealloced along with C, B along with A).
- //
- // If pointer was not allocated from this pool (or pools) then dealloc
- // will CRASH(). Callers should update any references they have to
- // this current BumpPointerPool to instead point to the returned
- // BumpPointerPool.
- BumpPointerPool* dealloc(void* position)
- {
- if ((position >= m_start) && (position <= static_cast<void*>(this))) {
- ASSERT(position <= m_current);
- m_current = position;
- return this;
- }
- return deallocCrossPool(this, position);
- }
-
-private:
- // Placement operator new, returns the last 'size' bytes of allocation for use as this.
- void* operator new(size_t size, const PageAllocation& allocation)
- {
- ASSERT(size < allocation.size());
- return reinterpret_cast<char*>(reinterpret_cast<intptr_t>(allocation.base()) + allocation.size()) - size;
- }
-
- BumpPointerPool(const PageAllocation& allocation)
- : m_current(allocation.base())
- , m_start(allocation.base())
- , m_next(0)
- , m_previous(0)
- , m_allocation(allocation)
- {
- }
-
- static BumpPointerPool* create(size_t minimumCapacity = 0)
- {
- // Add size of BumpPointerPool object, check for overflow.
- minimumCapacity += sizeof(BumpPointerPool);
- if (minimumCapacity < sizeof(BumpPointerPool))
- return 0;
-
- size_t poolSize = MINIMUM_BUMP_POOL_SIZE;
- while (poolSize < minimumCapacity) {
- poolSize <<= 1;
- // The following if check relies on MINIMUM_BUMP_POOL_SIZE being a power of 2!
- ASSERT(!(MINIMUM_BUMP_POOL_SIZE & (MINIMUM_BUMP_POOL_SIZE - 1)));
- if (!poolSize)
- return 0;
- }
-
- PageAllocation allocation = PageAllocation::allocate(poolSize);
- if (!!allocation)
- return new(allocation) BumpPointerPool(allocation);
- return 0;
- }
-
- void shrink()
- {
- ASSERT(!m_previous);
- m_current = m_start;
- while (m_next) {
- BumpPointerPool* nextNext = m_next->m_next;
- m_next->destroy();
- m_next = nextNext;
- }
- }
-
- void destroy()
- {
- m_allocation.deallocate();
- }
-
- static BumpPointerPool* ensureCapacityCrossPool(BumpPointerPool* previousPool, size_t size)
- {
- // The pool passed should not have capacity, so we'll start with the next one.
- ASSERT(previousPool);
- ASSERT((static_cast<char*>(previousPool->m_current) + size) > previousPool->m_current); // check for overflow
- ASSERT((static_cast<char*>(previousPool->m_current) + size) > static_cast<void*>(previousPool));
- BumpPointerPool* pool = previousPool->m_next;
-
- while (true) {
- if (!pool) {
- // We've run to the end; allocate a new pool.
- pool = BumpPointerPool::create(size);
- previousPool->m_next = pool;
- pool->m_previous = previousPool;
- return pool;
- }
-
- //
- void* current = pool->m_current;
- void* allocationEnd = static_cast<char*>(current) + size;
- ASSERT(allocationEnd > current); // check for overflow
- if (allocationEnd <= static_cast<void*>(pool))
- return pool;
- }
- }
-
- static BumpPointerPool* deallocCrossPool(BumpPointerPool* pool, void* position)
- {
- // Should only be called if position is not in the current pool.
- ASSERT((position < pool->m_start) || (position > static_cast<void*>(pool)));
-
- while (true) {
- // Unwind the current pool to the start, move back in the chain to the previous pool.
- pool->m_current = pool->m_start;
- pool = pool->m_previous;
-
- // position was nowhere in the chain!
- if (!pool)
- CRASH();
-
- if ((position >= pool->m_start) && (position <= static_cast<void*>(pool))) {
- ASSERT(position <= pool->m_current);
- pool->m_current = position;
- return pool;
- }
- }
- }
-
- void* m_current;
- void* m_start;
- BumpPointerPool* m_next;
- BumpPointerPool* m_previous;
- PageAllocation m_allocation;
-
- friend class BumpPointerAllocator;
-};
-
-// A BumpPointerAllocator manages a set of BumpPointerPool objects, which
-// can be used for LIFO (stack like) allocation.
-//
-// To begin allocating using this class call startAllocator(). The result
-// of this method will be null if the initial pool allocation fails, or a
-// pointer to a BumpPointerPool object that can be used to perform
-// allocations. Whilst running no memory will be released until
-// stopAllocator() is called. At this point all allocations made through
-// this allocator will be reaped, and underlying memory may be freed.
-//
-// (In practice we will still hold on to the initial pool to allow allocation
-// to be quickly restared, but aditional pools will be freed).
-//
-// This allocator is non-renetrant, it is encumbant on the clients to ensure
-// startAllocator() is not called again until stopAllocator() has been called.
-class BumpPointerAllocator {
-public:
- BumpPointerAllocator()
- : m_head(0)
- {
- }
-
- ~BumpPointerAllocator()
- {
- if (m_head)
- m_head->destroy();
- }
-
- BumpPointerPool* startAllocator()
- {
- if (!m_head)
- m_head = BumpPointerPool::create();
- return m_head;
- }
-
- void stopAllocator()
- {
- if (m_head)
- m_head->shrink();
- }
-
-private:
- BumpPointerPool* m_head;
-};
-
-}
-
-using WTF::BumpPointerAllocator;
-
-#endif // BumpPointerAllocator_h
projects / apple / javascriptcore.git / blobdiff