Sparse union array implementation without offset buffer. More...

#include <union_array.hpp>

Inheritance diagram for sparrow::sparse_union_array:

Collaboration diagram for sparrow::sparse_union_array:

Public Types
using	base_type = union_array_crtp_base<sparse_union_array>
using	type_id_buffer_type = typename base_type::type_id_buffer_type
Public Types inherited from sparrow::union_array_crtp_base< sparse_union_array >
using	self_type
using	derived_type
using	inner_value_type
using	value_type
using	const_reference
using	functor_type
using	const_functor_type
using	iterator
using	const_iterator
using	const_reverse_iterator
using	size_type
using	type_id_buffer_type

Public Member Functions
template<class... Args> requires (mpl::excludes_copy_and_move_ctor_v<sparse_union_array, Args...>)
	sparse_union_array (Args &&... args)
	Generic constructor for creating sparse union arrays.
SPARROW_API	sparse_union_array (arrow_proxy proxy)
	Constructs sparse union array from Arrow proxy.
SPARROW_API	sparse_union_array (const sparse_union_array &)
SPARROW_API sparse_union_array &	operator= (const sparse_union_array &)
Public Member Functions inherited from sparrow::union_array_crtp_base< sparse_union_array >
constexpr std::optional< std::string_view >	name () const
	Gets the optional name of the union array.
SPARROW_CONSTEXPR_CLANG std::optional< key_value_view >	metadata () const
	Gets the metadata associated with the union array.
SPARROW_CONSTEXPR_CLANG value_type	at (size_type i) const
	Gets element at specified position with bounds checking.
SPARROW_CONSTEXPR_CLANG value_type	operator[] (size_type i) const
	Gets element at specified position without bounds checking.
SPARROW_CONSTEXPR_CLANG value_type	operator[] (size_type i)
	Gets mutable element at specified position.
SPARROW_CONSTEXPR_CLANG value_type	front () const
	Gets reference to the first element.
SPARROW_CONSTEXPR_CLANG value_type	back () const
	Gets reference to the last element.
constexpr bool	empty () const
	Checks if the union array is empty.
constexpr size_type	size () const
	Gets the number of elements in the union array.
constexpr iterator	begin ()
	Gets iterator to the beginning of the array.
constexpr iterator	end ()
	Gets iterator to the end of the array.
constexpr const_iterator	begin () const
	Gets const iterator to the beginning of the array.
constexpr const_iterator	end () const
	Gets const iterator to the end of the array.
constexpr const_iterator	cbegin () const
	Gets const iterator to the beginning of the array.
constexpr const_iterator	cend () const
	Gets const iterator to the end of the array.
constexpr const_reverse_iterator	rbegin () const
	Gets reverse iterator to the beginning of reversed array.
constexpr const_reverse_iterator	rend () const
	Gets reverse iterator to the end of reversed array.
constexpr const_reverse_iterator	crbegin () const
	Gets const reverse iterator to the beginning of reversed array.
constexpr const_reverse_iterator	crend () const
	Gets const reverse iterator to the end of reversed array.
iterator	insert (const_iterator pos, const_reference value, size_type count=1)
	Inserts copies of a value before pos.
iterator	insert (const_iterator pos, const array_traits::value_type &value, size_type count=1)
	Inserts copies of an owned value before pos.
iterator	insert (const_iterator pos, InputIt first, InputIt last, size_type count=1)
	Inserts a range before pos, repeated count times.
iterator	erase (const_iterator pos)
	Erases the value at pos.
iterator	erase (const_iterator first, const_iterator last)
	Erases the half-open range [first, last).
void	push_back (const_reference value)
	Appends a borrowed value.
void	push_back (const array_traits::value_type &value)
	Appends an owned value.
void	resize (size_type new_length)
	Resizes the array, default-inserting any appended values.
void	resize (size_type new_length, const_reference value)
	Resizes the array, inserting value when it grows.
void	resize (size_type new_length, const array_traits::value_type &value)
	Resizes the array, inserting value when it grows.
constexpr void	zero_null_values (const inner_value_type &value)
	Replaces stored values at null positions.
constexpr auto	type_id_map_from_child_to_type_id (const std::optional< R > &child_index_to_type_id) -> type_id_map

Friends
class	union_array_crtp_base< sparse_union_array >

