Click here to Skip to main content
15,672,517 members
Please Sign up or sign in to vote.
5.00/5 (1 vote)
See more:
Hi Everyone,

Can any one help me in writing a code or an algorithm for my own malloc function using C.
Please make a note that i don't want to use any library functions.

Thanks in Advance.
Updated 5-Apr-11 8:23am

The only way I know to avoid library functions is preallocationg memory onto the stack and then using such memory for your own version of malloc.

Possibly a better way would be actually using library malloc to pre-allocate large blocks of memory and then manage them with you own function.
Share this answer
Sergey Alexandrovich Kryukov 5-Apr-11 14:38pm    
More exactly, pre-allocate memory anyhow and use it for your own malloc.
Another thing: use low-level system API, such as Windows API. GlobalAlloc... I think that might be intended by this task.
My 5.
CPallini 5-Apr-11 14:46pm    
Thank you. If it is homework (I don't know if it is) then Windows API is probably excluded.
BTW: Congratulations, Top Expert!
It depends on how far you want to go, but this is not a trivial task. I've done it a few times, and I still forget some things.

Think about what a malloc has to do:
1) Allocate a chunk of memory big enough to satisfy the request, and return a pointer to it.
2) Remember which chunks of ram are in use and which aren't.
3) Combine free chunks to make bigger ones.

So, the first thing you need is a big chunk of memory to allocate. The only way you are going to get it is to malloc it off the heap: generally speaking, stacks are far too small for this kind of thing. (In VS, the stack is only 1MB by default, but I've known C based systems with a 1K stack!) This is probably allowable in your homework as you have to get your memory from somewhere!

Now, you need a couple of linked lists.
1) You need a "free memory" list: Start of block, and size of block.
2) You need an "in use" list: Start of block, and size of block.

Next, you need to decide what algorithm you will use for allocation:
1) First fit: The first chunk in the free list that fits your request has a lump chopped off it, and returned as the new memory block
2) Best Fit: The smallest such chunk that will hold the request.
3) Worst Fit: The biggest chunk is always used.
4) Fixed size allocation: All chunks are the same size. (Works well in embedded applications since it doesn't fragment)
There are others! Wiki will probably help there.

Now you are ready to go:
1) Find the chunk to use: If none: error!
2) Remove chunk from free memory list.
3) Break chunk into two: request chunk, and free chunk.
4) Add the Free chunk to the free memory list
5) Add the request chunk to the in use list
6) Return the chunk pointer

You also need a Free:
1) Find the request chunk pointer in the in use list. If it isn't there, error!
2) Remove it from the in use list.
3) Add it to the free memory list.
4) If you aren't using a fixed size allocation, trawl through the free memory list and combine chunks into bigger chunks where they are contiguous.

Sound simple?

Not too bad in fact, but it is best to take it in easy stages, because it can be a bugger to debug.
Bear in mind, that you need to have somewhere to store your linked lists... That can cause it's own problems, as you may have to malloc space for the lists and they could grow, causing you to have to malloc a bigger space and copy them...

Loads of potential pitfalls!

I would read up on everything I could find first!
Share this answer
Albert Holguin 5-Apr-11 17:20pm    
wow, what an explanation! my 5 (can i give a 6?)
LaxmikantYadav 6-Apr-11 0:42am    
My 5 :)

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900