Vector

Collaboration diagram for Vector:

Files
file	vlc_vector.h
	This provides convenience helpers for vectors.

Macros
#define	VLC_VECTOR(type)
	Vector struct body.
#define	VLC_VECTOR_INITIALIZER   { 0, 0, NULL }
	Static initializer for a vector.
#define	vlc_vector_init(pv)
	Initialize an empty vector.
#define	vlc_vector_destroy(pv)    free((pv)->data)
	Destroy a vector.
#define	vlc_vector_clear(pv)
	Clear a vector.
#define	VLC_VECTOR_MINCAP_   ((size_t) 10)
	The minimal allocation size, in number of items.
#define	VLC_VECTOR_FAILFLAG_   (~(((size_t) -1) >> 1)) /* only the MSB */
#define	vlc_vector_realloc_(pv, newcap)
	Realloc the underlying array to newcap.
#define	vlc_vector_resize_(pv, newcap)
	Resize the vector to newcap exactly.
#define	vlc_vector_max_cap_(pv)   (SIZE_MAX / 2 / sizeof(*(pv)->data))
#define	vlc_vector_reserve(pv, mincap)
	Increase the capacity of the vector to at least mincap.
#define	vlc_vector_reserve_internal_(pv, mincap)
#define	vlc_vector_shrink_to_fit(pv)
	Resize the vector so that its capacity equals its actual size.
#define	vlc_vector_autoshrink(pv)
	Resize the vector down automatically.
#define	vlc_vector_check_same_ptr_type_(a, b)    (void) ((a) == (b)) /* warn on type mismatch */
#define	vlc_vector_push(pv, item)
	Push an item at the end of the vector.
#define	vlc_vector_push_hole(pv, count)
	Push a hole at the end of the vector.
#define	vlc_vector_push_all(pv, items, count)    vlc_vector_push_all_internal_(pv, items, vlc_vector_enforce_size_t_(count))
	Append count items at the end of the vector.
#define	vlc_vector_push_all_internal_(pv, items, count)
#define	vlc_vector_insert_hole(pv, index, count)
	Insert an hole of size count to the given index.
#define	vlc_vector_insert_hole_internal_(pv, index, count)
#define	vlc_vector_insert(pv, index, item)
	Insert an item at the given index.
#define	vlc_vector_insert_all(pv, index, items, count)
	Insert count items at the given index.
#define	vlc_vector_move_slice(pv, index, count, target)
	Move a slice of items to a given target index.
#define	vlc_vector_move_slice_internal_(pv, index, count, target)
#define	vlc_vector_move(pv, index, target)    vlc_vector_move_slice(pv, index, 1, target)
	Move an item to a given target index.
#define	vlc_vector_remove_slice_noshrink(pv, index, count)
	Remove a slice of items, without shrinking the array.
#define	vlc_vector_remove_slice_noshrink_internal_(pv, index, count)
#define	vlc_vector_remove_slice(pv, index, count)
	Remove a slice of items.
#define	vlc_vector_remove_noshrink(pv, index)    vlc_vector_remove_slice_noshrink(pv, index, 1)
	Remove an item, without shrinking the array.
#define	vlc_vector_remove(pv, index)
	Remove an item.
#define	vlc_vector_swap_remove(pv, index)
	Remove an item.
#define	vlc_vector_index_of(pv, item, pidx)
	Return the index of an item.
#define	vlc_vector_foreach(item, pv)
	For-each loop.
#define	vlc_vector_foreach_ref(ref, pv)
	For-each loop with a reference iterator.
#define	vlc_vector_last(pv)
	Returns the vector's last element.
#define	vlc_vector_last_ref(pv)
	Returns a reference on the vector's last element.

Functions
static size_t	vlc_vector_min_ (size_t a, size_t b)
static size_t	vlc_vector_max_ (size_t a, size_t b)
static size_t	vlc_vector_between_ (size_t x, size_t min, size_t max)
static size_t	vlc_vector_enforce_size_t_ (size_t value)
static void *	vlc_vector_reallocdata_ (void *ptr, size_t count, size_t size, size_t *restrict pcap, size_t *restrict psize)
	Realloc data and update vector fields.
