Having problems writing my own malloc, free, and realloc...

Question

I'm having some trouble implementing my own dynamic memory allocator using an Implicit list to track free blocks in c. ****Specifically I'm having problems with implementing realloc and changing the code from find-fit/first-fit to next-fit. Best-fit would be ideal but lets just say next fit for now. I've got everything thing else down, its just those two items specifically...

more info...

I'm trying to implement my own version of a dynamic memory allocator with my own versions of malloc, free, and realloc...There are four methods used to keep track of free blocks in a dynamic memory allocator, the first one of these which I have here is an Implicit list, which uses a header. For finding a free block in an Implicit list there are several placement policies which can be enacted in an Implicit list. The first of which is called first fit or find fit which is located in the code below...it searches the list from the beginning, and chooses the first free block that fits. The next method is called next fit which I am having trouble trying to implement, and this method is similar to first fit, but instead of starting each search at the beginning of the list, it starts each search where the previous search left off. Finally there is Best fit...this would be the ideal method for me but I know it is rather complicated and pretty difficult, so I will take just next fit, but, if there is someone out there who knows how to implement best fit in an implicit list PLEASE, feel free to post it. Best fit examines every free block and chooses the free block with the smallest size that fits...I do know that for Best fit it is possible to eliminate footers in allocated blocks...mostly cause they are really not necessary ...I'm just not exactly sure how to do this...

I understand this is a lot of code but I just wanted to put everything in all at once so nothing gets missed.

I left space for realloc which returns NULL and is somewhere in the middle of the code and find_ fit which I want to change to the next_fit placement policy method is towards the bottom...

Any help would be greatly appreciated...Thank You.

The code is all in this website...sorry...I was having many problems posting the code here...even more so since it is so large...I just used google so it seems more authentic...

DMA CODE

I've labeled the sections clearly in the code on the website so one should have no trouble finding the realloc and the find fit methods...

Answer 1

A naive way of solving realloc would be to have realloc call you malloc function and just copy the data, but I guess you're looking for a more sophisticated solution?

Answer 2

My own code is only a stop-gap implementation ATM, not very efficient compared to other solutions (dlmalloc() et al.).

It's an exact-fit, first-fit algorithm, but it should be trivial to extend the "remember the first-fit in case you don't have an exact-fit" part in lines 63 to 71 to handle best-fit:

Check the size of the current node, and if it's smaller than the one remembered so far but still large enough to satisfy the request, remember the current node instead of the one remembered so far.

The code is under a Public-Domain-alike license, i.e. you can use it however you like.

Answer 3

Best-fit isn't very good for a lot of purposes, but if you really want it, it's pretty easy to implement. When you add blocks to your free list, insert them in order, sorted by size. Then, when trying to allocate a block, a first-fit search also gives the best fit.

Answer 4

If you're not doing homework, why aren't you using valgrind to debug memory problems? Or if you need a more special version of malloc, why aren't you starting with Dave Hanson's debugging version of malloc?

If you are doing homework, why haven't you told us?