中科因仑“3+1”工程特种兵精英论坛

标题: C语言通用模式编程--栈的实现 [打印本页]

作者: emper 时间: 2016-3-29 17:54
标题: C语言通用模式编程--栈的实现
最近在做XML解析器，中间需要用到二叉树，堆栈，所以写了一些通用算法

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

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

============================== Header File =======================================

//******************************************************************************
//!
//! \file Stack.h
//! \brief Genernal 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 int uint32_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__

[color=rgb(51, 102, 153) !important]复制代码
============================== Source Code =======================================

#include "Stack.h"
#ifdef USE_MEMORY_ALLOC
//******************************************************************************************
//
//! \brief Create An New Stack.
//!
//! \param [in] StackSize is the size of stack.
//! \param [in] 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);
}
//******************************************************************************************
//
//! \brief Destory Stack
//! This function first release memory section, then reinit the stack pointer parameter.
//!
//! \param [in] 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
//******************************************************************************************
//
//! \brief Initialize an exist stack.
//!
//! \param [in] pStack is the pointer of valid stack.
//! \param [in] pStackBaseAddr is the base address pre-alloc memory, such as array.
//! \param [in] StackSize is the size of stack.
//! \param [in] 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);
}
//******************************************************************************************
//
//! \brief Pop an element from stack.
//!
//! \param [in] pStack is the pointer of valid stack.
//! \param [out] 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);
}
//******************************************************************************************
//
//! \brief Push an element into stack.
//!
//! \param [in] pStack is the pointer of valid stack.
//! \param [in] 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);
}

[color=rgb(51, 102, 153) !important]复制代码
注：
1：最新代码，请参考https://github.com/cedar-renjun/General_Programming_Stack/
2： BinTree在进行中，会分享给大家

欢迎光临中科因仑“3+1”工程特种兵精英论坛 (http://bbs.enlern.com/)