static bool	vlc_vector_test_and_reset_failflag_ (size_t *pcap)
	Test and reset the fail flag.
static size_t	vlc_vector_growsize_ (size_t value)
static void	vlc_vector_reverse_array_ (char *array, size_t len)
	Reverse a char array in place.
static void	vlc_vector_rotate_array_left_ (char *array, size_t len, size_t distance)
	Right-rotate a (char) array in place.
static void	vlc_vector_rotate_array_right_ (char *array, size_t len, size_t distance)
	Right-rotate a (char) array in place.
static void	vlc_vector_move_ (char *array, size_t index, size_t count, size_t target)
	Move items in a (char) array in place.

Detailed Description

Macro Definition Documentation

VLC_VECTOR

#define VLC_VECTOR

(

type

)

Value:

{ \
    size_t cap; \
    size_t size; \
    type *data; \
}

Vector struct body.

A vector is a dynamic array, managed by the vlc_vector_* helpers.

It is generic over the type of its items, so it is implemented as macros.

To use a vector, a new type must be defined:

struct vec_int VLC_VECTOR(int);

The struct may be anonymous:

struct VLC_VECTOR(const char *) names;

It is convenient to define a typedef to an anonymous structure:

typedef struct VLC_VECTOR(int) vec_int_t;

Vector size is accessible via vec.size, and items are intended to be accessed directly, via vec.data[i].

Functions and macros having name ending with '_' are private.

vlc_vector_autoshrink

#define vlc_vector_autoshrink

(

pv

)

Value:

(void) \
( \
    (pv)->cap <= VLC_VECTOR_MINCAP_ /* do not shrink to tiny length */ || \
    (pv)->cap < vlc_vector_growsize_((pv)->size+5) /* no need to shrink */ || \
    vlc_vector_resize_(pv, vlc_vector_max_((pv)->size+5, VLC_VECTOR_MINCAP_)) \
)

Resize the vector down automatically.

Shrink only when necessary (in practice when cap > (size+5)*1.5)

Parameters

pv	a pointer to the vector

vlc_vector_check_same_ptr_type_

#define vlc_vector_check_same_ptr_type_	(		a,
			b
	)		(void) ((a) == (b)) /* warn on type mismatch */

vlc_vector_clear

#define vlc_vector_clear

(

pv

)

Value:

( \
    /* cannot be implemented as do-while(0), called from vlc_vector_resize_() */ \
    vlc_vector_destroy(pv), \
    vlc_vector_init(pv) \
)

Clear a vector.

Remove all items from the vector.

vlc_vector_destroy

#define vlc_vector_destroy

(

pv

)

free((pv)->data)

Destroy a vector.

The vector may not be used anymore unless vlc_vector_init() is called.

VLC_VECTOR_FAILFLAG_

#define VLC_VECTOR_FAILFLAG_   (~(((size_t) -1) >> 1)) /* only the MSB */

vlc_vector_foreach

#define vlc_vector_foreach	(		item,
			pv
	)

