slice.hpp

// ***************************************************************** -*- C++ -*-
/*
 * Copyright (C) 2004-2021 Exiv2 authors
 * This program is part of the Exiv2 distribution.
 *
 * 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 2
 * 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 Street, 5th Floor, Boston, MA 02110-1301 USA.
 */
 
#ifndef EXIV2_INCLUDE_SLICE_HPP
#define EXIV2_INCLUDE_SLICE_HPP
 
#include <cassert>
#include <cstddef>
#include <iterator>
#include <stdexcept>
 
namespace Exiv2
{
    namespace Internal
    {
        // TODO: remove these custom implementations once we have C++11
        template <class T>
        struct remove_const
        {
            typedef T type;
        };
 
        template <class T>
        struct remove_const<const T>
        {
            typedef T type;
        };
 
        template <class T>
        struct remove_volatile
        {
            typedef T type;
        };
        template <class T>
        struct remove_volatile<volatile T>
        {
            typedef T type;
        };
        template <class T>
        struct remove_cv
        {
            typedef typename remove_const<typename remove_volatile<T>::type>::type type;
        };
 
        template <class T>
        struct remove_pointer
        {
            typedef T type;
        };
 
        template <class T>
        struct remove_pointer<T*>
        {
            typedef T type;
        };
 
        template <class T>
        struct remove_pointer<T* const>
        {
            typedef T type;
        };
 
        struct SliceBase
        {
            inline SliceBase(size_t begin, size_t end) : begin_(begin), end_(end)
            {
                if (begin >= end) {
                    throw std::out_of_range("Begin must be smaller than end");
                }
            }
 
            inline size_t size() const throw()
            {
                // cannot underflow, as we know that begin < end
                return end_ - begin_;
            }
 
        protected:
            inline void rangeCheck(size_t index) const
            {
                if (index >= size()) {
                    throw std::out_of_range("Index outside of the slice");
                }
            }
 
            const size_t begin_, end_;
        };
 
        template <template <typename data_type> class storage_type, typename data_type>
        struct ConstSliceBase : SliceBase
        {
            typedef typename storage_type<data_type>::iterator iterator;
            typedef typename storage_type<data_type>::const_iterator const_iterator;
            typedef typename storage_type<data_type>::value_type value_type;
 
            ConstSliceBase(data_type& data, size_t begin, size_t end)
                : SliceBase(begin, end), storage_(data, begin, end)
            {
            }
 
            const value_type& at(size_t index) const
            {
                rangeCheck(index);
                // we know: begin_ < end <= size() <= SIZE_T_MAX
                // and: index < end - begin
                // thus: index + begin < end <= SIZE_T_MAX
                // => no overflow is possible
                return storage_.unsafeAt(begin_ + index);
            }
 
            const_iterator cbegin() const throw()
            {
                return storage_.unsafeGetIteratorAt(begin_);
            }
 
            const_iterator cend() const throw()
            {
                return storage_.unsafeGetIteratorAt(end_);
            }
 
            template <typename slice_type>
            slice_type subSlice(size_t begin, size_t end) const
            {
                this->rangeCheck(begin);
                // end == size() is a legal value, since end is the first
                // element beyond the slice
                // end == 0 is not a legal value (subtraction will underflow and
                // throw an exception)
                this->rangeCheck(end - 1);
                // additions are safe, begin and end are smaller than size()
                const size_t new_begin = begin + this->begin_;
                const size_t new_end = this->begin_ + end;
                if (new_end > this->end_) {
                    throw std::out_of_range("Invalid input parameters to slice");
                }
                return slice_type(storage_.data_, new_begin, new_end);
            }
 
        protected:
            storage_type<data_type> storage_;
        };
 
        template <template <typename> class storage_type, typename data_type>
        struct MutableSliceBase : public ConstSliceBase<storage_type, data_type>
        {
            typedef typename ConstSliceBase<storage_type, data_type>::iterator iterator;
            typedef typename ConstSliceBase<storage_type, data_type>::const_iterator const_iterator;
            typedef typename ConstSliceBase<storage_type, data_type>::value_type value_type;
 
