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_ *data_;
  34     size_t size_;
  35     size_t capacity_;
  36
  37     void destroy() {
  38         data_ -= size_;
  39         for (size_t i(0); i != size_; ++i)
  40             data_[i].~Type_();
  41     }
  42
  43     void reserve(size_t capacity) {
  44         capacity_ = capacity;
  45         Type_ *data(static_cast<Type_ *>(::operator new(sizeof(Type_) * capacity_)));
  46
  47         data_ -= size_;
  48         for (size_t i(0); i != size_; ++i) {
  49             Type_ &old(data_[i]);
  50             new (data + i) Type_(old);
  51             old.~Type_();
  52         }
  53
  54         ::operator delete(data_);
  55         data_ = data + size_;
  56     }
  57
  58   public:
  59     stack() :
  60         data_(NULL),
  61         size_(0)
  62     {
  63         reserve(200);
  64     }
  65
  66     ~stack() {
  67         destroy();
  68         ::operator delete(data_);
  69     }
  70
  71     _finline Type_ &operator [](size_t i) {
  72         return data_[-1 - i];
  73     }
  74
  75     _finline const Type_ &operator [](size_t i) const {
  76         return data_[-1 - i];
  77     }
  78
  79     _finline void push(Type_ &t) {
  80         if (size_ == capacity_)
  81             reserve(capacity_ * 2);
  82         new (data_++) Type_(t);
  83         ++size_;
  84     }
  85
  86     _finline void pop() {
  87         (--data_)->~Type_();
  88         --size_;
  89     }
  90
  91     _finline void pop(unsigned int size) {
  92         for (; size != 0; --size)
  93             pop();
  94     }
  95
  96     void clear() {
  97         destroy();
  98         size_ = 0;
  99     }
 100
 101     _finline size_t size() const {
 102         return size_;
 103     }
 104
 105     _finline const_iterator begin() const {
 106         return const_iterator(data_);
 107     }
 108
 109     _finline const_iterator end() const {
 110         return const_iterator(data_ - size_);
 111     }
 112
 113   private:
 114     stack(const stack &);
 115     stack &operator =(const stack &);
 116 };
 117
 118 template <class Type_, class Stack_ = stack<Type_> >
 119 class slice {
 120   public:
 121     slice(const Stack_ &stack, unsigned int range) :
 122         stack_(stack),
 123         range_(range)
 124     {
 125     }
 126
 127     _finline const Type_ &operator [](unsigned int i) const {
 128         return stack_[range_ - i];
 129     }
 130
 131   private:
 132     const Stack_ &stack_;
 133     unsigned int range_;
 134 };
 135
 136 }
 137
 138 #endif/*YY_CY_STACK_HH_INCLUDED*/