1 /* ScummVM - Graphic Adventure Engine
2 *
3 * ScummVM is the legal property of its developers, whose names
4 * are too numerous to list here. Please refer to the COPYRIGHT
5 * file distributed with this source distribution.
6 *
7 * This program is free software; you can redistribute it and/or
8 * modify it under the terms of the GNU General Public License
9 * as published by the Free Software Foundation; either version 2
10 * of the License, or (at your option) any later version.
11 *
12 * This program is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with this program; if not, write to the Free Software
19 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
20 *
21 */
22
23 #ifndef COMMON_MEMORYPOOL_H
24 #define COMMON_MEMORYPOOL_H
25
26 #include "common/scummsys.h"
27 #include "common/array.h"
28
29
30 namespace Common {
31
32 /**
33 * @defgroup common_memory_pool Memory pool
34 * @ingroup common_memory
35 *
36 * @brief API for managing the memory pool.
37 * @{
38 */
39
40 /**
41 * This class provides a pool of memory 'chunks' of identical size.
42 * The size of a chunk is determined when creating the memory pool.
43 *
44 * Using a memory pool may yield better performance and memory usage
45 * when allocating and deallocating many memory blocks of equal size.
46 * E.g. the Common::String class uses a memory pool for the refCount
47 * variables (each the size of an int) it allocates for each string
48 * instance.
49 */
50 class MemoryPool {
51 protected:
52 MemoryPool(const MemoryPool&);
53 MemoryPool& operator=(const MemoryPool&);
54
55 struct Page {
56 void *start;
57 size_t numChunks;
58 };
59
60 const size_t _chunkSize;
61 Array<Page> _pages;
62 void *_next;
63 size_t _chunksPerPage;
64
65 void allocPage();
66 void addPageToPool(const Page &page);
67 bool isPointerInPage(void *ptr, const Page &page);
68
69 public:
70 /**
71 * Constructor for a memory pool with the given chunk size.
72 * @param chunkSize the chunk size of this memory pool
73 */
74 explicit MemoryPool(size_t chunkSize);
75 ~MemoryPool();
76
77 /**
78 * Allocate a new chunk from the memory pool.
79 */
80 void *allocChunk();
81 /**
82 * Return a chunk to the memory pool. The given pointer must have
83 * been obtained from calling the allocChunk() method of the very
84 * same MemoryPool instance. Passing any other pointer (e.g. to
85 * a chunk from another MemoryPool, or a malloc'ed memory block)
86 * will lead to undefined behavior and may result in a crash (if
87 * you are lucky) or in silent data corruption.
88 */
89 void freeChunk(void *ptr);
90
91 /**
92 * Perform garbage collection. The memory pool stores all the
93 * chunks it manages in memory 'pages' obtained via the classic
94 * memory allocation APIs (i.e. malloc/free). Ordinarily, once
95 * a page has been allocated, it won't be released again during
96 * the life time of the memory pool. The exception is when this
97 * method is called.
98 */
99 void freeUnusedPages();
100
101 /**
102 * Return the chunk size used by this memory pool.
103 */
getChunkSize()104 size_t getChunkSize() const { return _chunkSize; }
105 };
106
107 /**
108 * This is a memory pool which already contains in itself some storage
109 * space for a fixed number of chunks. Thus if the memory pool is only
110 * lightly used, no malloc() calls have to be made at all.
111 */
112 template<size_t CHUNK_SIZE, size_t NUM_INTERNAL_CHUNKS = 32>
113 class FixedSizeMemoryPool : public MemoryPool {
114 private:
115 enum {
116 REAL_CHUNK_SIZE = (CHUNK_SIZE + sizeof(void *) - 1) & (~(sizeof(void *) - 1))
117 };
118
119 byte _storage[NUM_INTERNAL_CHUNKS * REAL_CHUNK_SIZE];
120 public:
FixedSizeMemoryPool()121 FixedSizeMemoryPool() : MemoryPool(CHUNK_SIZE) {
122 assert(REAL_CHUNK_SIZE == _chunkSize);
123 // Insert some static storage
124 Page internalPage = { _storage, NUM_INTERNAL_CHUNKS };
125 addPageToPool(internalPage);
126 }
127 };
128
129 // Ensure NUM_INTERNAL_CHUNKS == 0 results in a compile error
130 template<size_t CHUNK_SIZE>
131 class FixedSizeMemoryPool<CHUNK_SIZE,0> : public MemoryPool {
132 public:
FixedSizeMemoryPool()133 FixedSizeMemoryPool() : MemoryPool(CHUNK_SIZE) {}
134 };
135
136 /**
137 * A memory pool for C++ objects.
138 */
139 template<class T, size_t NUM_INTERNAL_CHUNKS = 32>
140 class ObjectPool : public FixedSizeMemoryPool<sizeof(T), NUM_INTERNAL_CHUNKS> {
141 public:
142 /**
143 * Return the memory chunk used as storage for the given object back
144 * to the pool, after calling its destructor.
145 */
deleteChunk(T * ptr)146 void deleteChunk(T *ptr) {
147 ptr->~T();
148 this->freeChunk(ptr);
149 }
150 };
151
152 /** @} */
153
154 } // End of namespace Common
155
156 /**
157 * A custom placement new operator, using an arbitrary MemoryPool.
158 *
159 * This *should* work with all C++ implementations, but may not.
160 *
161 * For details on using placement new for custom allocators, see e.g.
162 * <http://www.parashift.com/c++-faq-lite/dtors.html#faq-11.14>
163 */
new(size_t nbytes,Common::MemoryPool & pool)164 inline void *operator new(size_t nbytes, Common::MemoryPool &pool) {
165 assert(nbytes <= pool.getChunkSize());
166 return pool.allocChunk();
167 }
168
delete(void * p,Common::MemoryPool & pool)169 inline void operator delete(void *p, Common::MemoryPool &pool) {
170 pool.freeChunk(p);
171 }
172
173 #endif
174