00001 // SafeStack.h A stack which doesn't drop or free references until explicitly 00002 // asked to do so, so that values outside of the stack are guaranteed good 00003 // in an appropriate scope. 00004 // 00005 // Copyright (C) 2007, 2008, 2009, 2010 Free Software Foundation, Inc. 00006 // 00007 // This program is free software; you can redistribute it and/or modify 00008 // it under the terms of the GNU General Public License as published by 00009 // the Free Software Foundation; either version 3 of the License, or 00010 // (at your option) any later version. 00011 // 00012 // This program is distributed in the hope that it will be useful, 00013 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00014 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00015 // GNU General Public License for more details. 00016 // 00017 // You should have received a copy of the GNU General Public License 00018 // along with this program; if not, write to the Free Software 00019 // Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA 00020 #ifndef GNASH_SAFESTACK_H 00021 #define GNASH_SAFESTACK_H 00022 00023 00024 #include <vector> 00025 00026 namespace gnash { 00027 00028 class StackException {}; 00029 00039 template <class T> 00040 class SafeStack 00041 { 00042 00043 typedef std::vector<T*> StackType; 00044 00045 public: 00046 00047 // May be useful for callers to know. 00048 typedef typename StackType::size_type StackSize; 00049 00051 // 00053 const T& top(StackSize i) const 00054 { 00055 00056 if (i >= size()) throw StackException(); 00057 const StackSize offset = _end - i; 00058 return _data[offset >> _chunkShift][offset & _chunkMod]; 00059 } 00060 00062 // 00065 T& top(StackSize i) 00066 { 00067 00068 if (i >= size()) throw StackException(); 00069 const StackSize offset = _end - i; 00070 return _data[offset >> _chunkShift][offset & _chunkMod]; 00071 } 00072 00074 // 00076 const T& at(StackSize i) const 00077 { 00078 00079 if (i >= totalSize()) throw StackException(); 00080 const StackSize offset = _end - i; 00081 return _data[offset >> _chunkShift][offset & _chunkMod]; 00082 } 00083 00084 00086 // 00089 T& at(StackSize i) 00090 { 00091 00092 if (i >= totalSize()) throw StackException(); 00093 const StackSize offset = _end - i; 00094 return _data[offset >> _chunkShift][offset & _chunkMod]; 00095 } 00096 00099 T& value(StackSize i) 00100 { 00101 if (i >= size()) throw StackException(); 00102 00103 StackSize offset = _downstop + i + 2; 00104 return _data[offset >> _chunkShift][offset & _chunkMod]; 00105 } 00106 00107 const T& value(StackSize i) const 00108 { 00109 if (i >= size()) throw StackException(); 00110 00111 StackSize offset = _downstop + i + 2; 00112 return _data[offset >> _chunkShift][offset & _chunkMod]; 00113 } 00114 00116 void assign(StackSize i, T val) 00117 { 00118 if (i >= size()) throw StackException(); 00119 00120 StackSize offset = _downstop + i + 2; 00121 _data[offset >> _chunkShift][offset & _chunkMod] = val; 00122 } 00123 00127 void drop(StackSize i) 00128 { 00129 if (i > size()) throw StackException(); 00130 _end -= i; 00131 } 00132 00134 void clear() 00135 { 00136 _downstop = 0; 00137 _end = 1; 00138 } 00139 00142 void push(const T t) 00143 { 00144 grow(1); 00145 top(0) = t; 00146 } 00147 00149 T& pop() 00150 { 00151 T& ret = top(0); 00152 drop(1); 00153 return ret; 00154 } 00155 00158 void grow(StackSize i) 00159 { 00160 StackSize available = (1 << _chunkShift) * _data.size() - _end + 1; 00161 StackSize n = size()+i; 00162 while (available < n) 00163 { 00164 //log_debug("Increasing size of the real stack: %d.",_data.size()); 00165 _data.push_back(new T[1 << _chunkShift]); 00166 available += 1 << _chunkShift; 00167 } 00168 _end += i; 00169 } 00170 00172 StackSize getDownstop() const 00173 { 00174 return _downstop; 00175 } 00176 00178 StackSize size() const { return _end - _downstop - 1; } 00179 00181 bool empty() const { return size() == 0; } 00182 00186 StackSize fixDownstop() 00187 { 00188 StackSize ret = _downstop; 00189 _downstop = _end - 1; 00190 return ret; 00191 } 00192 00195 void setDownstop(StackSize i) 00196 { 00197 if (i > _end) throw StackException(); 00198 _downstop = i; 00199 } 00200 00202 // 00205 StackSize totalSize() const { return _end - 1; } 00206 00209 void setAllSizes(StackSize total, StackSize downstop) 00210 { 00211 _end = total + 1; 00212 _downstop = downstop; 00213 } 00214 00216 SafeStack() : _data(), _downstop(0), _end(1) {} 00217 00219 ~SafeStack() 00220 { 00221 for (StackSize i = 0; i < _data.size(); ++i) delete [] _data[i]; 00222 } 00223 00224 private: 00225 StackType _data; 00226 StackSize _downstop; 00227 StackSize _end; 00228 00229 // If _chunkMod is not a power of 2 less 1, it will not work properly. 00230 static const StackSize _chunkShift = 6; 00231 static const StackSize _chunkMod = (1 << _chunkShift) - 1; 00232 }; 00233 00234 } // namespace gnash 00235 #endif