Явный свободный список (динамическое распределение памяти) - PullRequest
Новая
       15

Явный свободный список (динамическое распределение памяти)

1 голос
/ 04 октября 2019

Мне нужна помощь с моим заданием. Моя работа состоит в том, чтобы создавать / реализовывать функции malloc / free в C, используя технику «Явный свободный список среди только свободных блоков»Я уже изучил много материалов, но я все еще застрял в какой-то момент, и я не понимаю некоторые детали. Поэтому моя работа заключается в создании 4 функций - initialize (), allocate (), free () и check (). Я могу использовать только одну глобальную переменную void *memory - это блок, в котором я могу выделить свою память с помощью alloc ().

Поэтому я хотел реализовать это с помощью двунаправленного связного списка и создал структуру:

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

И структура заголовка: 

typedef struct header{
int size;
}header;

В моем классе мне посоветовали создать отдельную структуру для свободного блока памяти и другую отдельную структуру для выделенного блока. Моя первая идея состояла в том, чтобы различать свободные / выделенные блоки, используя один бит размера блока в заголовке - установите его равным 1, если блок выделен, и 0, если он свободен. (Я видел эту технику, используемую в неявных списках). Итак, мой вопрос: мне нужно создать структуру freeBlock и allocatedBlock для явного списка или я могу просто использовать один бит размера?

Второй вопрос: мне нуженотдельная структура для верхнего / нижнего колонтитула блока? Или я могу просто написать размер блока в верхнем / нижнем колонтитуле как *(int *)ptr = size;? Я пытался использовать это в функции initialize (): 

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

Это правильно, пожалуйста?

Большое спасибо за любую помощь.

1 Ответ

0 голосов
/ 04 октября 2019

мне нужно создать структуру freeBlock и allocBlock для явного списка […]?

Для меня это звучит как очень хорошая идея. Только не поймите неправильно совет: вам не нужны две разные структуры определения , а два разных списка. Вы можете реализовать это с помощью двух указателей, одного для свободных блоков и одного для выделенных блоков.

[…] я могу просто использовать один бит размера?

Вы можете использовать только один бит размера, если он не используется в противном случае. Если вы выберете бит 0, он будет работать только тогда, когда выделены только четные числа слов памяти.

нужна ли мне отдельная структура для верхнего / нижнего колонтитула блока?

Это зависит от вашего дизайна и алгоритма. Вы обязаны создать верхний и нижний колонтитулы?

Или я могу просто написать размер блока в верхнем / нижнем колонтитуле как *(int *)ptr = size;?

Вы можете сделать это. Но я бы назначил данный указатель (временному) указателю на правильную структуру, а затем назначил бы значения прямо на своих местах. 

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

Дополнительное наблюдение: вместо 

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

лучшепривыкнуть к этому, это сэкономит вам много выдернутых волос: 

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

Примечание: из-за (на первый взгляд) сложности указателя, пожалуйста, поднимите уровень предупреждения вашего компилятора домаксимум. Прочитайте все предупреждения и устраните их причины.

...