Value:

    for (size_t vlc_vector_idx_##item = 0; \
         vlc_vector_idx_##item < (pv)->size && \
             ((item) = (pv)->data[vlc_vector_idx_##item], true); \
         ++vlc_vector_idx_##item)

For-each loop.

Use only for vectors of primitive types or pointers (every struct would be copied for a vector of structs).

Parameters

[out]	item	the iteration variable
[out]	pv	a pointer to the vector

vlc_vector_foreach_ref

#define vlc_vector_foreach_ref	(		ref,
			pv
	)

Value:

    for (size_t vlc_vector_idx_##ref = 0; \
         vlc_vector_idx_##ref < (pv)->size && \
             ((ref) = &(pv)->data[vlc_vector_idx_##ref], true); \
         ++vlc_vector_idx_##ref)

For-each loop with a reference iterator.

Should be used for vector holding non-trivially copyable data.

Parameters

[out]	ref	The reference iterator
[in]	pv	a pointer to the vector

vlc_vector_index_of

#define vlc_vector_index_of	(		pv,
			item,
			pidx
	)

Value:

    do { \
        ssize_t *out = pidx; /* warning/error on type mismatch */ \
        size_t vlc_vector_find_idx_; \
        for (vlc_vector_find_idx_ = 0; \
             vlc_vector_find_idx_ < (pv)->size; \
             ++vlc_vector_find_idx_) \
            if ((pv)->data[vlc_vector_find_idx_] == (item)) \
                break; \
        *out = vlc_vector_find_idx_ == (pv)->size ? -1 : \
            (ssize_t) vlc_vector_find_idx_; \
    } while (0)

Return the index of an item.

Iterate over all items to find a given item.

Use only for vectors of primitive types or pointers.

The result is written to *(pidx):

• the index of the item if it is found;
• -1 if it is not found.

Parameters

	pv	a pointer to the vector
	item	the item to find (compared with ==)
[out]	pidx	a pointer to the result (ssize_t *)

vlc_vector_init

#define vlc_vector_init

(

pv

)

Value:

(void) \
( \
    /* cannot be implemented as do-while(0), called from vlc_vector_clear() */ \
    (pv)->cap = 0, \
    (pv)->size = 0, \
    (pv)->data = NULL \
)

Initialize an empty vector.

VLC_VECTOR_INITIALIZER

#define VLC_VECTOR_INITIALIZER   { 0, 0, NULL }

Static initializer for a vector.

vlc_vector_insert

#define vlc_vector_insert	(		pv,
			index,
			item
	)

Value:

( \
    vlc_vector_insert_hole(pv, index, 1) && \
    ( \
        (pv)->data[index] = (item), \
        true \
    ) \
)

Insert an item at the given index.

The items in range [index; size-1] will be moved.

Parameters

pv	a pointer to the vector
index	the index where the item is to be inserted
item	the item to append

Return values

true	if no allocation failed
false	on allocation failure (the vector is left untouched)

vlc_vector_insert_all

#define vlc_vector_insert_all	(		pv,
			index,
			items,
			count
	)

Value:

( \
    vlc_vector_check_same_ptr_type_((pv)->data, items), \
    vlc_vector_insert_hole(pv, index, count) && \
    ( \
        memcpy(&(pv)->data[index], items, (count) * sizeof(*(pv)->data)), \
        true \
    ) \
)

Insert count items at the given index.

The items in range [index; size-1] will be moved.

Parameters

pv	a pointer to the vector
index	the index where the items are to be inserted
items	the items array to append
count	the number of items in the array

Return values

true	if no allocation failed
false	on allocation failure (the vector is left untouched)

vlc_vector_insert_hole

#define vlc_vector_insert_hole	(		pv,
			index,
			count
	)

Value:

    vlc_vector_insert_hole_internal_(pv, vlc_vector_enforce_size_t_(index), \
                                     vlc_vector_enforce_size_t_(count))

Insert an hole of size count to the given index.

The items in range [index; size-1] will be moved. The items in the hole are left uninitialized.

Parameters

pv	a pointer to the vector
index	the index where the hole is to be inserted
count	the number of items in the hole

Return values

true	if no allocation failed
false	on allocation failure (the vector is left untouched)

vlc_vector_insert_hole_internal_

#define vlc_vector_insert_hole_internal_	(		pv,
			index,
			count
	)

Value:

( \
    assert(count), \
    vlc_vector_reserve(pv, (pv)->size + (count)) && \
    ( \
        (index) == (pv)->size || \
        ( \
            memmove(&(pv)->data[(index) + (count)], \
                    &(pv)->data[index], \
                    ((pv)->size - (index)) * sizeof(*(pv)->data)), \
            true \
        ) \
    ) && \
    ( \
        (pv)->size += (count), \
        true \
    ) \
)

vlc_vector_last

#define vlc_vector_last

(

pv

)

Value:

( \
    assert((pv)->size != 0), \
    (pv)->data[(pv)->size - 1] \
)

Returns the vector's last element.

vlc_vector_last_ref

#define vlc_vector_last_ref

(

pv

)

Value:

( \
    assert((pv)->size != 0), \
    &(pv)->data[(pv)->size - 1] \
)

Returns a reference on the vector's last element.

vlc_vector_max_cap_

#define vlc_vector_max_cap_

(

pv

)

(SIZE_MAX / 2 / sizeof(*(pv)->data))

VLC_VECTOR_MINCAP_

