Hi! I have some issues trying to implement a (sort of) memory allocator, it has to be tailored to the peculiarities of Java.
First and foremost, I'll describe what I have in Java instead of malloc() and friends:
Direct ByteBuffers, they're an object representing a chunk of memory outside JVM's heap, so it can't be moved by GC. They're used for interacting with native libraries (such as OpenGL, or Bullet). ByteBuffers expose methods for putting things into the buffer, they have a capacity and with some magical casting, you can free them manually.
ByteBuffers, unlike Java arrays, can be sliced via "byteBuffer.slice()" method. You get a ByteBuffer slice starting at the current position mark of the ByteBuffer, and a capacity equal to the remaining bytes in the backing buffer.
So what I wanted to do is the following:
Have a BufferAllocator that would allocate a big backing buffer (couple of MBs), and that it would manage slices of the backing buffer, so to avoid allocating/deallocating small buffers all over the codebase. "capacity" field of the slice can't be modified, so I modify it by reflection, so the user of the returned slice can't step on the memory that lies beyond their slice.
The ByteBuffer doesn't "knows" how much of it is being used. It only has a position mark, a limit mark, and a capacity. You write data into it however you want. So to manage the backing buffer I need an additional structure that can represent which parts of it are free and which parts of it are being used.
I decided to try a simple ArrayList of int[] arrays of size 2 representing the "free block list". First element of the int array is the offset of the block, second element is the end of the block.
Say that I want to ask for a 32 byte buffer, the allocator has 1KB capacity.
The allocator starts with a free block list containing a single element, a int[] with 0 as start value, and 1024 as the end value.
The allocator finds the smallest free block that can hold the 32 byte buffer it was asked for (ie, the only free block we have).
The allocator makes a slice starting at the free block start, ending at the 32 byte mark.
There is still a single contiguous free block, but now it starts at the 32 byte mark, and ends at the 1024 byte mark.
A ByteBuffer slice with capacity 32 is returned.
Have in mind this free block list is just a list of values to do the free block bookkeeping, not the actual memory.
Now, to "free" a ByteBuffer slice, I'd need to find roughly its position inside the free block list.
If there is a neighbor free block (ie, the freed block isn't between two used blocks), I'd need to modify its start/end offsets as required.
Otherwise, create a new int[] instance that holds the freed block's start and end offsets, then insert it into the free block list.
The problem is that if the block I'm trying to free is between two free blocks, I'd need to merge all 3 (left free block, the block I'm freeing, and the right free block). That would mean, removing one of the adjacent free blocks, and expanding the remaining one to cover the block I removed and the block I'm freeing.
Both things: I'm not sure how to do that without a chain of 10 if/else statements (hell, I even tried with lots of if/else statements and I still can't get it to work). And I'm obviously not making the most efficient lookup for finding free blocks to slice.
Here is my (broken) implementation so far:
http://paste.ofcode.org/3rJEwJtLx2L96KVBX8WX5e
Any help?