Грубый набросок free_block
с использованием списка последствий. Память организована в виде массива целых чисел, block
- это смещение блока к свободному в этом массиве, prev
и next
- смещения предыдущего и последующего блоков. Каждый блок начинается и заканчивается целым числом, содержащим размер блока, включая верхний и нижний колонтитулы:
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);
}
}
Поскольку заголовок, содержащий размер блока, дублируется в начале и конце каждого блока, он служит в качестве двусвязного списка, и вы можете перемещаться по свободному списку вперед и назад. Указатели являются неявными или относительными.