Освободить стек, реализованный в C

Question

Я реализую стек и его функции в C. Теперь, после того как все функции были вызваны, я хотел освободить стек.

Мой вопрос: должен ли я сначала освободить базовый указатель стека "st" илипросто напрямую освободить стек "st"?Оба, кажется, работают в моем коде.

#include <stdio.h>
#include <stdlib.h>

#define init_size 10
#define increment 1

typedef struct sqStack
{
    int* top;
    int* base;
    int stack_size;
}sqStack;

int init_stack(sqStack* sq)
{
    if(sq->base==NULL)
    {
       sq->base = (int*)malloc(init_size*sizeof(int));
    }
    if(sq->base==NULL) exit(-1);
    sq->stack_size=init_size;
    sq->top=sq->base;
    return 1;
}
int push(sqStack* sq, int e)
{
    if(sq==NULL) exit(-1);

    if(sq->top-sq->base==sq->stack_size-1)//pointer top reaches the top of the stack
    {
        int* q = (int*)realloc(sq->base,(sq->stack_size+increment)*sizeof(int));
        if(q==NULL)  exit(-1);
            sq->base=q;
        sq->top=sq->base+sq->stack_size-1;
            sq->stack_size += increment;

    }
    *sq->top++=e;
    return 1;
}
int pop(sqStack* sq,int* e)
{
    if(sq==NULL) exit(-1);
    if(sq->base==sq->top)  exit(-1);
    sq->top--;
    *e=*sq->top;
    sq->stack_size--;
    return *e;
}
int top(sqStack* sq,int* e)
{
    if(sq==NULL) exit(-1);
    if(sq->base==sq->top)  exit(-1);
    *e=*(sq->top-1);
    return *e;
}
int empty(sqStack* sq)
{
    if(sq->base==sq->top) return 1;
    else return 0;
}

int main() {
    sqStack* st= (sqStack*)calloc(1,sizeof(sqStack))  ;
    int e;
    init_stack(st);
    for(int i=0;i<12;i++)
    {
        push(st,i+1);

    }
    for(int i=0;i<12;i++)
    {
        printf("%d\n",top(st,&e));
        printf("%d\n",pop(st,&e));
    }
    free(st->base);
    free(st);
    return 0;
}

Результат: 12 12 11 11 10 10 9 9 8 8 7 7 6 6 5 5 4 4 3 3 2 2 1 1 каждый номер находится на одномлиния.

Answer 1

Каждое распределение должно быть в паре с соответствующим free, так что в вашем случае это означает освобождение как st->base, так и st (в этом порядке).Но ваша программа освобождается только непосредственно перед завершением, и все, что она не освобождает, будет возвращено ОС после завершения программы.Анализатор использования памяти, такой как Valgrind, может обнаружить для вас разницу, но на практике это не имеет значения.

Answer 2

Ваш код правильный.Обратная последовательность может сработать, но если это сработает, это будет случайным.

Причина в том, что free(st) освобождает память, в которой хранится объект *st.Указатель st->base хранится в части этой самой памяти.Предположим, что какая-то другая задача или поток приобрели ту же память, как только она была освобождена.Что тогда?То есть, что произойдет, когда free(st->base) будет в конце концов вызвано?

Ответ: что произойдет, не определено.

Даже если бы все еще можно было получить адрес из st->base (иэто может быть невозможно), этот адрес мог быть перезаписан произвольными данными, и в этом случае free(st->base) - при интерпретации произвольных данных как адреса - попросит операционную систему освободить ... ну, вы не знаете что будет запрашивать операционную систему для освобождения.Вряд ли стоит ожидать хороших результатов в этом случае.

Вы хорошо поработали.Ваша последовательность правильная.

ДОПОЛНИТЕЛЬНЫЕ СООБРАЖЕНИЯ

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

Answer 3

То, что у вас есть, является правильным с точки зрения malloc и free.

. Вы должны передать только free то, что было возвращено с malloc или realloc.Вы выделяете пространство для структуры и для стека и освобождаете оба, так что вы не теряете никакой памяти.

Вы не хотите сначала free(st), потому что после этого память, которая stбыло указано, что он больше не действителен, и впоследствии вы не сможете free(st->base) безопасно.Кроме того, поскольку free ничего не знает о содержимом данной памяти, он не пытается освободить какие-либо указатели, которые может содержать память.Так что простой вызов free(st) приводит к утечке памяти в st->base.