diff options
Diffstat (limited to 'devtools')
-rw-r--r-- | devtools/create_titanic/hashmap.h | 2 | ||||
-rw-r--r-- | devtools/create_titanic/memorypool.cpp | 182 | ||||
-rw-r--r-- | devtools/create_titanic/memorypool.h | 162 | ||||
-rw-r--r-- | devtools/create_titanic/str.cpp | 2 |
4 files changed, 346 insertions, 2 deletions
diff --git a/devtools/create_titanic/hashmap.h b/devtools/create_titanic/hashmap.h index d7ba100571..c8691aeb42 100644 --- a/devtools/create_titanic/hashmap.h +++ b/devtools/create_titanic/hashmap.h @@ -50,7 +50,7 @@ #endif #ifdef USE_HASHMAP_MEMORY_POOL -#include "common/memorypool.h" +#include "memorypool.h" #endif diff --git a/devtools/create_titanic/memorypool.cpp b/devtools/create_titanic/memorypool.cpp new file mode 100644 index 0000000000..13c640b6ad --- /dev/null +++ b/devtools/create_titanic/memorypool.cpp @@ -0,0 +1,182 @@ +/* ScummVM - Graphic Adventure Engine + * + * ScummVM is the legal property of its developers, whose names + * are too numerous to list here. Please refer to the COPYRIGHT + * file distributed with this source distribution. + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + * + */ + +#include "memorypool.h" +#include "common/util.h" + +namespace Common { + +enum { + INITIAL_CHUNKS_PER_PAGE = 8 +}; + +static size_t adjustChunkSize(size_t chunkSize) { + // You must at least fit the pointer in the node (technically unneeded considering the next rounding statement) + chunkSize = MAX(chunkSize, sizeof(void *)); + // There might be an alignment problem on some platforms when trying to load a void* on a non natural boundary + // so we round to the next sizeof(void *) + chunkSize = (chunkSize + sizeof(void *) - 1) & (~(sizeof(void *) - 1)); + + return chunkSize; +} + + +MemoryPool::MemoryPool(size_t chunkSize) + : _chunkSize(adjustChunkSize(chunkSize)) { + + _next = NULL; + + _chunksPerPage = INITIAL_CHUNKS_PER_PAGE; +} + +MemoryPool::~MemoryPool() { +#if 0 + freeUnusedPages(); + if (!_pages.empty()) + warning("Memory leak found in pool"); +#endif + + for (size_t i = 0; i < _pages.size(); ++i) + ::free(_pages[i].start); +} + +void MemoryPool::allocPage() { + Page page; + + // Allocate a new page + page.numChunks = _chunksPerPage; + assert(page.numChunks * _chunkSize < 16*1024*1024); // Refuse to allocate pages bigger than 16 MB + + page.start = ::malloc(page.numChunks * _chunkSize); + assert(page.start); + _pages.push_back(page); + + + // Next time, we'll allocate a page twice as big as this one. + _chunksPerPage *= 2; + + // Add the page to the pool of free chunk + addPageToPool(page); +} + +void MemoryPool::addPageToPool(const Page &page) { + // Add all chunks of the new page to the linked list (pool) of free chunks + void *current = page.start; + for (size_t i = 1; i < page.numChunks; ++i) { + void *next = (byte *)current + _chunkSize; + *(void **)current = next; + + current = next; + } + + // Last chunk points to the old _next + *(void **)current = _next; + + // From now on, the first free chunk is the first chunk of the new page + _next = page.start; +} + +void *MemoryPool::allocChunk() { + // No free chunks left? Allocate a new page + if (!_next) + allocPage(); + + assert(_next); + void *result = _next; + _next = *(void **)result; + return result; +} + +void MemoryPool::freeChunk(void *ptr) { + // Add the chunk back to (the start of) the list of free chunks + *(void **)ptr = _next; + _next = ptr; +} + +// Technically not compliant C++ to compare unrelated pointers. In practice... +bool MemoryPool::isPointerInPage(void *ptr, const Page &page) { + return (ptr >= page.start) && (ptr < (char *)page.start + page.numChunks * _chunkSize); +} + +void MemoryPool::freeUnusedPages() { + //std::sort(_pages.begin(), _pages.end()); + Array<size_t> numberOfFreeChunksPerPage; + numberOfFreeChunksPerPage.resize(_pages.size()); + for (size_t i = 0; i < numberOfFreeChunksPerPage.size(); ++i) { + numberOfFreeChunksPerPage[i] = 0; + } + + // Compute for each page how many chunks in it are still in use. + void *iterator = _next; + while (iterator) { + // TODO: This should be a binary search (requiring us to keep _pages sorted) + for (size_t i = 0; i < _pages.size(); ++i) { + if (isPointerInPage(iterator, _pages[i])) { + ++numberOfFreeChunksPerPage[i]; + break; + } + } + + iterator = *(void **)iterator; + } + + // Free all pages which are not in use. + size_t freedPagesCount = 0; + for (size_t i = 0; i < _pages.size(); ++i) { + if (numberOfFreeChunksPerPage[i] == _pages[i].numChunks) { + // Remove all chunks of this page from the list of free chunks + void **iter2 = &_next; + while (*iter2) { + if (isPointerInPage(*iter2, _pages[i])) + *iter2 = **(void ***)iter2; + else + iter2 = *(void ***)iter2; + } + + ::free(_pages[i].start); + ++freedPagesCount; + _pages[i].start = NULL; + } + } + +// debug("freed %d pages out of %d", (int)freedPagesCount, (int)_pages.size()); + + // Remove all now unused pages + size_t newSize = 0; + for (size_t i = 0; i < _pages.size(); ++i) { + if (_pages[i].start != NULL) { + if (newSize != i) + _pages[newSize] = _pages[i]; + ++newSize; + } + } + _pages.resize(newSize); + + // Reset _chunksPerPage + _chunksPerPage = INITIAL_CHUNKS_PER_PAGE; + for (size_t i = 0; i < _pages.size(); ++i) { + if (_chunksPerPage < _pages[i].numChunks) + _chunksPerPage = _pages[i].numChunks; + } +} + +} // End of namespace Common diff --git a/devtools/create_titanic/memorypool.h b/devtools/create_titanic/memorypool.h new file mode 100644 index 0000000000..c8a8fc7a53 --- /dev/null +++ b/devtools/create_titanic/memorypool.h @@ -0,0 +1,162 @@ +/* ScummVM - Graphic Adventure Engine + * + * ScummVM is the legal property of its developers, whose names + * are too numerous to list here. Please refer to the COPYRIGHT + * file distributed with this source distribution. + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + * + */ + +#ifndef COMMON_MEMORYPOOL_H +#define COMMON_MEMORYPOOL_H + +#include "common/array.h" + + +namespace Common { + +/** + * This class provides a pool of memory 'chunks' of identical size. + * The size of a chunk is determined when creating the memory pool. + * + * Using a memory pool may yield better performance and memory usage + * when allocating and deallocating many memory blocks of equal size. + * E.g. the Common::String class uses a memory pool for the refCount + * variables (each the size of an int) it allocates for each string + * instance. + */ +class MemoryPool { +protected: + MemoryPool(const MemoryPool&); + MemoryPool& operator=(const MemoryPool&); + + struct Page { + void *start; + size_t numChunks; + }; + + const size_t _chunkSize; + Array<Page> _pages; + void *_next; + size_t _chunksPerPage; + + void allocPage(); + void addPageToPool(const Page &page); + bool isPointerInPage(void *ptr, const Page &page); + +public: + /** + * Constructor for a memory pool with the given chunk size. + * @param chunkSize the chunk size of this memory pool + */ + explicit MemoryPool(size_t chunkSize); + ~MemoryPool(); + + /** + * Allocate a new chunk from the memory pool. + */ + void *allocChunk(); + /** + * Return a chunk to the memory pool. The given pointer must have + * been obtained from calling the allocChunk() method of the very + * same MemoryPool instance. Passing any other pointer (e.g. to + * a chunk from another MemoryPool, or a malloc'ed memory block) + * will lead to undefined behavior and may result in a crash (if + * you are lucky) or in silent data corruption. + */ + void freeChunk(void *ptr); + + /** + * Perform garbage collection. The memory pool stores all the + * chunks it manages in memory 'pages' obtained via the classic + * memory allocation APIs (i.e. malloc/free). Ordinarily, once + * a page has been allocated, it won't be released again during + * the life time of the memory pool. The exception is when this + * method is called. + */ + void freeUnusedPages(); + + /** + * Return the chunk size used by this memory pool. + */ + size_t getChunkSize() const { return _chunkSize; } +}; + +/** + * This is a memory pool which already contains in itself some storage + * space for a fixed number of chunks. Thus if the memory pool is only + * lightly used, no malloc() calls have to be made at all. + */ +template<size_t CHUNK_SIZE, size_t NUM_INTERNAL_CHUNKS = 32> +class FixedSizeMemoryPool : public MemoryPool { +private: + enum { + REAL_CHUNK_SIZE = (CHUNK_SIZE + sizeof(void *) - 1) & (~(sizeof(void *) - 1)) + }; + + byte _storage[NUM_INTERNAL_CHUNKS * REAL_CHUNK_SIZE]; +public: + FixedSizeMemoryPool() : MemoryPool(CHUNK_SIZE) { + assert(REAL_CHUNK_SIZE == _chunkSize); + // Insert some static storage + Page internalPage = { _storage, NUM_INTERNAL_CHUNKS }; + addPageToPool(internalPage); + } +}; + +// Ensure NUM_INTERNAL_CHUNKS == 0 results in a compile error +template<size_t CHUNK_SIZE> +class FixedSizeMemoryPool<CHUNK_SIZE,0> : public MemoryPool { +public: + FixedSizeMemoryPool() : MemoryPool(CHUNK_SIZE) {} +}; + +/** + * A memory pool for C++ objects. + */ +template<class T, size_t NUM_INTERNAL_CHUNKS = 32> +class ObjectPool : public FixedSizeMemoryPool<sizeof(T), NUM_INTERNAL_CHUNKS> { +public: + /** + * Return the memory chunk used as storage for the given object back + * to the pool, after calling its destructor. + */ + void deleteChunk(T *ptr) { + ptr->~T(); + this->freeChunk(ptr); + } +}; + +} // End of namespace Common + +/** + * A custom placement new operator, using an arbitrary MemoryPool. + * + * This *should* work with all C++ implementations, but may not. + * + * For details on using placement new for custom allocators, see e.g. + * <http://www.parashift.com/c++-faq-lite/dtors.html#faq-11.14> + */ +inline void *operator new(size_t nbytes, Common::MemoryPool &pool) { + assert(nbytes <= pool.getChunkSize()); + return pool.allocChunk(); +} + +inline void operator delete(void *p, Common::MemoryPool &pool) { + pool.freeChunk(p); +} + +#endif diff --git a/devtools/create_titanic/str.cpp b/devtools/create_titanic/str.cpp index 14a6e505ce..6aa66d0d20 100644 --- a/devtools/create_titanic/str.cpp +++ b/devtools/create_titanic/str.cpp @@ -22,7 +22,7 @@ #include "common/hash-str.h" #include "common/list.h" -#include "common/memorypool.h" +#include "memorypool.h" #include "common/str.h" #include "common/util.h" |