I am working on a problem (re inventing the wheel for learning)
I have a mxn matric (which is my simplified way of saying it is RAM with bytes on it)
Some of the locations on this metric is filled with some data and some places are empty.
The mxn are very big numbers in size.
I am trying to make a program so that if a system call wants to write some thing on empty locations on this mxn metric it should be able to do so without any problem.
The thing which I want to understand or logic of a data structure is what data structure do you people feel should I be maintaining so that I can allocate the requested space immediately from the above mxn matric when some system call requests for some (k) number of locations from above metrics.

The logic initially I thought was to maintain a hashtable

1bytes requested----------> location 1,location 2,location 3.........location n
2bytes requested----------> location 1,location 2,location 3.........location n
3bytes requested----------> location 1,location 2,location 3.........location n
4bytes requested----------> location 1,location 2,location 3.........location n
nbytes requested----------> location 1,location 2,location 3.........location n

but the problem with above logic is size of the pointers where I will be writing this problem is unsigned 64 byte.So to know location of one free byte if I am maintaining one pointer of type u64 this is not a feasible solution.
Can you people suggest me some logic,idea,algorithm,data structure for the same.

6 Years
Discussion Span
Last Post by Banfa

How about you don't try and individually allocate and reserve each byte of memory. Also is there any reason why you are doing it in 2 dimensions? Why a metric of mxn bytes and not just a flat p bytes (where p = n*m)?

So if you have a flat model what you can do is build up a list of blocks (that may be free or used (you could hold the free used list individually) using a structure something like

struct memBlock
    struct memBlock* next;
    unsigned int size;  // Size of this block
    unsigned int used;  // Could be bool 0 = not used 1 = used

You write one of these structures at the front of each memory block you currently have so at initialisation you have a single one at the head of your array with next set to NULL and size set to array size - sizeof struct memBlock and used to 0

You have a function that can take a single memory block and split it into 2 1 with a specific sized block and 1 with everything that's left over.

To release a block you just send used to 0 if you want you can check nearby blocks and merge them if they are all not used.

To allocate you find an unused block that is large enough to hold the required memory, if it is very much bigger than the required memory you split off a block of the right size then mark the block used and return a pointer to it.

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.