论坛首页 › CortexM3 › C语言通用模式编程--栈的实现

renjun_EMbest 发表于 2013-11-22 21:24:11

C语言通用模式编程--栈的实现

最近在做XML解析器，中间需要用到二叉树，堆栈，所以写了一些通用算法

堆栈：支持任意数据类型的进栈和出栈（完成）
树：支持存储任意数据，支持任意节点的插入和删除操作（暂未完成）

先把通用栈代码给大家看看，欢迎使用，欢迎提意见
在不提供说明和例子，仅看头文件的话，我想大家用起来这个Stack，应该是没问题的^_^

============================== Header File =======================================//******************************************************************************
//!
//! \file   Stack.h
//! \briefGenernal Stack Model Interface.
//!         You can use uniform stack API to manager different type of data
//!         element.
//! \author cedar
//! \date   2013-11-22
//!
//! \license
//!
//! Copyright (c) 2013 Cedar MIT License
//!
//! Permission is hereby granted, free of charge, to any person obtaining a copy
//! of this software and associated documentation files (the "Software"), to deal
//! in the Software without restriction, including without limitation the rights to
//! use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of
//! the Software, and to permit persons to whom the Software is furnished to do so,
//! subject to the following conditions:
//!
//! The above copyright notice and this permission notice shall be included in all
//! copies or substantial portions of the Software.
//!
//! THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
//! IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
//! FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
//! AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
//! LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
//! OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
//! IN THE SOFTWARE.
///
//******************************************************************************

#ifndef __STACK_H__
#define __STACK_H__

#ifdef __cplusplus
extern "C"
{
#endif

//******************************************************************************
//!                           CONFIGURE MACRO
//******************************************************************************

#define SYS_INTXX_T                         //!< Use stdint standard datatype
#define USE_MEMORY_ALLOC                  //!< Use system malloc/free function


#include <stdio.h>

#ifdef SYS_INTXX_T
#include <stdint.h>
#else
typedef unsigned char uint8_t;
typedef unsigned intuint32_t;
#endif

#ifdef USE_MEMORY_ALLOC
#include <stdlib.h>
#endif


//******************************************************************************
//!                           PUBLIC TYPE
//******************************************************************************

//! Stack Memory Model
typedef struct Stack_t
{
    uint8_t* pBaseAddr;                  //!< Stack Base Address
    uint8_t* pEndAddr;                     //!< Stack Top Address
    uint8_t* pIndex;                     //!< Stack Data Index Pointer
    uint32_t UnitSize;                     //!< Statck Element Size(Unit: Byte)
}Stack_t;


//******************************************************************************
//!                           PUBLIC API
//******************************************************************************
#ifdef USE_MEMORY_ALLOC
extern Stack_t* Stack_Create(uint32_t StackSize, uint32_t UnitSize);
extern void Stack_Destory(Stack_t* pStack);
#endif // USE_MEMORY_ALLOC
extern int Stack_Init(Stack_t* pStack, void* pStackBaseAddr, uint32_t StackSize,
      uint32_t UnitSize);
extern int Stack_Pop(Stack_t* pStack, void* pElement);
extern int Stack_Push(Stack_t* pStack, void* pElement);

#ifdef __cplusplus
}
#endif

#endif // __STACK_H__
============================== Source Code =======================================#include "Stack.h"

#ifdef USE_MEMORY_ALLOC
//******************************************************************************************
//
//! \briefCreate An New Stack.
//!
//! \param StackSize is the size of stack.
//! \param UnitSize is the size of base element.
//! \retval The Pointer of new create stack.
//! \note   -# If StackSize <= UnitSize or memory allocate failure, this function will return
//!            with NULL pointer, So, Caller must check return pointer carefully.
//!
//! \note   -# You must enable USE_MEMORY_ALLOC macro and ensure your system have <stdlib.h>
//!            Header file before use this function.
//******************************************************************************************
Stack_t* Stack_Create(uint32_t StackSize, uint32_t UnitSize)
{
    Stack_t*pStack         = NULL;         //!< Stack Pointer
    uint8_t*pStackBaseAddr = NULL;         //!< Stack Memory Base Address

    //! Check stack parameters.
    if(StackSize <= UnitSize)
    {
      //! Error, exit now.
      return (NULL);
    }

    //! Allocate Memory for pointer of new stack.
    pStack = (Stack_t*) malloc(sizeof(Stack_t));
    if(NULL == pStack)
    {
      //! Allocate Failure, exit now.
      return (NULL);
    }

    //! Allocate memory for stack.
    pStackBaseAddr = malloc(StackSize);
    if(NULL == pStackBaseAddr)
    {
      //! Allocate Failure, exit now.
      return (NULL);
    }

    //! Initialize General Stack.
    Stack_Init(pStack, pStackBaseAddr, StackSize, UnitSize);

    return (pStack);
}

