Implement "compaction", which moves all non-free chunks towards the beginning of the allocated space, and combines all the free space at the end.

FossilOrigin-Name: c757f65164e1aebf38bc3e9ea8abe4b9f98b183cec7cfbeed0175f65c72f7ca5

1 files changed, 119 insertions, 18 deletions

diff --git a/src/lib/memory.c b/src/lib/memory.c
index d540739..e95afc5 100644
--- a/src/lib/memory.c
+++ b/src/lib/memory.c
@@ -18,7 +18,6 @@ struct chunk {
 	size_t size;
 	enum chunk_tag tag;
 	unsigned int reachable:1;
-	uint8_t *data;
 };
 
 void
@@ -39,6 +38,15 @@ memory_destroy(struct aplwc *aplwc)
 		aplwc->fns.dealloc(aplwc->unaligned_data);
 }
 
+void *
+data(struct chunk *c)
+{
+	uint8_t *p;
+
+	p = (uint8_t*)c;
+	return p + HEADER_SIZE;
+}
+
 static void
 fixrefs(struct aplwc *aplwc, uint8_t *new, uint8_t *old)
 {
@@ -49,7 +57,7 @@ fixrefs(struct aplwc *aplwc, uint8_t *new, uint8_t *old)
 	} \
 }while(0)
 
-#define FIX_DATA(type, ptr) FIX(((type *)c->data)->ptr)
+#define FIX_DATA(type, ptr) FIX(((type *)data(c))->ptr)
 
 	struct chunk *c;
 	struct memory_ptr_frame *frame;
