6
\$\begingroup\$

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;
}
\$\endgroup\$
3
\$\begingroup\$
  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);
    
\$\endgroup\$
  • \$\begingroup\$ @gues532 I'd use size_t over unsigned, but we've gone over that before. \$\endgroup\$ – chux - Reinstate Monica Sep 13 '14 at 0:09
  • \$\begingroup\$ 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 ? \$\endgroup\$ – gues532 Sep 13 '14 at 0:44
  • \$\begingroup\$ 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 ? \$\endgroup\$ – gues532 Sep 13 '14 at 0:45
  • \$\begingroup\$ 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. \$\endgroup\$ – chux - Reinstate Monica Sep 13 '14 at 2:59
  • \$\begingroup\$ 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. \$\endgroup\$ – chux - Reinstate Monica Sep 13 '14 at 3:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.