memory cleanup - still buggy

1 files changed, 58 insertions, 25 deletions

diff --git a/src/memory.cpp b/src/memory.cpp
index 853c6fe..fb6c591 100644
--- a/src/memory.cpp
+++ b/src/memory.cpp
@@ -95,9 +95,9 @@ void *Pke_New(std::size_t sz, std::size_t alignment, MemBucket *bkt) {
 					if (index != bkt->lastEmptyBlockIndex) {
 						long moveCount = bkt->lastEmptyBlockIndex - index;
 						if (moveCount > 0) {
-							char *beforePos = bkt->blocks + (sizeof(MemBlock) * (index + 1));
-							char *afterPos = bkt->blocks + (sizeof(MemBlock) * (index + 2));
-							memmove(afterPos, beforePos, sizeof(MemBlock) * moveCount);
+							char *srcPos = bkt->blocks + (sizeof(MemBlock) * (index + 1));
+							char *dstPos = bkt->blocks + (sizeof(MemBlock) * (index + 2));
+							memmove(dstPos, srcPos, sizeof(MemBlock) * moveCount);
 						}
 					}
 					bkt->lastEmptyBlockIndex += 1;
@@ -117,9 +117,9 @@ void *Pke_New(std::size_t sz, std::size_t alignment, MemBucket *bkt) {
 				}
 				long moveCount = bkt->lastEmptyBlockIndex - index;
 				if (moveCount > 0) {
-					char *beforePos = bkt->blocks + (sizeof(MemBlock) * (index + 1));
-					char *afterPos = bkt->blocks + (sizeof(MemBlock) * (index + 0));
-					memmove(afterPos, beforePos, sizeof(MemBlock) * moveCount);
+					char *srcPos = bkt->blocks + (sizeof(MemBlock) * (index + 1));
+					char *dstPos = bkt->blocks + (sizeof(MemBlock) * (index + 0));
+					memmove(dstPos, srcPos, sizeof(MemBlock) * moveCount);
 					bkt->lastEmptyBlockIndex -= 1;
 				}
 			}
@@ -175,6 +175,22 @@ void inline Pke_CollapseEmptyBlocksToHead(MemBucket *bkt) {
 }
 
 void inline Pke_CollapseBlocks(MemBucket *bkt) {
+	/* JCB 2023-11-21
+	 * After writing this, I realized that if the MemBlocks are sorted,
+	 *  one free should cause at most 1 memmove shift, and only if both
+	 *  the block before and after are identified. This method does not
+	 *  know when to stop and is therefore less efficient, especially
+	 *  considering it would find 1 instance to memmove at most if called
+	 *  on every free.
+	 * Free has been refactored to handle the before+after block scenarios,
+	 *  so this method is no longer necessary, unless someday in the future
+	 *  we add a mechanism to toggle whether or not to resize blocks on free
+	 * Example: if we don't enforce sorting, then this would be a good GC
+	 *  after a sort. However, in that case it might be better to rebuild
+	 *  the blocks into a new array and memcpy over the original, instead
+	 *  of performing memmove an unspecified number of times.
+	 */
+	assert(!"for reference use only");
 	MemBlock *blocks = reinterpret_cast<MemBlock *>(bkt->blocks);
 	long skipDistance = 1;
 	long lastStartingIndex = 0;
@@ -189,9 +205,9 @@ void inline Pke_CollapseBlocks(MemBucket *bkt) {
 			i -= 1;
 		} else {
 			if (skipDistance > 1) {
-				char *beforePos = bkt->blocks + (sizeof(MemBlock) * (i + skipDistance));
-				char *afterPos = bkt->blocks + (sizeof(MemBlock) * (i + 1));
-				memmove(afterPos, beforePos, sizeof(MemBlock) * (skipDistance - 1));
+				char *srcPos = bkt->blocks + (sizeof(MemBlock) * (i + skipDistance));
+				char *dstPos = bkt->blocks + (sizeof(MemBlock) * (i + 1));
+				memmove(dstPos, srcPos, sizeof(MemBlock) * (skipDistance - 1));
 				bkt->lastEmptyBlockIndex -= (skipDistance - 1);
 			}
 			i += skipDistance - 1;
@@ -199,9 +215,9 @@ void inline Pke_CollapseBlocks(MemBucket *bkt) {
 		}
 	}
 	if (skipDistance > 1) {
-		char *beforePos = bkt->blocks + (sizeof(MemBlock) * (lastStartingIndex + skipDistance));
-		char *afterPos = bkt->blocks + (sizeof(MemBlock) * (lastStartingIndex + 1));
-		memmove(afterPos, beforePos, sizeof(MemBlock) * (skipDistance - 1));
+		char *srcPos = bkt->blocks + (sizeof(MemBlock) * (lastStartingIndex + skipDistance));
+		char *dstPos = bkt->blocks + (sizeof(MemBlock) * (lastStartingIndex + 1));
+		memmove(dstPos, srcPos, sizeof(MemBlock) * (skipDistance - 1));
 		bkt->lastEmptyBlockIndex -= (skipDistance - 1);
 	}
 }
