栈

stack.c

/** @file stack.c
  * @brief 栈.
  * @author [email protected]
  * @date 2010-7-31
  * @version 0.1
  * @note 栈的源代码文件
*/
#include "stack.h"

#include <stdlib.h>
#include <string.h>

 /*
  *@struct
  *@brief 栈的结构体定义
  *@author [email protected]
  *@note 无
  */
struct stack_t {
    int top;       /* 指向栈顶元素下一个位置*/
    int elem_size; /* 单个元素大小*/
    int capacity;  /* 容量大小，以元素为单位*/
    void *data;    /* 存放数据的内存块*/
};


int stack_init(stack_t **s, int elem_size)
{
    if(s == NULL) return ERR_NULL_POINTER;
    (*s) = (stack_t*)malloc(sizeof(stack_t));
    if((*s) == NULL) return ERR_MALLOC_FAILED;

    (*s)->top = 0;
    (*s)->elem_size = elem_size;
    (*s)->capacity = 4;
    (*s)->data = malloc((*s)->capacity * (*s)->elem_size);
    return SUCCESS;
}

int stack_uninit(stack_t **s)
{
    if((s !=NULL) && (*s != NULL)) {
        free((*s)->data);

        free((*s));
        (*s) = NULL;
    }
    return 0;
}

void stack_clear(stack_t *s)
{
    if(s != NULL) s->top = 0;
}

bool stack_is_empty(const stack_t *s) {
    if(s != NULL) {
        return s->top == 0;
    } else {
        return false;
    }
}

bool stack_is_full(const stack_t *s)
{
    if(s != NULL) {
        return s->top == s->capacity;
    } else {
        return false;
    }
}

int stack_push(stack_t *s, const void* x)
{
    if(stack_is_full(s)) {
        void* const tmp = realloc(s->data, 
            s->capacity * 2 * s->elem_size);
        if(tmp == NULL) return ERR_MALLOC_FAILED;
        s->capacity *= 2;
        s->data = tmp;
    }
    /* s->data[(s->top)++] = x; */
    memcpy((char*)s->data + s->top * s->elem_size, 
        x, s->elem_size);
    s->top++;
    return SUCCESS;
}

int stack_pop(stack_t *s, void* x)
{
    if(!stack_is_empty(s)) {
        /* *x = s->data[--(s->top)]; */
        s->top--;
        memcpy(x, (char*)s->data + s->top * s->elem_size, 
            s->elem_size);
        return SUCCESS;
    } else {
        return ERR_OTHER;
    }
}

stack.h

/** @file stack.h
  * @brief 栈.
  * @author [email protected]
  * @date 2010-7-31
  * @version 0.1
  * @note 栈的头文件.
  */
#ifndef _STACK_H_
#define _STACK_H_

#ifdef __cplusplus
extern "C"
{
#endif


#include "config.h"

/** 栈的不透明结构体. */
typedef struct stack_t stack_t;

/** 
  * @brief 初始化栈.
  * @param[inout] s 栈对象的二级指针
  * @param[in] elem_size 单个元素的大小
  * @return 成功返回0，失败返回错误码
  * @note 本函数会分配内存，创建一个stack_t对象，将其地址
  * 存放在s所指向的指针中
  * @remarks 无
  */
extern int stack_init(stack_t **s, int elem_size);

/** 
  * @brief 释放栈的内存空间.
  * @param[inout] s 栈对象的二级指针
  * @return 成功返回0，失败返回错误码
  * @note 释放掉栈的数据所占用的内存块，并释放栈对象本身
  * 所的内存
  * @remarks 无
  */
extern int stack_uninit(stack_t **s);

/** 
  * @brief 清空元素，但不释放内存.
  * @param[in] s 指向栈对象的指针
  * @return 无
  * @note 无
  * @remarks 无
  */
extern void stack_clear(stack_t *s);

/** 
  * @brief 判断栈是否为空.
  * @param[in] s 指向栈对象的指针
  * @return 是空，返回TRUE，否则返回FALSE
  * @note 无
  * @remarks 无
  */
extern bool stack_is_empty(const stack_t *s);

/** 
  * @brief 判断栈是否已满.
  * @param[in] s 指向栈对象的指针
  * @return 满，返回TRUE，否则返回FALSE
  * @note 无
  * @remarks 无
  */
extern bool stack_is_full(const stack_t *s);

/** 
  * @brief 进栈.
  * @param[in] s 指向栈对象的指针
  * @param[in] x 要进栈的元素
  * @return 成功返回0，失败返回错误码
  * @note 无
  * @remarks 无
  */
extern int stack_push(stack_t *s, const void* x);

/** 
  * @brief 退栈.
  * @param[in] s 指向栈对象的指针
  * @param[out] x 存放退出栈的元素
  * @return 成功返回0，失败返回错误码
  * @note 无
  * @remarks 无
  */
extern int stack_pop(stack_t *s, void* x);


#ifdef __cplusplus
}
#endif

#endif /* end of _STACK_H_ */