Additional Inherited Members
Protected Types inherited from sparrow::union_array_crtp_base< sparse_union_array >
using	type_id_map
using	children_type
Protected Types inherited from sparrow::crtp_base< D >
using	derived_type = D
Protected Member Functions inherited from sparrow::union_array_crtp_base< sparse_union_array >
constexpr children_type	make_children (arrow_proxy &proxy)
	Creates child array wrappers from Arrow proxy.
	union_array_crtp_base (arrow_proxy proxy)
	Protected constructor from Arrow proxy.
constexpr	union_array_crtp_base (const self_type &rhs)
	Copy constructor.
constexpr self_type &	operator= (const self_type &rhs)
	Copy assignment operator.
constexpr	union_array_crtp_base (self_type &&rhs)=default
constexpr self_type &	operator= (self_type &&rhs)=default
void	resize_impl (size_type new_length, VALUE &&value)
iterator	iterator_at (size_type index)
void	append_rebuild_entries (std::vector< detail::union_rebuild_value > &entries, size_type from, size_type to) const
	Appends one rebuild entry per element in [from, to), each referring to its current child slot.
iterator	insert_materialized (const_iterator pos, std::vector< array_traits::value_type > inserted, size_type count)
	Rebuilds the array with the owned `inserted` values repeated `count` times before `pos`.
iterator	erase_values (size_type first, size_type count)
std::vector< union_child_schema >	make_child_schemas (std::vector< std::uint8_t > &child_type_ids, std::array< bool, TYPE_ID_MAP_SIZE > &used_type_ids) const
	Initializes the schema bookkeeping of a rebuild from the current children.
std::vector< detail::union_rebuild_value >	make_union_fillers (size_type old_child_count, const std::vector< union_child_schema > &child_schemas, std::vector< std::size_t > &inserted_children, std::vector< array_traits::value_type > &inserted) const
	Builds the row padding the output rows a child is not selected for.
detail::union_rebuild_payload	make_rebuild_payload (std::span< const detail::union_rebuild_value > values, std::span< const std::size_t > inserted_children, std::span< const std::uint8_t > child_type_ids, std::span< const detail::union_rebuild_value > fillers) const
	Plans the rebuilt data from the row plan and the inserted-value resolution.
std::vector< array >	build_rebuilt_children (const detail::union_rebuild_payload &payload, std::span< const array_traits::value_type > inserted, std::span< const std::size_t > inserted_children, const children_type &old_children, std::vector< array > &new_child_templates) const
	Rebuilds each child array from the payload rows planned for it.
arrow_proxy	create_rebuild_proxy (std::vector< array > children, detail::union_rebuild_payload &&payload, std::span< const std::uint8_t > child_type_ids) const
	Creates the Arrow proxy of a rebuilt array from its children and buffers.
iterator	adopt_rebuilt_array (arrow_proxy replacement, std::vector< std::uint8_t > child_type_ids, size_type return_index)
	Replaces this array's data with the rebuilt `replacement`.
iterator	rebuild_values (std::vector< detail::union_rebuild_value > values, std::vector< array_traits::value_type > inserted, size_type return_index)
	Rebuilds this array from `values`, the inserted values they reference, and.
constexpr arrow_proxy &	get_arrow_proxy ()
	Gets mutable reference to the Arrow proxy.
constexpr const arrow_proxy &	get_arrow_proxy () const
	Gets const reference to the Arrow proxy.
Protected Member Functions inherited from sparrow::crtp_base< D >
constexpr derived_type &	derived_cast ()
constexpr const derived_type &	derived_cast () const
Static Protected Member Functions inherited from sparrow::union_array_crtp_base< sparse_union_array >
static std::vector< std::uint8_t >	child_type_ids_from_format (std::string_view format_string)
	Extracts child type IDs from an Arrow union format string.
static constexpr type_id_map	make_type_id_map (std::span< const std::uint8_t > child_type_ids)
	Creates a type-ID lookup table from child type IDs.
static constexpr type_id_map	type_id_map_from_child_to_type_id (const std::optional< R > &child_index_to_type_id)
	Creates type ID mapping from child index to type ID mapping.
static constexpr std::string	make_format_string (bool dense, std::size_t n, const std::optional< R > &child_index_to_type_id)
	Creates Arrow format string for union arrays.
