[Scummvm-cvs-logs] SF.net SVN: scummvm: [31320] scummvm/trunk/common

[tramboi at users.sourceforge.net]

Revision: 31320
          http://scummvm.svn.sourceforge.net/scummvm/?rev=31320&view=rev
Author:   tramboi
Date:     2008-03-29 22:42:39 -0700 (Sat, 29 Mar 2008)

Log Message:
-----------
Introduction of a fixed size memory pool with a typical free list implementation
+ : amortized O(1) allocation, O(1) deallocation, less overhead per allocation
- : unused memory is not reclaimed until death or manual invocation of a function

Modified Paths:
--------------
    scummvm/trunk/common/module.mk

Added Paths:
-----------
    scummvm/trunk/common/memorypool.cpp
    scummvm/trunk/common/memorypool.h

Added: scummvm/trunk/common/memorypool.cpp
===================================================================
--- scummvm/trunk/common/memorypool.cpp	                        (rev 0)
+++ scummvm/trunk/common/memorypool.cpp	2008-03-30 05:42:39 UTC (rev 31320)
@@ -0,0 +1,94 @@
+#include "common/memorypool.h"
+#include <algorithm>
+
+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 = std::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));
+
+  _next = NULL;
+}
+
+MemoryPool::~MemoryPool() {
+  for(size_t i=0; i<_pages.size(); ++i)
+    free(_pages[i]);
+}
+
+void* MemoryPool::malloc() {
+#if 1
+  if(!_next)
+    _next = allocPage();
+
+  void* result = _next;
+  _next = *(void**)result;
+  return result;
+#else
+  return ::malloc(_chunkSize);
+#endif
+}
+
+void MemoryPool::free(void* ptr) {
+#if 1
+  *(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);
+}
+
+void MemoryPool::freeUnusedPages() {
+  //std::sort(_pages.begin(), _pages.end());
+  Array<int> numberOfFreeChunksPerPage;
+  numberOfFreeChunksPerPage.resize(_pages.size());
+  for(size_t i=0; i<numberOfFreeChunksPerPage.size(); ++i) {
+      numberOfFreeChunksPerPage[i] = 0;
+  }
+  
+  void* iterator = _next;
+  while(iterator) {
+    // This should be a binary search
+    for(size_t i=0; i<_pages.size(); ++i) {
+      if(isPointerInPage(iterator, _pages[i])) {
+	++numberOfFreeChunksPerPage[i];
+	break;
+      }
+    }
+    iterator = *(void**)iterator;
+  }
+
+  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
+    }
+  }
+}
+
+}


Property changes on: scummvm/trunk/common/memorypool.cpp
___________________________________________________________________
Name: svn:mime-type
   + text/plain
Name: svn:eol-style
   + native

Added: scummvm/trunk/common/memorypool.h
===================================================================
--- scummvm/trunk/common/memorypool.h	                        (rev 0)
+++ scummvm/trunk/common/memorypool.h	2008-03-30 05:42:39 UTC (rev 31320)
@@ -0,0 +1,34 @@
+#ifndef COMMON_MEMORYPOOL_H
+#define COMMON_MEMORYPOOL_H
+
+#include <cstring>
+#include "common/array.h"
+
+namespace Common
+{
+
+class MemoryPool
+{
+ private:
+  MemoryPool(const MemoryPool&);
+  MemoryPool& operator=(const MemoryPool&);
+
+  size_t       _chunkSize;
+  Array<void*> _pages;
+  void*        _next;
+
+  void* allocPage();
+  bool  isPointerInPage(void* ptr, void* page);
+ public:
+  MemoryPool(size_t chunkSize);
+  ~MemoryPool();
+
+  void* malloc();
+  void  free(void* ptr);
+
+  void freeUnusedPages();
+};
+
+}
+
+#endif


Property changes on: scummvm/trunk/common/memorypool.h
___________________________________________________________________
Name: svn:mime-type
   + text/plain
Name: svn:eol-style
   + native

Modified: scummvm/trunk/common/module.mk
===================================================================
--- scummvm/trunk/common/module.mk	2008-03-30 03:21:01 UTC (rev 31319)
+++ scummvm/trunk/common/module.mk	2008-03-30 05:42:39 UTC (rev 31320)
@@ -7,6 +7,7 @@
 	file.o \
 	fs.o \
 	hashmap.o \
+	memorypool.o \
 	md5.o \
 	mutex.o \
 	str.o \


This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.