            MutableSliceBase(data_type& data, size_t begin, size_t end)
                : ConstSliceBase<storage_type, data_type>(data, begin, end)
            {
            }
 
            value_type& at(size_t index)
            {
                this->rangeCheck(index);
                return this->storage_.unsafeAt(this->begin_ + index);
            }
 
            const value_type& at(size_t index) const
            {
                // TODO: use using base_type::at once we have C++11
                return base_type::at(index);
            }
 
            iterator begin() throw()
            {
                return this->storage_.unsafeGetIteratorAt(this->begin_);
            }
 
            iterator end() throw()
            {
                return this->storage_.unsafeGetIteratorAt(this->end_);
            }
 
        protected:
            ConstSliceBase<storage_type, const data_type> to_const_base() const throw()
            {
                return ConstSliceBase<storage_type, const data_type>(this->storage_.data_, this->begin_, this->end_);
            }
 
            typedef ConstSliceBase<storage_type, data_type> base_type;
 
            template <typename slice_type>
            slice_type subSlice(size_t begin, size_t end)
            {
                this->rangeCheck(begin);
                // end == size() is a legal value, since end is the first
                // element beyond the slice
                // end == 0 is not a legal value (subtraction will underflow and
                // throw an exception)
                this->rangeCheck(end - 1);
 
                // additions are safe, begin & end are smaller than size()
                const size_t new_begin = begin + this->begin_;
                const size_t new_end = this->begin_ + end;
                if (new_end > this->end_) {
                    throw std::out_of_range("Invalid input parameters to slice");
                }
                return slice_type(this->storage_.data_, new_begin, new_end);
            }
        };
 
        template <typename container>
        struct ContainerStorage
        {
            typedef typename container::iterator iterator;
 
            typedef typename container::const_iterator const_iterator;
 
            typedef typename Internal::remove_cv<typename container::value_type>::type value_type;
 
            ContainerStorage(container& data, size_t /* begin*/, size_t end) : data_(data)
            {
                if (end > data.size()) {
                    throw std::out_of_range("Invalid input parameters to slice");
                }
            }
 
            const value_type& unsafeAt(size_t index) const
            {
                return data_.at(index);
            }
 
            value_type& unsafeAt(size_t index)
            {
                return data_.at(index);
            }
 
            iterator unsafeGetIteratorAt(size_t index)
            {
                // we are screwed if the container got changed => try to catch it
                assert(index <= data_.size());
 
                iterator it = data_.begin();
                std::advance(it, index);
                return it;
            }
 
            const_iterator unsafeGetIteratorAt(size_t index) const
            {
                assert(index <= data_.size());
 
                const_iterator it = data_.begin();
                std::advance(it, index);
                return it;
            }
 
            container& data_;
        };
 
        template <typename storage_type>
        struct PtrSliceStorage
        {
            typedef typename remove_cv<typename remove_pointer<storage_type>::type>::type value_type;
            typedef value_type* iterator;
            typedef const value_type* const_iterator;
 
            PtrSliceStorage(storage_type ptr, size_t /*begin*/, size_t /*end*/) : data_(ptr)
            {
                // TODO: change this to nullptr once we use C++11
                if (ptr == NULL) {
                    throw std::invalid_argument("Null pointer passed to slice constructor");
                }
            }
 
            value_type& unsafeAt(size_t index) throw()
            {
                return data_[index];
            }
 
            const value_type& unsafeAt(size_t index) const throw()
            {
                return data_[index];
            }
 
            iterator unsafeGetIteratorAt(size_t index) throw()
            {
                return data_ + index;
            }
 
            const_iterator unsafeGetIteratorAt(size_t index) const throw()
            {
                return data_ + index;
            }
 
            storage_type data_;
        };
 
    }  // namespace Internal
 
