Sorted Stack (dailyprogrammer)

dlist.h

#pragma once

struct dlist {
    struct dlist *prev, *next;
};

static inline void dlist_insert(struct dlist *list, struct dlist *node)
{
    node->next = list->next;
    node->prev = list;
    if (list->next)
        list->next->prev = node;
    list->next = node;
}

static inline void dlist_remove(struct dlist *node)
{
    if (node->prev)
        node->prev->next = node->next;
    if (node->next)
        node->next->prev = node->prev;
}

main.c

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include "sstack.h"

int intcmp(const void *a, const void *b)
{
    return (intptr_t) a - (intptr_t) b;
}

void intprint(const void *v)
{
    printf("%ld ", (intptr_t) v);
}

int main()
{
    struct sstack ss = {intcmp};
    for (int i = 0; i < 10; i++) {
        intptr_t value = (rand() % 10);
        sstack_push(&ss, (void *) value);
    }
    sstack_visit_stack(&ss, intprint);
    printf("\n");
    sstack_visit_sorted(&ss, intprint);
    printf("\n");

    sstack_remove_gt(&ss, (void *) 5);
    sstack_pop(&ss);
    sstack_pop(&ss);
    sstack_pop(&ss);
    sstack_pop(&ss);
    sstack_visit_stack(&ss, intprint);
    printf("\n");
    sstack_visit_sorted(&ss, intprint);
    printf("\n");

    return 0;
}

Makefile

CFLAGS = -std=c99 -Wall -g3

main : main.o sstack.o

main.o : main.c sstack.h
sstack.o : sstack.c sstack.h dlist.h

run : main
	./$^

clean :
	$(RM) *.o main

sstack.c

#include <stddef.h>
#include <stdlib.h>
#include "sstack.h"
#include "dlist.h"

#define container_of(ptr, type, member) \
    ((type *) ((char *)(ptr) - offsetof(type, member)))

void sstack_push(struct sstack *ss, void *value)
{
    ss->count++;
    struct sstack_node *node = malloc(sizeof(*node));
    node->value = value;
    dlist_insert(&ss->stack, &node->stack);
    struct dlist *prev = &ss->sort, *next = ss->sort.next;
    while (next) {
        struct sstack_node *current;
        current = container_of(next, struct sstack_node, sort);
        if (ss->compare(current->value, value) <= 0)
            break;
        prev = next;
        next = next->next;
    }
    dlist_insert(prev, &node->sort);
}

void *sstack_pop(struct sstack *ss)
{
    ss->count--;
    struct dlist *dnode = ss->stack.next;
    struct sstack_node *node = container_of(dnode, struct sstack_node, stack);
    dlist_remove(&node->stack);
    dlist_remove(&node->sort);
    void *value = node->value;
    free(node);
    return value;
}

void sstack_remove_gt(struct sstack *ss, void *value)
{
    struct dlist *dnode = ss->sort.next;
    while (dnode) {
        struct sstack_node *node;
        node = container_of(dnode, struct sstack_node, sort);
        if (ss->compare(node->value, value) <= 0)
            break;
        dlist_remove(&node->stack);
        dlist_remove(&node->sort);
        dnode = dnode->next;
        free(node);
        ss->count--;
    }
}

void sstack_visit_stack(struct sstack *ss, void (*visit)(const void *value))
{
    struct dlist *dnode = ss->stack.next;
    for (; dnode; dnode = dnode->next) {
        struct sstack_node *node;
        node = container_of(dnode, struct sstack_node, stack);
        visit(node->value);
    }
}

void sstack_visit_sorted(struct sstack *ss, void (*visit)(const void *value))
{
    struct dlist *dnode = ss->sort.next;
    for (; dnode; dnode = dnode->next) {
        struct sstack_node *node;
        node = container_of(dnode, struct sstack_node, sort);
        visit(node->value);
    }
}

sstack.h

#pragma once

#include "dlist.h"

typedef int (*sstack_compare_t)(const void *, const void *);
typedef void (*sstack_visit_t)(const void *value);

struct sstack_node {
    void *value;
    struct dlist stack, sort;
};

struct sstack {
    sstack_compare_t compare;
    size_t count;
    struct dlist stack, sort;
};

void  sstack_push(struct sstack *ss, void *value);
void *sstack_pop(struct sstack *ss);
void  sstack_remove_gt(struct sstack *ss, void *value);
void  sstack_visit_stack(struct sstack *ss, sstack_visit_t visit);
void  sstack_visit_sorted(struct sstack *ss, sstack_visit_t visit);