Dynamically-sized stack - follow-up 2

Question

Follow up of - Dynamically-sized stack - follow up

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

• changing the function names to have a prefix
• making the pop() function only popping and not returning the value as well
• checking for OOM exception / scenario that 0 is passed to capacityIncrement variable when initializing the stack (in those cases, if trying to push values to the stack, just ignore)
• added a decrement mechanism, when popping values a check will be made to see if there are (capacityIncrement / 2 + capacityIncrement) elements in the stack that are not in use, and if so, decrement the stack size by capacityIncrement

#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);
void stack_push(Stack*, int);
void stack_pop(Stack*);
int stack_peek(const Stack*);
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 s1;
 stack_initialize(&s1, 4);
 for(int i = 0; i < 25; i++)
 {
 stack_push(&s1, i + 1);
 }
 stack_pop(&s1);
 stack_push(&s1, 88);
 stack_push(&s1, 25);
 printf("The top of the stack is %d.\n", stack_peek(&s1));
 while(!stack_isEmpty(&s1))
 {
 int top = stack_peek(&s1);
 stack_pop(&s1);
 printf("Popping %d from the top of the stack.\n", top);
 printf("Size of stack is %d.\n", s1.stackSize);
 }
 return 0;
}
void stack_initialize(Stack *p, unsigned int capacityIncrement)
{
 p->elementData = NULL;
 p->stackSize = 0;
 p->capacityIncrement = capacityIncrement;
 p->elementCount = 0;
}
void stack_push(Stack *p, int value)
{
 if (p->elementCount == p->stackSize)
 {
 int newStackSize = p->stackSize + p->capacityIncrement;
 void *temp = realloc(p->elementData, sizeof(*p->elementData) * newStackSize);
 if (temp == NULL || newStackSize == 0)
 {
 return;
 }
 p->stackSize = newStackSize;
 p->elementData = temp;
 }
 p->elementData[p->elementCount] = value;
 p->elementCount++;
}
void stack_pop(Stack *p)
{
 if (!stack_isEmpty(p))
 {
 p->elementCount--;
 if(p->stackSize - p->elementCount == p->capacityIncrement / 2 + p->capacityIncrement)
 {
 int newStackSize = p->stackSize - p->capacityIncrement;
 p->elementData = realloc(p->elementData, sizeof(*p->elementData) * newStackSize);
 p->stackSize = newStackSize;
 }
 }
}
int stack_peek(const Stack *p)
{
 if (!stack_isEmpty(p))
 {
 return p->elementData[p->elementCount - 1];
 }
 return 0;
}
void stack_destroy(Stack *p)
{
 free(p);
}
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;
}

Answer 1

1. Use same case prefix for type "Stack" and functions "stack" --> "gStack" or whatever.

2. Use correct print specifier. This implies that either OP does not have all warnings enabled or is using a weak compiler. Suggest remedying that.

   // printf("Size of stack is %d.\n", s1.stackSize);
   printf("Size of stack is %u.\n", s1.stackSize);
   

3. Use consistent sign-ness

   // int newStackSize;
   unsigned newStackSize;
   

4. In push(), newStackSize test should be corrected or eliminated.

   // if (temp == NULL || newStackSize == 0)
   if (temp == NULL && newStackSize > 0)
   // or if confident newStackSize will never be 0 here
   if (temp == NULL)
   

5. Silently failing push() due to OOM is a concern.

6. pop() should do similar OOM protection as pop(). Even though it sounds silly that reducing memory usage should ever fail.

7. Consider putting all memory allocation into one helper function. (BTW: destroy() did not free p->elementData.

   static int stack_realloc(int **ptr, unsigned *oldsize, unsigned newsize) {
    if (newsize > 0) {
    void *newptr = realloc(*ptr, newsize);
    if (newptr == NULL) return 1; // fail
    *ptr = newptr;
    }
    else {
    free(*ptr);
    *ptr = NULL;
    }
    *oldsize = newsize;
    return 0; // success;
   }
   // push()
   unsigned newStackSize = p->stackSize + p->capacityIncrement;
   if (stack_realloc(&p->elementData, &p->stackSize, newStackSize);
   // pop()
   // change from == to >=
   if(p->stackSize - p->elementCount >= p->capacityIncrement / 2 + p->capacityIncrement) {
    unsigned newStackSize = p->stackSize - p->capacityIncrement;
    // No problem is realloc failed, just continue with current stack
    stack_realloc(&p->elementData, &p->stackSize, newStackSize);
   // destroy() 
   stack_realloc(&p->elementData, &p->stackSize, 0);
   // Do not free `p`.
   // free(p);
   

• chux: @gues532 I'd use size_t over unsigned, but we've gone over that before.
• gues532: I'm having couple of difficulties with your corrections : 4. I don't understand why it should be && and not ||. In a case that capacityIncrement is set to 0 and we try to push a value for the first time, let's say temp will point to an address which is NOT NULL, the newStackSize will equal 0 and because of the && we'll skip the if statement and try to push a value to a 0 bytes address. 6. I've thought about it, but how would such scenario where if we decrement the size it'll fail due to OOM exception, mind giving an example ? 7. Why didn't it free elementData exatcly ?
• gues532: About size_T I haven't worked with it yet and I don't understand what is it exactly ? Is it a structure ? The only thing I've understood from reading online that it's the same as unsigned integer, yet it doesn't tell me what it is (structure I assume ? ) and why should I prefer it over unsigned int if it's basically an unsigned int ?
• chux: size_t is the type of unsigned integer returned from sizeof(). Sometimes it is wider than unsigned. So it always covers the index-able range for arrays. It is also the type returned by strlen(), used in memcpy(), etc.
• chux: When push() occurs, the newsize must always be greater than the current size. If code's newsize calculation ever resulted in a equal or less value the rest of code will not work as the stack will be too small. This has nothing to do with a realloc() failure. If newsize <= p->elementCount, code should test and cope with that before calling realloc(). Thus push() should only ever call realloc() with a newsize >= 1.