|
最近在做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__
复制代码 ============================== 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);
- }
复制代码 注:
1: 最新代码,请参考https://github.com/cedar-renjun/General_Programming_Stack/
2: BinTree在进行中,会分享给大家
|
阿莫论坛20周年了!感谢大家的支持与爱护!!
曾经有一段真挚的爱情摆在我的面前,我没有珍惜,现在想起来,还好我没有珍惜……
|