compiler2/stack.hh

   1 /******************************************************************************
   2  * Copyright (c) 2000-2016 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  * Contributors:
   9  *   Balasko, Jeno
  10  *   Forstner, Matyas
  11  *   Gecse, Roland
  12  *   Raduly, Csaba
  13  *   Szabo, Janos Zoltan – initial implementation
  14  *
  15  ******************************************************************************/
  16 #ifndef _Common_stack_HH
  17 #define _Common_stack_HH
  18
  19 #include "error.h"
  20 #include "../common/memory.h"
  21
  22 /**
  23  * LIFO container optimized to store elements sequentially,
  24  * and access only the element on the top of the stack.
  25  * Accessing the top of the stack has amortized constant time cost.
  26  *
  27  * The container stores pointers to objects of type T; it doesn't own them.
  28  * It is the responsibility of the caller to create and destroy the objects
  29  * and supply the pointers to the container.
  30  *
  31  * \ingroup containers
  32  */
  33 template<class T>
  34 class stack {
  35
  36 private:
  37
  38   size_t num_s; ///< used size
  39   size_t max_s; ///< allocated size
  40   T **s_ptr; ///< array of pointers to objects of type T
  41
  42   static const size_t initial_size = 1, increment_factor = 2;
  43
  44   /** Copy constructor: DO NOT IMPLEMENT! */
  45   stack(const stack&);
  46   /** Copy assignment: DO NOT IMPLEMENT! */
  47   stack& operator=(const stack&);
  48
  49 public:
  50
  51   static const size_t max_stack_length = -1;
  52
  53   /** Creates an empty stack. */
  54   stack() : num_s(0), max_s(0), s_ptr(NULL) { }
  55
  56   /** Deallocates its memory. If the container is not empty,
  57    * FATAL_ERROR occurs, so before destructing, clear()
  58    * must be invoked explicitly.
  59    */
  60   ~stack() {
  61     if(num_s > 0) FATAL_ERROR("stack::~stack(): stack is not empty");
  62     Free(s_ptr);
  63   }
  64
  65   /** Returns the number of elements in the container. */
  66   size_t size() const { return num_s; }
  67
  68   /** Returns true if the container has no elements. */
  69   bool empty() const { return num_s == 0; }
  70
  71   /** Forgets all elements in the container.
  72    * No memory is freed. */
  73   void clear() { num_s = 0; }
  74
  75   /** Push the elem onto the stack. */
  76   void push(T *elem) {
  77     if (max_s <= num_s) {
  78       if (max_s == 0) {
  79         max_s = initial_size;
  80         s_ptr = static_cast<T**>(Malloc(initial_size * sizeof(*s_ptr)));
  81       } else {
  82         if(max_s >= max_stack_length / increment_factor)
  83           FATAL_ERROR("stack::push(): stack index overflow");
  84         max_s *= increment_factor;
  85         s_ptr = static_cast<T**>(Realloc(s_ptr, max_s * sizeof(*s_ptr)));
  86       }
  87     }
  88     s_ptr[num_s++] = elem;
  89   }
  90
  91   /** Returns the top of the stack or FATAL_ERROR if empty. */
  92   T* top() const {
  93     if(num_s == 0) FATAL_ERROR("stack::top() const: stack is empty");
  94     return s_ptr[num_s - 1];
  95   }
  96
  97   /** Returns the top of the stack, and removes it from the
  98    * container. If the stack is empty then FATAL_ERROR occurs. */
  99   T* pop() {
 100     if(num_s == 0) FATAL_ERROR("stack::pop(): stack is empty");
 101     return s_ptr[--num_s];
 102   }
 103
 104 };
 105
 106 #endif // _Common_stack_HH