Click here to Skip to main content
11,568,180 members (37,853 online)
Rate this: bad
good
Please Sign up or sign in to vote.
See more: C Homework
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.
Posted 5-Apr-11 7:19am
Edited 5-Apr-11 8:23am
v2
Rate this: bad
good
Please Sign up or sign in to vote.

Solution 1

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.
Smile | :)
  Permalink  
v3
Comments
SAKryukov at 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.
--SA
CPallini at 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!
Rate this: bad
good
Please Sign up or sign in to vote.

Solution 2

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:
Malloc:
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!
  Permalink  
Comments
Albert Holguin at 5-Apr-11 17:20pm
   
wow, what an explanation! my 5 (can i give a 6?)
Laxmikant_Yadav at 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)

  Print Answers RSS


Advertise | Privacy | Mobile
Web03 | 2.8.150624.2 | Last Updated 5 Apr 2011
Copyright © CodeProject, 1999-2015
All Rights Reserved. Terms of Service
Layout: fixed | fluid

CodeProject, 503-250 Ferrand Drive Toronto Ontario, M3C 3G8 Canada +1 416-849-8900 x 100