Dynamically-sized stack - follow-up 3

Question

Follow up of - Dynamically-sized stack - follow-up 2

I've took the tips given to me, and what I did now is:

• Use same case type for type stack and it's functions
• Returning 1 if push failed due to an OOM exception otherwise return 0 if succeeded.
• push could now only return a pointer to null due to OOM exception and not because of allocating 0 bytes, in stack_initialize capacitiyIncrement is set to 1 if it's 0 preventing newStackSize being 0 if trying to push elements. Only occurrence where newStackSize will be 0 is if trying to shrink the stack size and there're no elements left in the stack.
• Made a stack_realloc() function to deal with all stack reallocations.
• stack_destroy() function is now freeing the memory of the elements saved in the stack and not the actual stack object.

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
typedef struct
{
 int *elementData;
 unsigned int stackSize;
 unsigned int capacityIncrement;
 unsigned int elementCount;
} stack;
void stack_initialize(stack*, unsigned int);
int stack_push(stack*, int);
void stack_pop(stack*);
int stack_peek(const stack*);
static int stack_realloc(stack*, unsigned int);
void stack_destroy(stack*);
bool stack_isEmpty(const stack*);
void stack_setCapacityIncrement(stack*, unsigned int);
unsigned int stack_getCapacityIncrement(const stack*);
unsigned int stack_getNumberOfElements(const stack*);
unsigned int stack_getSize(const stack*);
int main()
{
 stack s;
 stack_initialize(&s, 4);
 for(int i = 0; i < 25; i++)
 {
 stack_push(&s, i + 1);
 }
 stack_pop(&s);
 stack_push(&s, 88);
 stack_push(&s, 25);
 while (!stack_isEmpty(&s))
 {
 printf("The top of the stack is %d.\n", stack_peek(&s));
 stack_pop(&s);
 printf("The size of the stack is %u.\n", s.stackSize);
 }
}
void stack_initialize(stack *p, unsigned int capacityIncrement)
{
 p->elementData = NULL;
 p->stackSize = 0;
 if (capacityIncrement == 0)
 {
 capacityIncrement++;
 }
 p->capacityIncrement = capacityIncrement;
 p->elementCount = 0;
}
int stack_push(stack *p, int value)
{
 if(p->elementCount == p->stackSize)
 {
 if(stack_realloc(p, p->stackSize + p->capacityIncrement) == 1)
 {
 return 1;
 }
 }
 p->elementData[p->elementCount] = value;
 p->elementCount++;
 return 0;
}
void stack_pop(stack *p)
{
 if(!stack_isEmpty(p))
 {
 p->elementCount--;
 if(p->elementCount == 0 || p->stackSize - p->elementCount >= p->capacityIncrement / 2 + p->capacityIncrement)
 {
 stack_realloc(p, p->stackSize - p->capacityIncrement);
 }
 }
}
int stack_peek(const stack *p)
{
 if(!stack_isEmpty(p))
 {
 return p->elementData[p->elementCount - 1];
 }
 return 0;
}
static int stack_realloc(stack *p, unsigned int newStackSize)
{
 if (newStackSize > 0)
 {
 void *temp = realloc(p->elementData, sizeof(*p->elementData) * newStackSize);
 if(temp == NULL)
 {
 return 1;
 }
 p->elementData = temp;
 }
 else
 {
 stack_destroy(p);
 }
 p->stackSize = newStackSize;
 return 0;
}
void stack_destroy(stack *p)
{
 free(p->elementData);
 p->elementData = NULL;
}
bool stack_isEmpty(const stack *p)
{
 return p->elementCount == 0;
}
void stack_setCapacityIncrement(stack *p, unsigned int capacityIncrement)
{
 p->capacityIncrement = capacityIncrement;
}
unsigned int stack_getCapacityIncrement(const stack *p)
{
 return p->capacityIncrement;
}
unsigned int stack_getNumberOfElements(const stack *p)
{
 return p->elementCount;
}
unsigned int stack_getSize(const stack *p)
{
 return p->stackSize;
}

• chux: Add p->stackSize = 0; to stack_destroy(). it may be called independently of other functions.
• gues532: @chux Besides that (and size_t) everything else is fine ? :)
• chux: 0 check in stack_setCapacityIncrement()? newsize in pop() is a problem given CapacityIncrement could be > stackSize. Maybe stack_realloc(p, p->elementCount); Suggest elminateing stack_setCapacityIncrement()
• syb0rg: Why did you change your typedef struct for Stack to be lowercase (stack)? That wasn't recommended to you in your last review, and is what I would consider not following modern C conventions.
• gues532: @chux I thought it could cause problem, but for someone who will use the header that something he should know before changing the capacitySize to something that wont be greater than the stackSize, but don't you think if it'll be better to leave that method in-case someone will ever find use for it ? Although he'll need to know what he's doing.

