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"