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

renjun_EMbest

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

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

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

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

1. //******************************************************************************
   
2. //!
   
3. //! \file   Stack.h
   
4. //! \brief  Genernal Stack Model Interface.
   
5. //!         You can use uniform stack API to manager different type of data
   
6. //!         element.
   
7. //! \author cedar
   
8. //! \date   2013-11-22
   
9. //!
   
10. //! \license
    
11. //!
    
12. //! Copyright (c) 2013 Cedar MIT License
    
13. //!
    
14. //! Permission is hereby granted, free of charge, to any person obtaining a copy
    
15. //! of this software and associated documentation files (the "Software"), to deal
    
16. //! in the Software without restriction, including without limitation the rights to
    
17. //! use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of
    
18. //! the Software, and to permit persons to whom the Software is furnished to do so,
    
19. //! subject to the following conditions:
    
20. //!
    
21. //! The above copyright notice and this permission notice shall be included in all
    
22. //! copies or substantial portions of the Software.
    
23. //!
    
24. //! THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
    
25. //! IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
    
26. //! FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
    
27. //! AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
    
28. //! LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
    
29. //! OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
    
30. //! IN THE SOFTWARE.
    
31. ///
    
32. //******************************************************************************
    
33. 
    
34. #ifndef __STACK_H__
    
35. #define __STACK_H__
    
36. 
    
37. #ifdef __cplusplus
    
38. extern "C"
    
39. {
    
40. #endif
    
41. 
    
42. //******************************************************************************
    
43. //!                           CONFIGURE MACRO
    
44. //******************************************************************************
    
45. 
    
46. #define SYS_INTXX_T                         //!< Use stdint standard datatype
    
47. #define USE_MEMORY_ALLOC                    //!< Use system malloc/free function
    
48. 
    
49. 
    
50. #include <stdio.h>
    
51. 
    
52. #ifdef SYS_INTXX_T
    
53. #include <stdint.h>
    
54. #else
    
55. typedef unsigned char uint8_t;
    
56. typedef unsigned int  uint32_t;
    
57. #endif
    
58. 
    
59. #ifdef USE_MEMORY_ALLOC
    
60. #include <stdlib.h>
    
61. #endif
    
62. 
    
63. 
    
64. //******************************************************************************
    
65. //!                           PUBLIC TYPE
    
66. //******************************************************************************
    
67. 
    
68. //! Stack Memory Model
    
69. typedef struct Stack_t
    
70. {
    
71.     uint8_t* pBaseAddr;                    //!< Stack Base Address
    
72.     uint8_t* pEndAddr;                     //!< Stack Top Address
    
73.     uint8_t* pIndex;                       //!< Stack Data Index Pointer
    
74.     uint32_t UnitSize;                     //!< Statck Element Size(Unit: Byte)
    
75. }Stack_t;
    
76. 
    
77. 
    
78. //******************************************************************************
    
79. //!                           PUBLIC API
    
80. //******************************************************************************
    
81. #ifdef USE_MEMORY_ALLOC
    
82. extern Stack_t* Stack_Create(uint32_t StackSize, uint32_t UnitSize);
    
83. extern void Stack_Destory(Stack_t* pStack);
    
84. #endif // USE_MEMORY_ALLOC
    
85. extern int Stack_Init(Stack_t* pStack, void* pStackBaseAddr, uint32_t StackSize,
    
86.         uint32_t UnitSize);
    
87. extern int Stack_Pop(Stack_t* pStack, void* pElement);
    
88. extern int Stack_Push(Stack_t* pStack, void* pElement);
    
89. 
    
90. #ifdef __cplusplus
    
91. }
    
92. #endif
    
93. 
    
94. #endif // __STACK_H__
    

复制代码

============================== Source Code =======================================

1. #include "Stack.h"
   
2. 
   
3. #ifdef USE_MEMORY_ALLOC
   
4. //******************************************************************************************
   
