A C stack with minimum and maximum values

Question

I have this C stack implementation that knows its minimum and maximum values:

minmax_stack.h

#ifndef NET_CODERODDE_UTIL_MINMAX_STACK
#define NET_CODERODDE_UTIL_MINMAX_STACK

#include <stdlib.h>

typedef struct minmax_stack_node {
    void* datum;
    struct minmax_stack_node* next_node;
    struct minmax_stack_node* min_node;
    struct minmax_stack_node* max_node;
} minmax_stack_node;

typedef struct {
    size_t size;
    minmax_stack_node* top_node;
    minmax_stack_node* min_node;
    minmax_stack_node* max_node;
    int (*compare)(void*, void*);
} minmax_stack;

void   minmax_stack_init (minmax_stack* stack, int (*compare)(void*, void*));
void   minmax_stack_free (minmax_stack* stack);
void   minmax_stack_push (minmax_stack* stack, void* datum);
size_t minmax_stack_size (minmax_stack* stack);
void*  minmax_stack_pop  (minmax_stack* stack);
void*  minmax_stack_min  (minmax_stack* stack);
void*  minmax_stack_max  (minmax_stack* stack);
void   minmax_stack_print(minmax_stack* stack);

#endif /* NET_CODERODDE_UTIL_MINMAX_STACK */

minmax_stack.c

#include "minmax_stack.h"
#include <stdio.h>
#include <stdlib.h>

void minmax_stack_init(minmax_stack* stack, int (*compare)(void*, void*))
{
    stack->compare = compare;
    stack->size = 0;
    stack->top_node = NULL;
    stack->min_node = NULL;
    stack->max_node = NULL;
}

void minmax_stack_free(minmax_stack* stack)
{
    minmax_stack_node* current_node = stack->top_node;
    minmax_stack_node* next_node;

    while (current_node)
    {
        next_node = current_node->next_node;
        free(current_node);
        current_node = next_node;
    }

    stack->compare  = NULL;
    stack->min_node = NULL;
    stack->max_node = NULL;
    stack->top_node = NULL;
    stack->size     = 0;
}

void minmax_stack_push(minmax_stack* stack, void* datum)
{
    int cmp_min;
    int cmp_max;

    minmax_stack_node* new_node = malloc(sizeof(*new_node));
    new_node->datum = datum;

    if (stack->top_node)
    {
        new_node->next_node = stack->top_node;
        new_node->min_node  = stack->min_node;
        new_node->max_node  = stack->max_node;
        stack->top_node     = new_node;

        cmp_min = stack->compare(datum, stack->min_node->datum);
        cmp_max = stack->compare(datum, stack->max_node->datum);

        if (cmp_min < 0) stack->min_node = new_node;
        if (cmp_max > 0) stack->max_node = new_node;
    }
    else
    {
        stack->top_node = new_node;
        stack->min_node = new_node;
        stack->max_node = new_node;
        new_node->next_node = NULL;
    }

    stack->size++;
}

size_t minmax_stack_size(minmax_stack* stack)
{
    return stack->size;
}


void* minmax_stack_pop(minmax_stack* stack)
{
    minmax_stack_node* node;
    void* return_value;

    if (stack->size == 0) return NULL;

    node = stack->top_node;
    return_value = node->datum;
    stack->max_node = node->max_node;
    stack->min_node = node->min_node;
    stack->top_node = node->next_node;
    stack->size--;
    return return_value;
}

void* minmax_stack_min(minmax_stack* stack)
{
    return stack->size == 0 ? NULL : stack->min_node->datum;
}

void* minmax_stack_max(minmax_stack* stack)
{
    return stack->size == 0 ? NULL : stack->max_node->datum;
}

void minmax_stack_print(minmax_stack* stack)
{
    const char* separator = "";
    printf("[");

    for (minmax_stack_node* current_node = stack->top_node;
         current_node;
         current_node = current_node->next_node)
    {
        printf("%s", separator);
        printf("%d", (int) current_node->datum);
        separator = ", ";
    }

    printf("]");
}

main.c

#include "minmax_stack.h"
#include <stdio.h>
#include <string.h>

static int compare(void* a, void* b)
{
    return (int)((int) a - (int) b);
}

