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).
What would be a better way to use the function in my implementation, or what might the problem be?
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 missingreturn s
.spop
does not return anything (except for theNULL
case).salloc
is not allocating enough memory for aStack
object (sizeof(s)
is the size of the pointer, not theStack
object).- In all the calls in the form:
s->storage = realloc(...)
- the result fromrealloc
(void*
) should be cast tochar**
. expand_stack
is defined to return anint
but nothing is actually returned. Should probably be changed to returnvoid
.shrink_stack
is not calculating the size properly. As a result in your caserealloc
can actually allocate a 0 size memory (Note:: this is a cause for an access violation exception inprint_stack
after callingspop
). 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));
or
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 theint
return, I suspect you intended to return the new capacity (which should besize_t
.shrink_stack
should not just keep dividing the capacity, or eventually we hit zero. So using theinitial_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 thatconst
is added or some compilers will complain about passing a non-const pointer to a string literal, which is dangerous.spop
- As perspush
, pop fromsize - 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 thespop
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 anstrncpy
. 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 usesize - 1
empty
- Usesspop
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, ¬used, 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);
}