5. //
   
6. //! \brief  Create An New Stack.
   
7. //!
   
8. //! \param  [in] StackSize is the size of stack.
   
9. //! \param  [in] UnitSize is the size of base element.
   
10. //! \retval The Pointer of new create stack.
    
11. //! \note   -# If StackSize <= UnitSize or memory allocate failure, this function will return
    
12. //!            with NULL pointer, So, Caller must check return pointer carefully.
    
13. //!
    
14. //! \note   -# You must enable USE_MEMORY_ALLOC macro and ensure your system have <stdlib.h>
    
15. //!            Header file before use this function.
    
16. //******************************************************************************************
    
17. Stack_t* Stack_Create(uint32_t StackSize, uint32_t UnitSize)
    
18. {
    
19.     Stack_t*  pStack         = NULL;         //!< Stack Pointer
    
20.     uint8_t*  pStackBaseAddr = NULL;         //!< Stack Memory Base Address
    
21. 
    
22.     //! Check stack parameters.
    
23.     if(StackSize <= UnitSize)
    
24.     {
    
25.         //! Error, exit now.
    
26.         return (NULL);
    
27.     }
    
28. 
    
29.     //! Allocate Memory for pointer of new stack.
    
30.     pStack = (Stack_t*) malloc(sizeof(Stack_t));
    
31.     if(NULL == pStack)
    
32.     {
    
33.         //! Allocate Failure, exit now.
    
34.         return (NULL);
    
35.     }
    
36. 
    
37.     //! Allocate memory for stack.
    
38.     pStackBaseAddr = malloc(StackSize);
    
39.     if(NULL == pStackBaseAddr)
    
40.     {
    
41.         //! Allocate Failure, exit now.
    
42.         return (NULL);
    
43.     }
    
44. 
    
45.     //! Initialize General Stack.
    
46.     Stack_Init(pStack, pStackBaseAddr, StackSize, UnitSize);
    
47. 
    
48.     return (pStack);
    
49. }
    
50. 
    
51. //******************************************************************************************
    
52. //
    
53. //! \brief  Destory Stack
    
54. //!  This function first release memory section, then reinit the stack pointer parameter.
    
55. //!
    
56. //! \param  [in] pStack is the pointer of valid stack.
    
57. //! \retval None.
    
58. //!
    
59. //! \note   -# You must enable USE_MEMORY_ALLOC macro and ensure your system have <stdlib.h>
    
60. //!            Header file before use this function.
    
61. //
    
62. //******************************************************************************************
    
63. void Stack_Destory(Stack_t* pStack)
    
64. {
    
65.     //! Check stack parameters.
    
66.     if(NULL == pStack || NULL == pStack->pBaseAddr)
    
67.     {
    
68.         return; //!< Failure
    
69.     }
    
70. 
    
71.     //! Free stack memory
    
72.     free(pStack->pBaseAddr);
    
73. 
    
74.     //! Reset stack parameters
    
75.     pStack->pBaseAddr = NULL;
    
76.     pStack->pEndAddr  = NULL;
    
77.     pStack->pIndex    = NULL;
    
78.     pStack->UnitSize  = NULL;
    
79. 
    
80.     return;     //!< Success
    
81. }
    
82. #endif // USE_MEMORY_ALLOC
    
83. 
    
84. //******************************************************************************************
    
85. //
    
86. //! \brief  Initialize an exist stack.
    
87. //!
    
88. //! \param  [in] pStack is the pointer of valid stack.
    
89. //! \param  [in] pStackBaseAddr is the base address pre-alloc memory, such as array.
    
90. //! \param  [in] StackSize is the size of stack.
    
91. //! \param  [in] UnitSize is the size of base element.
    
92. //! \retval 0 if initialize successfully, otherwise return -1.
    
93. //!
    
94. //! \note   -# If stack pointer invalid or memory allocate failure, this function will return
    
