Shrinking a Stack in personal implementation-CodePudding

I am experiencing a problem in shrinking the size of a stack in a personal implementation of the data structure. I suppose is due to bad usage of realloc(). When the execution comes it (spop(), empty())(If I remove the realloc and decrement the number of elements, the implementation works fine), the program just ends (crash). Therefore, can you suggest me a better way to use the fucntion in my implementation or just point out what the problem might be? Thanks in advanced for any useful comment or answers.

stack.h

/*Stack.h*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stddef.h>


typedef struct Stack{   
    char **storage;     //Elements container;
    size_t capacity;    //Total amount of elements POSSIBLE in the stack;
    size_t size;        //Total amount of elements within the stack;
}Stack;

Stack *salloc(size_t);
void spush(Stack *, char *);
char *spop(Stack *);
void speek(Stack *);
void empty(Stack *);
void print_stack(Stack *);  //Useful but non-conventional

stack.c

/*Stack.c*/
#include "stack.h"

Stack *salloc(size_t size){
    Stack *s = (Stack *)malloc(sizeof(s));
    s->storage = (char **)malloc(sizeof(char *) * size);
    s->capacity = size;
    s->size = 0;
}

static int expand_stack(Stack *s){
    s->storage = realloc(s->storage, (s->capacity * 2));
}

static void shrink_stack(Stack *s){
    s->storage = realloc(s->storage, (s->capacity / sizeof(char *)));
}

void spush(Stack *s, char *elem){
    char *p = elem;
    int k = (s->capacity-1) - s->size; //Next free position

    if(s->size == s->capacity)
        expand_stack(s);

    s->storage[k] = (char *)malloc(sizeof(char) * (strlen(p)   1));
    memcpy(s->storage[k], p, (strlen(p)   1));
    // *(s->storage[k]   (strlen(p)   1)) = '\0';
    s->size  ;
}

char *spop(Stack *s){
    int k = s->capacity - s->size;

    if(s->size == 0)
        return NULL;

    free(s->storage[k]);
    s->size--;
    shrink_stack(s);
}

void speek(Stack *s){
    int k = s->capacity - s->size;
    printf("'%s'\n", s->storage[k]);
}

void empty(Stack *s){
    s->storage = realloc(s->storage, 0);
    s->capacity = 0;
    s->size = 0;
}

void print_stack(Stack *s){
    printf("[STACK] = {\n");
    int k = s->capacity - s->size;
    for(int i = k; i <= s->capacity-1; i  )
        printf("   '%s'\n", s->storage[i]);
    printf("}\n");
}

main.c

#include "stack.h"

#define COM1    "echo"
#define COM2    "start"
#define COM3    "sort"

int main(){
    Stack *s = salloc(5);

    spush(s, COM1);
    spush(s, COM2);
    spush(s, COM3);

    // speek(s);

    print_stack(s); //Full Stack

    spop(s);

    print_stack(s);

    spush(s, "cd");

    print_stack(s);

    empty(s);

    print_stack(s);

}

CodePudding user response：

There are quite a few issues in your code:

salloc is missing return s.
spop does not return anything (except for the NULL case).
salloc is not allocating enough memory for a Stack object (sizeof(s) is the size of the pointer, not the Stack object).
In all the calls in the form: s->storage = realloc(...) - the result from realloc (void*) should be cast to char**.
expand_stack is defined to return an int but nothing is actually returned. Should probably be changed to return void.
shrink_stack is not calculating the size properly. As a result in your case realloc can actually allocate a 0 size memory (Note:: this is a cause for an access violation exception in print_stack after calling spop). I suggest you use a debugger to catch this bug.

CodePudding user response：

Stack *salloc(size_t size){
    Stack *s = (Stack *)malloc(sizeof(s));
    s->storage = (char **)malloc(sizeof(char *) * size);
    s->capacity = size;
    s->size = 0;
}

Your first malloc call only allocates enough space for a Stack*, not enough space for the actual Stack structure. You want:

    Stack *s = (Stack *)malloc(sizeof(*s));

    Stack *s = (Stack *)malloc(sizeof(Stack));