@@ -68,7 +76,6 @@ fixrefs(struct aplwc *aplwc, uint8_t *new, uint8_t *old)
 
 	for(c = (struct chunk *)new; c; c = c->next){
 		FIX(c->next);
-		FIX(c->data);
 
 		switch(c->tag){
 		case CHUNK_TAG_APLWC_LINE:
@@ -110,7 +117,7 @@ grow(struct aplwc *aplwc, size_t extra)
 {
 	uint8_t *unaligned_data, *aligned_data;
 	size_t unaligned_newsize, aligned_newsize, adjust;
-	struct chunk **free, *head;
+	struct chunk **free, *head, *last;
 
 	if(aplwc->fns.alloc == NULL)
 		goto error;
@@ -129,24 +136,33 @@ grow(struct aplwc *aplwc, size_t extra)
 
 	assert(aligned_newsize >= (aplwc->size + extra));
 	head = (struct chunk *)aligned_data;
+	last = NULL;
 
 	if(aplwc->data){
 		memmove(aligned_data, aplwc->data, aplwc->size);
 		fixrefs(aplwc, aligned_data, aplwc->data);
 		if(aplwc->fns.dealloc)
 			aplwc->fns.dealloc(aplwc->unaligned_data);
-		for(free = &head; (*free); free = &(*free)->next);
+		for(free = &head; (*free); free = &(*free)->next)
+			if((*free)->next)
+				assert((*free)->tag != CHUNK_TAG_FREE);
+			else
+				last = (*free);
 	}else
 		free = &head;
 
-
 	(*free) = (struct chunk *)(aligned_data + aplwc->size);
 	(*free)->tag = CHUNK_TAG_FREE;
-	(*free)->data = NULL;
 	(*free)->size = aligned_newsize - aplwc->size;
 	(*free)->next = NULL;
 	(*free)->stack = NULL;
 
+	if(last && (last->tag == CHUNK_TAG_FREE)){
+		assert(last->next == (*free));
+		last->size += (*free)->size;
+		last->next = NULL;
+	}
+
 	aplwc->unaligned_data = unaligned_data;
 	aplwc->data = aligned_data;
 	aplwc->size = aligned_newsize;
@@ -236,7 +252,7 @@ collect(struct aplwc *aplwc)
 
 	while(stack){
 		c = pop(&stack);
-#define PUSH(type, ptr) push(aplwc, &stack, ((type *)c->data)->ptr)
+#define PUSH(type, ptr) push(aplwc, &stack, ((type *)data(c))->ptr)
 		switch(c->tag){
 		case CHUNK_TAG_APLWC_LINE:
 			PUSH(struct aplwc_line, text);
@@ -262,17 +278,100 @@ collect(struct aplwc *aplwc)
 
 	/* Free chunks not marked */
 	for(c = (struct chunk *)aplwc->data; c; c = c->next){
-		if((c->reachable != aplwc->reachable_bit)){
+		if((c->reachable != aplwc->reachable_bit))
 			c->tag = CHUNK_TAG_FREE;
-			c->data = NULL;
+	}
+}
+
+static void
+swapptr(struct aplwc *aplwc, void *old, void *new)
+{
+#define SWAP(ptr) do{ \
+	if((ptr) == old) \
+		(ptr) = new; \
+}while(0)
+
+#define SWAP_DATA(type, ptr) SWAP(((type *)data(c))->ptr)
+
+	struct chunk *c;
+	struct memory_ptr_frame *frame;
+	struct root_ptr *root;
+	size_t i;
+
+	SWAP(aplwc->modules);
+
+	for(c = (struct chunk *)new; c; c = c->next){
+		SWAP(c->next);
+
+		switch(c->tag){
+		case CHUNK_TAG_APLWC_LINE:
+			SWAP_DATA(struct aplwc_line, text);
+			SWAP_DATA(struct aplwc_line, tokens);
+			break;
+		case CHUNK_TAG_STRING:
+			break;
+		case CHUNK_TAG_TOKEN_LIST:
+			SWAP_DATA(struct token_list, text);
+			break;
+		case CHUNK_TAG_APLWC_VALUE:
+			break;
+		case CHUNK_TAG_APLWC_MODULE:
+			SWAP_DATA(struct aplwc_module, name);
+			SWAP_DATA(struct aplwc_module, tokens);
+			SWAP_DATA(struct aplwc_module, link);
+			break;
+		case CHUNK_TAG_FREE:
+			break;
 		}
 	}
+
+	for(frame = aplwc->memptrs; frame; frame = frame->link)
+		for(i = 0; i < frame->count; i++)
+			if(frame->ptrs[i])
+				SWAP(*frame->ptrs[i]);
+	
+	for(root = aplwc->rootptrs; root; root = root->link)
+		if(root->ptr)
+			SWAP(root->ptr);
+
+#undef SWAP 
+#undef SWAP_DATA
 }
 
 static void
 compact(struct aplwc *aplwc)
 {
-	UNUSED_PARAMETER(aplwc);
+	struct chunk *c, *prev, *next;
+	void *oldptr, *newptr;
+	size_t size;
+
+	for(c = (struct chunk *)aplwc->data, prev = NULL; c; prev = c, c = c->next){
+		if((prev == NULL) || (prev->tag != CHUNK_TAG_FREE))
+			continue;
+
+		if(c->tag == CHUNK_TAG_FREE){
+			prev->size += c->size;
+			prev->next = c->next;
+		}else{
+			/* swap prev and c */
+			oldptr = data(c);
+			newptr = data(prev);
+
+			next = c->next;
+			size = prev->size;
+			
+			memmove(prev, c, c->size);
+
+			c = (struct chunk *)(((uint8_t *)prev) + prev->size);
+			prev->next = c;
+			c->next = next;
+			c->stack = NULL;
+			c->tag = CHUNK_TAG_FREE;
+			c->size = size;
+
+			swapptr(aplwc, oldptr, newptr);
+		}
+	}
 }
 
 static void *
@@ -280,9 +379,15 @@ alloc(struct aplwc *aplwc, size_t size, enum chunk_tag tag)
 {
 	struct chunk *free;
 	struct chunk *new;
+	size_t pad;
 
 	int attempt;
 
+	pad = size % ALIGNMENT;
+	if(pad)
+		size += ALIGNMENT - pad;
+		
+
 	attempt = 0;
 retry:
 	free = find_free(aplwc, size);
@@ -303,7 +408,7 @@ retry:
 		}
 	}
 
-	assert(free->data == NULL);
+	assert(free->tag == CHUNK_TAG_FREE);
 
 	new = free;
 
@@ -311,20 +416,16 @@ retry:
 		free = (struct chunk *)(((uint8_t*)free) + HEADER_SIZE + size);
 		free->tag = CHUNK_TAG_FREE;
 		free->size = new->size - (HEADER_SIZE + size);
-		free->data = NULL;
 		free->stack = NULL;
 		free->next = new->next;
 		new->next = free;
 	}
 
 	new->tag = tag;
-	new->size = sizeof(struct chunk) + size;
-	new->data = ((uint8_t*)new) + sizeof(struct chunk);
+	new->size = size + HEADER_SIZE;
 	new->reachable = aplwc->reachable_bit;
 
-	new->data += ((uintptr_t)new->data) % ALIGNMENT;
-
-	return new->data;
+	return data(new);
 }
 
 struct aplwc_ref