VLC  4.0.0-dev
Files | Macros | Functions
Collaboration diagram for Vector:

Files

file  vlc_vector.h
 This provides convenience helpers for vectors.
 

Macros

#define VLC_VECTOR(type)
 Vector struct body. More...
 
#define VLC_VECTOR_INITIALIZER   { 0, 0, NULL }
 Static initializer for a vector. More...
 
#define vlc_vector_init(pv)
 Initialize an empty vector. More...
 
#define vlc_vector_destroy(pv)    free((pv)->data)
 Destroy a vector. More...
 
#define vlc_vector_clear(pv)
 Clear a vector. More...
 
#define VLC_VECTOR_MINCAP_   ((size_t) 10)
 The minimal allocation size, in number of items. More...
 
#define VLC_VECTOR_FAILFLAG_   (~(((size_t) -1) >> 1)) /* only the MSB */
 
#define vlc_vector_realloc_(pv, newcap)
 Realloc the underlying array to newcap. More...
 
#define vlc_vector_resize_(pv, newcap)
 Resize the vector to newcap exactly. More...
 
#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. More...
 
#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. More...
 
#define vlc_vector_autoshrink(pv)
 Resize the vector down automatically. More...
 
#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. More...
 
#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. More...
 
#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. More...
 
#define vlc_vector_insert_hole_internal_(pv, index, count)
 
#define vlc_vector_insert(pv, index, item)
 Insert an item at the given index. More...
 
#define vlc_vector_insert_all(pv, index, items, count)
 Insert count items at the given index. More...
 
#define vlc_vector_move_slice(pv, index, count, target)
 Move a slice of items to a given target index. More...
 
#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. More...
 
#define vlc_vector_remove_slice_noshrink(pv, index, count)
 Remove a slice of items, without shrinking the array. More...
 
#define vlc_vector_remove_slice_noshrink_internal_(pv, index, count)
 
#define vlc_vector_remove_slice(pv, index, count)
 Remove a slice of items. More...
 
#define vlc_vector_remove_noshrink(pv, index)    vlc_vector_remove_slice_noshrink(pv, index, 1)
 Remove an item, without shrinking the array. More...
 
#define vlc_vector_remove(pv, index)
 Remove an item. More...
 
#define vlc_vector_swap_remove(pv, index)
 Remove an item. More...
 
#define vlc_vector_index_of(pv, item, pidx)
 Return the index of an item. More...
 
#define vlc_vector_foreach(item, pv)
 For-each loop. More...
 

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. More...
 
static bool vlc_vector_test_and_reset_failflag_ (size_t *pcap)
 Test and reset the fail flag. More...
 
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. More...
 
static void vlc_vector_rotate_array_left_ (char *array, size_t len, size_t distance)
 Right-rotate a (char) array in place. More...
 
static void vlc_vector_rotate_array_right_ (char *array, size_t len, size_t distance)
 Right-rotate a (char) array in place. More...
 
static void vlc_vector_move_ (char *array, size_t index, size_t count, size_t target)
 Move items in a (char) array in place. More...
 

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);
#define VLC_VECTOR(type)
Vector struct body.
Definition: vlc_vector.h:65

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 */ || \
)
static size_t vlc_vector_growsize_(size_t value)
Definition: vlc_vector.h:242
#define vlc_vector_resize_(pv, newcap)
Resize the vector to newcap exactly.
Definition: vlc_vector.h:232
static size_t vlc_vector_max_(size_t a, size_t b)
Definition: vlc_vector.h:122
#define VLC_VECTOR_MINCAP_
The minimal allocation size, in number of items.
Definition: vlc_vector.h:113

Resize the vector down automatically.

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

Parameters
pva pointer to the vector

◆ vlc_vector_check_same_ptr_type_

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

◆ vlc_vector_clear

