1 ///////////////////////////////////////////////////////////////////////////////
2 // Copyright (c) 2000-2014 Ericsson Telecom AB
3 // All rights reserved. This program and the accompanying materials
4 // are made available under the terms of the Eclipse Public License v1.0
5 // which accompanies this distribution, and is available at
6 // http://www.eclipse.org/legal/epl-v10.html
7 ///////////////////////////////////////////////////////////////////////////////
8 #ifndef _Common_stack_HH
9 #define _Common_stack_HH
12 #include "../common/memory.h"
15 * LIFO container optimized to store elements sequentially,
16 * and access only the element on the top of the stack.
17 * Accessing the top of the stack has amortized constant time cost.
19 * The container stores pointers to objects of type T; it doesn't own them.
20 * It is the responsibility of the caller to create and destroy the objects
21 * and supply the pointers to the container.
30 size_t num_s; ///< used size
31 size_t max_s; ///< allocated size
32 T **s_ptr; ///< array of pointers to objects of type T
34 static const size_t initial_size = 1, increment_factor = 2;
36 /** Copy constructor: DO NOT IMPLEMENT! */
38 /** Copy assignment: DO NOT IMPLEMENT! */
39 stack& operator=(const stack&);
43 static const size_t max_stack_length = -1;
45 /** Creates an empty stack. */
46 stack() : num_s(0), max_s(0), s_ptr(NULL) { }
48 /** Deallocates its memory. If the container is not empty,
49 * FATAL_ERROR occurs, so before destructing, clear()
50 * must be invoked explicitly.
53 if(num_s > 0) FATAL_ERROR("stack::~stack(): stack is not empty");
57 /** Returns the number of elements in the container. */
58 size_t size() const { return num_s; }
60 /** Returns true if the container has no elements. */
61 bool empty() const { return num_s == 0; }
63 /** Forgets all elements in the container.
64 * No memory is freed. */
65 void clear() { num_s = 0; }
67 /** Push the elem onto the stack. */
72 s_ptr = static_cast<T**>(Malloc(initial_size * sizeof(*s_ptr)));
74 if(max_s >= max_stack_length / increment_factor)
75 FATAL_ERROR("stack::push(): stack index overflow");
76 max_s *= increment_factor;
77 s_ptr = static_cast<T**>(Realloc(s_ptr, max_s * sizeof(*s_ptr)));
80 s_ptr[num_s++] = elem;
83 /** Returns the top of the stack or FATAL_ERROR if empty. */
85 if(num_s == 0) FATAL_ERROR("stack::top() const: stack is empty");
86 return s_ptr[num_s - 1];
89 /** Returns the top of the stack, and removes it from the
90 * container. If the stack is empty then FATAL_ERROR occurs. */
92 if(num_s == 0) FATAL_ERROR("stack::pop(): stack is empty");
93 return s_ptr[--num_s];
98 #endif // _Common_stack_HH