source/blender/blenlib/BLI_offset_indices.hh

   1 /* SPDX-FileCopyrightText: 2023 Blender Authors
   2  *
   3  * SPDX-License-Identifier: GPL-2.0-or-later */
   4
   5 #pragma once
   6
   7 #include <algorithm>
   8 #include <optional>
   9
  10 #include "BLI_index_mask_fwd.hh"
  11 #include "BLI_index_range.hh"
  12 #include "BLI_span.hh"
  13
  14 namespace blender::offset_indices {
  15
  16 /** Utility struct that can be passed into a function to skip a check for sorted indices. */
  17 struct NoSortCheck {};
  18
  19 /**
  20  * This class is a thin wrapper around an array of increasing indices that makes it easy to
  21  * retrieve an index range at a specific index. Each index range is typically a representation of
  22  * a contiguous chunk of a larger array.
  23  *
  24  * Another common way to store many index ranges is to store the start and size of every range.
  25  * Using #OffsetIndices instead requires that chunks are ordered consecutively but halves the
  26  * memory consumption. Another downside is that the underlying array has to be one element longer
  27  * than the total number of ranges. The extra element necessary to encode the size of the last
  28  * range without requiring a branch for each range access.
  29  */
  30 template<typename T> class OffsetIndices {
  31  private:
  32   static_assert(std::is_integral_v<T>);
  33
  34   Span<T> offsets_;
  35
  36  public:
  37   OffsetIndices() = default;
  38   OffsetIndices(const Span<T> offsets) : offsets_(offsets)
  39   {
  40     BLI_assert(offsets_.size() < 2 || std::is_sorted(offsets_.begin(), offsets_.end()));
  41   }
  42
  43   /**
  44    * Same as above, but skips the debug check that indices are sorted, because that can have a
  45    * high performance impact making debug builds unusable for files that would be fine otherwise.
  46    * This can be used when it is known that the indices are sorted already.
  47    */
  48   OffsetIndices(const Span<T> offsets, NoSortCheck /*no_sort_check*/) : offsets_(offsets) {}
  49
  50   /** Return the total number of elements in the referenced arrays. */
  51   T total_size() const
  52   {
  53     return offsets_.size() > 1 ? offsets_.last() - offsets_.first() : 0;
  54   }
  55
  56   /**
  57    * Return the number of ranges encoded by the offsets, not including the last value used
  58    * internally.
  59    */
  60   int64_t size() const
  61   {
  62     return std::max<int64_t>(offsets_.size() - 1, 0);
  63   }
  64
  65   bool is_empty() const
  66   {
  67     return this->size() == 0;
  68   }
  69
  70   IndexRange index_range() const
  71   {
  72     return IndexRange(this->size());
  73   }
  74
  75   IndexRange operator[](const int64_t index) const
  76   {
  77     BLI_assert(index >= 0);
  78     BLI_assert(index < offsets_.size() - 1);
  79     const int64_t begin = offsets_[index];
  80     const int64_t end = offsets_[index + 1];
  81     return IndexRange::from_begin_end(begin, end);
  82   }
  83
  84   IndexRange operator[](const IndexRange indices) const
  85   {
  86     const int64_t begin = offsets_[indices.start()];
  87     const int64_t end = offsets_[indices.one_after_last()];
  88     return IndexRange::from_begin_end(begin, end);
  89   }
  90
  91   /**
  92    * Return a subset of the offsets describing the specified range of source elements.
  93    * This is a slice into the source ranges rather than the indexed elements described by the
  94    * offset values.
  95    */
  96   OffsetIndices slice(const IndexRange range) const
  97   {
  98     BLI_assert(range.is_empty() || offsets_.index_range().drop_back(1).contains(range.last()));
  99     return OffsetIndices(offsets_.slice(range.start(), range.size() + 1));
 100   }
 101
 102   Span<T> data() const
 103   {
 104     return offsets_;
 105   }
 106 };
 107
 108 /**
 109  * References many separate spans in a larger contiguous array. This gives a more efficient way to
 110  * store many grouped arrays, without requiring many small allocations, giving the general benefits
 111  * of using contiguous memory.
 112  *
 113  * \note If the offsets are shared between many #GroupedSpan objects, it will be more efficient
 114  * to retrieve the #IndexRange only once and slice each span.
 115  */
 116 template<typename T> struct GroupedSpan {
 117   OffsetIndices<int> offsets;
 118   Span<T> data;
 119
 120   GroupedSpan() = default;
 121   GroupedSpan(OffsetIndices<int> offsets, Span<T> data) : offsets(offsets), data(data)
 122   {
 123     BLI_assert(this->offsets.total_size() == this->data.size());
 124   }
 125
 126   Span<T> operator[](const int64_t index) const
 127   {
 128     return this->data.slice(this->offsets[index]);
 129   }
 130
 131   int64_t size() const
 132   {
 133     return this->offsets.size();
 134   }
 135
 136   IndexRange index_range() const
 137   {
 138     return this->offsets.index_range();
 139   }
 140
 141   bool is_empty() const
 142   {
 143     return this->data.size() == 0;
 144   }
 145 };
 146
 147 /**
 148  * Turn an array of sizes into the offset at each index including all previous sizes.
 149  */
 150 OffsetIndices<int> accumulate_counts_to_offsets(MutableSpan<int> counts_to_offsets,
 151                                                 int start_offset = 0);
 152
 153 std::optional<OffsetIndices<int>> accumulate_counts_to_offsets_with_overflow_check(
 154     MutableSpan<int> counts_to_offsets, int start_offset = 0);
 155
 156 /** Create offsets where every group has the same size. */
 157 void fill_constant_group_size(int size, int start_offset, MutableSpan<int> offsets);
 158
 159 /** Copy the number of indices in every group in the mask to the corresponding index. */
 160 void copy_group_sizes(OffsetIndices<int> offsets, const IndexMask &mask, MutableSpan<int> sizes);
 161
 162 /** Gather the number of indices in each indexed group to sizes. */
 163 void gather_group_sizes(OffsetIndices<int> offsets, const IndexMask &mask, MutableSpan<int> sizes);
 164 void gather_group_sizes(OffsetIndices<int> offsets, Span<int> indices, MutableSpan<int> sizes);
 165
 166 /** Calculate the total size of all the referenced groups. */
 167 int sum_group_sizes(OffsetIndices<int> offsets, const IndexMask &mask);
 168 int sum_group_sizes(OffsetIndices<int> offsets, Span<int> indices);
 169
 170 /** Build new offsets that contains only the groups chosen by \a selection. */
 171 OffsetIndices<int> gather_selected_offsets(OffsetIndices<int> src_offsets,
 172                                            const IndexMask &selection,
 173                                            int start_offset,
 174                                            MutableSpan<int> dst_offsets);
 175 inline OffsetIndices<int> gather_selected_offsets(OffsetIndices<int> src_offsets,
 176                                                   const IndexMask &selection,
 177                                                   MutableSpan<int> dst_offsets)
 178 {
 179   return gather_selected_offsets(src_offsets, selection, 0, dst_offsets);
 180 }
 181
 182 /**
 183  * Create a map from indexed elements to the source indices, in other words from the larger array
 184  * to the smaller array.
 185  */
 186 void build_reverse_map(OffsetIndices<int> offsets, MutableSpan<int> r_map);
 187
 188 /**
 189  * Build offsets to group the elements of \a indices pointing to the same index.
 190  */
 191 void build_reverse_offsets(Span<int> indices, MutableSpan<int> offsets);
 192
 193 }  // namespace blender::offset_indices
 194
 195 namespace blender {
 196 using offset_indices::GroupedSpan;
 197 using offset_indices::OffsetIndices;
 198 }  // namespace blender