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 for the same.

Hi

There are many ways to implement this.

http://en.wikipedia.org/wiki/Sparse_matrix

Why are you using a matrix rather than a single dimension array?
A mxn matrix could be useful if you are allocating memory in blocks of n bytes and so you have m available to allocate.

Do you want your memory model have the ability to reallocate itself, this allowing it to shuffle the memory around and so remove gaps?
Does the memory allocated need to be contiguous?

Not the memory which will be allocated need not be contiguous.
It can be like one byte at some location another byte at some other location and if a user space system call has requested
say k bytes then my program should be able to find these k bytes which may not be at same place but a group of blocks on 1 byte or 2 or 3 or more and a combination of these whose sum total is k bytes.

What advantage will I get using array out of matrix.
Imagine a real situation you want to write some data in RAM then would you consider the different memory locations on RAM as array or you would choose it as a matrix.

The quick answer is a linked list.

The more detailed answer along with caveats may come after I've completed my parental duties

Okay here is one approach:

You can build a linked list that in the simplest case has a node that contains a reference to the first part of memory (the address) and the amount of memory allocated and the pointer to the next node in the list allowing for non-contiguous blocks of memory.
Then you can have a second list that consists of these linked lists as nodes, along with details of the process that has allocated the memory, one of these will be the free memory list, allowing you to quickly locate unallocated memory, and to free previously allocated memory.

If you are allocating a lot of small blocks of memory the overhead of this approach is going to be quite significant otherwise it shouldn't be too much of a problem.

Ok some one suggested me to be able to use heaps as glibc has implemented.
If you understand what this suggestion means can you give me some link in glibc where this has been actually done.