int main() {
    int num;
    minmax_stack stack;
    minmax_stack_init(&stack, compare);
    char command[100];

    while (1)
    {
        scanf("%s", command);

        if (strcmp(command, "push") == 0)
        {
            scanf("%d", &num);
            minmax_stack_push(&stack, (void*) num);
        }
        else if (strcmp(command, "pop") == 0)
        {
            printf("%d\n", (int) minmax_stack_pop(&stack));
        }
        else if (strcmp(command, "min") == 0)
        {
            printf("%d\n", (int) minmax_stack_min(&stack));
        }
        else if (strcmp(command, "max") == 0)
        {
            printf("%d\n", (int) minmax_stack_max(&stack));
        }
        else if (strcmp(command, "print") == 0)
        {
            minmax_stack_print(&stack);
            puts("");
        } else if (strcmp(command, "quit") == 0)
        {
            return 0;
        }
    }
}

Any critique is much appreciated.

@RolandIllig Why would you want to do something as stupid as that? — coderodde
– coderodde, Commented Sep 7, 2017 at 19:43
Just to crash your program. You know, I'm evil and I'm only waiting for you to write a web server or a setuid executable. — Roland Illig
– Roland Illig, Commented Sep 7, 2017 at 19:51

chux · Accepted Answer · 2017-09-07 22:57:29Z

Leak

When a node is popped, the node is not free'd.

compare()

Avoid int overflow which is undefined behavior (UB). Use the idiom (a>b)-(a<b). It is recognized by a number of compilers to make lean code and does not overflow.

static int compare(void* a, void* b) {
    // return (int)((int) a - (int) b);
    return ((int) a > (int) b) - ((int) a < (int) b);
}

Note that qsort() expects int (*compar)(const void *, const void *) and so follow that const signature. Adjust minmax_stack and functions accordingly.

Casting a void * to int may lose information. If conversion to an integer type is truly needed, consider the optional type intptr_t or better yet uintptr_t.

the property that any valid pointer to void can be converted to this type, then converted back to pointer to void, and the result will compare equal to the original pointer C11dr §7.20.1.4 1

static int compare(const void* a, const void* b) {
    uintptr_t ua = (uintptr_t) a;
    uintptr_t ub = (uintptr_t) b;
    return (ua > ub) - (ua < ub);
}

Printing datum

Down casting to int can lose information. As a minmax_stack function, better to show all information.

// printf("%d", (int) current_node->datum);
printf("%p", current_node->datum);
// or cast to widest type through `uintptr_t`
printf("%ju", (uintmax_t) (uintptr_t) current_node->datum);

Prevent buffer overrun

Although only test code, limit user input.

char command[100];
...
    // scanf("%s", command);
    scanf("%99s", command);

Tolerate stack == NULL?

Should functions tolerate stack == NULL - IMO yes, but a design decision.

free(void *ptr) is tolerant of free(NULL), suggest the same for minmax_stack_free().

void minmax_stack_free(minmax_stack* stack) {
  if (stack == NULL) return;
  ...

Alloc size

Good use of sizing by the referenced type, rather than the size of the explicit type! Could add allocation success test.

//                                   size of referenced type 
minmax_stack_node* new_node = malloc(sizeof(*new_node));
if (new_node == NULL) TBD_Handle_Error();

Minor style implication: sizeof(*new_node) --> sizeof *new_node.

Variable declaration

A style issue, yet I find declaring variables when there are needed better as well as bracketed if()

// minmax_stack_node* node;
// void* return_value;
// if (stack->size == 0) return NULL;

if (stack->size == 0) { 
  return NULL;
}
minmax_stack_node* node = stack->top_node;
void* return_value = node->datum;

Use of NULL as datum

Code uses return value of NULL to indicate an error, yet a datum == NULL is not necessarily wrong in a general sense and so with a return value of NULL, it is ambiguous if that is an error or datum? To support datum == NULL, the architecture of this code may need significant re-write. Is this important? - Depends on coding goals. For a general purpose function set, I say yes.

So maybe i'm missing something c - related (i'm coming from c++) but it looks like the compare here and the compare of the OP compares the incoming pointers and not the contents of the address pointed to. Should it not be return (*ua > *ub) - (*ua < *ub); ? — Harald Scheirich
– Harald Scheirich, Commented Sep 8, 2017 at 1:30
@HaraldScheirich Certainly OP's compare()function is only a sample function used to exercise the minmax_stack.c code. It could be quite different depending on the nature of the pushed/popped void*. What is important here is its signature which I suggest to be int compare(const void* a, const void* b), thus like compare functions for qsort(). — chux
– chux, Commented Sep 8, 2017 at 3:14
I hadn't seen the (a>b)-(a<b) idiom before - thanks for recommending that! — Toby Speight
– Toby Speight, Commented Sep 8, 2017 at 7:37

Stack Exchange Network

A C stack with minimum and maximum values

1 Answer 1

You must log in to answer this question.

Hot Network Questions

A C stack with minimum and maximum values

1 Answer 1

You must log in to answer this question.

Related

Hot Network Questions