Gnash  0.8.10
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, 2012
00006 //   Free Software Foundation, Inc.
00007 // 
00008 // This program is free software; you can redistribute it and/or modify
00009 // it under the terms of the GNU General Public License as published by
00010 // the Free Software Foundation; either version 3 of the License, or
00011 // (at your option) any later version.
00012 // 
00013 // This program is distributed in the hope that it will be useful,
00014 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00015 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00016 // GNU General Public License for more details.
00017 // 
00018 // You should have received a copy of the GNU General Public License
00019 // along with this program; if not, write to the Free Software
00020 // Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
00021 #ifndef GNASH_SAFESTACK_H
00022 #define GNASH_SAFESTACK_H
00023 
00024 
00025 #include <vector>
00026 
00027 namespace gnash {
00028 
00029 class StackException {};
00030 
00040 template <class T>
00041 class SafeStack
00042 {
00043 
00044         typedef std::vector<T*> StackType;
00045 
00046 public:
00047 
00048     // May be useful for callers to know.
00049     typedef typename StackType::size_type StackSize;
00050 
00052     //
00054         const T& top(StackSize i) const
00055         {
00056 
00057                 if (i >= size()) throw StackException();
00058                 const StackSize offset = _end - i;
00059                 return _data[offset >> _chunkShift][offset & _chunkMod];
00060         }
00061 
00063     //
00066         T& top(StackSize i)
00067         {
00068 
00069                 if (i >= size()) throw StackException();
00070                 const StackSize offset = _end - i;
00071                 return _data[offset >> _chunkShift][offset & _chunkMod];
00072         }
00073     
00075     //
00077         const T& at(StackSize i) const
00078         {
00079 
00080                 if (i >= totalSize()) throw StackException();
00081                 const StackSize offset = _end - i;
00082                 return _data[offset >> _chunkShift][offset & _chunkMod];
00083         }
00084 
00085         
00087     //
00090         T& at(StackSize i)
00091         {
00092 
00093                 if (i >= totalSize()) throw StackException();
00094                 const StackSize offset = _end - i;
00095                 return _data[offset >> _chunkShift][offset & _chunkMod];
00096         }
00097 
00100         T& value(StackSize i)
00101         {
00102                 if (i >= size()) throw StackException();
00103 
00104                 StackSize offset = _downstop + i + 2;
00105                 return _data[offset >> _chunkShift][offset & _chunkMod];
00106         }
00107 
00108         const T& value(StackSize i) const
00109         {
00110                 if (i >= size()) throw StackException();
00111 
00112                 StackSize offset = _downstop + i + 2;
00113                 return _data[offset >> _chunkShift][offset & _chunkMod];
00114         }
00115 
00117         void assign(StackSize i, T val)
00118         { 
00119                 if (i >= size()) throw StackException();
00120 
00121                 StackSize offset = _downstop + i + 2;
00122                 _data[offset >> _chunkShift][offset & _chunkMod] = val;
00123         }
00124 
00128         void drop(StackSize i) {
00129         if (i > size()) throw StackException();
00130         _end -= i;
00131     }
00132 
00134         void clear() {
00135         _downstop = 0;
00136         _end = 1;
00137     }
00138 
00141         void push(const T& t) {
00142         grow(1);
00143         top(0) = t;
00144     }
00145 
00147         T& pop() {
00148         T& ret = top(0);
00149         drop(1);
00150         return ret;
00151     }
00152 
00155         void grow(StackSize i)
00156         {
00157                 StackSize available = (1 << _chunkShift) * _data.size() - _end + 1;
00158                 StackSize n = size()+i;
00159                 while (available < n)
00160                 {
00161             //log_debug("Increasing size of the real stack: %d.",_data.size());
00162                         _data.push_back(new T[1 << _chunkShift]);
00163                         available += 1 << _chunkShift;
00164                 }
00165                 _end += i;
00166         }
00167 
00169         StackSize getDownstop() const 
00170         {
00171         return _downstop;
00172     }
00173 
00175         StackSize size() const { return _end - _downstop - 1; }
00176 
00178         bool empty() const { return size() == 0; }
00179 
00183         StackSize fixDownstop() 
00184         {
00185         StackSize ret = _downstop;
00186         _downstop = _end - 1;
00187         return ret;
00188     }
00189 
00192         void setDownstop(StackSize i)
00193         {
00194         if (i > _end) throw StackException();
00195         _downstop = i;
00196     }
00197 
00199     //
00202         StackSize totalSize() const { return _end - 1; }
00203 
00206         void setAllSizes(StackSize total, StackSize downstop)
00207         {
00208         _end = total + 1;
00209         _downstop = downstop;
00210     }
00211 
00213         SafeStack() : _data(), _downstop(0), _end(1) {}
00214 
00216         ~SafeStack()
00217         {
00218                 for (StackSize i = 0; i < _data.size(); ++i) delete [] _data[i];
00219         }
00220 
00221 private:
00222         StackType _data;
00223         StackSize _downstop;
00224         StackSize _end;
00225 
00226         // If _chunkMod is not a power of 2 less 1, it will not work properly.
00227         static const StackSize _chunkShift = 6;
00228         static const StackSize _chunkMod = (1 << _chunkShift) - 1;
00229 };
00230 
00231 } // namespace gnash
00232 #endif