compiler2/stack.hh

   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
  10
  11 #include "error.h"
  12 #include "../common/memory.h"
  13
  14 /**
  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.
  18  *
  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.
  22  *
  23  * \ingroup containers
  24  */
  25 template<class T>
  26 class stack {
  27
  28 private:
  29
  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
  33
  34   static const size_t initial_size = 1, increment_factor = 2;
  35
  36   /** Copy constructor: DO NOT IMPLEMENT! */
  37   stack(const stack&);
  38   /** Copy assignment: DO NOT IMPLEMENT! */
  39   stack& operator=(const stack&);
  40
  41 public:
  42
  43   static const size_t max_stack_length = -1;
  44
  45   /** Creates an empty stack. */
  46   stack() : num_s(0), max_s(0), s_ptr(NULL) { }
  47
  48   /** Deallocates its memory. If the container is not empty,
  49    * FATAL_ERROR occurs, so before destructing, clear()
  50    * must be invoked explicitly.
  51    */
  52   ~stack() {
  53     if(num_s > 0) FATAL_ERROR("stack::~stack(): stack is not empty");
  54     Free(s_ptr);
  55   }
  56
  57   /** Returns the number of elements in the container. */
  58   size_t size() const { return num_s; }
  59
  60   /** Returns true if the container has no elements. */
  61   bool empty() const { return num_s == 0; }
  62
  63   /** Forgets all elements in the container.
  64    * No memory is freed. */
  65   void clear() { num_s = 0; }
  66
  67   /** Push the elem onto the stack. */
  68   void push(T *elem) {
  69     if (max_s <= num_s) {
  70       if (max_s == 0) {
  71         max_s = initial_size;
  72         s_ptr = static_cast<T**>(Malloc(initial_size * sizeof(*s_ptr)));
  73       } else {
  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)));
  78       }
  79     }
  80     s_ptr[num_s++] = elem;
  81   }
  82
  83   /** Returns the top of the stack or FATAL_ERROR if empty. */
  84   T* top() const {
  85     if(num_s == 0) FATAL_ERROR("stack::top() const: stack is empty");
  86     return s_ptr[num_s - 1];
  87   }
  88
  89   /** Returns the top of the stack, and removes it from the
  90    * container. If the stack is empty then FATAL_ERROR occurs. */
  91   T* pop() {
  92     if(num_s == 0) FATAL_ERROR("stack::pop(): stack is empty");
  93     return s_ptr[--num_s];
  94   }
  95
  96 };
  97
  98 #endif // _Common_stack_HH