reuse freed space in buckets

1 files changed, 93 insertions, 24 deletions

diff --git a/src/memory.cpp b/src/memory.cpp
index 360e2e2..1bf1a49 100644
--- a/src/memory.cpp
+++ b/src/memory.cpp
@@ -1,44 +1,87 @@
 
 #include "memory.hpp"
 
+struct MemBlock {
+	char *data;
+	std::size_t size;
+};
+
 struct MemBucket {
 	int64_t size;
 	int64_t head;
-	int64_t free;
+	int64_t lostBytes;
 	int64_t allocs;
+	int64_t lastEmptyBlockIndex;
+	int64_t maxBlockCount;
+	char *blocks;
+	char *ptr;
 	bool transient;
-	char * ptr;
 };
 
 MemBucket buckets[128];
 int64_t bucketHead = 0;
 
 int64_t InitNewBucket(int64_t sz, bool transient = false) {
-	buckets[bucketHead].size = sz;
-	buckets[bucketHead].head = 0;
-	buckets[bucketHead].free = 0;
-	buckets[bucketHead].allocs = 0;
-	buckets[bucketHead].transient = transient;
-	buckets[bucketHead].ptr = reinterpret_cast<char *>(std::malloc(sz));
+	int64_t blockCount = sz * 0.01;
+	auto &bkt = buckets[bucketHead];
+	bkt.size = sz;
+	bkt.head = 0;
+	bkt.lostBytes = 0;
+	bkt.allocs = 0;
+	bkt.lastEmptyBlockIndex = -1;
+	bkt.maxBlockCount = blockCount < 10 ? 10 : blockCount;
+	bkt.blocks = reinterpret_cast<char *>(std::malloc(sz));
+	bkt.ptr = bkt.blocks + (sizeof(MemBlock) * bkt.maxBlockCount);
+	bkt.transient = transient;
+	auto *memBlock = reinterpret_cast<MemBlock *>(bkt.blocks);
+	memBlock->data = bkt.ptr;
+	memBlock->size = sz - (sizeof(MemBlock) * bkt.maxBlockCount);
 	return bucketHead++;
 }
 
 void DestroyBucket(MemBucket *bkt) {
-	std::free(bkt->ptr);
+	std::free(bkt->blocks);
 	bkt->size = 0;
 	bkt->head = 0;
-	bkt->free = 0;
+	bkt->lostBytes = 0;
 	bkt->allocs = 0;
-	bkt->transient = false;
+	bkt->lastEmptyBlockIndex = -1;
+	bkt->maxBlockCount = 0;
+	bkt->blocks = CAFE_BABE(char);
 	bkt->ptr = CAFE_BABE(char);
+	bkt->transient = false;
 }
 
 void *Pke_New(std::size_t sz, MemBucket *bkt) {
-	assert(bkt->head + sz <= bkt->size && "memory bucket specified, but full");
-	void *ptr = bkt->ptr + bkt->head;
-	bkt->head += sz;
+	MemBlock *blocks = reinterpret_cast<MemBlock *>(bkt->blocks);
+	int64_t availBlockIndex = -1;
+	void *data = nullptr;
+	for (int64_t i = 0; i <= bkt->lastEmptyBlockIndex; ++i) {
+		auto blk = blocks[i];
+		if (blk.size > sz) {
+			availBlockIndex = i;
+			break;
+		}
+	}
+	if (availBlockIndex != -1) {
+		data = blocks[availBlockIndex].data;
+		blocks[availBlockIndex].data += sz;
+		blocks[availBlockIndex].size -= sz;
+		assert(blocks[availBlockIndex].size < bkt->size);
+		if (blocks[availBlockIndex].size == 0) {
+			if (availBlockIndex != bkt->lastEmptyBlockIndex) {
+				blocks[availBlockIndex].data = blocks[bkt->lastEmptyBlockIndex].data;
+				blocks[availBlockIndex].size = blocks[bkt->lastEmptyBlockIndex].size;
+			}
+			bkt->lastEmptyBlockIndex -= 1;
+		}
+	} else {
+		assert(bkt->head + sz <= bkt->size && "memory bucket specified, but full");
+		data = bkt->ptr + bkt->head;
+		bkt->head += sz;
+	}
 	bkt->allocs++;
-	return ptr;
+	return data;
 }
 
 void *Pke_New(std::size_t sz) {
@@ -57,11 +100,34 @@ void *Pke_New(std::size_t sz) {
 void Pke_Delete(const void *ptr, std::size_t sz, MemBucket *bkt) {
 	assert(ptr >= bkt->ptr && ptr < bkt->ptr + bkt->size && "pointer not in memory bucket range");
 	bkt->allocs--;
-	bkt->free += sz;
-	if (ptr == bkt->ptr + bkt->head - sz) bkt->head -= sz;
 	if (bkt->allocs == 0) {
 		bkt->head = 0;
-		bkt->free = 0;
+		bkt->lastEmptyBlockIndex = -1;
+		return;
+	}
+	if (ptr == bkt->ptr + bkt->head - sz) {
+		bkt->head -= sz;
+	} else {
+		MemBlock *blocks = reinterpret_cast<MemBlock *>(bkt->blocks);
+		for (int64_t i = 0; i < bkt->lastEmptyBlockIndex; ++i) {
+			auto &blk = blocks[i];
+			if (blk.data == reinterpret_cast<const char *>(ptr) + sz) {
+				blk.data -= sz;
+				blk.size += sz;
+				return;
+			}
+			if (reinterpret_cast<const char *>(ptr) == blk.data + blk.size ) {
+				blk.size += sz;
+				return;
+			}
+		}
+		if (bkt->lastEmptyBlockIndex != bkt->maxBlockCount) {
+			bkt->lastEmptyBlockIndex += 1;
+			blocks[bkt->lastEmptyBlockIndex].data = reinterpret_cast<char *>(const_cast<void *>(ptr));
+			blocks[bkt->lastEmptyBlockIndex].size = sz;
+		} else {
+			bkt->lostBytes += sz;
+		}
 	}
 }
 
@@ -128,11 +194,14 @@ void Pke_DebugPrint() {
 	printf("Memory Manager printout:\nBucket count: %li\n", bucketHead + 1);
 	for (long i = 0; i <= bucketHead; ++i) {
 		printf("- bucket #%li\n", i);
-		printf("\tsize:      %li\n", buckets[i].size);
-		printf("\thead:      %li\n", buckets[i].head);
-		printf("\tfree:      %li\n", buckets[i].free);
-		printf("\tallocs:    %li\n", buckets[i].allocs);
-		printf("\ttransient: %i\n", buckets[i].transient);
-		printf("\tptr:        %p\n", buckets[i].ptr);
+		printf("\tsize:                %li\n", buckets[i].size);
+		printf("\thead:                %li\n", buckets[i].head);
+		printf("\tlostBytes:           %li\n", buckets[i].lostBytes);
+		printf("\tallocs:              %li\n", buckets[i].allocs);
+		printf("\tlastEmptyBlockIndex: %li\n", buckets[i].lastEmptyBlockIndex);
+		printf("\tmaxBlockCount:       %li\n", buckets[i].maxBlockCount);
+		printf("\tblocks:              %p\n", buckets[i].blocks);
+		printf("\tptr:                 %p\n", buckets[i].ptr);
+		printf("\ttransient:           %i\n", buckets[i].transient);
 	}
 }