Merged revisions 33452-33453,33455-33459,33463-33464,33466-33471,33473-33474,33478,33490,33492,33495-33496,33509-33512,33518-33519,33522-33527,33529-33530,33537,33541,33544,33546,33550,33552-33554,33556,33558,33561-33562,33565,33568,33570,33574,33576,33578-33581,33584-33587,33590,33596,33604-33611,33614-33615,33617-33618,33620-33621,33623,33626-33627,33632-33633,33635,33637,33639-33640,33642-33645,33648,33654-33655,33664,33667-33670,33673-33674,33678,33682,33686-33691,33693,33696,33698,33700,33703,33708,33710,33712-33714,33716,33719,33721-33723,33725-33727,33729-33730,33733,33736,33742,33754,33756,33758,33761,33763,33766,33777,33781-33788,33790,33792-33793,33795,33797,33805,33807-33812,33815-33817,33819,33822,33826,33829,33837,33839,33844,33847,33858-33861,33864,33871-33873,33875,33877-33879,33886,33889-33892,33894,33896,33900,33902-33903,33919,33928,33930,33932-33936,33938-33940,33942-33943,33948,33950,33953,33967,33973,33976,33978,33980,33985,33991,33993,33999-34000,34006,34009,34011,34013,34015,34019,34021-34023,34025,34027-34028,34030,34032-34034,34036,34038-34039,34041,34046-34048,34050-34055,34057,34059-34065,34067,34072,34074,34076,34078-34081,34084,34086-34087,34089-34090,34093,34096-34102,34104,34107,34113,34116,34119,34122,34124,34126,34128,34131-34132,34135,34138,34141,34144,34146,34149,34152-34154,34156-34157,34160,34163-34164,34169,34173,34179-34194,34196-34198,34200-34201,34205-34206,34208-34217,34219-34225,34227-34228,34234-34237,34239-34249,34251-34279,34281-34284,34286-34288,34290-34320,34323-34324,34326,34328-34329,34332,34334,34336,34338-34340,34343-34353,34356-34357,34359-34371,34373,34375,34378,34381-34382,34384-34385,34389-34391,34393-34394,34396-34397,34399-34405,34407-34409,34411,34413,34415,34417-34420,34423-34426,34428-34438,34440-34454,34456-34458,34460,34462-34469,34472,34474,34479-34481,34483-34498,34501-34505,34508,34511-34518,34520-34524,34526-34563,34566-34569,34571-34590,34592,34595-34599,34602-34603,34605,34613-34615,34617,34619-34624,34627-34628,34630-34639,34642-34649 via svnmerge from

https://scummvm.svn.sourceforge.net/svnroot/scummvm/scummvm/trunk

svn-id: r34654

1 files changed, 73 insertions, 38 deletions

diff --git a/common/memorypool.cpp b/common/memorypool.cpp
index f3dfb7975f..12307ba5d6 100644
--- a/common/memorypool.cpp
+++ b/common/memorypool.cpp
@@ -28,22 +28,6 @@
 
 namespace Common {
 
-static const size_t CHUNK_PAGE_SIZE = 32;
-
-void* MemoryPool::allocPage() {
-	void* result = ::malloc(CHUNK_PAGE_SIZE * _chunkSize);
-	_pages.push_back(result);
-	void* current = result;
-	for (size_t i = 1; i < CHUNK_PAGE_SIZE; ++i) {
-		void* next    = ((char*)current + _chunkSize);
-		*(void**)current = next;
-
-		current = next;
-	}
-	*(void**)current = NULL;
-	return result;
-}
-
 MemoryPool::MemoryPool(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*));
@@ -52,38 +36,68 @@ MemoryPool::MemoryPool(size_t chunkSize) {
 	_chunkSize = (_chunkSize + sizeof(void*) - 1) & (~(sizeof(void*) - 1));
 
 	_next = NULL;
+	
+	_chunksPerPage = 8;
 }
 
 MemoryPool::~MemoryPool() {
-	for (size_t i = 0; i<_pages.size(); ++i)
-		::free(_pages[i]);
+	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;
+	page.start = ::malloc(page.numChunks * _chunkSize);
+	assert(page.start);
+	_pages.push_back(page);
+	
+	// Next time, we'll alocate 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    = ((char*)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::malloc() {
-#if 1
-	if (!_next)
-		_next = allocPage();
+void *MemoryPool::malloc() {
+	if (!_next)	// No free chunks left? Allocate a new page
+		allocPage();
 
-	void* result = _next;
+	assert(_next);
+	void *result = _next;
 	_next = *(void**)result;
 	return result;
-#else
-	return ::malloc(_chunkSize);
-#endif
 }
 
 void MemoryPool::free(void* ptr) {
-#if 1
+	// Add the chunk back to (the start of) the list of free chunks
 	*(void**)ptr = _next;
 	_next = ptr;
-#else
-	::free(ptr);
-#endif
 }
 
 // Technically not compliant C++ to compare unrelated pointers. In practice...
-bool MemoryPool::isPointerInPage(void* ptr, void* page) {
-	return (ptr >= page) && (ptr < (char*)page + CHUNK_PAGE_SIZE * _chunkSize);
+bool MemoryPool::isPointerInPage(void *ptr, const Page &page) {
+	return (ptr >= page.start) && (ptr < (char*)page.start + page.numChunks * _chunkSize);
 }
 
 void MemoryPool::freeUnusedPages() {
@@ -94,9 +108,10 @@ void MemoryPool::freeUnusedPages() {
 		numberOfFreeChunksPerPage[i] = 0;
 	}
 
-	void* iterator = _next;
+	// Compute for each page how many chunks in it are still in use.
+	void *iterator = _next;
 	while (iterator) {
-		// This should be a binary search
+		// 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];
@@ -106,12 +121,32 @@ void MemoryPool::freeUnusedPages() {
 		iterator = *(void**)iterator;
 	}
 
+	// Free all pages which are not in use.
+	// TODO: Might want to reset _chunksPerPage here (e.g. to the largest
+	//      _pages[i].numChunks value still in use).
 	size_t freedPagesCount = 0;
-	for (size_t i = 0; i < _pages.size(); ++i) {
-		if (numberOfFreeChunksPerPage[i] == CHUNK_PAGE_SIZE) {
-			::free(_pages[i]);
-			_pages[i] = NULL; // TODO : Remove NULL values
+	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;
+		}
+	}
+
+	for (size_t i = 0; i < _pages.size(); )  {
+		if (_pages[i].start == NULL) {
+			_pages.remove_at(i);
+			// We just removed an entry, so we do not advance "i"
+		} else {
+			++i;
 		}
 	}