Stack.hpp

   1 /* Cycript - Optimizing JavaScript Compiler/Runtime
   2  * Copyright (C) 2009-2015  Jay Freeman (saurik)
   3 */
   4
   5 /* GNU Affero General Public License, Version 3 {{{ */
   6 /*
   7  * This program is free software: you can redistribute it and/or modify
   8  * it under the terms of the GNU Affero General Public License as published by
   9  * the Free Software Foundation, either version 3 of the License, or
  10  * (at your option) any later version.
  11
  12  * This program is distributed in the hope that it will be useful,
  13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15  * GNU Affero General Public License for more details.
  16
  17  * You should have received a copy of the GNU Affero General Public License
  18  * along with this program.  If not, see <http://www.gnu.org/licenses/>.
  19 **/
  20 /* }}} */
  21
  22 #ifndef YY_CY_STACK_HH_INCLUDED
  23 #define YY_CY_STACK_HH_INCLUDED
  24
  25 namespace cy {
  26
  27 template <class Type_>
  28 class stack {
  29   public:
  30     typedef std::reverse_iterator<Type_ *> const_iterator;
  31
  32   private:
  33     Type_ *begin_;
  34     Type_ *end_;
  35     Type_ *capacity_;
  36
  37     void destroy() {
  38         for (Type_ *i(begin_); i != end_; ++i)
  39             i->~Type_();
  40     }
  41
  42     void reserve() {
  43         size_t capacity(capacity_ - begin_);
  44         if (capacity == 0)
  45             capacity = 200;
  46         else
  47             capacity *= 2;
  48
  49         Type_ *data(static_cast<Type_ *>(::operator new(sizeof(Type_) * capacity)));
  50
  51         size_t size(end_ - begin_);
  52         for (size_t i(0); i != size; ++i) {
  53             Type_ &old(begin_[i]);
  54             new (data + i) Type_(old);
  55             old.~Type_();
  56         }
  57
  58         ::operator delete(begin_);
  59
  60         begin_ = data;
  61         end_ = data + size;
  62         capacity_ = data + capacity;
  63     }
  64
  65   public:
  66     stack() :
  67         begin_(NULL),
  68         end_(NULL),
  69         capacity_(NULL)
  70     {
  71         reserve();
  72     }
  73
  74     ~stack() {
  75         destroy();
  76         ::operator delete(begin_);
  77     }
  78
  79     _finline Type_ &operator [](size_t i) {
  80         return end_[-1 - i];
  81     }
  82
  83     _finline const Type_ &operator [](size_t i) const {
  84         return end_[-1 - i];
  85     }
  86
  87     _finline void push(Type_ &t) {
  88         if (end_ == capacity_)
  89             reserve();
  90         new (end_++) Type_(t);
  91     }
  92
  93     _finline void pop() {
  94         (--end_)->~Type_();
  95     }
  96
  97     _finline void pop(unsigned int size) {
  98         for (; size != 0; --size)
  99             pop();
 100     }
 101
 102     void clear() {
 103         destroy();
 104         end_ = begin_;
 105     }
 106
 107     _finline size_t size() const {
 108         return end_ - begin_;
 109     }
 110
 111     _finline const_iterator begin() const {
 112         return const_iterator(end_);
 113     }
 114
 115     _finline const_iterator end() const {
 116         return const_iterator(begin_);
 117     }
 118
 119   private:
 120     stack(const stack &);
 121     stack &operator =(const stack &);
 122 };
 123
 124 template <class Type_, class Stack_ = stack<Type_> >
 125 class slice {
 126   public:
 127     slice(const Stack_ &stack, unsigned int range) :
 128         stack_(stack),
 129         range_(range)
 130     {
 131     }
 132
 133     _finline const Type_ &operator [](unsigned int i) const {
 134         return stack_[range_ - i];
 135     }
 136
 137   private:
 138     const Stack_ &stack_;
 139     unsigned int range_;
 140 };
 141
 142 }
 143
 144 #endif/*YY_CY_STACK_HH_INCLUDED*/