EIC code displayed by LXR master/​include/​boost/​histogram/​unlimited_storage.hpp	Source navigation Diff markup Identifier search General search
	Version: master test Revert   Change

File indexing completed on 2025-12-16 09:53:11

 // Copyright 2015-2019 Hans Dembinski
 // Copyright 2019 Glen Joseph Fernandes (glenjofe@gmail.com)
 //
 // Distributed under the Boost Software License, Version 1.0.
 // (See accompanying file LICENSE_1_0.txt
 // or copy at http://www.boost.org/LICENSE_1_0.txt)
 
 #ifndef BOOST_HISTOGRAM_UNLIMTED_STORAGE_HPP
 #define BOOST_HISTOGRAM_UNLIMTED_STORAGE_HPP
 
 #include <algorithm>
 #include <boost/core/alloc_construct.hpp>
 #include <boost/core/exchange.hpp>
 #include <boost/core/nvp.hpp>
 #include <boost/histogram/detail/array_wrapper.hpp>
 #include <boost/histogram/detail/iterator_adaptor.hpp>
 #include <boost/histogram/detail/large_int.hpp>
 #include <boost/histogram/detail/operators.hpp>
 #include <boost/histogram/detail/safe_comparison.hpp>
 #include <boost/histogram/fwd.hpp>
 #include <boost/mp11/algorithm.hpp>
 #include <boost/mp11/list.hpp>
 #include <boost/mp11/utility.hpp>
 #include <cassert>
 #include <cmath>
 #include <cstdint>
 #include <functional>
 #include <iterator>
 #include <memory>
 #include <type_traits>
 
 namespace boost {
 namespace histogram {
 namespace detail {
 
 template <class T>
 struct is_large_int : std::false_type {};
 
 template <class A>
 struct is_large_int<large_int<A>> : std::true_type {};
 
 template <class T, class ReturnType>
 using if_arithmetic_or_large_int =
     std::enable_if_t<(std::is_arithmetic<T>::value || is_large_int<T>::value),
                      ReturnType>;
 
 template <class L, class T>
 using next_type = mp11::mp_at_c<L, (mp11::mp_find<L, T>::value + 1)>;
 
 template <class Allocator>
 class construct_guard {
 public:
   using pointer = typename std::allocator_traits<Allocator>::pointer;
 
   construct_guard(Allocator& a, pointer p, std::size_t n) noexcept
       : a_(a), p_(p), n_(n) {}
 
   ~construct_guard() {
     if (p_) { a_.deallocate(p_, n_); }
   }
 
   void release() { p_ = pointer(); }
 
   construct_guard(const construct_guard&) = delete;
   construct_guard& operator=(const construct_guard&) = delete;
 
 private:
   Allocator& a_;
   pointer p_;
   std::size_t n_;
 };
 
 template <class Allocator>
 void* buffer_create(Allocator& a, std::size_t n) {
   auto ptr = a.allocate(n); // may throw
   static_assert(std::is_trivially_copyable<decltype(ptr)>::value,
                 "ptr must be trivially copyable");
   construct_guard<Allocator> guard(a, ptr, n);
   boost::alloc_construct_n(a, ptr, n);
   guard.release();
   return static_cast<void*>(ptr);
 }
 
 template <class Allocator, class Iterator>
 auto buffer_create(Allocator& a, std::size_t n, Iterator iter) {
   assert(n > 0u);
   auto ptr = a.allocate(n); // may throw
   static_assert(std::is_trivially_copyable<decltype(ptr)>::value,
                 "ptr must be trivially copyable");
   construct_guard<Allocator> guard(a, ptr, n);
   using T = typename std::allocator_traits<Allocator>::value_type;
   struct casting_iterator {
     void operator++() noexcept { ++iter_; }
     T operator*() noexcept {
       return static_cast<T>(*iter_);
     } // silence conversion warnings
     Iterator iter_;
   };
   boost::alloc_construct_n(a, ptr, n, casting_iterator{iter});
   guard.release();
   return ptr;
 }
 
 template <class Allocator>
 void buffer_destroy(Allocator& a, typename std::allocator_traits<Allocator>::pointer p,
                     std::size_t n) {
   assert(p);
   assert(n > 0u);
   boost::alloc_destroy_n(a, p, n);
   a.deallocate(p, n);
 }
 
 } // namespace detail
 
 /**
   Memory-efficient storage for integral counters which cannot overflow.
 
   This storage provides a no-overflow-guarantee if the counters are incremented with
   integer weights. It maintains a contiguous array of elemental counters, one for each
   cell. If an operation is requested which would overflow a counter, the array is
   replaced with another of a wider integral type, then the operation is executed. The
   storage uses integers of 8, 16, 32, 64 bits, and then switches to a multiprecision
   integral type, similar to those in
   [Boost.Multiprecision](https://www.boost.org/doc/libs/develop/libs/multiprecision/doc/html/index.html).
 
   A scaling operation or adding a floating point number triggers a conversion of the
   elemental counters into doubles, which voids the no-overflow-guarantee.
 */
 template <class Allocator>
 class unlimited_storage {
   static_assert(
       std::is_same<typename std::allocator_traits<Allocator>::pointer,
                    typename std::allocator_traits<Allocator>::value_type*>::value,
       "unlimited_storage requires allocator with trivial pointer type");
   using U8 = std::uint8_t;
   using U16 = std::uint16_t;
   using U32 = std::uint32_t;
   using U64 = std::uint64_t;
 
 public:
   static constexpr bool has_threading_support = false;
 
   using allocator_type = Allocator;
   using value_type = double;
   using large_int = detail::large_int<
       typename std::allocator_traits<allocator_type>::template rebind_alloc<U64>>;
 
   struct buffer_type {
     // cannot be moved outside of scope of unlimited_storage, large_int is dependent type
     using types = mp11::mp_list<U8, U16, U32, U64, large_int, double>;
 
     template <class T>
     static constexpr unsigned type_index() noexcept {
       return static_cast<unsigned>(mp11::mp_find<types, T>::value);
     }
 
     template <class F, class... Ts>
     decltype(auto) visit(F&& f, Ts&&... ts) const {
       // this is intentionally not a switch, the if-chain is faster in benchmarks
       if (type == type_index<U8>())
         return f(static_cast<U8*>(ptr), std::forward<Ts>(ts)...);
       if (type == type_index<U16>())
         return f(static_cast<U16*>(ptr), std::forward<Ts>(ts)...);
       if (type == type_index<U32>())
         return f(static_cast<U32*>(ptr), std::forward<Ts>(ts)...);
       if (type == type_index<U64>())
         return f(static_cast<U64*>(ptr), std::forward<Ts>(ts)...);
       if (type == type_index<large_int>())
         return f(static_cast<large_int*>(ptr), std::forward<Ts>(ts)...);
       return f(static_cast<double*>(ptr), std::forward<Ts>(ts)...);
     }
 
     buffer_type(const allocator_type& a = {}) : alloc(a) {}
 
     buffer_type(buffer_type&& o) noexcept
         : alloc(std::move(o.alloc))
         , size(boost::exchange(o.size, 0))
         , type(boost::exchange(o.type, 0))
         , ptr(boost::exchange(o.ptr, nullptr)) {}
 
     buffer_type& operator=(buffer_type&& o) noexcept {
       using std::swap;
       swap(alloc, o.alloc);
       swap(size, o.size);
       swap(type, o.type);
       swap(ptr, o.ptr);
       return *this;
     }
 
     buffer_type(const buffer_type& x) : alloc(x.alloc) {
       x.visit([this, n = x.size](const auto* xp) {
         using T = std::decay_t<decltype(*xp)>;
         this->template make<T>(n, xp);
       });
     }
 
     buffer_type& operator=(const buffer_type& o) {
       *this = buffer_type(o);
       return *this;
     }
 
     ~buffer_type() noexcept { destroy(); }
 
     void destroy() noexcept {
       assert((ptr == nullptr) == (size == 0));
       if (ptr == nullptr) return;
       visit([this](auto* p) {
         using T = std::decay_t<decltype(*p)>;
         using alloc_type =
             typename std::allocator_traits<allocator_type>::template rebind_alloc<T>;
         alloc_type a(alloc); // rebind allocator
         detail::buffer_destroy(a, p, this->size);
       });
       size = 0;
       type = 0;
       ptr = nullptr;
     }
 
     template <class T>
     void make(std::size_t n) {
       // note: order of commands is to not leave buffer in invalid state upon throw
       destroy();
       if (n > 0) {
         // rebind allocator
         using alloc_type =
             typename std::allocator_traits<allocator_type>::template rebind_alloc<T>;
         alloc_type a(alloc);
         ptr = detail::buffer_create(a, n); // may throw
       }
       size = n;
       type = type_index<T>();
     }
 
     template <class T, class U>
     void make(std::size_t n, U iter) {
       // note: iter may be current ptr, so create new buffer before deleting old buffer
       void* new_ptr = nullptr;
       const auto new_type = type_index<T>();
       if (n > 0) {
         // rebind allocator
         using alloc_type =
             typename std::allocator_traits<allocator_type>::template rebind_alloc<T>;
         alloc_type a(alloc);
         new_ptr = detail::buffer_create(a, n, iter); // may throw
       }
       destroy();
       size = n;
       type = new_type;
       ptr = new_ptr;
     }
 
     allocator_type alloc;
     std::size_t size = 0;
     unsigned type = 0;
     mutable void* ptr = nullptr;
   };
 
   class reference; // forward declare to make friend of const_reference
 
   /// implementation detail
   class const_reference
       : detail::partially_ordered<const_reference, const_reference, void> {
   public:
     const_reference(buffer_type& b, std::size_t i) noexcept : bref_(b), idx_(i) {
       assert(idx_ < bref_.size);
     }
 
     const_reference(const const_reference&) noexcept = default;
 
     // no assignment for const_references
     const_reference& operator=(const const_reference&) = delete;
     const_reference& operator=(const_reference&&) = delete;
 
     operator double() const noexcept {
       return bref_.visit(
           [this](const auto* p) { return static_cast<double>(p[this->idx_]); });
     }
 
     bool operator<(const const_reference& o) const noexcept {
       return apply_binary<detail::safe_less>(o);
     }
 
     bool operator==(const const_reference& o) const noexcept {
       return apply_binary<detail::safe_equal>(o);
     }
 
     template <class U>
     detail::if_arithmetic_or_large_int<U, bool> operator<(const U& o) const noexcept {
       return apply_binary<detail::safe_less>(o);
     }
 
     template <class U>
     detail::if_arithmetic_or_large_int<U, bool> operator>(const U& o) const noexcept {
       return apply_binary<detail::safe_greater>(o);
     }
 
     template <class U>
     detail::if_arithmetic_or_large_int<U, bool> operator==(const U& o) const noexcept {
       return apply_binary<detail::safe_equal>(o);
     }
 
   private:
     template <class Binary>
     bool apply_binary(const const_reference& x) const noexcept {
       return x.bref_.visit([this, ix = x.idx_](const auto* xp) {
         return this->apply_binary<Binary>(xp[ix]);
       });
     }
 
     template <class Binary, class U>
     bool apply_binary(const U& x) const noexcept {
       return bref_.visit([i = idx_, &x](const auto* p) { return Binary()(p[i], x); });
     }
 
   protected:
     buffer_type& bref_;
     std::size_t idx_;
     friend class reference;
   };
 
   /// implementation detail
   class reference : public const_reference,
                     public detail::partially_ordered<reference, reference, void> {
   public:
     reference(buffer_type& b, std::size_t i) noexcept : const_reference(b, i) {}
 
     // references do copy-construct
     reference(const reference& x) noexcept = default;
 
     // references do not rebind, assign through
     reference& operator=(const reference& x) {
       return operator=(static_cast<const_reference>(x));
     }
 
     // references do not rebind, assign through
     reference& operator=(const const_reference& x) {
       // safe for self-assignment, assigning matching type doesn't invalide buffer
       x.bref_.visit([this, ix = x.idx_](const auto* xp) { this->operator=(xp[ix]); });
       return *this;
     }
 
     template <class U>
     detail::if_arithmetic_or_large_int<U, reference&> operator=(const U& x) {
       this->bref_.visit([this, &x](auto* p) {
         // gcc-8 optimizes the expression `p[this->idx_] = 0` away even at -O0,
         // so we merge it into the next line which is properly counted
         adder()((p[this->idx_] = 0, p), this->bref_, this->idx_, x);
       });
       return *this;
     }
 
     bool operator<(const reference& o) const noexcept {
       return const_reference::operator<(o);
     }
 
     bool operator==(const reference& o) const noexcept {
       return const_reference::operator==(o);
     }
 
     template <class U>
     detail::if_arithmetic_or_large_int<U, bool> operator<(const U& o) const noexcept {
       return const_reference::operator<(o);
     }
 
     template <class U>
     detail::if_arithmetic_or_large_int<U, bool> operator>(const U& o) const noexcept {
       return const_reference::operator>(o);
     }
 
     template <class U>
     detail::if_arithmetic_or_large_int<U, bool> operator==(const U& o) const noexcept {
       return const_reference::operator==(o);
     }
 
     reference& operator+=(const const_reference& x) {
       x.bref_.visit([this, ix = x.idx_](const auto* xp) { this->operator+=(xp[ix]); });
       return *this;
     }
 
     template <class U>
     detail::if_arithmetic_or_large_int<U, reference&> operator+=(const U& x) {
       this->bref_.visit(adder(), this->bref_, this->idx_, x);
       return *this;
     }
 
     reference& operator-=(const double x) { return operator+=(-x); }
 
     reference& operator*=(const double x) {
       this->bref_.visit(multiplier(), this->bref_, this->idx_, x);
       return *this;
     }
 
     reference& operator/=(const double x) { return operator*=(1.0 / x); }
 
     reference& operator++() {
       this->bref_.visit(incrementor(), this->bref_, this->idx_);
       return *this;
     }
   };
 
 private:
   template <class Value, class Reference>
   class iterator_impl : public detail::iterator_adaptor<iterator_impl<Value, Reference>,
                                                         std::size_t, Reference, Value> {
   public:
     iterator_impl() = default;
     template <class V, class R>
     iterator_impl(const iterator_impl<V, R>& it)
         : iterator_impl::iterator_adaptor_(it.base()), buffer_(it.buffer_) {}
     iterator_impl(buffer_type* b, std::size_t i) noexcept
         : iterator_impl::iterator_adaptor_(i), buffer_(b) {}
 
     Reference operator*() const noexcept { return {*buffer_, this->base()}; }
 
     template <class V, class R>
     friend class iterator_impl;
 
   private:
     mutable buffer_type* buffer_ = nullptr;
   };
 
 public:
   using const_iterator = iterator_impl<const value_type, const_reference>;
   using iterator = iterator_impl<value_type, reference>;
 
   explicit unlimited_storage(const allocator_type& a = {}) : buffer_(a) {}
   unlimited_storage(const unlimited_storage&) = default;
   unlimited_storage& operator=(const unlimited_storage&) = default;
   unlimited_storage(unlimited_storage&&) = default;
   unlimited_storage& operator=(unlimited_storage&&) = default;
 
   // TODO
   // template <class Allocator>
   // unlimited_storage(const unlimited_storage<Allocator>& s)
 
   template <class Iterable, class = detail::requires_iterable<Iterable>>
   explicit unlimited_storage(const Iterable& s) {
     using std::begin;
     using std::end;
     auto s_begin = begin(s);
     auto s_end = end(s);
     using V = typename std::iterator_traits<decltype(begin(s))>::value_type;
     // must be non-const to avoid msvc warning about if constexpr
     auto ti = buffer_type::template type_index<V>();
     auto nt = mp11::mp_size<typename buffer_type::types>::value;
     const std::size_t size = static_cast<std::size_t>(std::distance(s_begin, s_end));
     if (ti < nt)
       buffer_.template make<V>(size, s_begin);
     else
       buffer_.template make<double>(size, s_begin);
   }
 
   template <class Iterable, class = detail::requires_iterable<Iterable>>
   unlimited_storage& operator=(const Iterable& s) {
     *this = unlimited_storage(s);
     return *this;
   }
 
   allocator_type get_allocator() const { return buffer_.alloc; }
 
   void reset(std::size_t n) { buffer_.template make<U8>(n); }
 
   std::size_t size() const noexcept { return buffer_.size; }
 
   reference operator[](std::size_t i) noexcept { return {buffer_, i}; }
   const_reference operator[](std::size_t i) const noexcept { return {buffer_, i}; }
 
   bool operator==(const unlimited_storage& x) const noexcept {
     if (size() != x.size()) return false;
     return buffer_.visit([&x](const auto* p) {
       return x.buffer_.visit([p, n = x.size()](const auto* xp) {
         return std::equal(p, p + n, xp, detail::safe_equal{});
       });
     });
   }
 
   template <class Iterable>
   bool operator==(const Iterable& iterable) const {
     if (size() != iterable.size()) return false;
     return buffer_.visit([&iterable](const auto* p) {
       return std::equal(p, p + iterable.size(), std::begin(iterable),
                         detail::safe_equal{});
     });
   }
 
   unlimited_storage& operator*=(const double x) {
     buffer_.visit(multiplier(), buffer_, x);
     return *this;
   }
 
   iterator begin() noexcept { return {&buffer_, 0}; }
   iterator end() noexcept { return {&buffer_, size()}; }
   const_iterator begin() const noexcept { return {&buffer_, 0}; }
   const_iterator end() const noexcept { return {&buffer_, size()}; }
 
   /// implementation detail; used by unit tests, not part of generic storage interface
   template <class T>
   unlimited_storage(std::size_t s, const T* p, const allocator_type& a = {})
       : buffer_(std::move(a)) {
     buffer_.template make<T>(s, p);
   }
 
   template <class Archive>
   void serialize(Archive& ar, unsigned /* version */) {
     if (Archive::is_loading::value) {
       buffer_type tmp(buffer_.alloc);
       std::size_t size;
       ar& make_nvp("type", tmp.type);
       ar& make_nvp("size", size);
       tmp.visit([this, size](auto* tp) {
         assert(tp == nullptr);
         using T = std::decay_t<decltype(*tp)>;
         buffer_.template make<T>(size);
       });
     } else {
       ar& make_nvp("type", buffer_.type);
       ar& make_nvp("size", buffer_.size);
     }
     buffer_.visit([this, &ar](auto* tp) {
       auto w = detail::make_array_wrapper(tp, this->buffer_.size);
       ar& make_nvp("buffer", w);
     });
   }
 
 private:
   struct incrementor {
     template <class T>
     void operator()(T* tp, buffer_type& b, std::size_t i) {
       assert(tp && i < b.size);
       if (!detail::safe_increment(tp[i])) {
         using U = detail::next_type<typename buffer_type::types, T>;
         b.template make<U>(b.size, tp);
         ++static_cast<U*>(b.ptr)[i];
       }
     }
 
     void operator()(large_int* tp, buffer_type&, std::size_t i) { ++tp[i]; }
 
     void operator()(double* tp, buffer_type&, std::size_t i) { ++tp[i]; }
   };
 
   struct adder {
     template <class U>
     void operator()(double* tp, buffer_type&, std::size_t i, const U& x) {
       tp[i] += static_cast<double>(x);
     }
 
     void operator()(large_int* tp, buffer_type&, std::size_t i, const large_int& x) {
       tp[i] += x; // potentially adding large_int to itself is safe
     }
 
     template <class T, class U>
     void operator()(T* tp, buffer_type& b, std::size_t i, const U& x) {
       is_x_integral(std::is_integral<U>{}, tp, b, i, x);
     }
 
     template <class T, class U>
     void is_x_integral(std::false_type, T* tp, buffer_type& b, std::size_t i,
                        const U& x) {
       // x could be reference to buffer we manipulate, make copy before changing buffer
       const auto v = static_cast<double>(x);
       b.template make<double>(b.size, tp);
       operator()(static_cast<double*>(b.ptr), b, i, v);
     }
 
     template <class T>
     void is_x_integral(std::false_type, T* tp, buffer_type& b, std::size_t i,
                        const large_int& x) {
       // x could be reference to buffer we manipulate, make copy before changing buffer
       const auto v = static_cast<large_int>(x);
       b.template make<large_int>(b.size, tp);
       operator()(static_cast<large_int*>(b.ptr), b, i, v);
     }
 
     template <class T, class U>
     void is_x_integral(std::true_type, T* tp, buffer_type& b, std::size_t i, const U& x) {
       is_x_unsigned(std::is_unsigned<U>{}, tp, b, i, x);
     }
 
     template <class T, class U>
     void is_x_unsigned(std::false_type, T* tp, buffer_type& b, std::size_t i,
                        const U& x) {
       if (x >= 0)
         is_x_unsigned(std::true_type{}, tp, b, i, detail::make_unsigned(x));
       else
         is_x_integral(std::false_type{}, tp, b, i, static_cast<double>(x));
     }
 
     template <class T, class U>
     void is_x_unsigned(std::true_type, T* tp, buffer_type& b, std::size_t i, const U& x) {
       if (detail::safe_radd(tp[i], x)) return;
       // x could be reference to buffer we manipulate, need to convert to value
       const auto y = x;
       using TN = detail::next_type<typename buffer_type::types, T>;
       b.template make<TN>(b.size, tp);
       is_x_unsigned(std::true_type{}, static_cast<TN*>(b.ptr), b, i, y);
     }
 
     template <class U>
     void is_x_unsigned(std::true_type, large_int* tp, buffer_type&, std::size_t i,
                        const U& x) {
       tp[i] += x;
     }
   };
 
   struct multiplier {
     template <class T>
     void operator()(T* tp, buffer_type& b, const double x) {
       // potential lossy conversion that cannot be avoided
       b.template make<double>(b.size, tp);
       operator()(static_cast<double*>(b.ptr), b, x);
     }
 
     void operator()(double* tp, buffer_type& b, const double x) {
       for (auto end = tp + b.size; tp != end; ++tp) *tp *= x;
     }
 
     template <class T>
     void operator()(T* tp, buffer_type& b, std::size_t i, const double x) {
       b.template make<double>(b.size, tp);
       operator()(static_cast<double*>(b.ptr), b, i, x);
     }
 
     void operator()(double* tp, buffer_type&, std::size_t i, const double x) {
       tp[i] *= static_cast<double>(x);
     }
   };
 
   mutable buffer_type buffer_;
   friend struct unsafe_access;
 };
 
 } // namespace histogram
 } // namespace boost
 
 #endif

This page was automatically generated by the 2.3.7 LXR engine. The LXR team