static std::vector< std::size_t >	resolve_inserted_children (std::span< const array_traits::value_type > inserted, std::vector< union_child_schema > &child_schemas, std::vector< std::uint8_t > &child_type_ids, std::array< bool, TYPE_ID_MAP_SIZE > &used_type_ids, std::vector< array > &new_child_templates)
	Maps each inserted value to the child it belongs to.
Protected Attributes inherited from sparrow::union_array_crtp_base< sparse_union_array >
arrow_proxy	m_proxy
	Internal Arrow proxy.
const std::uint8_t *	p_type_ids
	Pointer to type ID buffer.
children_type	m_children
	Child array wrappers.
std::vector< std::uint8_t >	m_child_type_ids
	Type IDs in child order.
std::array< std::uint8_t, TYPE_ID_MAP_SIZE >	m_type_id_map
	Type ID to child index mapping.
Static Protected Attributes inherited from sparrow::union_array_crtp_base< sparse_union_array >
static constexpr size_t	TYPE_ID_MAP_SIZE

Detailed Description

Sparse union array implementation without offset buffer.

Sparse union arrays do not store an offset buffer. Instead, all child arrays have the same length as the union array, and each element directly corresponds to the same position in its child array. This is simpler but less memory efficient when union elements are sparse.

Memory layout:

Type ID buffer: Maps each element to child array type
Child arrays: All have the same length as the union array

Related Apache Arrow specification: https://arrow.apache.org/docs/dev/format/Columnar.html#sparse-union

Postcondition: Maintains Arrow sparse union format compatibility ("+us:"); All child arrays have the same length as the union array; Provides simpler access pattern at the cost of memory efficiency

// Create sparse union with int and string children
std::vector<array> children = {int_array, string_array};  // same length as union
type_id_buffer_type type_ids = {0, 1, 0, 1};              // alternating types
 
sparse_union_array union_arr(std::move(children),
                              std::move(type_ids));

Definition at line 1099 of file union_array.hpp.

Member Typedef Documentation

◆ base_type

using sparrow::sparse_union_array::base_type = union_array_crtp_base<sparse_union_array>

Definition at line 1103 of file union_array.hpp.

◆ type_id_buffer_type

using sparrow::sparse_union_array::type_id_buffer_type = typename base_type::type_id_buffer_type

Definition at line 1104 of file union_array.hpp.

Constructor & Destructor Documentation

◆ sparse_union_array() [1/3]

template<class... Args>
requires (mpl::excludes_copy_and_move_ctor_v<sparse_union_array, Args...>)

sparrow::sparse_union_array::sparse_union_array ( Args &&... args )

inlineexplicit

Generic constructor for creating sparse union arrays.

Creates a sparse union array from various input combinations including child arrays, type IDs, and optional type mapping.

Template Parameters

Args	Parameter pack for constructor arguments

Parameters

args	Constructor arguments (children, type_ids, etc.)

Precondition: Args must match one of the create_proxy() overload signatures; Args must exclude copy and move constructor signatures; All child arrays must have the same length

Postcondition: Array is created with the specified children and configuration

Definition at line 1122 of file union_array.hpp.

Here is the caller graph for this function:

◆ sparse_union_array() [2/3]

SPARROW_API sparrow::sparse_union_array::sparse_union_array ( arrow_proxy proxy )

explicit

Constructs sparse union array from Arrow proxy.

Parameters

proxy Arrow proxy containing sparse union array data and schema

Precondition: proxy must contain valid Arrow sparse union array and schema; proxy format must be "+us:..."; proxy must have type ID buffer; All child arrays must have same length as union array

Postcondition: Array is initialized with data from proxy

◆ sparse_union_array() [3/3]

SPARROW_API sparrow::sparse_union_array::sparse_union_array ( const sparse_union_array & )

Here is the call graph for this function:

Member Function Documentation

◆ operator=()

SPARROW_API sparse_union_array & sparrow::sparse_union_array::operator= ( const sparse_union_array & )

Here is the call graph for this function:

◆ union_array_crtp_base< sparse_union_array >

friend class union_array_crtp_base< sparse_union_array >

friend

Definition at line 1213 of file union_array.hpp.

The documentation for this class was generated from the following file:

sparrow/union_array.hpp

Public Types

Public Member Functions

Friends

Additional Inherited Members