slice.hpp

// SPDX-License-Identifier: GPL-2.0-or-later
 
#ifndef EXIV2_INCLUDE_SLICE_HPP
#define EXIV2_INCLUDE_SLICE_HPP
 
#include <cassert>
#include <cstddef>
#include <iterator>
#include <stdexcept>
 
namespace Exiv2 {
namespace Internal {
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");
    }
  }
 
  [[nodiscard]] inline size_t size() const noexcept {
    // 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");
    }
  }
 
  size_t begin_;
  size_t end_;
};
 
template <template <typename data_type> class storage_type, typename data_type>
struct ConstSliceBase : SliceBase {
  using iterator = typename storage_type<data_type>::iterator;
  using const_iterator = typename storage_type<data_type>::const_iterator;
  using value_type = typename storage_type<data_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);
  }
 
  [[nodiscard]] const_iterator cbegin() const noexcept {
    return storage_.unsafeGetIteratorAt(begin_);
  }
 
  [[nodiscard]] const_iterator cend() const noexcept {
    return storage_.unsafeGetIteratorAt(end_);
  }
 
  template <typename slice_type>
  [[nodiscard]] 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> {
  using ConstSliceBase<storage_type, data_type>::ConstSliceBase;
  using iterator = typename ConstSliceBase<storage_type, data_type>::iterator;
  using const_iterator = typename ConstSliceBase<storage_type, data_type>::const_iterator;
  using value_type = typename ConstSliceBase<storage_type, data_type>::value_type;
 
  value_type& at(size_t index) {
    this->rangeCheck(index);
    return this->storage_.unsafeAt(this->begin_ + index);
  }
 
  const value_type& at(size_t index) const {
    return base_type::at(index);
  }
 
  iterator begin() noexcept {
    return this->storage_.unsafeGetIteratorAt(this->begin_);
  }
 
  iterator end() noexcept {
    return this->storage_.unsafeGetIteratorAt(this->end_);
  }
 
 protected:
  [[nodiscard]] ConstSliceBase<storage_type, const data_type> to_const_base() const noexcept {
    return {this->storage_.data_, this->begin_, this->end_};
  }
 
  using base_type = ConstSliceBase<storage_type, data_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 {
  using iterator = typename container::iterator;
  using const_iterator = typename container::const_iterator;
 
#if __cplusplus >= 201402L || (defined(_MSVC_LANG) && (_MSVC_LANG >= 201402L))
  using value_type = std::remove_cv_t<typename container::value_type>;
#else
  using value_type = typename std::remove_cv<typename container::value_type>::type;
#endif
 
  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");
    }
  }
 
  [[nodiscard]] const value_type& unsafeAt(size_t index) const {
    return data_.at(index);
  }
 
  [[nodiscard]] value_type& unsafeAt(size_t index) {
    return data_.at(index);
  }
 
  [[nodiscard]] iterator unsafeGetIteratorAt(size_t index) {
    // we are screwed if the container got changed => try to catch it
    assert(index <= data_.size());
 
    auto it = data_.begin();
    std::advance(it, index);
    return it;
  }
 
  [[nodiscard]] const_iterator unsafeGetIteratorAt(size_t index) const {
    assert(index <= data_.size());
 
    auto it = data_.begin();
    std::advance(it, index);
    return it;
  }
 
  container& data_;
};
 
template <typename storage_type>
struct PtrSliceStorage {
#if __cplusplus >= 201402L || (defined(_MSVC_LANG) && (_MSVC_LANG >= 201402L))
  using value_type = std::remove_cv_t<std::remove_pointer_t<storage_type>>;
#else
  using value_type = typename std::remove_cv<typename std::remove_pointer<storage_type>::type>::type;
#endif
  using iterator = value_type*;
  using const_iterator = const value_type*;
 
  PtrSliceStorage(storage_type ptr, size_t /*begin*/, size_t /*end*/) : data_(ptr) {
    if (!ptr) {
      throw std::invalid_argument("Null pointer passed to slice constructor");
    }
  }
 
  [[nodiscard]] value_type& unsafeAt(size_t index) noexcept {
    return data_[index];
  }
 
  [[nodiscard]] const value_type& unsafeAt(size_t index) const noexcept {
    return data_[index];
  }
 
  [[nodiscard]] iterator unsafeGetIteratorAt(size_t index) noexcept {
    return data_ + index;
  }
 
  [[nodiscard]] const_iterator unsafeGetIteratorAt(size_t index) const noexcept {
    return data_ + index;
  }
 
  storage_type data_;
};
 
}  // namespace Internal
 
template <typename container>
struct Slice : public Internal::MutableSliceBase<Internal::ContainerStorage, container> {
  using Internal::MutableSliceBase<Internal::ContainerStorage, container>::MutableSliceBase;
  using iterator = typename container::iterator;
  using const_iterator = typename container::const_iterator;
 
#if __cplusplus >= 201402L || (defined(_MSVC_LANG) && (_MSVC_LANG >= 201402L))
  using value_type = std::remove_cv_t<typename container::value_type>;
#else
  using value_type = typename std::remove_cv<typename container::value_type>::type;
#endif
 
  Slice subSlice(size_t begin, size_t end) {
    return Internal::MutableSliceBase<Internal::ContainerStorage, container>::template subSlice<Slice>(begin, end);
  }
 
  [[nodiscard]] 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> {
  using Internal::ConstSliceBase<Internal::ContainerStorage, const container>::ConstSliceBase;
  using iterator = typename container::iterator;
  using const_iterator = typename container::const_iterator;
 
#if __cplusplus >= 201402L || (defined(_MSVC_LANG) && (_MSVC_LANG >= 201402L))
  using value_type = std::remove_cv_t<typename container::value_type>;
#else
  using value_type = typename std::remove_cv<typename container::value_type>::type;
#endif
 
  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);
  }
 
  [[nodiscard]] 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 */