#define vlc_vector_clear (   pv)
Value:
( \
/* cannot be implemened 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
itemthe iteration variable [OUT]
pva pointer to the vector [OUT]

◆ 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
pva pointer to the vector
itemthe item to find (compared with ==)
apointer to the result (ssize_t *) [OUT]

◆ vlc_vector_init

#define vlc_vector_init (   pv)
Value:
(void) \
( \
/* cannot be implemened 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
pva pointer to the vector
indexthe index where the item is to be inserted
itemthe item to append
Return values
trueif no allocation failed
falseon 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 \
) \
)
size_t count
Definition: core.c:398

Insert count items at the given index.

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

Parameters
pva pointer to the vector
indexthe index where the items are to be inserted
itemsthe items array to append
countthe number of items in the array
Return values
trueif no allocation failed
falseon allocation failure (the vector is left untouched)

◆ vlc_vector_insert_hole

#define vlc_vector_insert_hole (   pv,
  index,
  count 
)
Value:
#define vlc_vector_insert_hole_internal_(pv, index, count)
Definition: vlc_vector.h:361
static size_t vlc_vector_enforce_size_t_(size_t value)
Definition: vlc_vector.h:134

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
pva pointer to the vector
indexthe index where the hole is to be inserted
countthe number of items in the hole
Return values
trueif no allocation failed
falseon allocation failure (the vector is left untouched)

◆ vlc_vector_insert_hole_internal_

#define vlc_vector_insert_hole_internal_ (   pv,
  index,
  count 
)
Value:
( \
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_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
pva pointer to the vector
indexthe index of the item to move
targetthe new index of the moved item

◆ vlc_vector_move_slice

#define vlc_vector_move_slice (   pv,
  index,
  count,
  target 
)
Value:
#define vlc_vector_move_slice_internal_(pv, index, count, target)
Definition: vlc_vector.h:496

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
pva pointer to the vector
indexthe index of the first item to move
countthe number of items to move
targetthe 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]))
static void vlc_vector_move_(char *array, size_t index, size_t count, size_t target)
Move items in a (char) array in place.
Definition: vlc_vector.h:469

◆ 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
pva pointer to the vector
itemthe item to append
Return values
trueif no allocation failed
falseon 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
pva pointer to the vector
itemsthe items array to append
countthe number of items in the array
Return values
trueif no allocation failed
falseon allocation failure (the vector is left untouched)

◆ vlc_vector_push_all_internal_

#define vlc_vector_push_all_internal_ (   pv,
  items,
  count 
)
Value:
( \
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_realloc_

#define vlc_vector_realloc_ (   pv,
  newcap 
)
Value:
( \
(pv)->data = vlc_vector_reallocdata_((pv)->data, newcap, \
sizeof(*(pv)->data), \
&(pv)->cap, &(pv)->size), \
)
static bool vlc_vector_test_and_reset_failflag_(size_t *pcap)
Test and reset the fail flag.
Definition: vlc_vector.h:192
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.
Definition: vlc_vector.h:168

Realloc the underlying array to newcap.

Private.

Parameters
pva pointer to the vector
newcap(size_t) the requested size
Return values
trueif no allocation failed
falseon 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
pva pointer to the vector
indexthe 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
pva pointer to the vector
indexthe 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
pva pointer to the vector
indexthe index of the first item to remove
countthe number of items to remove

◆ vlc_vector_remove_slice_noshrink

#define vlc_vector_remove_slice_noshrink (   pv,
  index,
  count 
)
Value:
#define vlc_vector_remove_slice_noshrink_internal_(pv, index, count)
Definition: vlc_vector.h:531

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
pva pointer to the vector
indexthe index of the first item to remove
countthe number of items to remove

◆ vlc_vector_remove_slice_noshrink_internal_

#define vlc_vector_remove_slice_noshrink_internal_ (   pv,
  index,
  count 
)
Value:
do { \
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, \

Increase the capacity of the vector to at least mincap.

Parameters
pva pointer to the vector
mincap(size_t) the requested capacity
Return values
trueif no allocation failed
falseon 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] */ \
mincap, \
) \
)
#define vlc_vector_max_cap_(pv)
Definition: vlc_vector.h:249
static size_t vlc_vector_between_(size_t x, size_t min, size_t max)
Definition: vlc_vector.h:128

◆ 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) \
) \
)
#define vlc_vector_clear(pv)
Clear a vector.
Definition: vlc_vector.h:101
#define vlc_vector_realloc_(pv, newcap)
Realloc the underlying array to newcap.
Definition: vlc_vector.h:212

Resize the vector to newcap exactly.

If newcap is 0, the vector is cleared.

Private.

Parameters
pva pointer to the vector
newcap(size_t) the requested capacity
Return values
trueif no allocation failed
falseon 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
pva 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
pva pointer to the vector
indexthe 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

◆ 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

◆ 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
ptrthe current data to realloc
countthe requested capacity, in number of items
sizethe size of one item
pcapa pointer to the cap field of the vector [IN/OUT]
psizea pointer to the size field of the vector [IN/OUT]
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
trueif the flag was set
falseif the flag was not set

References VLC_VECTOR_FAILFLAG_.