0
\$\begingroup\$

I've a simple push/pop implementation in my program:

void Push(int* stack, int top, int item)
{
  if (top == SIZE - 1) {
    printf("Overflow\n");
    return;
  } else if (item == INT_MIN) {
    printf("Item size out of bounds\n");
    return;
  }
  stack[++top] = item;
}

int Pop(int* stack, int top)
{
  if (top == -1) {
    printf("Empty\n");
    return INT_MIN;
  }
  return stack[top--];
}

In the Pop() function, I've wanted to return some kind of error code when the stack is empty but since all of the int values are valid returns: Can I resort to reserving INT_MIN for this? Is this a 'good practice', have unwanted consequences etc?

\$\endgroup\$
5
  • 1
    \$\begingroup\$ All of the int values are valid returns. INT_MIN is a valid integer. What does that tell you? \$\endgroup\$
    – Reinderien
    Jan 22, 2023 at 5:08
  • 1
    \$\begingroup\$ SIZE is undefined, and I'm guessing there should be some #includes for INT_MIN and printf. \$\endgroup\$ Jan 22, 2023 at 7:29
  • \$\begingroup\$ [There are some good answers to this on SO] stackoverflow.com/q/75198536/20017547 \$\endgroup\$
    – Harith
    Jan 22, 2023 at 9:58
  • \$\begingroup\$ Currently we don't have enough code to do a code review. We need to see how the code is used and the definitions of the constants. \$\endgroup\$
    – pacmaninbw
    Jan 22, 2023 at 15:40
  • \$\begingroup\$ Pop() should just remove the value. You should have a top() to get the top value. That is where the complexity comes from: pop() doing two different things. \$\endgroup\$
    – Kristian H
    Jan 25, 2023 at 4:23

3 Answers 3

3
\$\begingroup\$

This is a classic example of in-band error signalling, and it's not a good idea (I think you suspect this, having asked about it). You need to separate the data from the error/success status of the function. There are several ways to do this, but most of them involve a return value for one, and a pointer argument for the other. For instance,

bool Push(int *stack, int *top, int item);
int Pop(const int *stack, int *top, bool *success);

Note that stack should be const, and this function will not work correctly unless top is passed by reference.

Also, for your error prints, you should usually print to stderr and not stdout.

\$\endgroup\$
5
  • 1
    \$\begingroup\$ "Note that stack should be const" --> Disagree. Making stack const only adds unneeded clutter to these function declarations and serves no purpose. \$\endgroup\$ Jan 24, 2023 at 18:25
  • \$\begingroup\$ @chux One person's clutter is another person's critical self-documenting code annotation. We will agree to disagree. \$\endgroup\$
    – Reinderien
    Jan 24, 2023 at 23:50
  • \$\begingroup\$ Reinderien, const stack has some use in the function definition. What documentation do you see in the declaration that the caller cares about? \$\endgroup\$ Jan 25, 2023 at 0:45
  • \$\begingroup\$ Do you perhaps have those reversed? The declaration matters more than the definition for the purposes of API documentation. Anyway: the declaration and definition should never, ever be different. \$\endgroup\$
    – Reinderien
    Jan 25, 2023 at 0:46
  • \$\begingroup\$ Do you perhaps have those reversed? No. The declaration matters more than the definition for the purposes of API documentation - true. Anyway: the declaration and definition should never, ever be different - a good generality except when the function definition use const parameters - the caller simply does not need to know or care if the parameter is used in a const fashion or not. But to each his own. \$\endgroup\$ Jan 25, 2023 at 0:57
2
\$\begingroup\$

Can I resort to reserving INT_MIN for this?

Yes.

Is this a 'good practice', have unwanted consequences etc?

Not good. This is a poor practice.

The obvious unwanted consequences is that code cannot handle all int.

It is good that Push(..., ..., INT_MIN) does fail, yet calling code does not receive an indication of a failure. Instead use the return value of the functions to indicate an error.


Missing

Missing code show how calling code should initialize its stack and top objects.

SIZE undefined.

Missing #include <limits.h>. (INT_MIN).

Missing #include <stdio.h>.

Unexpected output

Rather than print a overly simplistic message to stdout, return an error code and let the calling code decide what to do.

\$\endgroup\$
2
\$\begingroup\$

You’re Throwing Away the Top of the Stack

You increment or decrement your function parameter named top, but that’s just a local temporary variable inside the function. As soon as you return, any changes you make to it will be thrown away. Your code makes me extremely suspicious that you expect top to be passed by reference. But if you call pop(stack_top), the stack_top variable in the scope of the call will not be updated. In fact, you could even pass in a constant, like pop(0).

What you really want to do here is declare your stack as a struct with a member named top, and pass around pointers to that.

Your Stacks Cannot Have Different Sizes

There’s one predefined constant in your program, named SIZE, which must be the size of every stack in your program. This is an extremely inflexible approach and you should change it, but if you do want to stick with it, you could declare your stacks as int[SIZE] rather than int* and make it a little harder to shoot yourself in the foot.

You Could Widen the Return Type, But ....

There’s an even better approach here, but: Another way to handle error-signaling would be to make the return type wider than int. For example, you could store int32_t but return int64_t. Or, on most actually-existing implementations, sizeof(long long int) > sizeof(int)—but if you rely on this assumption, you ought to static_assert() it, which doesn’t cost you anything at runtime.

If you return a 64-bit value whose error code is something like LLONG_MIN, that’s equivalent to returning a 32-bit int in the lower word, and a 32-bit Boolean value in the upper word, but a lot more efficient than passing in two output parameters because they’re packed into a single value.