CodePudding user response：

There's a lot of problems here. Both in design and in implementation, but all lessons worth learning.

Here are a summary of the changes:

salloc - We should store the initial capacity. empty was just freeing all storage which would make the stack unusable. By storing initial capacity, shrink_stack can avoid shrinking below that.
expand_stack - capacity must be modified after the expansion or we lose track of what the actual allocation is. Also, we wouldn't be able to add beyond the initial capacity without running into problems. Going by the int return, I suspect you intended to return the new capacity (which should be size_t.
shrink_stack should not just keep dividing the capacity, or eventually we hit zero. So using the initial_capacity we keep things no smaller than at the outset. It also needs to only shrink if the size has dropped to the point where there is value doing so.
spush - I don't know why you chose to allocate from the end of the storage but this fundamentally would break when the capacity increased and expansion occurred. Much simpler to add according to size, and pop off from size back towards zero. Note that const is added or some compilers will complain about passing a non-const pointer to a string literal, which is dangerous.
spop - As per spush, pop from size - 1 back towards zero. The other bug here was that the string is stored in a malloc'd buffer, so we should be freeing that, and that means we can't just return the pointer, but need the spop signature to provide a buffer and max size in which to put it. Given that we are dealing with null terminated strings, this can be an strncpy. Note that the return value is the passed address, or NULL if there is no element to pop. There are other ways to perhaps handle this that help remove the risk of elem == NULL etc.
speek - Again, just use size - 1
empty - Uses spop to remove all elements without discarding the initial capacity storage.
print_stack - From zero to size.

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


typedef struct Stack{   
    char **storage;     //Elements container;
    size_t capacity;    //Total amount of elements POSSIBLE in the stack;
    size_t size;        //Total amount of elements within the stack;
    size_t initial_capacity;
}Stack;

Stack *salloc(size_t size){
    Stack *s = (Stack *)malloc(sizeof(s));
    s->storage = (char **)malloc(sizeof(char *) * size);
    s->capacity = s->initial_capacity = size;
    s->size = 0;
    return s;
}

static int expand_stack(Stack *s){
    
    s->storage = (char **)realloc(s->storage, (sizeof(char *) * s->capacity * 2));
    s->capacity = s->capacity * 2;
    return s->capacity;
}

static void shrink_stack(Stack *s){
    if (s->capacity > s->initial_capacity && s->size < s->capacity / 2) {
        s->storage = (char **)realloc(s->storage, (sizeof(char *) * (s->capacity / 2)));
        s->capacity = s->capacity / 2;
    }
}

void spush(Stack *s, char const * elem){

    if(s->size == s->capacity)
        expand_stack(s);

    size_t size = strlen(elem)   1;
    s->storage[s->size] = (char *)malloc(sizeof(char) * size);
    memcpy(s->storage[s->size], elem, size);
    s->size  ;
}

char *spop(Stack *s, char * elem, size_t size){

    if(s->size == 0)
        return NULL;

    if (size > 0) {
        strncpy(elem, s->storage[s->size - 1], size);
    }
    free(s->storage[s->size - 1]);
    s->storage[s->size - 1] = NULL;
    s->size--;
    shrink_stack(s);
    return elem;
}

void speek(Stack *s){
    printf("'%s'\n", s->storage[s->size - 1]);
}

void empty(Stack *s){
    char notused;
    while (spop(s, &notused, 0) != NULL);
}

void print_stack(Stack *s){
    printf("[STACK] = {\n");
    for(int i = 0; i < s->size; i  )
        printf("   '%s'\n", s->storage[i]);
    printf("}\n");
}

#define COM1    "echo"
#define COM2    "start"
#define COM3    "sort"

int main(){
    
    Stack *s = salloc(5);

    spush(s, COM1);
    spush(s, COM2);
    spush(s, COM3);

    // speek(s);

    print_stack(s); //Full Stack

    char string[64];
    spop(s, string, sizeof(string)/sizeof(string[0]));

    print_stack(s);

    spush(s, "cd");

    print_stack(s);

    empty(s);

    print_stack(s);
}