    template <typename container>
    struct Slice : public Internal::MutableSliceBase<Internal::ContainerStorage, container>
    {
        typedef typename container::iterator iterator;
 
        typedef typename container::const_iterator const_iterator;
 
        typedef typename Internal::remove_cv<typename container::value_type>::type value_type;
 
        Slice(container& cont, size_t begin, size_t end)
            : Internal::MutableSliceBase<Internal::ContainerStorage, container>(cont, begin, end)
        {
        }
 
        Slice subSlice(size_t begin, size_t end)
        {
            return Internal::MutableSliceBase<Internal::ContainerStorage, container>::template subSlice<Slice>(begin,
                                                                                                               end);
        }
 
        Slice<const container> subSlice(size_t begin, size_t end) const
        {
            return this->to_const_base().template subSlice<Slice<const container> >(begin, end);
        }
    };
 
    template <typename container>
    struct Slice<const container> : public Internal::ConstSliceBase<Internal::ContainerStorage, const container>
    {
        typedef typename container::iterator iterator;
 
        typedef typename container::const_iterator const_iterator;
 
        typedef typename Internal::remove_cv<typename container::value_type>::type value_type;
 
        Slice(const container& cont, size_t begin, size_t end)
            : Internal::ConstSliceBase<Internal::ContainerStorage, const container>(cont, begin, end)
        {
        }
 
        Slice subSlice(size_t begin, size_t end) const
        {
            return Internal::ConstSliceBase<Internal::ContainerStorage,
                                            const container>::template subSlice<Slice<const container> >(begin, end);
        }
    };
 
    template <typename T>
    struct Slice<const T*> : public Internal::ConstSliceBase<Internal::PtrSliceStorage, const T*>
    {
        Slice(const T* ptr, size_t begin, size_t end)
            : Internal::ConstSliceBase<Internal::PtrSliceStorage, const T*>(ptr, begin, end)
        {
            // TODO: use using in C++11
        }
 
        Slice<const T*> subSlice(size_t begin, size_t end) const
        {
            return Internal::ConstSliceBase<Internal::PtrSliceStorage, const T*>::template subSlice<Slice<const T*> >(
                begin, end);
        }
    };
 
    template <typename T>
    struct Slice<T*> : public Internal::MutableSliceBase<Internal::PtrSliceStorage, T*>
    {
        Slice(T* ptr, size_t begin, size_t end)
            : Internal::MutableSliceBase<Internal::PtrSliceStorage, T*>(ptr, begin, end)
        {
            // TODO: use using in C++11
        }
 
        Slice<T*> subSlice(size_t begin, size_t end)
        {
            return Internal::MutableSliceBase<Internal::PtrSliceStorage, T*>::template subSlice<Slice<T*> >(begin, end);
        }
 
        Slice<const T*> subSlice(size_t begin, size_t end) const
        {
            return this->to_const_base().template subSlice<Slice<const T*> >(begin, end);
        }
    };
 
    template <typename T>
    inline Slice<T> makeSlice(T& cont, size_t begin, size_t end)
    {
        return Slice<T>(cont, begin, end);
    }
 
    template <typename T>
    inline Slice<T*> makeSlice(T* ptr, size_t begin, size_t end)
    {
        return Slice<T*>(ptr, begin, end);
    }
 
    template <typename container>
    inline Slice<container> makeSlice(container& cont)
    {
        return Slice<container>(cont, 0, cont.size());
    }
 
    template <typename container>
    inline Slice<container> makeSliceFrom(container& cont, size_t begin)
    {
        return Slice<container>(cont, begin, cont.size());
    }
 
    template <typename container>
    inline Slice<container> makeSliceUntil(container& cont, size_t end)
    {
        return Slice<container>(cont, 0, end);
    }
 
    template <typename T>
    inline Slice<T*> makeSliceUntil(T* ptr, size_t end)
    {
        return Slice<T*>(ptr, 0, end);
    }
 
}  // namespace Exiv2
 
#endif /* EXIV2_INCLUDE_SLICE_HPP */