Detailed Description

Author: hacatu

Version: 0.3.0 Simple, featureful generic vector

This Source Code Form is subject to the terms of the Mozilla Public License, v. 2.0. If a copy of the MPL was not distributed with this file, You can obtain one at http://mozilla.org/MPL/2.0/.

Definition in file vec.h.

Go to the source code of this file.

Data Structures
struct	cr8r_vec
	A vector Take care if manipulating these fields directly, this should only be done if the functions in this file are not sufficient. More...

struct	cr8r_vec_ft
	Function table for vector. More...

Macros
#define	CR8R_VEC_ISORT_BOUND 16
	Threshold below which quicksort and quickselect will switch to using insertion sort.

Typedefs
typedef bool(*	cr8r_vec_pred) (const cr8r_vec_ft , const void ent, void *data)
	Callback type for predicates on vector elements. More...

typedef void(*	cr8r_vec_mapper) (const cr8r_vec_ft src_ft, const cr8r_vec_ft dest_ft, void o, const void e, void *data)
	Callback type for functions mapping from one vector element type to another. More...

typedef void (	cr8r_vec_accumulator) (const cr8r_vec_ft , void acc, const void *e)
	Callback type for accumulator functions on vectors (cr8r_vec_foldl) More...

Functions
bool	cr8r_vec_ft_init (cr8r_vec_ft , void data, uint64_t size, uint64_t(new_size)(cr8r_base_ft , uint64_t cap), void (resize)(cr8r_base_ft , void p, uint64_t cap), void(del)(cr8r_base_ft , void p), void(copy)(cr8r_base_ft , void dest, const void src), int(cmp)(const cr8r_base_ft , const void a, const void b), void(swap)(cr8r_base_ft , void a, void *b))
	Convenience function to initialize a cr8r_vec_ft. More...

bool	cr8r_vec_init (cr8r_vec , cr8r_vec_ft , uint64_t cap)
	Initialize a vector with an empty buffer of a given capacity. More...

void	cr8r_vec_delete (cr8r_vec , cr8r_vec_ft )
	Delete all entries in a vector and free its buffer. More...

bool	cr8r_vec_copy (cr8r_vec dest, const cr8r_vec src, cr8r_vec_ft *)
	Create a copy of a vector. More...

bool	cr8r_vec_sub (cr8r_vec dest, const cr8r_vec src, cr8r_vec_ft *, uint64_t a, uint64_t b)
	Create a copy of a slice of a vector. More...

bool	cr8r_vec_resize (cr8r_vec , cr8r_vec_ft , uint64_t cap)
	Resize a vector's reserved buffer. More...

bool	cr8r_vec_trim (cr8r_vec , cr8r_vec_ft )
	Resize a vector's reserved buffer to its length. More...

void	cr8r_vec_clear (cr8r_vec , cr8r_vec_ft )
	Remove all elements from a vector. More...

void	cr8r_vec_shuffle (cr8r_vec , cr8r_vec_ft , cr8r_prng *)
	Shuffle the vector into a random permutation. More...

void *	cr8r_vec_get (cr8r_vec , const cr8r_vec_ft , uint64_t i)
	Get the element at a given index. More...

void *	cr8r_vec_getx (cr8r_vec , const cr8r_vec_ft , int64_t i)
	Get the element at a given index, with support for negative indices. More...

uint64_t	cr8r_vec_len (cr8r_vec *)
	Get the length of a vector. More...

bool	cr8r_vec_pushr (cr8r_vec , cr8r_vec_ft , const void *e)
	Add an element to the right hand end of a vector. More...

bool	cr8r_vec_popr (cr8r_vec , cr8r_vec_ft , void *o)
	Remove an element from the right hand end of a vector. More...

bool	cr8r_vec_pushl (cr8r_vec , cr8r_vec_ft , const void *e)
	Add an element to the left hand end of a vector. More...

bool	cr8r_vec_popl (cr8r_vec , cr8r_vec_ft , void *o)
	Remove an element from the left hand end of a vector. More...

bool	cr8r_vec_filter (cr8r_vec , cr8r_vec_ft , cr8r_vec_pred pred, void *data)
	Filter a vector in-place. More...

bool	cr8r_vec_filtered (cr8r_vec dest, const cr8r_vec src, cr8r_vec_ft , cr8r_vec_pred pred, void data)
	Create a new vector as a subsequence matching a predicate. More...

bool	cr8r_vec_map (cr8r_vec dest, const cr8r_vec src, cr8r_vec_ft src_ft, cr8r_vec_ft dest_ft, cr8r_vec_mapper f, void *data)
	Create a new vector by applying a transformation function to each element. More...

int	cr8r_vec_forEachPermutation (cr8r_vec , cr8r_vec_ft , void(f)(const cr8r_vec , const cr8r_vec_ft , void data), void *data)
	Execute a function on every permutation of a vector. More...

bool	cr8r_vec_combine (cr8r_vec dest, const cr8r_vec src_a, const cr8r_vec src_b, cr8r_vec_ft )
	Create a new vector by concatenating copies of two given vectors. More...

bool	cr8r_vec_augment (cr8r_vec self, const cr8r_vec other, cr8r_vec_ft *)
	Add a copy of another vector to a given vector. More...