@@ -222,26 +238,44 @@ void Pke_Delete(const void *ptr, std::size_t sz, MemBucket *bkt) {
 	MemBlock *blocks = reinterpret_cast<MemBlock *>(bkt->blocks);
 	size_t prevBlockIndex = 0xFFFFFFFFFFFFFFFF;
 	void *prevPointer = reinterpret_cast<void *>(prevBlockIndex);
-	bool found = false;
+	long beforeIndex = -1;
+	long afterIndex = -1;
 	for (int64_t i = 0; i <= bkt->lastEmptyBlockIndex; ++i) {
-		auto &blk = blocks[i];
+		const auto &blk = blocks[i];
 		if (blk.data < ptr && prevPointer < blk.data) {
 			prevBlockIndex = i;
 			prevPointer = blk.data;
 		}
+		if (reinterpret_cast<const char *>(ptr) == blk.data + blk.size ) {
+			beforeIndex = i;
+			continue;
+		}
 		if (blk.data == reinterpret_cast<const char *>(ptr) + sz) {
-			blk.data -= sz;
-			blk.size += sz;
-			found = true;
+			afterIndex = i;
 			break;
 		}
-		if (reinterpret_cast<const char *>(ptr) == blk.data + blk.size ) {
-			blk.size += sz;
-			found = true;
+		// we found beforeIndex on the previous loop, but then didn't find afterIndex on this loop
+		if (beforeIndex != -1) {
 			break;
 		}
 	}
-	if (found == false) {
+	if (beforeIndex != -1 && afterIndex != -1) {
+		MemBlock &beforeBlk = blocks[beforeIndex];
+		MemBlock &afterBlk = blocks[afterIndex];
+		beforeBlk.size += sz + afterBlk.size;
+		afterBlk.size = 0;
+		char *srcPos = bkt->blocks + (sizeof(MemBlock) * (afterIndex + 1));
+		char *dstPos = bkt->blocks + (sizeof(MemBlock) * (afterIndex));
+		memmove(dstPos, srcPos, sizeof(MemBlock) * (bkt->lastEmptyBlockIndex - afterIndex));
+		bkt->lastEmptyBlockIndex -= 1;
+	} else if (beforeIndex != -1) {
+		MemBlock &beforeBlk = blocks[beforeIndex];
+		beforeBlk.size += sz;
+	} else if (afterIndex != -1) {
+		MemBlock &afterBlk = blocks[afterIndex];
+		afterBlk.data -= sz;
+		afterBlk.size += sz;
+	} else {
 		if (bkt->lastEmptyBlockIndex == bkt->maxBlockCount) {
 			bkt->lostBytes += sz;
 		} else {
@@ -249,9 +283,9 @@ void Pke_Delete(const void *ptr, std::size_t sz, MemBucket *bkt) {
 			if (prevBlockIndex < bkt->lastEmptyBlockIndex) {
 				long moveCount = bkt->lastEmptyBlockIndex - prevBlockIndex;
 				assert(moveCount > 0);
-				char *beforePos = bkt->blocks + (sizeof(MemBlock) * (prevBlockIndex + 1));
-				char *afterPos = bkt->blocks + (sizeof(MemBlock) * (prevBlockIndex + 2));
-				memmove(afterPos, beforePos, sizeof(MemBlock) * moveCount);
+				char *srcPos = bkt->blocks + (sizeof(MemBlock) * (prevBlockIndex + 1));
+				char *dstPos = bkt->blocks + (sizeof(MemBlock) * (prevBlockIndex + 2));
+				memmove(dstPos, srcPos, sizeof(MemBlock) * moveCount);
 				targetBlock = &blocks[prevBlockIndex + 1];
 			} else {
 				targetBlock = &blocks[bkt->lastEmptyBlockIndex + 1];
@@ -261,7 +295,6 @@ void Pke_Delete(const void *ptr, std::size_t sz, MemBucket *bkt) {
 			targetBlock->size = sz;
 		}
 	}
-	Pke_CollapseBlocks(bkt);
 	Pke_CollapseEmptyBlocksToHead(bkt);
 }