#define VLC_VECTOR_MINCAP_   ((size_t) 10)

The minimal allocation size, in number of items.

Private.

vlc_vector_move

#define vlc_vector_move	(		pv,
			index,
			target
	)		vlc_vector_move_slice(pv, index, 1, target)

Move an item to a given target index.

The items will be moved so that its new position is target.

Parameters

pv	a pointer to the vector
index	the index of the item to move
target	the new index of the moved item

vlc_vector_move_slice

#define vlc_vector_move_slice	(		pv,
			index,
			count,
			target
	)

Value:

    vlc_vector_move_slice_internal_(pv, \
                                    vlc_vector_enforce_size_t_(index), \
                                    vlc_vector_enforce_size_t_(count), \
                                    vlc_vector_enforce_size_t_(target))

Move a slice of items to a given target index.

The items in range [index; count] will be moved so that the new position of the first item is target.

Parameters

pv	a pointer to the vector
index	the index of the first item to move
count	the number of items to move
target	the new index of the moved slice

vlc_vector_move_slice_internal_

#define vlc_vector_move_slice_internal_	(		pv,
			index,
			count,
			target
	)

Value:

    vlc_vector_move_((char *) (pv)->data, \
                     (index) * sizeof((pv)->data[0]), \
                     (count) * sizeof((pv)->data[0]), \
                     (target) * sizeof((pv)->data[0]))

vlc_vector_push

#define vlc_vector_push	(		pv,
			item
	)

Value:

( \
    vlc_vector_reserve(pv, (pv)->size + 1) && \
    ( \
        (pv)->data[(pv)->size++] = (item), \
        true \
    ) \
)

Push an item at the end of the vector.

The amortized complexity is O(1).

Parameters

pv	a pointer to the vector
item	the item to append

Return values

true	if no allocation failed
false	on allocation failure (the vector is left untouched)

vlc_vector_push_all

#define vlc_vector_push_all	(		pv,
			items,
			count
	)		vlc_vector_push_all_internal_(pv, items, vlc_vector_enforce_size_t_(count))

Append count items at the end of the vector.

Parameters

pv	a pointer to the vector
items	the items array to append
count	the number of items in the array

Return values

true	if no allocation failed
false	on allocation failure (the vector is left untouched)

vlc_vector_push_all_internal_

#define vlc_vector_push_all_internal_	(		pv,
			items,
			count
	)

Value:

( \
    assert(count), \
    vlc_vector_check_same_ptr_type_((pv)->data, items), \
    vlc_vector_reserve(pv, (pv)->size + (count)) && \
    ( \
        memcpy(&(pv)->data[(pv)->size], items, (count) * sizeof(*(pv)->data)), \
        (pv)->size += (count), \
        true \
    ) \
)

vlc_vector_push_hole

#define vlc_vector_push_hole	(		pv,
			count
	)

Value:

( \
    vlc_vector_reserve(pv, (pv)->size + vlc_vector_enforce_size_t_(count)) && \
    ( \
        (pv)->size += vlc_vector_enforce_size_t_(count), \
        true \
    ) \
)

Push a hole at the end of the vector.

The amortized complexity is O(1). The items in the hole are left uninitialized and can be accessed in the range [size-count; size-1].

Parameters

pv	a pointer to the vector
count	the number of items in the hole

Return values

true	if no allocation failed
false	on allocation failure (the vector is left untouched)

vlc_vector_realloc_

#define vlc_vector_realloc_	(		pv,
			newcap
	)

Value:

( \
    (pv)->data = vlc_vector_reallocdata_((pv)->data, newcap, \
                                         sizeof(*(pv)->data), \
                                         &(pv)->cap, &(pv)->size), \
    !vlc_vector_test_and_reset_failflag_(&(pv)->cap) \
)

Realloc the underlying array to newcap.

Private.

Parameters

pv	a pointer to the vector
newcap	(size_t) the requested size

Return values

true	if no allocation failed
false	on allocation failure (the vector is left untouched)

vlc_vector_remove

#define vlc_vector_remove	(		pv,
			index
	)

Value:

    do { \
        vlc_vector_remove_noshrink(pv, index); \
        vlc_vector_autoshrink(pv); \
    } while (0)