95. //!            with NULL pointer, So, Caller must check return pointer carefully.
    
96. //!
    
97. //******************************************************************************************
    
98. int Stack_Init(Stack_t* pStack, void* pStackBaseAddr, uint32_t StackSize, uint32_t UnitSize)
    
99. {
    
100.     //! Check stack parameters.
     
101.     if(NULL == pStack || NULL == pStackBaseAddr || StackSize <= UnitSize)
     
102.     {
     
103.         //! Error, exit now.
     
104.         return (-1);
     
105.     }
     
106. 
     
107.     //! Success, Initilize stack
     
108.     pStack->pBaseAddr = (uint8_t*) pStackBaseAddr;
     
109.     pStack->pEndAddr  = (uint8_t*) ((uint32_t)pStackBaseAddr + StackSize);
     
110.     pStack->pIndex    = (uint8_t*) pStackBaseAddr;
     
111.     pStack->UnitSize  = UnitSize;
     
112. 
     
113.     return (0);
     
114. 
     
115. }
     
116. 
     
117. //******************************************************************************************
     
118. //
     
119. //! \brief  Pop an element from stack.
     
120. //!
     
121. //! \param  [in]  pStack is the pointer of valid stack.
     
122. //! \param  [out] pElement is the address of memory that store the pop element.
     
123. //!
     
124. //! \retval 0 if initialize successfully, otherwise return -1.
     
125. //
     
126. //******************************************************************************************
     
127. int Stack_Pop(Stack_t* pStack, void* pElement)
     
128. {
     
129.     uint8_t * _pElement = (uint8_t *)pElement;
     
130.     int i = 0;
     
131. 
     
132.     //! Check stack parameters.
     
133.     if(NULL == pStack || NULL == pElement)
     
134.     {
     
135.         //! Error, exit now.
     
136.         return (-1);
     
137.     }
     
138. 
     
139.     //! UnderFlow ?
     
140.     if(pStack->pIndex < pStack->pBaseAddr + pStack->UnitSize)
     
141.     {
     
142.         //! Error, Stack is empty!
     
143.         return (-1);
     
144.     }
     
145. 
     
146.     //! Move Stack Pointer
     
147.     pStack->pIndex = pStack->pIndex - pStack->UnitSize;
     
148. 
     
149.     //! Copy Data
     
150.     for(i = 0; i < pStack->UnitSize; i++)
     
151.     {
     
152.         *_pElement++ = *(pStack->pIndex + i);
     
153.     }
     
154. 
     
155.     return (0);
     
156. }
     
157. 
     
158. //******************************************************************************************
     
159. //
     
160. //! \brief  Push an element into stack.
     
161. //!
     
162. //! \param  [in] pStack is the pointer of valid stack.
     
163. //! \param  [in] pElement is data element you want to push.
     
164. //!
     
165. //! \retval 0 if initialize successfully, otherwise return -1.
     
166. //
     
167. //******************************************************************************************
     
168. int Stack_Push(Stack_t* pStack, void* pElement)
     
169. {
     
170.     uint8_t * _pElement = (uint8_t *)pElement;
     
171.     int i = 0;
     
172. 
     
173.     //! Check stack parameters.
     
174.     if(NULL == pStack || NULL == pElement)
     
175.     {
     
176.         //! Error, exit now.
     
177.         return (-1);
     
178.     }
     
179. 
     
180.     //! Overflow ?
     
181.     if(pStack->pIndex + pStack->UnitSize > pStack->pEndAddr)
     
182.     {
     
183.         return (-1);
     
184.     }
     
185. 
     
186.     //! Copy Data
     
187.     for(i = 0; i < pStack->UnitSize; i++)
     
188.     {
     
189.          *(pStack->pIndex++) = *_pElement++;
     
190.     }
     
191. 
     
192.     return (0);
     
193. }
     
194. 
     

复制代码

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

kinsno

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