Разграничение памяти стека и кучи

Question

Допустим, у меня есть реализация списка, который использует следующие listnode_t:

typedef struct ListNode { 
    struct ListNode *next; 
    struct ListNode *prev; 
    void *value; 
} listnode_t; 

Это вдвойне связанный список А, как вы можете видеть. У меня также есть list_t, которые имеют два указателя на listnode_t как первый и последний узел и размер списка. Теперь я предполагаю следующее в моем основной

int main(int argc, char *argv[]){ 
    ... 
    // Create two empty lists 
    list_t *list1 = make_list(); 
    list_t *list2 = make_list(); 

    // Populate one with ints 
    int x = 4; 
    int y = 5; 
    list_push(list1, &x); 
    list_push(list1, &y); 

    // Populate other with strings 
    string_t *str1 = make_string("foo"); 
    string_t *str2 = make_string("bar"); 
    list_push(list2, str1); 
    list_push(list2, str2); 
    ... 

    // Delete at the end 
    destroy_list(list1); 
    destroy_list(list2); 
} 

У меня есть проблема с реализацией destroy_list. Вот что я пробовал;

void destroy_list(list_t *list) 
{ 
    listnode_t *cur = list -> first; 
    for(cur = list -> first; cur != NULL; cur = cur -> next){ 
     if(cur -> prev){ 
      free(cur -> prev); 
     } 
    } 

    free(list -> last); 
    free(list); 
    list = NULL; 
} 

Моя проблема заключается в том, что я пытаюсь использовать void * в listnode_t, чтобы иметь возможность использовать этот список в общих чертах. Но когда я удаляю вещи, применение free(cur -> prev) кажется проблематичным. Когда я использую список таких вещей, как ints, как указано выше, поскольку они выделены в стеке, все идет хорошо, я думаю. Но если бы у меня был список строк, как указано выше, поскольку я использую динамическое распределение в моей реализации строки, я должен сначала применить free(cur -> prev -> value). Я не знаю, как это сделать, потому что, если я его добавлю, у меня возникает другая проблема с попыткой освободить выделенную стекю память на главном.

Что мне делать, я не получаю это общее поведение в списке.

Answer 1

// Populate one with ints 
int x, y = 4, 5; 
list_push(list1, &x); 
list_push(list1, &y); 

Не делайте этого.

интерфейс вы установили для list структуры эффективно говорит, что «собственность» указатель переходит к списку, когда list_push называется, и что указатель будет free() d списка в destroy_list. Передача указателя на переменную стека нарушает этот интерфейс - если вы хотите передать целое число, вам нужно сделать копию для списка, в который вы должны вступить.

Альтернативный интерфейс для структуры list может быть передан указателем и длиной до list_push, и эта функция возьмет копию структуры, а не сохранит ее. Будет ли это уместно, будет зависеть от используемого варианта, который вы имеете в виду для этой структуры.

(.. Кроме того, int x, y = 4, 5 не делать то, что вы думаете, что делает Вы, вероятно, означает int x = 4, y = 5)

Answer 2

ИНТ х, у = 4, 5;

Я не думаю, что это делает то, что вы думаете.

Но когда я удаляю вещи, применение cur -> prev кажется проблематичным.

«Проблемный» не является технологическим термином. Опишите точно, что вы ожидали, и что именно происходит.

Когда я использую список таких вещей, как ints, как указано выше, поскольку они выделены в стеке, все идет хорошо, я думаю.

Нет, они ничего, кроме штрафа. Когда вы берете адрес переменной в стеке, вы настраиваете себя на большое разочарование, потому что как только ваша функция вернется, стек будет мусором.

Но если бы я был список строк, как описано выше, так как я использую динамическое распределение в моей реализации строки я должен применить cur -> prev -> value первый

Что вы имеете в виду «применить»? И что вы подразумеваете под «первым»?

Я не знаю, как я могу это сделать, потому что, если я добавлю его,

Что вы имеете в виду под «добавить»? Что это"? Добавить к чему? В технологических текстах мы никогда не используем предлоги, такие как «это» и «это». Запишите это.

, тогда у меня возникает другая проблема, связанная с попыткой освободить выделенную память на основной памяти.

Снова «проблема» не говорит много. В любом случае, если я нахожусь в угадываю, в чем проблема, решение прост: всегда выделяйте место для value, чтобы вы всегда могли его освободить.

if(cur -> prev){ 
     free(cur -> prev); 
    } 

это не так, как вы удалять узлы из двусвязного списка. Чтобы удалить узел Y из дважды связанного списка, вы должны сначала отсоединить узел Y, так что prev узла Z указывает на узел X, а next узла X указывает на узел Z, а затем вы можете освободить узел Y. (После освобождения его значения.) И, конечно, вы всегда должны помнить, что узел Y может быть первым или последним узлом в списке, и в этом случае он не имеет предыдущего или следующего узла, и вместо этого вам нужно изменить либо головой или хвостом самой структуры списка.

Answer 3

Пользователь должен предоставить функцию для уничтожения value, поскольку только пользователь списка знает, что хранится и что нужно сделать.

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

struct LISTROOT { 
    listnode_t list; 
    void (*freeitem)(void * value); 
}; 
struct LISTROOT myList; 

struct MYTYPE { 
    char *buffer; 
    int *whatever; 
}; 
void myFreeItem(struct MYTYPE *item) 
{ 
    if (item) { 
     if (item->buffer) free(item->buffer); 
     ... 
     free(item); 
    } 
    } 

myList.list= make_list(myFreeItem); 

и в вашем коде:

if(cur -> prev){ 
     if (myList.freeitem) mylist.freeitem(cur->value); 
     free(cur -> prev); 

Обратите внимание, что список определяет freeitem принять значение void * и тому пользователя myFreeItem принимает указатель на более сложный struct. Компилятор принимает это и позволяет вам скрыть сложность того, что хранится в списке.

Answer 4

Очень распространенная модель для вызывающего абонента вашего интерфейса, чтобы указать, должны ли вещи быть освобождены контейнером. т.е.

list_t *list1 = make_list(0); // dont free items 
list_t *list1 = make_list(1); // free items 

и если они говорят «пожалуйста бесплатно», то вы просто вызываете free для них.Это проще, так как общий «здесь - это бесплатный обратный вызов», который должен предоставить вызывающий абонент (предлагается другим ответом)

Answer 5

Простым и довольно безопасным решением было бы позволить списку управлять копиями переданных значений. список отвечает за правильное распределение и освобождение памяти. См. Следующий код, который соответствующим образом адаптирует функции struct ListNode и list_push. Обратите внимание, что структура больше не содержит указателя на значение; он скорее сохраняет значение в элементе переменной длины value[] и выделяет достаточно памяти для самой структуры. Следовательно, освобождение объекта struct позже будет автоматически освобождать память для копии значения.

typedef struct ListNode { 
    struct ListNode *next; 
    struct ListNode *prev; 
    char value[]; 
} listnode_t; 

void list_push(list_t *t, void *value, size_t valueSize) { 

    listnode_t *newNode = malloc(sizeof(listnode_t) + valueSize); 
    memcpy (newNode->value, value, valueSize); 

    // ... any code necessary for attaching the new node to the list goes here 
}