Remove an item.

The items in range [index+1; size-1] will be moved.

Parameters

pv	a pointer to the vector
index	the index of item to remove

vlc_vector_remove_noshrink

#define vlc_vector_remove_noshrink	(		pv,
			index
	)		vlc_vector_remove_slice_noshrink(pv, index, 1)

Remove an item, without shrinking the array.

If you have no good reason to use the _noshrink() version, use vlc_vector_remove() instead.

The items in range [index+1; size-1] will be moved.

Parameters

pv	a pointer to the vector
index	the index of item to remove

vlc_vector_remove_slice

#define vlc_vector_remove_slice	(		pv,
			index,
			count
	)

Value:

    do { \
        vlc_vector_remove_slice_noshrink(pv, index, count); \
        vlc_vector_autoshrink(pv); \
    } while (0)

Remove a slice of items.

The items in range [index+count; size-1] will be moved.

Parameters

pv	a pointer to the vector
index	the index of the first item to remove
count	the number of items to remove

vlc_vector_remove_slice_noshrink

#define vlc_vector_remove_slice_noshrink	(		pv,
			index,
			count
	)

Value:

    vlc_vector_remove_slice_noshrink_internal_(pv, \
            vlc_vector_enforce_size_t_(index), \
            vlc_vector_enforce_size_t_(count))

Remove a slice of items, without shrinking the array.

If you have no good reason to use the _noshrink() version, use vlc_vector_remove_slice() instead.

The items in range [index+count; size-1] will be moved.

Parameters

pv	a pointer to the vector
index	the index of the first item to remove
count	the number of items to remove

vlc_vector_remove_slice_noshrink_internal_

#define vlc_vector_remove_slice_noshrink_internal_	(		pv,
			index,
			count
	)

Value:

    do { \
        assert(count); \
        if ((index) + (count) < (pv)->size) \
            memmove(&(pv)->data[index], \
                    &(pv)->data[(index) + (count)], \
                    ((pv)->size - (index) - (count)) * sizeof(*(pv)->data)); \
        (pv)->size -= (count); \
    } while (0)

vlc_vector_reserve

#define vlc_vector_reserve	(		pv,
			mincap
	)

Value:

    /* avoid to allocate tiny arrays (< VLC_VECTOR_MINCAP_) */ \
    vlc_vector_reserve_internal_(pv, \
                                 vlc_vector_max_(mincap, VLC_VECTOR_MINCAP_))

Increase the capacity of the vector to at least mincap.

Parameters

pv	a pointer to the vector
mincap	(size_t) the requested capacity

Return values

true	if no allocation failed
false	on allocation failure (the vector is left untouched)

vlc_vector_reserve_internal_

#define vlc_vector_reserve_internal_	(		pv,
			mincap
	)

Value:

( \
    (mincap) <= (pv)->cap /* nothing to do */ || \
    ( \
        (mincap) <= vlc_vector_max_cap_(pv) /* not too big */ && \
        vlc_vector_realloc_(pv, \
                        /* multiply by 1.5, force between [mincap, maxcap] */ \
                        vlc_vector_between_(vlc_vector_growsize_((pv)->cap), \
                                            mincap, \
                                            vlc_vector_max_cap_(pv))) \
    ) \
)

vlc_vector_resize_

#define vlc_vector_resize_	(		pv,
			newcap
	)

Value:

( \
    (pv)->cap == (newcap) /* nothing to do */ || \
    ( \
        (newcap) > 0 ? vlc_vector_realloc_(pv, newcap) \
                     : (vlc_vector_clear(pv), true) \
    ) \
)

Resize the vector to newcap exactly.

If newcap is 0, the vector is cleared.

Private.

Parameters

pv	a pointer to the vector
newcap	(size_t) the requested capacity

Return values

true	if no allocation failed
false	on allocation failure (the vector is left untouched)

vlc_vector_shrink_to_fit

#define vlc_vector_shrink_to_fit

(

pv

)

Value:

    (void) /* decreasing the size may not fail */ \
    vlc_vector_resize_(pv, (pv)->size)

Resize the vector so that its capacity equals its actual size.

Parameters

pv	a pointer to the vector