bool	cr8r_vec_ensure_cap (cr8r_vec self, cr8r_vec_ft ft, uint64_t cap)
	Expand a vector's internal storage if needed to fit a given capacity Will not reallocate if self->cap >= cap already Otherwise, try to get a size hint from ft->new_size, but falls back if this is still < cap. More...

bool	cr8r_vec_all (const cr8r_vec , const cr8r_vec_ft , cr8r_vec_pred pred, void *data)
	Test if a predicate holds for all elements in a vector. More...

bool	cr8r_vec_any (const cr8r_vec , const cr8r_vec_ft , cr8r_vec_pred pred, void *data)
	Test if a predicate holds for any element in a vector. More...

bool	cr8r_vec_contains (const cr8r_vec , const cr8r_vec_ft , const void *e)
	Check if a vector contains a given element. More...

int64_t	cr8r_vec_index (const cr8r_vec , const cr8r_vec_ft , const void *e)
	Get the first index of an element in a vector. More...

void *	cr8r_vec_exm (cr8r_vec , const cr8r_vec_ft , int ord)
	Find the extremal (minimum or maximum) element of a vector. More...

void *	cr8r_vec_foldr (const cr8r_vec , const cr8r_vec_ft , cr8r_vec_accumulator f, void *init)
	Perform a right fold on a vector. More...

void *	cr8r_vec_foldl (const cr8r_vec , const cr8r_vec_ft , cr8r_vec_accumulator f, void *init)
	Perform a left fold on a vector. More...

void	cr8r_vec_sort (cr8r_vec , cr8r_vec_ft )
	Sort a vector in-place according to ft->cmp. More...

bool	cr8r_vec_sorted (cr8r_vec dest, const cr8r_vec src, cr8r_vec_ft *)
	Create a sorted copy of a vector. More...

void	cr8r_vec_reverse (cr8r_vec , cr8r_vec_ft )
	Reverse a vector in place.

bool	cr8r_vec_reversed (cr8r_vec dest, const cr8r_vec src, cr8r_vec_ft *)
	Create a reversed copy of a vector. More...

bool	cr8r_vec_containss (const cr8r_vec , const cr8r_vec_ft , const void *e)
	Check if a sorted vector contains an element. More...

int64_t	cr8r_vec_indexs (const cr8r_vec , const cr8r_vec_ft , const void *e)
	Get the index of an element in a sorted vector. More...

int64_t	cr8r_vec_first_gts (const cr8r_vec , const cr8r_vec_ft , const void *e)
	Get the index of the first element greater than a given key in a sorted vector. More...

int64_t	cr8r_vec_first_ges (const cr8r_vec , const cr8r_vec_ft , const void *e)
	Get the index of the first element greater than or equal to a given key in a sorted vector. More...

int64_t	cr8r_vec_last_lts (const cr8r_vec , const cr8r_vec_ft , const void *e)
	Get the index of the last element less than a given key in a sorted vector. More...

int64_t	cr8r_vec_last_les (const cr8r_vec , const cr8r_vec_ft , const void *e)
	Get the index of the last element greater than a given key in a sorted vector. More...

int	cr8r_vec_cmp (const cr8r_vec a, const cr8r_vec b, const cr8r_vec_ft *)
	Lexicographically compare two vectors. More...

void *	cr8r_vec_pivot_m3 (const cr8r_vec , cr8r_vec_ft , uint64_t a, uint64_t b)
	Pick a pivot for cr8r_vec_partition using the median of 3 approach. More...

void *	cr8r_vec_pivot_mm (cr8r_vec , cr8r_vec_ft , uint64_t a, uint64_t b)
	Pick a pivot for cr8r_vec_partition using the median of medians approach. More...

void *	cr8r_vec_partition (cr8r_vec , cr8r_vec_ft , uint64_t a, uint64_t b, void *piv)
	Partition a subrange of a vector into elements < a pivot and elements >= a pivot. More...

void *	cr8r_vec_partition_with_median (cr8r_vec , cr8r_vec_ft , uint64_t a, uint64_t b, void *piv)
	Partition a subrange of a vector into elements <, ==, and > a pivot. More...

void *	cr8r_vec_ith (cr8r_vec , cr8r_vec_ft , uint64_t a, uint64_t b, uint64_t i)
	Find the ith element of a subrange of a vector without completely sorting it. More...

void *	cr8r_default_acc_sum_u64 (const cr8r_vec_ft , void acc, const void *ent)
	Callback for cr8r_vec_foldr to sum up elements in vector. More...

void *	cr8r_default_acc_sumpowmod_u64 (const cr8r_vec_ft , void acc, const void *ent)
	Callback for cr8r_vec_foldr to sum up powers of elements in a vector mod a number. More...

Variables
cr8r_vec_ft	cr8r_vecft_u64
	Function table for vectors of uint64_t's. More...

cr8r_vec_ft	cr8r_vecft_cstr
	Function table for vectors of strings. More...

cr8r_vec_ft	cr8r_vecft_u8
	Function table for vectors of uint8_t's, which can be used as smart strings. More...

Typedef Documentation

◆ cr8r_vec_pred

typedef bool(* cr8r_vec_pred) (const cr8r_vec_ft *, const void *ent, void *data)

Callback type for predicates on vector elements.

