Maintaining a free list in a malloc implementation

开发者_JAVA百科I'm trying to implement malloc for my Operating Systems class, and I was wondering about the advantages of maintaining a doubly linked list of free memory blocks as opposed to a singly linked list.

If you split one big block of memory into smaller ones in malloc(), then when you return those pieces of it with free(), you'll have to concatenate each returned block with its 2 neighbors. A doubly linked list is the easiest to deal with in such a situation.

Rough sketch of free_block using an implict list. Memory is arranged as an array of ints, block is the offset of the block to the free in that array, prev and next are the offsets of the preceding and following blocks. Each block both begins and ends with an integer containing the size of the block, including the header and footer:

void free_block(int memory[], int block) {
    // Write the header of the free block
    int block_size = GET_SIZE(memory[block]);
    memory[block] = MAKE_FREE(block_size);

    // Check if the next block is free
    int next = block + block_size;
    int next_size = GET_SIZE(memory[next]);
    if (IS_FREE(memory[next])) {
        // Great! Coalesce the blocks
        block_size = block_size + next_size;
        memory[block] = MAKE_FREE(block_size);
    }

    // Check if the previous block is free
    int prev_size = GET_SIZE(memory[block - 1]);
    int prev = block - prev_size;
    if (IS_FREE(memory[prev])) {
        prev_size = prev_size + block_size;
        memory[prev] = MAKE_FREE(prev_size);
    }
}

Because the header containing the block size is duplicated at the beginning and end of each block, it serves as the doubly linked list and you can traverse the free list forwards and backwards. The pointers are implicit or or relative.