vlc_vector_swap_remove

#define vlc_vector_swap_remove	(		pv,
			index
	)

Value:

    do { \
        (pv)->data[index] = (pv)->data[(pv)->size-1]; \
        (pv)->size--; \
    } while(0)

Remove an item.

The removed item is replaced by the last item of the vector.

This does not preserve ordering, but is O(1). This is useful when the order of items is not meaningful.

Parameters

pv	a pointer to the vector
index	the index of item to remove

Function Documentation

vlc_vector_between_()

static size_t vlc_vector_between_ ( size_t  x, size_t  min, size_t  max  )

inlinestatic

References vlc_vector_max_(), and vlc_vector_min_().

vlc_vector_enforce_size_t_()

static size_t vlc_vector_enforce_size_t_ ( size_t  value )

inlinestatic

vlc_vector_growsize_()

static size_t vlc_vector_growsize_ ( size_t  value )

inlinestatic

vlc_vector_max_()

static size_t vlc_vector_max_ ( size_t  a, size_t  b  )

inlinestatic

Referenced by vlc_vector_between_().

vlc_vector_min_()

static size_t vlc_vector_min_ ( size_t  a, size_t  b  )

inlinestatic

Referenced by vlc_vector_between_(), and vlc_vector_reallocdata_().

vlc_vector_move_()

static void vlc_vector_move_ ( char *  array, size_t  index, size_t  count, size_t  target  )

inlinestatic

Move items in a (char) array in place.

Move slice [index, count] to target.

References count, vlc_vector_rotate_array_left_(), and vlc_vector_rotate_array_right_().

vlc_vector_reallocdata_()

static void * vlc_vector_reallocdata_ ( void *  ptr, size_t  count, size_t  size, size_t *restrict  pcap, size_t *restrict  psize  )

inlinestatic

Realloc data and update vector fields.

On reallocation success, return the reallocated array and update the vector capacity and size.

On reallocation failure, return ptr, keep *psize untouched, and set the failflag in *pcap to indicate allocation failure (to be consumed by vlc_vector_test_and_reset_failflag_()).

This weird behavior allows to simultaneously:

• not require compiler extensions like "statement expressions"
• keep the vector data, size and capacity unchanged on reallocation failure
• not require output variables other than vector fields from the caller
• not violate the strict aliasing rules
• report the reallocation status (success or failure)

Private.

Parameters

	ptr	the current data to realloc
	count	the requested capacity, in number of items
	size	the size of one item
[in,out]	pcap	a pointer to the cap field of the vector
[in,out]	psize	a pointer to the size field of the vector

Returns

the reallocated array, or ptr if reallocation failed

References count, vlc_reallocarray(), VLC_VECTOR_FAILFLAG_, and vlc_vector_min_().

vlc_vector_reverse_array_()

static void vlc_vector_reverse_array_ ( char *  array, size_t  len  )

inlinestatic

Reverse a char array in place.

Referenced by vlc_vector_rotate_array_left_().

vlc_vector_rotate_array_left_()

static void vlc_vector_rotate_array_left_ ( char *  array, size_t  len, size_t  distance  )

inlinestatic

Right-rotate a (char) array in place.

For example, left-rotating a char array containing {1, 2, 3, 4, 5, 6} with distance 4 will result in {5, 6, 1, 2, 3, 4}.

Private.

References vlc_vector_reverse_array_().

Referenced by vlc_vector_move_(), and vlc_vector_rotate_array_right_().

vlc_vector_rotate_array_right_()

static void vlc_vector_rotate_array_right_ ( char *  array, size_t  len, size_t  distance  )

inlinestatic

Right-rotate a (char) array in place.

For example, left-rotating a char array containing {1, 2, 3, 4, 5, 6} with distance 2 will result in {5, 6, 1, 2, 3, 4}.

Private.

References vlc_vector_rotate_array_left_().

Referenced by vlc_vector_move_().

vlc_vector_test_and_reset_failflag_()

static bool vlc_vector_test_and_reset_failflag_ ( size_t *  pcap )

inlinestatic

Test and reset the fail flag.

Return values

true	if the flag was set
false	if the flag was not set

References VLC_VECTOR_FAILFLAG_.