Are There Really Any Recoverable Errors?

There are only two possible error conditions: full and empty. You don’t actually have push() return any kind of error value as it is, only print a message to the console. These are already so exceptional that you’re breaking the behavior of the program to report the bug out-of-band. (Which, if you’re going to, should be to standard error instead of standard output.)

Trying to pop off an empty stack is a logic error in the program. It should never happen. If there ever is a case where client code is handed a stack that might or might not be empty, it would compare the size to 0 before calling pop(), not the return value afterward. It’s pretty silly to say that the program should handle this kind of logic error by passing in -1 as the size parameter and then testing the return value to check whether the value it passed in was -1! You could therefore justifiably make this a fatal logic error and abort the program with an error message.

If your stack uses dynamic memory, and allocates more as needed, it’s no longer possible to exceed the fixed size. You might get an out-of-memory error, but, first, you can handle that as an unrecoverable error too instead of returning an error value. Second, unless you’re coding some kind of embedded microcontroller or something, a modern OS would be thrashing to death long before it reported to an app that it was out of memory.

Use the Right Type for Size and Index Values

This is usually size_t. On most compilers, int is a 31-bit value, with a maximum value a little over 2 billion, less than the size of many modern data files. If you ever ported it to a 16-bit compiler, it could limit you to a size of only 32,767 elements on the stack.

Some programmers prefer to use a signed value, to check for wraparound. That would be ptrdiff_t, from <stddef.h>. (Your code does indeed use negative values of the stack top, but in a way you could easily refactor out.) A few shops, such as Microsoft, use an unsigned value whose top bit must be zero, like rsize_t.

Putting it All Together

Here’s a very bare-bones implementation that uses a vector:

#include <assert.h>
#include <stdint.h>
#include <stdlib.h>

typedef struct stack_t {
  int* data;
  size_t used;
  size_t allocated;
} stack_t;

/* An expression suitable for:
 * stack_t foo = STACK_INITIALIZER;
 */
#define STACK_INITIALIZER { .data = NULL, .used = 0, .allocated = 0 }

int pop( stack_t* const stackp )
{
  // For this project, unrecoverable errors will be handled by assertions.
  assert(stackp->used > 0);

  return stackp->data[--stackp->used];
}

void push( stack_t* const stackp, const int value )
{
  if ( stackp->used == stackp->allocated ) {
    static const size_t default_alloc = 1024;
    stackp->allocated = (stackp->allocated == 0) ? default_alloc : stackp->allocated * 3 / 2;
    assert( stackp->allocated < SIZE_MAX / sizeof(int) );
    stackp->data = realloc( stackp->data, sizeof(int) * stackp->allocated );
    assert(stackp->data);
  }
  // If control reaches this point, stackp->data has enough storage to hold the new element.
  stackp->data[stackp->used++] = value;
  return;
}

And a primitive test harness, without full code coverage.

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

/* Crude testcase-checker.  Doesn’t even print the line number.
 */
bool test_int( const int got, const int expected )
{
  if (got == expected) {
    return true;
  } else {
    fflush(stdout);
    fprintf( stderr, "Case Failed: Expected %d, got %d.\n", expected, got );
    return false;
  }
}

int main(void)
{
  stack_t stack = STACK_INITIALIZER;
  bool passed_so_far = true;

  push( &stack, 1 );
  push( &stack, 2 );
  push( &stack, 3 );
  push( &stack, 4 );
  push( &stack, 5 );

  passed_so_far &= test_int( pop(&stack), 5 );
  passed_so_far &= test_int( pop(&stack), 4 );

  push( &stack, 6 );
  push( &stack, 7 );

  passed_so_far &= test_int( pop(&stack), 7 );
  passed_so_far &= test_int( pop(&stack), 6 );
  passed_so_far &= test_int( pop(&stack), 3 );
  passed_so_far &= test_int( pop(&stack), 2 );
  passed_so_far &= test_int( pop(&stack), 1 );

  // pop(&stack); // Causes an assertion to fail.

  if (passed_so_far) {
    printf("All test cases passed.\n");
    return EXIT_SUCCESS;
  }

  return EXIT_FAILURE;
}
\$\endgroup\$
7
  • \$\begingroup\$ Note that the obvious way of using "a signed value, to check for wraparound" is Undefined Behaviour, and the correct way to check for overflow is to check before the arithmetic (or possibly to use compiler extensions such as signalling saturating arithmetic). \$\endgroup\$ Jan 25, 2023 at 6:33
  • \$\begingroup\$ Oh, perhaps you were talking of underflow (passing zero, rather than exceeding max). That's different, and not a problem. \$\endgroup\$ Jan 25, 2023 at 6:34
  • \$\begingroup\$ @TobySpeight I’m not completely sure what line you’re responding to. If you mean the use of a signed size value, the idea there is that it will catch wraparound from below, but not from above. However, Microsoft did create an unsigned type to handle wraparound in both directions, rsize_t. \$\endgroup\$
    – Davislor
    Jan 25, 2023 at 6:42
  • 1
    \$\begingroup\$ @TobySpeight The fact is, it’s hard. I caught three bugs in the memory-management after I posted, one of which was that I hadn’t tested whether the size of my memory allocation overflows. \$\endgroup\$
    – Davislor
    Jan 25, 2023 at 6:44
  • 1
    \$\begingroup\$ @TobySpeight It’s in the optional Annex K of C11, I believe. \$\endgroup\$
    – Davislor
    Jan 25, 2023 at 7:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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