These callbacks are provided with the vec_ft, the ent, and the data pointer passed to the caller

Definition at line 72 of file vec.h.

◆ cr8r_vec_mapper

typedef void(* cr8r_vec_mapper) (const cr8r_vec_ft *src_ft, const cr8r_vec_ft *dest_ft, void *o, const void *e, void *data)

Callback type for functions mapping from one vector element type to another.

These callbacks are provided with the src_ft, dest_ft, dest ent pointer, src ent pointer, and data pointer passed to the caller

Definition at line 77 of file vec.h.

◆ cr8r_vec_accumulator

typedef void*(* cr8r_vec_accumulator) (const cr8r_vec_ft *, void *acc, const void *e)

Callback type for accumulator functions on vectors (cr8r_vec_foldl)

These callbacks are provided with the vec_ft, pointer to the accumulator, and pointer to the ent

Definition at line 82 of file vec.h.

Function Documentation

◆ cr8r_vec_ft_init()

bool cr8r_vec_ft_init	(	cr8r_vec_ft *	,
		void *	data,
		uint64_t	size,
		uint64_t()(cr8r_base_ft , uint64_t cap)	new_size,
		void ()(cr8r_base_ft , void p, uint64_t cap)	resize,
		void()(cr8r_base_ft , void *p)	del,
		void()(cr8r_base_ft , void dest, const void src)	copy,
		int()(const cr8r_base_ft , const void a, const void b)	cmp,
		void()(cr8r_base_ft , void a, void b)	swap
	)

Convenience function to initialize a cr8r_vec_ft.

Using standard structure initializer syntax with designated initializers may be simpler. However, this function automatically sets some functions to defaults if they are NULL.

Parameters

[in]	data	pointer to user defined data to associate with the function table. generally NULL is sufficient. see cr8r_base_ft for a more in-depth explaination
[in]	size	size of a single element in bytes
[in]	new_size	called to determine the capacity to grow to given the previous capacity (both in number of elements). Defaults to cr8r_default_new_size which doubles the current size if it is nonzero or sets it to 8 otherwise.
[in]	resize	memory management function. Should "free" the buffer if cap is 0 (and do nothing if the current buffer is NULL). Should allocate a new buffer if the current buffer is NULL and cap is not 0. Otherwise, should resize the buffer to the requested size, possibly copying it to a new address. Defaults to cr8r_default_resize which is a good basic generic implementation.
[in]	del	called on any element before deleting it. can be NULL if no action is required.
[in]	copy	copy an element. can be NULL if memcpy is sufficient.
[in]	cmp	comparison function. must not be NULL to call search and sort functions. If NULL, no default will be provided, but cr8r_default_cmp can be used if memcmp is sufficient.
[in]	swap	swap two element. only required for a few functions (namely cr8r_vec_shuffle). Defaults to cr8r_default_swap.

Returns: 1 on success, 0 on failure (if inputs are invalid, but currently all inputs are valid)

◆ cr8r_vec_init()

bool cr8r_vec_init	(	cr8r_vec *	,
		cr8r_vec_ft *	,
		uint64_t	cap
	)

Initialize a vector with an empty buffer of a given capacity.

Parameters

[in] cap how many entries to reserve space for initially

Returns: 1 on success, 0 on failure (memory allocation failure)

◆ cr8r_vec_delete()

void cr8r_vec_delete	(	cr8r_vec *	,
		cr8r_vec_ft *
	)

Delete all entries in a vector and free its buffer.

ft->del (can be NULL) is called on each element, then ft->resize is called to "resize" to 0. the fields of the vector are all zeroed out

◆ cr8r_vec_copy()

bool cr8r_vec_copy	(	cr8r_vec *	dest,
		const cr8r_vec *	src,
		cr8r_vec_ft *
	)

Create a copy of a vector.

dest should NOT be initialized or its buffer will be leaked! Copies entries with ft->copy if applicable. The copy's capacity is only its length.

Parameters

[out]	dest	the vector to copy TO
[in]	src	the vector to copy FROM

Returns: 1 on success, 0 on failure (memory allocation failure)

◆ cr8r_vec_sub()

bool cr8r_vec_sub	(	cr8r_vec *	dest,
		const cr8r_vec *	src,
		cr8r_vec_ft *	,
		uint64_t	a,
		uint64_t	b
	)

Create a copy of a slice of a vector.

dest should NOT be initialized or its buffer will be leaked! Copies the range [ a : b ) from src to dest. Copies entries with ft->copy if applicable. The copy's capacity is only its length (b - a).

Parameters

[out]	dest	the vector to copy TO
[in]	src	the vector to copy FROM
[in]	a,b	inclusive start index and exclusive end index

Returns: 1 on success, 0 on failure (memory allocation failure or invalid bounds)

◆ cr8r_vec_resize()

bool cr8r_vec_resize	(	cr8r_vec *	,
		cr8r_vec_ft *	,
		uint64_t	cap
	)

Resize a vector's reserved buffer.

Can extend or shrink the buffer, but cannot make it smaller than its length.

Parameters

[in] cap the target capacity, should not be less than the current length

Returns: 1 on success, 0 on failure (memory allocation or invalid bounds)

◆ cr8r_vec_trim()