//******************************************************************************************
//
//! \briefDestory Stack
//!This function first release memory section, then reinit the stack pointer parameter.
//!
//! \param pStack is the pointer of valid stack.
//! \retval None.
//!
//! \note   -# You must enable USE_MEMORY_ALLOC macro and ensure your system have <stdlib.h>
//!            Header file before use this function.
//
//******************************************************************************************
void Stack_Destory(Stack_t* pStack)
{
    //! Check stack parameters.
    if(NULL == pStack || NULL == pStack->pBaseAddr)
    {
      return; //!< Failure
    }

    //! Free stack memory
    free(pStack->pBaseAddr);

    //! Reset stack parameters
    pStack->pBaseAddr = NULL;
    pStack->pEndAddr= NULL;
    pStack->pIndex    = NULL;
    pStack->UnitSize= NULL;

    return;   //!< Success
}
#endif // USE_MEMORY_ALLOC

//******************************************************************************************
//
//! \briefInitialize an exist stack.
//!
//! \param pStack is the pointer of valid stack.
//! \param pStackBaseAddr is the base address pre-alloc memory, such as array.
//! \param StackSize is the size of stack.
//! \param UnitSize is the size of base element.
//! \retval 0 if initialize successfully, otherwise return -1.
//!
//! \note   -# If stack pointer invalid or memory allocate failure, this function will return
//!            with NULL pointer, So, Caller must check return pointer carefully.
//!
//******************************************************************************************
int Stack_Init(Stack_t* pStack, void* pStackBaseAddr, uint32_t StackSize, uint32_t UnitSize)
{
    //! Check stack parameters.
    if(NULL == pStack || NULL == pStackBaseAddr || StackSize <= UnitSize)
    {
      //! Error, exit now.
      return (-1);
    }

    //! Success, Initilize stack
    pStack->pBaseAddr = (uint8_t*) pStackBaseAddr;
    pStack->pEndAddr= (uint8_t*) ((uint32_t)pStackBaseAddr + StackSize);
    pStack->pIndex    = (uint8_t*) pStackBaseAddr;
    pStack->UnitSize= UnitSize;

    return (0);

}

//******************************************************************************************
//
//! \briefPop an element from stack.
//!
//! \parampStack is the pointer of valid stack.
//! \param pElement is the address of memory that store the pop element.
//!
//! \retval 0 if initialize successfully, otherwise return -1.
//
//******************************************************************************************
int Stack_Pop(Stack_t* pStack, void* pElement)
{
    uint8_t * _pElement = (uint8_t *)pElement;
    int i = 0;

    //! Check stack parameters.
    if(NULL == pStack || NULL == pElement)
    {
      //! Error, exit now.
      return (-1);
    }

    //! UnderFlow ?
    if(pStack->pIndex < pStack->pBaseAddr + pStack->UnitSize)
    {
      //! Error, Stack is empty!
      return (-1);
    }

    //! Move Stack Pointer
    pStack->pIndex = pStack->pIndex - pStack->UnitSize;

    //! Copy Data
    for(i = 0; i < pStack->UnitSize; i++)
    {
      *_pElement++ = *(pStack->pIndex + i);
    }

    return (0);
}

//******************************************************************************************
//
//! \briefPush an element into stack.
//!
//! \param pStack is the pointer of valid stack.
//! \param pElement is data element you want to push.
//!
//! \retval 0 if initialize successfully, otherwise return -1.
//
//******************************************************************************************
int Stack_Push(Stack_t* pStack, void* pElement)
{
    uint8_t * _pElement = (uint8_t *)pElement;
    int i = 0;

    //! Check stack parameters.
    if(NULL == pStack || NULL == pElement)
    {
      //! Error, exit now.
      return (-1);
    }

    //! Overflow ?
    if(pStack->pIndex + pStack->UnitSize > pStack->pEndAddr)
    {
      return (-1);
    }

    //! Copy Data
    for(i = 0; i < pStack->UnitSize; i++)
    {
         *(pStack->pIndex++) = *_pElement++;
    }

    return (0);
}

注：
1： 最新代码，请参考https://github.com/cedar-renjun/General_Programming_Stack/
2： BinTree在进行中，会分享给大家

kinsno 发表于 2013-11-22 21:32:51

话说你的XML语言做脚语言吗？然后下面你自己再做个XML解析器，这样配多能配置一些参数啥的；如果做过程控制，效率很低吧。

查看完整版本: C语言通用模式编程--栈的实现