1/*
2* Copyright (c) 2010 Erin Catto http://www.box2d.org
3*
4* This software is provided 'as-is', without any express or implied
5* warranty. In no event will the authors be held liable for any damages
6* arising from the use of this software.
7* Permission is granted to anyone to use this software for any purpose,
8* including commercial applications, and to alter it and redistribute it
9* freely, subject to the following restrictions:
10* 1. The origin of this software must not be misrepresented; you must not
11* claim that you wrote the original software. If you use this software
12* in a product, an acknowledgment in the product documentation would be
13* appreciated but is not required.
14* 2. Altered source versions must be plainly marked as such, and must not be
15* misrepresented as being the original software.
16* 3. This notice may not be removed or altered from any source distribution.
17*/
18
19#ifndef B2_GROWABLE_STACK_H
20#define B2_GROWABLE_STACK_H
21#include <Box2D/Common/b2Settings.h>
22#include <string.h>
23
24/// This is a growable LIFO stack with an initial capacity of N.
25/// If the stack size exceeds the initial capacity, the heap is used
26/// to increase the size of the stack.
27template <typename T, int32 N>
28class b2GrowableStack
29{
30public:
31 b2GrowableStack()
32 {
33 m_stack = m_array;
34 m_count = 0;
35 m_capacity = N;
36 }
37
38 ~b2GrowableStack()
39 {
40 if (m_stack != m_array)
41 {
42 b2Free(m_stack);
43 m_stack = NULL;
44 }
45 }
46
47 void Push(const T& element)
48 {
49 if (m_count == m_capacity)
50 {
51 T* old = m_stack;
52 m_capacity *= 2;
53 m_stack = (T*)b2Alloc(m_capacity * sizeof(T));
54 memcpy(m_stack, old, m_count * sizeof(T));
55 if (old != m_array)
56 {
57 b2Free(old);
58 }
59 }
60
61 m_stack[m_count] = element;
62 ++m_count;
63 }
64
65 T Pop()
66 {
67 b2Assert(m_count > 0);
68 --m_count;
69 return m_stack[m_count];
70 }
71
72 int32 GetCount()
73 {
74 return m_count;
75 }
76
77private:
78 T* m_stack;
79 T m_array[N];
80 int32 m_count;
81 int32 m_capacity;
82};
83
84
85#endif
86