Gnash 0.8.10dev
SafeStack.h
Go to the documentation of this file.
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, 2011 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         if (i > size()) throw StackException();
00129         _end -= i;
00130     }
00131 
00133         void clear() {
00134         _downstop = 0;
00135         _end = 1;
00136     }
00137 
00140         void push(const T& t) {
00141         grow(1);
00142         top(0) = t;
00143     }
00144 
00146         T& pop() {
00147         T& ret = top(0);
00148         drop(1);
00149         return ret;
00150     }
00151 
00154         void grow(StackSize i)
00155         {
00156                 StackSize available = (1 << _chunkShift) * _data.size() - _end + 1;
00157                 StackSize n = size()+i;
00158                 while (available < n)
00159                 {
00160             //log_debug("Increasing size of the real stack: %d.",_data.size());
00161                         _data.push_back(new T[1 << _chunkShift]);
00162                         available += 1 << _chunkShift;
00163                 }
00164                 _end += i;
00165         }
00166 
00168         StackSize getDownstop() const 
00169         {
00170         return _downstop;
00171     }
00172 
00174         StackSize size() const { return _end - _downstop - 1; }
00175 
00177         bool empty() const { return size() == 0; }
00178 
00182         StackSize fixDownstop() 
00183         {
00184         StackSize ret = _downstop;
00185         _downstop = _end - 1;
00186         return ret;
00187     }
00188 
00191         void setDownstop(StackSize i)
00192         {
00193         if (i > _end) throw StackException();
00194         _downstop = i;
00195     }
00196 
00198     //
00201         StackSize totalSize() const { return _end - 1; }
00202 
00205         void setAllSizes(StackSize total, StackSize downstop)
00206         {
00207         _end = total + 1;
00208         _downstop = downstop;
00209     }
00210 
00212         SafeStack() : _data(), _downstop(0), _end(1) {}
00213 
00215         ~SafeStack()
00216         {
00217                 for (StackSize i = 0; i < _data.size(); ++i) delete [] _data[i];
00218         }
00219 
00220 private:
00221         StackType _data;
00222         StackSize _downstop;
00223         StackSize _end;
00224 
00225         // If _chunkMod is not a power of 2 less 1, it will not work properly.
00226         static const StackSize _chunkShift = 6;
00227         static const StackSize _chunkMod = (1 << _chunkShift) - 1;
00228 };
00229 
00230 } // namespace gnash
00231 #endif