C语言实现可伸缩的栈结构

// stack.h

#ifndef _STACK_H_
#define _STACK_H_

#ifdef __cplusplus
extern "C" {
#endif



// 接口声明
typedef struct stack stack_t;
void stack_push(stack_t **pstk, void *value);
void* stack_pop(stack_t **pstk);
void* stack_top(stack_t **pstk);

// 调用者自行实现销毁栈的函数, 或调用如下函数销毁栈
static inline void
stack_destroy(stack_t **pstk, void (*destroy_element)(void*))
{
    void *value;
    while (!!(value = stack_pop(pstk)))
        if (destroy_element)
            destroy_element(value);
}

#ifdef __cplusplus
} // extern "C"
#endif

#endif // _STACK_H_

// stack.c

#include "stack.h"

// stack结构无需对用户暴露
struct stack {
    int top;
    int cnt;
    struct stack *next;
    void *value[1];
};

static inline int
stack_empty(stack_t *stk)
{
    return (stk->top == -1);
}

static inline int
stack_full(stack_t *stk)
{
    return (stk->top + 1 == stk->cnt);
}

#define DEFAULT_STACK_CNT 128

static inline void
stack_expand(stack_t **pstk)
{
    // 这里假定内存分配不会失败，可以实现这样的函数，例如kmem_alloc(size, KM_SLEEP), 分配不到内存则睡眠等待
    stack_t *stk = malloc(sizeof(stack_t)
        + sizeof(void*) * (DEFAULT_STACK_CNT - 1));
    stk->next = *pstk;
    stk->top = -1;
    stk->cnt = DEFAULT_STACK_CNT;
    
    *pstk = stk;
}

static inline void
stack_reduce(stack_t **pstk)
{
    stack_t *stk = *pstk;
    while (stk && stack_empty(stk)) {
        stack_t *next = stk->next;
        free(stk);
        stk = next;
    }
    *pstk = stk;
}

void
stack_push(stack_t **pstk, void *value)
{
    if (!*pstk || stack_full(*pstk))
        stack_expand(pstk);
    
    stack_t *stk = *pstk;
    stk->value[++stk->top] = value;
}

void*
stack_pop(stack_t **pstk)
{
    if (!*pstk)
        return (NULL);
    
    
    stack_t *stk = *pstk;
    void *value = stk->value[stk->top--];
    stack_reduce(pstk);
    
    return (value);
}

void*
stack_top(stack_t **pstk)
{
    stack_t *stk = *pstk;
    return (stk ? stk->value[stk->top] : NULL);
}