User:Pancakes/StackBasedHeapImplementation

Stack Based

This uses a stack of 32-bit entries. I used 32-bit to keep alignment which I felt was important at the time that I wrote this. In any case it should still serve as an example of a way to implement a heap like this. Also, there is unused space at the start of the stack that could have been used for data if I improved the way it calculates the stack size and how it calculates it which I felt which over complicate the code. So this keeps it simple and I think if someone wanted to improve it then that would be a possible place.

I did think about using 16-bit entries and using an index in them which then could be multiplied with the block size to get an offset in the block. So this could be an option to reduce the size of the stack. However, it would limit the number of allocations per block to 0xffff which might not be a bad idea. I am just not sure at the moment. I might look into it further later.

Code

typedef struct _KHEAPBLOCKSS {
	struct _KHEAPBLOCKSS	*next;
	uint32					top;
	uint32					max;
	uintptr					size;			/* total size in bytes including this header */
} KHEAPBLOCKSS;

typedef struct _KHEAPSS {
	KHEAPBLOCKSS			*fblock;
	uint32					bsize;
} KHEAPSS;

void k_heapSSInit(KHEAPSS *heap, uint32 bsize) {
	heap->fblock = 0;
	heap->bsize = bsize;
}

int k_heapSSAddBlock(KHEAPSS *heap, uintptr addr, uint32 size) {
	KHEAPBLOCKSS		*b;
	uint32				x;
	uint32				*stack;
	uint32				stacksz;
	uint32				slotres;
	
	b = (KHEAPBLOCKSS*)addr;
	b->next = heap->fblock;
	heap->fblock = b;
	
	b->size = size;
	
	size = size - sizeof(KHEAPBLOCKSS);
	
	b->max = size / (heap->bsize);
	
	stacksz = b->max * 4;
	slotres = (stacksz / heap->bsize) * heap->bsize < stacksz ? (stacksz / heap->bsize) + 1 : stacksz / heap->bsize;
	
	b->top = slotres;
	
	stack = (uint32*)&b[1];
	for (x = slotres; x < b->max; ++x) {
		stack[x] = x * heap->bsize;
	}
		
	return 1;
}

void *k_heapSSAlloc(KHEAPSS *heap, uint32 size) {
	KHEAPBLOCKSS		*b;
	uintptr				ptr;
	uint32				*stack;
	
	/* too big */
	if (size > heap->bsize) {
		return 0;
	}
	
	for (b = heap->fblock; b; b = b->next) {
		if (b->top != b->max) {
			stack = (uint32*)&b[1];
			ptr = stack[b->top++];
			ptr = (uintptr)&b[1] + ptr;
			return (void*)ptr;
		}
	}
	
	/* no more space left */
	return 0;
}

void k_heapSSFree(KHEAPSS *heap, void *ptr) {
	KHEAPBLOCKSS		*b;
	uintptr				_ptr;
	uint32				*stack;
	
	/* find block */
	_ptr = (uintptr)ptr;
	for (b = heap->fblock; b; b = b->next) {
		if (_ptr > (uintptr)b && _ptr < ((uintptr)b + b->size))
			break;
	}
	
	/* might want to catch this somehow or somewhere.. kinda means corruption */
	if (!b)
		return;
	
	/* get stack */
	stack = (uint32*)&b[1];
	/* normalize offset to after block header */
	/* decrement top index */
	/* place entry back into stack */
	stack[--b->top] = _ptr - (uintptr)&b[1];
	return;
}