BLI_unique_sorted_indices.hh File Reference

#include <optional>
#include <variant>
#include "BLI_binary_search.hh"
#include "BLI_vector.hh"

Go to the source code of this file.

Namespaces
namespace	blender
namespace	blender::unique_sorted_indices

Functions
template<typename T >
bool	blender::unique_sorted_indices::non_empty_is_range (const Span< T > indices)
template<typename T >
IndexRange	blender::unique_sorted_indices::non_empty_as_range (const Span< T > indices)
template<typename T >
std::optional< IndexRange >	blender::unique_sorted_indices::non_empty_as_range_try (const Span< T > indices)
template<typename T >
int64_t	blender::unique_sorted_indices::find_size_of_next_range (const Span< T > indices)
template<typename T >
int64_t	blender::unique_sorted_indices::find_size_until_next_range (const Span< T > indices, const int64_t min_range_size)
template<typename T , int64_t InlineBufferSize>
int64_t	blender::unique_sorted_indices::split_to_ranges_and_spans (const Span< T > indices, const int64_t range_threshold, Vector< std::variant< IndexRange, Span< T > >, InlineBufferSize > &r_segments)

Detailed Description

This file provides functions that deal with integer arrays fulfilling two constraints:

• Values are sorted in ascending order, e.g. [2, 3, 6, 8].
• The array doesn't have any duplicate elements, so [3, 4, 4, 5] is not allowed.

Arrays satisfying these constraints are useful to "mask" indices that should be processed for two main reasons:

• The sorted order makes hardware prefetching work best, because memory access patterns are more predictable (unless the indices are too far apart).
• One can check in constant time whether an array of indices contains consecutive integers which can be represented more efficiently with an #IndexRange.

Just using a single array as a mask works well as long as the number of indices is not too large. For potentially larger masks it's better to use #IndexMask which allows for better multi-threading.

Definition in file BLI_unique_sorted_indices.hh.