Explicit free list (dynamic memory allocation)

Question

I need some help with my assignment. My job is to create/implement malloc/free functions in C using “Explicit free list among only the free blocks” technique. I have already studied a lot of materials, but I am still stuck at some point and I do not understand some details. So my job is to create 4 functions – initialize(), allocate() ,free() and check(). I can use only one global variable void *memory – this is the block in which I can allocate my memory using alloc().

So I wanted to implement this using doubly linked-list and I created a structure:

typedef struct memoryBlock{
    struct memoryBlock *prev,*next;
}memoryBlock;

And the structure for the header:

typedef struct header{
int size;
}header;

I was advised in my class to create a separate structure for a free memory block and another separate structure for an allocated block. My first idea was to distinguish the free/allocated blocks using one bit of the block size in header – set it to 1 if the block is allocated and 0 if it is free. ( I saw this technique used in implicit lists). So my question is: do I need to create a freeBlock and allocatedBlock structure for an explicit list or can I just use the one bit of the size?

The second question is: do I need a separate structure for the header/footer of the block? Or can I just write the size of the block in the header/footer as *(int *)ptr = size; ? I tried to use this in the initialize() function:

void initialize(void *ptr, int size){
memory = ptr;
*(int *)memory = size; //header
*((int *)memory + size) = size; //footer
}

Is this correct, please?

Many thanks for any help.

You can only use one bit of size if it is unused otherwise. If you choose bit 0 it will only work when only even numbers of memory words are allocated. I'd rather use two lists or add another element to the struct as a flag. The code will be so must clearer. — the busybee

the busybee the busybee · Accepted Answer · 2019-10-04T19:06:39

do I need to create a freeBlock and allocatedBlock structure for an explicit list[…]?

This sound to me like a very good idea. Just don't misunderstand the advice: You don't need two different structure definitions but two different lists. You can realize this with two pointers, one for free blocks and one for allocated blocks.

[…] can I just use the one bit of the size?

You can only use one bit of size if it is unused otherwise. If you choose bit 0 it will only work when only even numbers of memory words are allocated.

do I need a separate structure for the header/footer of the block?

That depends on your design and algorithm. Are you bound to create a header and a footer?

Or can I just write the size of the block in the header/footer as *(int *)ptr = size;?

You can do this. But I would assign the given pointer to a (temporary) pointer to the right struct and then assign values right in their places.

void initialize(void *ptr, int size) {
    memory = ptr;
    header* h = memory;
    h->size = size;
}

Additional observation: Instead of

typedef struct memoryBlock{
    struct memoryBlock *prev,*next;
}memoryBlock;

better get used to this, it will save you a lot of pulled-out hair:

typedef struct memoryBlock {
    struct memoryBlock *prev;
    struct memoryBlock *next;
} memoryBlock;

Note: Due to the (seemingly) complexity of pointer, please raise the warning level of you compiler to the maximum. Read all warnings and eliminate their reasons.

Explicit free list (dynamic memory allocation)

1 Answers