Answer 1

Its not a problem but this seems strange:

stack_realloc(p, p->stackSize - p->capacityIncrement);

Decreasing the size of the stack when you take elements out. This may cause a lot of work (in your code) if you are near a boundary and do a lot of push/pop combinations. It is unlikely that the memory is actually released by realloc() when shrinking anyway.

• gues532: I've been suggested to shrink the size of the stack when popping on previous follows-up so I'm not sure to whom I should listen. it would be helpful if someone could give me a concrete answer. Also, why is it unlikely that the memory will be releaed after calling realloc() ? Isn't that what the method is doing if the address is changed / the size shrank and the address remained the same ?
• glampert: @gues532, I agree with Loki that it is not very useful to realloc when shrinking the stack. It is possible that in the future it will grow again, so why not keep that space around and ready for use? This is same premisse realloc() goes by. The function is free to do nothing if the new size is < than the old size, since the user might very well expand the array back to the larger size in the future.
• Carl: I am of the mindset that the stack should not shrink in size, as well as that when the stack does need to grow, it should simply double its capacity. This means the chances for reallocation only go down as the stack is used.

Answer 2

Two comments:

• having stack_pop not return the value popped is silly. I see no advantage in this and it has the disadvantage that I have to call two functions to remove each value from the stack (against one for adding each value).

• static functions should normally be at the top of the file before public functions (as should main). This avoids the need for prototypes of statics.

EDIT

Arguing that a pop that returns the value popped is doing too much places too much value on dogma (such as, a function should do one thing well). Do you know of any processor 'pop' command that separates copying values from the stack into registers from adjusting the stack pointer? That is the one thing that a 'pop' does. It is made of two components but conceptually it is one. Just like a 'push' makes space on the stack and copies registers into that space.

Moreover, separating the two parts makes protecting against concurrent access so much harder - with a normal pop you just wrap the two parts in a mutex (or whatever). With two separate functions (peek/pop) you have to leave it the the user - a recipe for problems.

--

Functions are not considered static automatically - they default to being public. Only by using the static keyword do they become static (private to the file). Putting them at the beginning of the file before functions that will use them (and omitting a now-redundant prototype) is normal. Putting main at the end is also common.

• Carl: stack_pop shouldn't return a value because that means the function is doing more than popping. Also, and this isn't a big deal for a stack of int, but it would mean that whatever was returned from stack_pop would have to be a copy of the element that was in the stack.
• gues532: @William Morris I like to keep prototype for every function, but if I declare the function with it's body on top of the file even before main is it considered static function automatically ?
• William Morris: @carl I added some stuff to my answer for you.
• Carl: @WilliamMorris If I have a stack of char *, I expect it to make a copy when a string is pushed to it. If pop returns a string then that string must be a copy of what was on the stack. Now a user must be concerned about the memory management of the stack.
• William Morris: @carl are you suggesting that, because a stack of strings would present its own particular problems in C, all stacks must solve those problems (from which they may not suffer), even at the expense of making them clumsy to use?

Answer 3

The stack should be an incomplete type to the user. This is going to allow you to hide all of the implementation details of the stack. Right now, it is possible for the user of your stack to change the variables contained within the struct.

typedef struct Stack Stack;
Stack* stack_initialize( void );
int main( void )
{
 Stack* my_stack = stack_initialize( void );
 my_stack->data = NULL; // compile error
 // stack_destroy( my_stack );
}
struct Stack
{
 int *data;
};
Stack* stack_initialize( void )
{
 Stack* ret = malloc( sizeof( Stack ) );
 ret->data = malloc( whatever ); // okay
 return ret;
}

---

I would also say that the user should have no idea about capacityIncrement. A practical reason for this is that I, as a lowly stack user, have no idea what the most efficient capacityIncrement is. The OO reason for this is that this is a detail that I do not need to care about.

All I need to know about a stack is that it is a FILO container. I would expect it to have push, peek, and pop functionality. I don't care if it is implemented as a dynamic array, or a linked-list, or whatever.

Answer 4

1. Add a check to every stack functions like stack_initialize, stack_push, stack_destroy to check the pointer p for NULL.

   if(p == NULL) { return 1; }

2. This is quite strange your pop operation does not return the item. Also, please handle the execution status of each function call.