SafeStack.h

Go to the documentation of this file.

// SafeStack.h A stack which doesn't drop or free references until explicitly
// asked to do so, so that values outside of the stack are guaranteed good
// in an appropriate scope.
//
//   Copyright (C) 2007, 2008, 2009, 2010, 2011, 2012
//   Free Software Foundation, Inc.
// 
// This program is free software; you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation; either version 3 of the License, or
// (at your option) any later version.
// 
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
// 
// You should have received a copy of the GNU General Public License
// along with this program; if not, write to the Free Software
// Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
#ifndef GNASH_SAFESTACK_H
#define GNASH_SAFESTACK_H


#include <vector>

namespace gnash {

class StackException {};

template <class T>
class SafeStack
{

        typedef std::vector<T*> StackType;

public:

    // May be useful for callers to know.
    typedef typename StackType::size_type StackSize;

    //
        const T& top(StackSize i) const
        {

                if (i >= size()) throw StackException();
                const StackSize offset = _end - i;
                return _data[offset >> _chunkShift][offset & _chunkMod];
        }

    //
        T& top(StackSize i)
        {

                if (i >= size()) throw StackException();
                const StackSize offset = _end - i;
                return _data[offset >> _chunkShift][offset & _chunkMod];
        }
    
    //
        const T& at(StackSize i) const
        {

                if (i >= totalSize()) throw StackException();
                const StackSize offset = _end - i;
                return _data[offset >> _chunkShift][offset & _chunkMod];
        }

        
    //
        T& at(StackSize i)
        {

                if (i >= totalSize()) throw StackException();
                const StackSize offset = _end - i;
                return _data[offset >> _chunkShift][offset & _chunkMod];
        }

        T& value(StackSize i)
        {
                if (i >= size()) throw StackException();

                StackSize offset = _downstop + i + 2;
                return _data[offset >> _chunkShift][offset & _chunkMod];
        }

        const T& value(StackSize i) const
        {
                if (i >= size()) throw StackException();

                StackSize offset = _downstop + i + 2;
                return _data[offset >> _chunkShift][offset & _chunkMod];
        }

        void assign(StackSize i, T val)
        { 
                if (i >= size()) throw StackException();

                StackSize offset = _downstop + i + 2;
                _data[offset >> _chunkShift][offset & _chunkMod] = val;
        }

        void drop(StackSize i) {
        if (i > size()) throw StackException();
        _end -= i;
    }

        void clear() {
        _downstop = 0;
        _end = 1;
    }

        void push(const T& t) {
        grow(1);
        top(0) = t;
    }

        T& pop() {
        T& ret = top(0);
        drop(1);
        return ret;
    }

        void grow(StackSize i)
        {
                StackSize available = (1 << _chunkShift) * _data.size() - _end + 1;
                StackSize n = size()+i;
                while (available < n)
                {
            //log_debug("Increasing size of the real stack: %d.",_data.size());
                        _data.push_back(new T[1 << _chunkShift]);
                        available += 1 << _chunkShift;
                }
                _end += i;
        }

        StackSize getDownstop() const 
        {
        return _downstop;
    }

        StackSize size() const { return _end - _downstop - 1; }

        bool empty() const { return size() == 0; }

        StackSize fixDownstop() 
        {
        StackSize ret = _downstop;
        _downstop = _end - 1;
        return ret;
    }

        void setDownstop(StackSize i)
        {
        if (i > _end) throw StackException();
        _downstop = i;
    }

    //
        StackSize totalSize() const { return _end - 1; }

        void setAllSizes(StackSize total, StackSize downstop)
        {
        _end = total + 1;
        _downstop = downstop;
    }

        SafeStack() : _data(), _downstop(0), _end(1) {}

        ~SafeStack()
        {
                for (auto& elem : _data) delete [] elem;
        }

private:
        StackType _data;
        StackSize _downstop;
        StackSize _end;

        // If _chunkMod is not a power of 2 less 1, it will not work properly.
        static const StackSize _chunkShift = 6;
        static const StackSize _chunkMod = (1 << _chunkShift) - 1;
};

} // namespace gnash
#endif