bool cr8r_vec_trim	(	cr8r_vec *	,
		cr8r_vec_ft *
	)

Resize a vector's reserved buffer to its length.

Exactly like cr8r_vec_resize with self->len as the cap parameter

Returns: 1 on success, 0 on failure (memory allocation, shouldn't happen unless ft->resize can fail to shrink)

◆ cr8r_vec_clear()

void cr8r_vec_clear	(	cr8r_vec *	,
		cr8r_vec_ft *
	)

Remove all elements from a vector.

Calls ft->del if applicable, and sets len to 0

◆ cr8r_vec_shuffle()

void cr8r_vec_shuffle	(	cr8r_vec *	,
		cr8r_vec_ft *	,
		cr8r_prng *
	)

Shuffle the vector into a random permutation.

The algorithm produces permutations uniformly in theory, although in practice the number of permutations of a sufficiently large vector is enormously larger than the state space of any pseudorandom number generator. This won't cause any remotely meaningful patterns.

◆ cr8r_vec_get()

void* cr8r_vec_get	(	cr8r_vec *	,
		const cr8r_vec_ft *	,
		uint64_t	i
	)

Get the element at a given index.

Similar to just doing self->buf + i*ft->base.size (recall that void pointer arithmetic acts like char pointer arithmetic), except that this function does bounds checking.

Parameters

[in] i the index to get, should be from 0 inclusive to self->len exclusive

Returns: a pointer to the element at index i, or NULL if i is out of bounds

◆ cr8r_vec_getx()

void* cr8r_vec_getx	(	cr8r_vec *	,
		const cr8r_vec_ft *	,
		int64_t	i
	)

Get the element at a given index, with support for negative indices.

Negative indicies work backwards, with -1 referring to the last element and so on.

Parameters

[in] i the index to get, should be from 0 inclusive to self->len exclusive

Returns: a pointer to the element at index i, or NULL if i is out of bounds

◆ cr8r_vec_len()

uint64_t cr8r_vec_len ( cr8r_vec * )

Get the length of a vector.

Simply returns self->len

Returns: the length of the vector

◆ cr8r_vec_pushr()

bool cr8r_vec_pushr	(	cr8r_vec *	,
		cr8r_vec_ft *	,
		const void *	e
	)

Add an element to the right hand end of a vector.

Vectors are arranged with increasing indicies at increasing memory addresses, so this is an O(1) operation

Parameters

[in] e the element to add, which is copied from this pointer into the vector

Returns: 1 on success, 0 on failure

◆ cr8r_vec_popr()

bool cr8r_vec_popr	(	cr8r_vec *	,
		cr8r_vec_ft *	,
		void *	o
	)

Remove an element from the right hand end of a vector.

Vectors are arranged with increasing indicies at increasing memory addresses, so this is an O(1) operation

Parameters

[out] o the removed element is copied here from the vector

Returns: 1 on success, 0 on failure (ie if the vector was empty)

◆ cr8r_vec_pushl()

bool cr8r_vec_pushl	(	cr8r_vec *	,
		cr8r_vec_ft *	,
		const void *	e
	)

Add an element to the left hand end of a vector.

This is an O(n) operation because vectors are arranged with increasing indicies at increasing memory addresses.

Parameters

[in] e the element to add, which is copied from this pointer into the vector

Returns: 1 on success, 0 on failure

◆ cr8r_vec_popl()

bool cr8r_vec_popl	(	cr8r_vec *	,
		cr8r_vec_ft *	,
		void *	o
	)

Remove an element from the left hand end of a vector.

This is an O(n) operation because vectors are arranged with increasing indicies at increasing memory addresses.

Parameters

[out] o the removed element is copied here from the vector

Returns: 1 on success, 0 on failure (ie if the vector was empty)

◆ cr8r_vec_filter()

bool cr8r_vec_filter	(	cr8r_vec *	,
		cr8r_vec_ft *	,
		cr8r_vec_pred	pred,
		void *	data
	)

Filter a vector in-place.

ft->del is called on elements that fail the predicate, if applicable

Parameters

[in]	pred	predicate to check elements with
[in]	data	reentrant data to pass to the predicate

Returns: 1 on success, 0 on failure (memory allocation, shouldn't happen unless ft->resize can fail to shrink)

◆ cr8r_vec_filtered()

bool cr8r_vec_filtered	(	cr8r_vec *	dest,
		const cr8r_vec *	src,
		cr8r_vec_ft *	,
		cr8r_vec_pred	pred,
		void *	data
	)

Create a new vector as a subsequence matching a predicate.

dest should NOT be initialized or its buffer will be leaked! Iterate over the elements of a vector and copy them into a new vector if they match the predicate. ft->copy function is called if applicable.

Parameters

[out]	dest	vector to fill with filtered subsequence, should have a cap of 0 or valid buffer
[in]	src	vector to copy filtered sequence from
[in]	pred	predicate to check elements with
[in]	data	reentrant data to pass to the predicate

Returns: 1 on success, 0 on failure (allocation failure)

◆ cr8r_vec_map()

bool cr8r_vec_map	(	cr8r_vec *	dest,
		const cr8r_vec *	src,
		cr8r_vec_ft *	src_ft,
		cr8r_vec_ft *	dest_ft,
		cr8r_vec_mapper	f,
		void *	data
	)

Create a new vector by applying a transformation function to each element.

dest should NOT be initialized or its buffer will be leaked! This creates a new vector, whose element type and entire function table may be different. The transformation funtion also must perform any relevant work that ft->copy would have to, since the output element type is not necessarily the same as the input element type.

Parameters

[out]	dest	vector to fill with outputs of transformation function, should have a cap of 0 or valid buffer
[in]	src	vector of elements to pass to the transformation function
[in]	src_ft	function table for src vector cr8r_vec_ft
[in]	dest_ft	function table for dest vector cr8r_vec_ft
[in]	f	transformation function. The first argument, o, is a pointer to the element in the destination vector to output to, and the second argument, e, is a pointer to the element in the source vector to read from
[in]	data	reentrant data to pass to the transformation function

Returns: 1 on success, 0 on failure (allocation failure)

◆ cr8r_vec_forEachPermutation()

int cr8r_vec_forEachPermutation	(	cr8r_vec *	,
		cr8r_vec_ft *	,
		void()(const cr8r_vec , const cr8r_vec_ft , void data)	f,
		void *	data
	)

Execute a function on every permutation of a vector.

The vector is actually permuted in place using Heap's algorithm, and ends at the "last" permutation without being restored.

Parameters

[in]	f	callback function
[in,out]	data	reentrant data to pass to the callback, can provide input, output, and persistant state without needing to hijack ft->base.data or similar

Returns: 1 on success, 0 on failure (if an array of self->len uint64_t's cannot be allocated)

◆ cr8r_vec_combine()

bool cr8r_vec_combine	(	cr8r_vec *	dest,
		const cr8r_vec *	src_a,
		const cr8r_vec *	src_b,
		cr8r_vec_ft *
	)

Create a new vector by concatenating copies of two given vectors.

dest should NOT be initialized or its buffer will be leaked! First, ensures the dest buffer has enough capacity for both src vectors, extending if necessary, then copy the vectors one after the other. ft->copy is called if applicable

Parameters

[out]	dest	vector in which to store result
[in]	src_a,src_b	vectors to copy elements from

Returns: 1 on success, 0 on failure (allocation failure)

◆ cr8r_vec_augment()

bool cr8r_vec_augment	(	cr8r_vec *	self,
		const cr8r_vec *	other,
		cr8r_vec_ft *
	)

Add a copy of another vector to a given vector.

First, extends self->buf if needed, then copy the other vector right after the current end. ft->copy is called if applicable

Parameters

[in,out]	self	vector to extend with a copy of the other vector
[in]	other	vector to copy from

Returns: 1 on success, 0 on failure (allocation failure)

◆ cr8r_vec_ensure_cap()

bool cr8r_vec_ensure_cap	(	cr8r_vec *	self,
		cr8r_vec_ft *	ft,
		uint64_t	cap
	)

Expand a vector's internal storage if needed to fit a given capacity Will not reallocate if self->cap >= cap already Otherwise, try to get a size hint from ft->new_size, but falls back if this is still < cap.

Returns: 1 on success, 0 on failure (allocation failure)

◆ cr8r_vec_all()

bool cr8r_vec_all	(	const cr8r_vec *	,
		const cr8r_vec_ft *	,
		cr8r_vec_pred	pred,
		void *	data
	)

Test if a predicate holds for all elements in a vector.

Returns false immediately if any element does not satisfy the predicate.

Parameters

[in]	pred	predicate function, called on each element in the vector
[in,out]	data	reentrant data to pass to pred

Returns: 1 if the predicate function returns 1 on all elements, 0 (as soon as it doesn't) otherwise

◆ cr8r_vec_any()

bool cr8r_vec_any	(	const cr8r_vec *	,
		const cr8r_vec_ft *	,
		cr8r_vec_pred	pred,
		void *	data
	)

Test if a predicate holds for any element in a vector.

Returns true immediately if any element satisfies the predicate. Note that this is completely equivalent to the negation of cr8r_vec_all with the negation of the predicate.

Parameters

[in]	pred	predicate function, called on each element in the vector
[in,out]	data	reentrant data to pass to pred

Returns: 1 (as soon as) the predicate function returns 1 on any element, 0 if it returns 0 on all of them

◆ cr8r_vec_contains()

bool cr8r_vec_contains	(	const cr8r_vec *	,
		const cr8r_vec_ft *	,
		const void *	e
	)

Check if a vector contains a given element.

This is O(n) because it does not assume a sorted vector and simply does a linear search. See cr8r_vec_containss for a binary search version that does require a sorted vector.

Parameters

[in] e element to search for (using ft->cmp)

Returns: 1 if the vector contains the element, 0 otherwise

◆ cr8r_vec_index()

int64_t cr8r_vec_index	(	const cr8r_vec *	,
		const cr8r_vec_ft *	,
		const void *	e
	)

Get the first index of an element in a vector.

This is O(n) because it does not assume a sorted vector and simply does a linear search. See cr8r_vec_indexs for a binary search version that does require a sorted vector. Returns -1 on failure.

Parameters

[in] e element to search for (using ft->cmp)

Returns: the index of the element if it is in the vector, or -1 otherwise

◆ cr8r_vec_exm()

void* cr8r_vec_exm	(	cr8r_vec *	,
		const cr8r_vec_ft *	,
		int	ord
	)

Find the extremal (minimum or maximum) element of a vector.

Parameters

[in] ord 1 for minimum or -1 for maximum

Returns: a pointer to the extremal element, or NULL if the vector is empty

◆ cr8r_vec_foldr()

void* cr8r_vec_foldr	(	const cr8r_vec *	,
		const cr8r_vec_ft *	,
		cr8r_vec_accumulator	f,
		void *	init
	)

Perform a right fold on a vector.

Given an initial accumulator value of some type T in a void pointer, a vector, and a function that takes a void pointer to a T value and an element of the vector and returns a void pointer to a T value, this function repeatedly applies that function to the current accumulator value and vector element to get the new accumulator value. This is repeated for every element in the vector, going from left to right (low indices to high), and the final accumulator value is returned. The accumulation function must handle freeing old accumulator values once it is finished with them if necessary.

Parameters

[in]	init	starting value for the accumulator
[in]	f	accumulation function: should take current accumulator value (as void pointer) and current vector element and return new accumulator value. It should either modify the accumulator value in place, returning it as well, or allocate a new pointer for the new accumulator value and free the old one once the new one has been computed. In cases where the accumulator value is an integer or something else that fits within a pointer, the pointer can be used as a casted integer or whatnot instead of as a pointer.

Returns: the final accumulator value

◆ cr8r_vec_foldl()

void* cr8r_vec_foldl	(	const cr8r_vec *	,
		const cr8r_vec_ft *	,
		cr8r_vec_accumulator	f,
		void *	init
	)

Perform a left fold on a vector.

Exactly the same as cr8r_vec_foldr except vector entries are processed from right to left (high indices to low) instead of left to right (low to high).

Parameters

[in]	init	starting value for the accumulator
[in]	f	accumulation function

Returns: the final accumulator value

◆ cr8r_vec_sort()

void cr8r_vec_sort	(	cr8r_vec *	,
		cr8r_vec_ft *
	)

Sort a vector in-place according to ft->cmp.

Currently uses heapsort, so average and worst case time complexities are both O(n*log(n)).

◆ cr8r_vec_sorted()

bool cr8r_vec_sorted	(	cr8r_vec *	dest,
		const cr8r_vec *	src,
		cr8r_vec_ft *
	)

Create a sorted copy of a vector.

Simply calls cr8r_vec_copy followed by cr8r_vec_sort on the copy

Parameters

[out]	dest	the vector to copy to and sort
[in]	src	the vector to copy from

Returns: 1 on success, 0 on failure (memory allocation failure)

◆ cr8r_vec_reversed()

bool cr8r_vec_reversed	(	cr8r_vec *	dest,
		const cr8r_vec *	src,
		cr8r_vec_ft *
	)

Create a reversed copy of a vector.

dest should NOT be initialized or its buffer will be leaked! copies elements in reverse order, using ft->copy if applicable

Parameters

[out]	dest	the vector to store the reversed copy in
[in]	src	the vector to create a reversed copy from

Returns: 1 on success, 0 on failure (memory allocation failure)

◆ cr8r_vec_containss()

bool cr8r_vec_containss	(	const cr8r_vec *	,
		const cr8r_vec_ft *	,
		const void *	e
	)

Check if a sorted vector contains an element.

The vector should be in ascending order according to ft->cmp. Uses binary search, so the average and worst case time complexities are O(log(n)). If the elements are sorted and belong to some known distribution, some form of interpolation seach could work even faster, but this is best implemented as a custom function.

Parameters

[in] e element to search for (using ft->cmp)

Returns: 1 if the vector contains the element, 0 otherwise

◆ cr8r_vec_indexs()

int64_t cr8r_vec_indexs	(	const cr8r_vec *	,
		const cr8r_vec_ft *	,
		const void *	e
	)

Get the index of an element in a sorted vector.

The vector should be in ascending order according to ft->cmp. If there are multiple elements which compare equal to the query, the index of any one of them may be returned. Uses binary search, so the average and worst case time complexities are O(log(n)). If the elements are sorted and belong to some known distribution, some form of interpolation seach could work even faster, but this is best implemented as a custom function.

Parameters

[in] e element to search for (using ft->cmp)

Returns: index of the element in the vector, or -1 if not present

◆ cr8r_vec_first_gts()

int64_t cr8r_vec_first_gts	(	const cr8r_vec *	,
		const cr8r_vec_ft *	,
		const void *	e
	)

Get the index of the first element greater than a given key in a sorted vector.

The vector should be in ascending order according to ft->cmp. Uses binary search, so the average and worst case time complexities are O(log(n)). If the elements are sorted and belong to some known distribution, some form of interpolation seach could work even faster, but this is best implemented as a custom function.

Parameters

[in] e element to search for (using ft->cmp)

Returns: index of the element in the vector, or -1 if not present

◆ cr8r_vec_first_ges()

int64_t cr8r_vec_first_ges	(	const cr8r_vec *	,
		const cr8r_vec_ft *	,
		const void *	e
	)

Get the index of the first element greater than or equal to a given key in a sorted vector.

The vector should be in ascending order according to ft->cmp. Uses binary search, so the average and worst case time complexities are O(log(n)). If the elements are sorted and belong to some known distribution, some form of interpolation seach could work even faster, but this is best implemented as a custom function.

Parameters

[in] e element to search for (using ft->cmp)

Returns: index of the element in the vector, or -1 if not present

◆ cr8r_vec_last_lts()

int64_t cr8r_vec_last_lts	(	const cr8r_vec *	,
		const cr8r_vec_ft *	,
		const void *	e
	)

Get the index of the last element less than a given key in a sorted vector.

The vector should be in ascending order according to ft->cmp. Uses binary search, so the average and worst case time complexities are O(log(n)). If the elements are sorted and belong to some known distribution, some form of interpolation seach could work even faster, but this is best implemented as a custom function.

Parameters

[in] e element to search for (using ft->cmp)

Returns: index of the element in the vector, or -1 if not present

◆ cr8r_vec_last_les()

int64_t cr8r_vec_last_les	(	const cr8r_vec *	,
		const cr8r_vec_ft *	,
		const void *	e
	)

Get the index of the last element greater than a given key in a sorted vector.

The vector should be in ascending order according to ft->cmp. Uses binary search, so the average and worst case time complexities are O(log(n)). If the elements are sorted and belong to some known distribution, some form of interpolation seach could work even faster, but this is best implemented as a custom function.

Parameters

[in] e element to search for (using ft->cmp)

Returns: index of the element in the vector, or -1 if not present

◆ cr8r_vec_cmp()

int cr8r_vec_cmp	(	const cr8r_vec *	a,
		const cr8r_vec *	b,
		const cr8r_vec_ft *
	)

Lexicographically compare two vectors.

Parameters

[in] a,b vectors to compare

Returns: -1 if a is lexicographically before b, +1 visa versa, or 0 if they are equal

◆ cr8r_vec_pivot_m3()

void* cr8r_vec_pivot_m3	(	const cr8r_vec *	,
		cr8r_vec_ft *	,
		uint64_t	a,
		uint64_t	b
	)

Pick a pivot for cr8r_vec_partition using the median of 3 approach.

This is an O(1) pivot selection algorithm that can cause quicksort/quickselect to perform badly (O(n**2)) in pathological cases, but most of the time works very well (O(n*log(n)) and faster than cr8r_vec_pivot_mm in practice most of the time). Picks the median of the first, middle (rounded down), and last elements. In the event of ties, which valid element is chosen is not specified, but is consistent for the same elements. The vector is not modified

Parameters

[in] a,b inclusive, exclusive indices of the subrange to pick a pivot for

Returns: a pointer to the selected pivot, or NULL if a and b are not valid subrange indices for the given vector.

◆ cr8r_vec_pivot_mm()

void* cr8r_vec_pivot_mm	(	cr8r_vec *	,
		cr8r_vec_ft *	,
		uint64_t	a,
		uint64_t	b
	)

Pick a pivot for cr8r_vec_partition using the median of medians approach.

This is an O(n) pivot selection algorithm that ensures quicksort/quickselect will always run in O(n*log(n)) time. However, because the entire subrange is processed, this will often end up slower than cr8r_vec_pivot_m3. The reason median of medians ensures quicksort/quickselect will finish in O(n*log(n)) time is because it will select a pivot whose index is within a certain ratio of the median (eg if the subrange has k elements then the pivot selected will be one of the central a*k elements for some small fixed coefficient). The median of medians algorithm used does not allocate extra space, but the order of the given subrange is not preserved. Picks the median of the first, middle (rounded down), and last elements. In the event of ties, which valid element is chosen is not specified, but is consistent for the same elements. The vector to pick a pivot for (a subrange of), will be reordered in place, but only within the given subrange

Parameters

[in] a,b inclusive, exclusive indices of the subrange to pick a pivot for

Returns: a pointer to the selected pivot, or NULL if a and b are not valid subrange indices for the given vector. because the target subrange is reordered so the algorithm can run in place, the pivot will always end up at index a, but this should not be relied on.

◆ cr8r_vec_partition()

void* cr8r_vec_partition	(	cr8r_vec *	,
		cr8r_vec_ft *	,
		uint64_t	a,
		uint64_t	b,
		void *	piv
	)

Partition a subrange of a vector into elements < a pivot and elements >= a pivot.

The given subrange is rearranged so that all elements before the pivot are < the pivot and all elements >= the pivot are after the pivot, and a pointer to the pivot is returned the vector has its relevant subrange reordered in place

Parameters

[in]	a,b	inclusive, exclusive bounds of subrange (ie, consider elements [a, b))
[in]	piv	a pointer to the pivot

Returns: pointer to the pivot, which was placed after all elements < itself but before all other elements >= itself

◆ cr8r_vec_partition_with_median()

void* cr8r_vec_partition_with_median	(	cr8r_vec *	,
		cr8r_vec_ft *	,
		uint64_t	a,
		uint64_t	b,
		void *	piv
	)

Partition a subrange of a vector into elements <, ==, and > a pivot.

The given subrange is rearranged so that all elements < the pivot occur first, followed by all elements == the pivot (including the pivot), then finally all elements

the pivot. A pointer to the ending position of the pivot is returned.

Notice in particular that if piv is the ith element in sorted order, calling this function will actually place that element (or an == one) at the ith index, with the subrange arranged into a <, ==, and > block as just described the vector has its relevant subrange reordered in place

Parameters

[in]	a,b	inclusive, exclusive bounds of subrange (ie, consider elements [a, b))
[in]	piv	a pointer to the pivot (usually obtained from cr8r_vec_ith)

Returns: pointer to the pivot, which was moved to somewhere in the == block

◆ cr8r_vec_ith()

void* cr8r_vec_ith	(	cr8r_vec *	,
		cr8r_vec_ft *	,
		uint64_t	a,
		uint64_t	b,
		uint64_t	i
	)

Find the ith element of a subrange of a vector without completely sorting it.

The given subrange is partitioned in place, but the quickselect algorithm is used rather than sorting so the expected running time is linear. Using median of medians would guarantee linear time, but median of 3 is good enough most of the time. The vector to find ith element of may be reoredered.

Parameters

[in]	a,b	inclusive, exclusive bounds of subrange
[in]	i	index to find. For example, 0 finds the smallest element, 1 the second smallest, and so on.

◆ cr8r_default_acc_sum_u64()

void* cr8r_default_acc_sum_u64	(	const cr8r_vec_ft *	,
		void *	acc,
		const void *	ent
	)

Callback for cr8r_vec_foldr to sum up elements in vector.

The acc argument is treated as a uint64_t, NOT a pointer to uint64_t. Thus the call can be (uint64_t)cr8r_vec_foldr(self, ft, (void*)0, cr8r_default_acc_sum_u64).

◆ cr8r_default_acc_sumpowmod_u64()

void* cr8r_default_acc_sumpowmod_u64	(	const cr8r_vec_ft *	,
		void *	acc,
		const void *	ent
	)

Callback for cr8r_vec_foldr to sum up powers of elements in a vector mod a number.

The acc argument MUST be a pointer to three consecutive uint64_t's: the accumulator, the exponent, and the modulus, respectively. The same pointer is returned: the accumulator is modified in place.

Variable Documentation

◆ cr8r_vecft_u64

cr8r_vec_ft cr8r_vecft_u64

extern

Function table for vectors of uint64_t's.

Trivial copy/swap and cr8r_default_cmp_u64 are used, plus the default allocation scheme cr8r_default_new_size and cr8r_default_resize.

◆ cr8r_vecft_cstr

cr8r_vec_ft cr8r_vecft_cstr

extern

Function table for vectors of strings.

Strings are null-terminated and "owned" by the vector. Trivial swap, strdup copy, cr8r_default_cmp_cstr, and cr8r_default_free. The default allocation scheme of cr8r_default_new_size and cr8r_default_resize is used for the vector itself.

◆ cr8r_vecft_u8

cr8r_vec_ft cr8r_vecft_u8

extern

Function table for vectors of uint8_t's, which can be used as smart strings.

Trivial copy/swap and cr8r_default_cmp_u8 are used, plus the default allocation scheme cr8r_default_new_size and cr8r_default_resize.

Detailed Description

Data Structures

Macros

Typedefs

Functions

Variables

Typedef Documentation

◆ cr8r_vec_pred

◆ cr8r_vec_mapper

◆ cr8r_vec_accumulator

Function Documentation

◆ cr8r_vec_ft_init()

◆ cr8r_vec_init()

◆ cr8r_vec_delete()

◆ cr8r_vec_copy()

◆ cr8r_vec_sub()

◆ cr8r_vec_resize()

◆ cr8r_vec_trim()

◆ cr8r_vec_clear()

◆ cr8r_vec_shuffle()

◆ cr8r_vec_get()

◆ cr8r_vec_getx()

◆ cr8r_vec_len()

◆ cr8r_vec_pushr()

◆ cr8r_vec_popr()

◆ cr8r_vec_pushl()

◆ cr8r_vec_popl()

◆ cr8r_vec_filter()

◆ cr8r_vec_filtered()

◆ cr8r_vec_map()

◆ cr8r_vec_forEachPermutation()

◆ cr8r_vec_combine()

◆ cr8r_vec_augment()

◆ cr8r_vec_ensure_cap()

◆ cr8r_vec_all()

◆ cr8r_vec_any()

◆ cr8r_vec_contains()

◆ cr8r_vec_index()

◆ cr8r_vec_exm()

◆ cr8r_vec_foldr()

◆ cr8r_vec_foldl()

◆ cr8r_vec_sort()

◆ cr8r_vec_sorted()

◆ cr8r_vec_reversed()

◆ cr8r_vec_containss()

◆ cr8r_vec_indexs()

◆ cr8r_vec_first_gts()

◆ cr8r_vec_first_ges()

◆ cr8r_vec_last_lts()

◆ cr8r_vec_last_les()

◆ cr8r_vec_cmp()

◆ cr8r_vec_pivot_m3()

◆ cr8r_vec_pivot_mm()

◆ cr8r_vec_partition()

◆ cr8r_vec_partition_with_median()

◆ cr8r_vec_ith()

◆ cr8r_default_acc_sum_u64()

◆ cr8r_default_acc_sumpowmod_u64()

Variable Documentation

◆ cr8r_vecft_u64

◆ cr8r_vecft_cstr

◆ cr8r_vecft_u8