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 COMPUTER, INC. ``AS IS'' AND ANY
14 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16 * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE COMPUTER, INC. OR
17 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24 */
25
26#ifndef PODFreeListArena_h
27#define PODFreeListArena_h
28
29#include "PODArena.h"
30
31namespace WebCore {
32
33template <class T>
34class PODFreeListArena : public PODArena {
35public:
36    static PassRefPtr<PODFreeListArena> create()
37    {
38        return adoptRef(new PODFreeListArena);
39    }
40
41    template<class Argument1Type> T* allocateObject(const Argument1Type& argument1)
42    {
43        size_t roundedSize = roundUp(sizeof(T), minAlignment<T>());
44        void* ptr = allocate(roundedSize);
45        if (ptr) {
46            // Use placement operator new to allocate a T at this location.
47            new(ptr) T(argument1);
48        }
49        return static_cast<T*>(ptr);
50    }
51
52    void freeObject(T* ptr)
53    {
54        for (typename Vector<OwnPtr<FreeListChunk> >::const_iterator it = m_chunks.begin(), end = m_chunks.end(); it != end; ++it) {
55            FreeListChunk* chunk = static_cast<FreeListChunk*>(it->get());
56            if (chunk->contains(ptr))
57                chunk->free(ptr);
58        }
59    }
60
61private:
62    // The initial size of allocated chunks; increases as necessary to
63    // satisfy large allocations. Mainly public for unit tests.
64    enum {
65        DefaultChunkSize = 16384
66    };
67
68    PODFreeListArena()
69        : m_current(0)
70        , m_currentChunkSize(DefaultChunkSize)
71    {
72    }
73
74    void* allocate(size_t size)
75    {
76        void* ptr = 0;
77        if (m_current) {
78            // First allocate from the current chunk.
79            ptr = m_current->allocate(size);
80            if (!ptr) {
81                // Check if we can allocate from other chunks' free list.
82                for (typename Vector<OwnPtr<FreeListChunk> >::const_iterator it = m_chunks.begin(), end = m_chunks.end(); it != end; ++it) {
83                    FreeListChunk* chunk = static_cast<FreeListChunk*>(it->get());
84                    if (chunk->hasFreeList()) {
85                        ptr = chunk->allocate(size);
86                        if (ptr)
87                            break;
88                    }
89                }
90            }
91        }
92
93        if (!ptr) {
94            if (size > m_currentChunkSize)
95                m_currentChunkSize = size;
96            m_chunks.append(adoptPtr(new FreeListChunk(m_currentChunkSize)));
97            m_current = m_chunks.last().get();
98            ptr = m_current->allocate(size);
99        }
100        return ptr;
101    }
102
103    // Manages a chunk of memory and individual allocations out of it.
104    class FreeListChunk {
105        WTF_MAKE_NONCOPYABLE(FreeListChunk);
106
107        struct FreeCell {
108            FreeCell *m_next;
109        };
110    public:
111        explicit FreeListChunk(size_t size)
112            : m_size(size)
113            , m_currentOffset(0)
114            , m_freeList(0)
115        {
116            m_base = static_cast<uint8_t*>(fastMalloc(size));
117        }
118
119        // Frees the memory allocated from the Allocator in the
120        // constructor.
121        ~FreeListChunk()
122        {
123            fastFree(m_base);
124        }
125
126        // Returns a pointer to "size" bytes of storage, or 0 if this
127        // Chunk could not satisfy the allocation.
128        void* allocate(size_t size)
129        {
130            if (m_freeList) {
131                // Reuse a cell from the free list.
132                void *cell = m_freeList;
133                m_freeList = m_freeList->m_next;
134                return cell;
135            }
136
137            // Check for overflow
138            if (m_currentOffset + size < m_currentOffset)
139                return 0;
140
141            if (m_currentOffset + size > m_size)
142                return 0;
143
144            void* result = m_base + m_currentOffset;
145            m_currentOffset += size;
146            return result;
147        }
148
149        void free(void* ptr)
150        {
151            // Add the pointer to free list.
152            ASSERT(contains(ptr));
153
154            FreeCell* cell = reinterpret_cast<FreeCell*>(ptr);
155            cell->m_next = m_freeList;
156            m_freeList = cell;
157        }
158
159        bool contains(void* ptr) const
160        {
161            return ptr >= m_base && ptr < m_base + m_size;
162        }
163
164        bool hasFreeList() const
165        {
166            return m_freeList;
167        }
168
169    private:
170        uint8_t* m_base;
171        size_t m_size;
172        size_t m_currentOffset;
173
174        FreeCell *m_freeList;
175    };
176
177    FreeListChunk* m_current;
178    size_t m_currentChunkSize;
179    Vector<OwnPtr<FreeListChunk> > m_chunks;
180};
181
182} // namespace WebCore
183
184#endif
185