1
$\begingroup$

Let's say I want to implement my simple version of free/malloc

Let's assume I got a huge chunk of memory where I manage my free/malloc there. and also I can only allocate fixed block size on each malloc (1 byte for example).

So in general I keep "free list" of free addresses of one byte, so whenever somebody do malloc, I just return the address in the head of list and take out the head .. (head=head->next) .

and when a user does free(ptr) I just add that address to the head of the list.

So both actions are $O(1)$.

Now, I see some implementation that puts "header" before each data to keep the next pointer there, and I don't understand why is it doing so? Because it's complicating things a bit, and I can't see where the advantage of doing that comparing to just use Linked list in different memory area.

|cite|improve this question
$\endgroup$
  • $\begingroup$ Did the implementations you saw manage fixed-size blocks? Fixed-size blocks simplify the problem considerably, so it's natural that they would require less control data. $\endgroup$ – Gilles Mar 28 '16 at 20:51
  • $\begingroup$ @Gilles and if its not fixed size ? how does that help $\endgroup$ – nadavgam Mar 28 '16 at 20:53
  • $\begingroup$ The advantage of fixed size is that when you get a pointer passed to free, you know already what size block it refers to (because there's only one size). If you support many sizes, you usually want there to be a header associated with the memory to tell you what size the block is. The headers also allow you to add more sophisticated logic to reduce memory fragmentation (e.g. you can check if a newly freed block is adjacent to other free memory or not, by checking the adjacent headers). $\endgroup$ – Blckknght Mar 28 '16 at 21:41
  • $\begingroup$ @Blckknght but you can do that by keeping linked list in different place, why the nodes of the list must be the headers that preceed the data.. $\endgroup$ – nadavgam Mar 28 '16 at 21:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.