VLC  4.0.0-dev
vlc_vector.h
Go to the documentation of this file.
1 /******************************************************************************
2  * vlc_vector.h
3  ******************************************************************************
4  * Copyright (C) 2018 VLC authors and VideoLAN
5  *
6  * This program is free software; you can redistribute it and/or modify it
7  * under the terms of the GNU Lesser General Public License as published by
8  * the Free Software Foundation; either version 2.1 of the License, or
9  * (at your option) any later version.
10  *
11  * This program is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14  * GNU Lesser General Public License for more details.
15  *
16  * You should have received a copy of the GNU Lesser General Public License
17  * along with this program; if not, write to the Free Software Foundation,
18  * Inc., 51 Franklin Street, Fifth Floor, Boston MA 02110-1301, USA.
19  *****************************************************************************/
20 #ifndef VLC_VECTOR_H
21 #define VLC_VECTOR_H
22 
23 #include <stdbool.h>
24 #include <stddef.h>
25 
26 /**
27  * \defgroup vector Vector
28  * \ingroup cext
29  * @{
30  * \file
31  * This provides convenience helpers for vectors.
32  */
33 
34 /**
35  * Vector struct body.
36  *
37  * A vector is a dynamic array, managed by the vlc_vector_* helpers.
38  *
39  * It is generic over the type of its items, so it is implemented as macros.
40  *
41  * To use a vector, a new type must be defined:
42  *
43  * \code
44  * struct vec_int VLC_VECTOR(int);
45  * \endcode
46  *
47  * The struct may be anonymous:
48  *
49  * \code
50  * struct VLC_VECTOR(const char *) names;
51  * \endcode
52  *
53  * It is convenient to define a typedef to an anonymous structure:
54  *
55  * \code
56  * typedef struct VLC_VECTOR(int) vec_int_t;
57  * \endcode
58  *
59  * Vector size is accessible via `vec.size`, and items are intended to be
60  * accessed directly, via `vec.data[i]`.
61  *
62  * Functions and macros having name ending with '_' are private.
63  */
64 #define VLC_VECTOR(type) \
65 { \
66  size_t cap; \
67  size_t size; \
68  type *data; \
69 }
70 
71 /**
72  * Static initializer for a vector.
73  */
74 #define VLC_VECTOR_INITIALIZER { 0, 0, NULL }
75 
76 /**
77  * Initialize an empty vector.
78  */
79 #define vlc_vector_init(pv) (void) \
80 ( \
81  /* cannot be implemened as do-while(0), called from vlc_vector_clear() */ \
82  (pv)->cap = 0, \
83  (pv)->size = 0, \
84  (pv)->data = NULL \
85 )
86 
87 /**
88  * Destroy a vector.
89  *
90  * The vector may not be used anymore unless vlc_vector_init() is called.
91  */
92 #define vlc_vector_destroy(pv) \
93  free((pv)->data)
94 
95 /**
96  * Clear a vector.
97  *
98  * Remove all items from the vector.
99  */
100 #define vlc_vector_clear(pv) \
101 ( \
102  /* cannot be implemened as do-while(0), called from vlc_vector_resize_() */ \
103  vlc_vector_destroy(pv), \
104  vlc_vector_init(pv) \
105 )
106 
107 /**
108  * The minimal allocation size, in number of items.
109  *
110  * Private.
111  */
112 #define VLC_VECTOR_MINCAP_ ((size_t) 10)
113 
114 static inline size_t
115 vlc_vector_min_(size_t a, size_t b)
116 {
117  return a < b ? a : b;
118 }
119 
120 static inline size_t
121 vlc_vector_max_(size_t a, size_t b)
122 {
123  return a > b ? a : b;
124 }
125 
126 static inline size_t
127 vlc_vector_between_(size_t x, size_t min, size_t max)
128 {
129  return vlc_vector_max_(min, vlc_vector_min_(max, x));
130 }
131 
132 static inline size_t
133 vlc_vector_enforce_size_t_(size_t value)
134 {
135  return value;
136 }
137 
138 #define VLC_VECTOR_FAILFLAG_ (~(((size_t) -1) >> 1)) /* only the MSB */
139 
140 /**
141  * Realloc data and update vector fields.
142  *
143  * On reallocation success, return the reallocated array and update the vector
144  * capacity and size.
145  *
146  * On reallocation failure, return `ptr`, keep `*psize` untouched, and set the
147  * failflag in `*pcap` to indicate allocation failure (to be consumed by
148  * `vlc_vector_test_and_reset_failflag_()`).
149  *
150  * This weird behavior allows to simultaneously:
151  * - not require compiler extensions like "statement expressions"
152  * - keep the vector data, size and capacity unchanged on reallocation failure
153  * - not require output variables other than vector fields from the caller
154  * - not violate the strict aliasing rules
155  * - report the reallocation status (success or failure)
156  *
157  * Private.
158  *
159  * \param ptr the current data to realloc
160  * \param count the requested capacity, in number of items
161  * \param size the size of one item
162  * \param pcap a pointer to the `cap` field of the vector [IN/OUT]
163  * \param psize a pointer to the `size` field of the vector [IN/OUT]
164  * \return the reallocated array, or `ptr` if reallocation failed
165  */
166 static inline void *
167 vlc_vector_reallocdata_(void *ptr, size_t count, size_t size,
168  size_t *restrict pcap, size_t *restrict psize)
169 {
170  void *n = vlc_reallocarray(ptr, count, size);
171  if (!n)
172  {
173  /* this vector implementation guarantees that the capacity may not
174  * exceed SIZE_MAX/2 (to prevent overflows), so we can use the MSB to
175  * report allocation failure */
176  *pcap |= VLC_VECTOR_FAILFLAG_;
177  return ptr;
178  }
179  *pcap = count;
180  *psize = vlc_vector_min_(*psize, count);
181  return n;
182 }
183 
184 /**
185  * Test and reset the fail flag.
186  *
187  * \retval true if the flag was set
188  * \retval false if the flag was not set
189  */
190 static inline bool
192 {
193  if (*pcap & VLC_VECTOR_FAILFLAG_)
194  {
195  *pcap &= ~VLC_VECTOR_FAILFLAG_;
196  return true;
197  }
198  return false;
199 }
200 
201 /**
202  * Realloc the underlying array to `newcap`.
203  *
204  * Private.
205  *
206  * \param pv a pointer to the vector
207  * \param newcap (size_t) the requested size
208  * \retval true if no allocation failed
209  * \retval false on allocation failure (the vector is left untouched)
210  */
211 #define vlc_vector_realloc_(pv, newcap) \
212 ( \
213  (pv)->data = vlc_vector_reallocdata_((pv)->data, newcap, \
214  sizeof(*(pv)->data), \
215  &(pv)->cap, &(pv)->size), \
216  !vlc_vector_test_and_reset_failflag_(&(pv)->cap) \
217 )
218 
219 /**
220  * Resize the vector to `newcap` exactly.
221  *
222  * If `newcap` is 0, the vector is cleared.
223  *
224  * Private.
225  *
226  * \param pv a pointer to the vector
227  * \param newcap (size_t) the requested capacity
228  * \retval true if no allocation failed
229  * \retval false on allocation failure (the vector is left untouched)
230  */
231 #define vlc_vector_resize_(pv, newcap) \
232 ( \
233  (pv)->cap == (newcap) /* nothing to do */ || \
234  ( \
235  (newcap) > 0 ? vlc_vector_realloc_(pv, newcap) \
236  : (vlc_vector_clear(pv), true) \
237  ) \
238 )
239 
240 static inline size_t
241 vlc_vector_growsize_(size_t value)
242 {
243  /* integer multiplication by 1.5 */
244  return value + (value >> 1);
245 }
246 
247 /* SIZE_MAX/2 to fit in ssize_t, and so that cap*1.5 does not overflow. */
248 #define vlc_vector_max_cap_(pv) (SIZE_MAX / 2 / sizeof(*(pv)->data))
249 
250 /**
251  * Increase the capacity of the vector to at least `mincap`.
252  *
253  * \param pv a pointer to the vector
254  * \param mincap (size_t) the requested capacity
255  * \retval true if no allocation failed
256  * \retval false on allocation failure (the vector is left untouched)
257  */
258 #define vlc_vector_reserve(pv, mincap) \
259  /* avoid to allocate tiny arrays (< VLC_VECTOR_MINCAP_) */ \
260  vlc_vector_reserve_internal_(pv, \
261  vlc_vector_max_(mincap, VLC_VECTOR_MINCAP_))
262 
263 #define vlc_vector_reserve_internal_(pv, mincap) \
264 ( \
265  (mincap) <= (pv)->cap /* nothing to do */ || \
266  ( \
267  (mincap) <= vlc_vector_max_cap_(pv) /* not too big */ && \
268  vlc_vector_realloc_(pv, \
269  /* multiply by 1.5, force between [mincap, maxcap] */ \
270  vlc_vector_between_(vlc_vector_growsize_((pv)->cap), \
271  mincap, \
272  vlc_vector_max_cap_(pv))) \
273  ) \
274 )
275 
276 /**
277  * Resize the vector so that its capacity equals its actual size.
278  *
279  * \param pv a pointer to the vector
280  */
281 #define vlc_vector_shrink_to_fit(pv) \
282  (void) /* decreasing the size may not fail */ \
283  vlc_vector_resize_(pv, (pv)->size)
284 
285 /**
286  * Resize the vector down automatically.
287  *
288  * Shrink only when necessary (in practice when cap > (size+5)*1.5)
289  *
290  * \param pv a pointer to the vector
291  */
292 #define vlc_vector_autoshrink(pv) (void) \
293 ( \
294  (pv)->cap <= VLC_VECTOR_MINCAP_ /* do not shrink to tiny length */ || \
295  (pv)->cap < vlc_vector_growsize_((pv)->size+5) /* no need to shrink */ || \
296  vlc_vector_resize_(pv, vlc_vector_max_((pv)->size+5, VLC_VECTOR_MINCAP_)) \
297 )
298 
299 #define vlc_vector_check_same_ptr_type_(a, b) \
300  (void) ((a) == (b)) /* warn on type mismatch */
301 
302 /**
303  * Push an item at the end of the vector.
304  *
305  * The amortized complexity is O(1).
306  *
307  * \param pv a pointer to the vector
308  * \param item the item to append
309  * \retval true if no allocation failed
310  * \retval false on allocation failure (the vector is left untouched)
311  */
312 #define vlc_vector_push(pv, item) \
313 ( \
314  vlc_vector_reserve(pv, (pv)->size + 1) && \
315  ( \
316  (pv)->data[(pv)->size++] = (item), \
317  true \
318  ) \
319 )
320 
321 /**
322  * Append `count` items at the end of the vector.
323  *
324  * \param pv a pointer to the vector
325  * \param items the items array to append
326  * \param count the number of items in the array
327  * \retval true if no allocation failed
328  * \retval false on allocation failure (the vector is left untouched)
329  */
330 #define vlc_vector_push_all(pv, items, count) \
331  vlc_vector_push_all_internal_(pv, items, vlc_vector_enforce_size_t_(count))
332 
333 #define vlc_vector_push_all_internal_(pv, items, count) \
334 ( \
335  vlc_vector_check_same_ptr_type_((pv)->data, items), \
336  vlc_vector_reserve(pv, (pv)->size + (count)) && \
337  ( \
338  memcpy(&(pv)->data[(pv)->size], items, (count) * sizeof(*(pv)->data)), \
339  (pv)->size += (count), \
340  true \
341  ) \
342 )
343 
344 /**
345  * Insert an hole of size `count` to the given index.
346  *
347  * The items in range [index; size-1] will be moved. The items in the hole are
348  * left uninitialized.
349  *
350  * \param pv a pointer to the vector
351  * \param index the index where the hole is to be inserted
352  * \param count the number of items in the hole
353  * \retval true if no allocation failed
354  * \retval false on allocation failure (the vector is left untouched)
355  */
356 #define vlc_vector_insert_hole(pv, index, count) \
357  vlc_vector_insert_hole_internal_(pv, vlc_vector_enforce_size_t_(index), \
358  vlc_vector_enforce_size_t_(count))
359 
360 #define vlc_vector_insert_hole_internal_(pv, index, count) \
361 ( \
362  vlc_vector_reserve(pv, (pv)->size + (count)) && \
363  ( \
364  (index) == (pv)->size || \
365  ( \
366  memmove(&(pv)->data[(index) + (count)], \
367  &(pv)->data[index], \
368  ((pv)->size - (index)) * sizeof(*(pv)->data)), \
369  true \
370  ) \
371  ) && \
372  ( \
373  (pv)->size += (count), \
374  true \
375  ) \
376 )
377 
378 /**
379  * Insert an item at the given index.
380  *
381  * The items in range [index; size-1] will be moved.
382  *
383  * \param pv a pointer to the vector
384  * \param index the index where the item is to be inserted
385  * \param item the item to append
386  * \retval true if no allocation failed
387  * \retval false on allocation failure (the vector is left untouched)
388  */
389 #define vlc_vector_insert(pv, index, item) \
390 ( \
391  vlc_vector_insert_hole(pv, index, 1) && \
392  ( \
393  (pv)->data[index] = (item), \
394  true \
395  ) \
396 )
397 
398 /**
399  * Insert `count` items at the given index.
400  *
401  * The items in range [index; size-1] will be moved.
402  *
403  * \param pv a pointer to the vector
404  * \param index the index where the items are to be inserted
405  * \param items the items array to append
406  * \param count the number of items in the array
407  * \retval true if no allocation failed
408  * \retval false on allocation failure (the vector is left untouched)
409  */
410 #define vlc_vector_insert_all(pv, index, items, count) \
411 ( \
412  vlc_vector_check_same_ptr_type_((pv)->data, items), \
413  vlc_vector_insert_hole(pv, index, count) && \
414  ( \
415  memcpy(&(pv)->data[index], items, (count) * sizeof(*(pv)->data)), \
416  true \
417  ) \
418 )
419 
420 /** Reverse a char array in place. */
421 static inline void
422 vlc_vector_reverse_array_(char *array, size_t len)
423 {
424  for (size_t i = 0; i < len / 2; ++i)
425  {
426  char c = array[i];
427  array[i] = array[len - i - 1];
428  array[len - i - 1] = c;
429  }
430 }
431 
432 /**
433  * Right-rotate a (char) array in place.
434  *
435  * For example, left-rotating a char array containing {1, 2, 3, 4, 5, 6} with
436  * distance 4 will result in {5, 6, 1, 2, 3, 4}.
437  *
438  * Private.
439  */
440 static inline void
441 vlc_vector_rotate_array_left_(char *array, size_t len, size_t distance)
442 {
443  vlc_vector_reverse_array_(array, distance);
444  vlc_vector_reverse_array_(&array[distance], len - distance);
445  vlc_vector_reverse_array_(array, len);
446 }
447 
448 /**
449  * Right-rotate a (char) array in place.
450  *
451  * For example, left-rotating a char array containing {1, 2, 3, 4, 5, 6} with
452  * distance 2 will result in {5, 6, 1, 2, 3, 4}.
453  *
454  * Private.
455  */
456 static inline void
457 vlc_vector_rotate_array_right_(char *array, size_t len, size_t distance)
458 {
459  vlc_vector_rotate_array_left_(array, len, len - distance);
460 }
461 
462 /**
463  * Move items in a (char) array in place.
464  *
465  * Move slice [index, count] to target.
466  */
467 static inline void
468 vlc_vector_move_(char *array, size_t index, size_t count, size_t target)
469 {
470  if (index < target)
471  vlc_vector_rotate_array_left_(&array[index], target - index + count,
472  count);
473  else
474  vlc_vector_rotate_array_right_(&array[target], index - target + count,
475  count);
476 }
477 
478 /**
479  * Move a slice of items to a given target index.
480  *
481  * The items in range [index; count] will be moved so that the *new* position
482  * of the first item is `target`.
483  *
484  * \param pv a pointer to the vector
485  * \param index the index of the first item to move
486  * \param count the number of items to move
487  * \param target the new index of the moved slice
488  */
489 #define vlc_vector_move_slice(pv, index, count, target) \
490  vlc_vector_move_slice_internal_(pv, \
491  vlc_vector_enforce_size_t_(index), \
492  vlc_vector_enforce_size_t_(count), \
493  vlc_vector_enforce_size_t_(target))
494 
495 #define vlc_vector_move_slice_internal_(pv, index, count, target) \
496  vlc_vector_move_((char *) (pv)->data, \
497  (index) * sizeof((pv)->data[0]), \
498  (count) * sizeof((pv)->data[0]), \
499  (target) * sizeof((pv)->data[0]))
500 
501 /**
502  * Move an item to a given target index.
503  *
504  * The items will be moved so that its *new* position is `target`.
505  *
506  * \param pv a pointer to the vector
507  * \param index the index of the item to move
508  * \param target the new index of the moved item
509  */
510 #define vlc_vector_move(pv, index, target) \
511  vlc_vector_move_slice(pv, index, 1, target)
512 
513 /**
514  * Remove a slice of items, without shrinking the array.
515  *
516  * If you have no good reason to use the _noshrink() version, use
517  * vlc_vector_remove_slice() instead.
518  *
519  * The items in range [index+count; size-1] will be moved.
520  *
521  * \param pv a pointer to the vector
522  * \param index the index of the first item to remove
523  * \param count the number of items to remove
524  */
525 #define vlc_vector_remove_slice_noshrink(pv, index, count) \
526  vlc_vector_remove_slice_noshrink_internal_(pv, \
527  vlc_vector_enforce_size_t_(index), \
528  vlc_vector_enforce_size_t_(count))
529 
530 #define vlc_vector_remove_slice_noshrink_internal_(pv, index, count) \
531  do { \
532  if ((index) + (count) < (pv)->size) \
533  memmove(&(pv)->data[index], \
534  &(pv)->data[(index) + (count)], \
535  ((pv)->size - (index) - (count)) * sizeof(*(pv)->data)); \
536  (pv)->size -= (count); \
537  } while (0)
538 
539 /**
540  * Remove a slice of items.
541  *
542  * The items in range [index+count; size-1] will be moved.
543  *
544  * \param pv a pointer to the vector
545  * \param index the index of the first item to remove
546  * \param count the number of items to remove
547  */
548 #define vlc_vector_remove_slice(pv, index, count) \
549  do { \
550  vlc_vector_remove_slice_noshrink(pv, index, count); \
551  vlc_vector_autoshrink(pv); \
552  } while (0)
553 
554 /**
555  * Remove an item, without shrinking the array.
556  *
557  * If you have no good reason to use the _noshrink() version, use
558  * vlc_vector_remove() instead.
559  *
560  * The items in range [index+1; size-1] will be moved.
561  *
562  * \param pv a pointer to the vector
563  * \param index the index of item to remove
564  */
565 #define vlc_vector_remove_noshrink(pv, index) \
566  vlc_vector_remove_slice_noshrink(pv, index, 1)
567 
568 /**
569  * Remove an item.
570  *
571  * The items in range [index+1; size-1] will be moved.
572  *
573  * \param pv a pointer to the vector
574  * \param index the index of item to remove
575  */
576 #define vlc_vector_remove(pv, index) \
577  do { \
578  vlc_vector_remove_noshrink(pv, index); \
579  vlc_vector_autoshrink(pv); \
580  } while (0)
581 
582 /**
583  * Remove an item.
584  *
585  * The removed item is replaced by the last item of the vector.
586  *
587  * This does not preserve ordering, but is O(1). This is useful when the order
588  * of items is not meaningful.
589  *
590  * \param pv a pointer to the vector
591  * \param index the index of item to remove
592  */
593 #define vlc_vector_swap_remove(pv, index) \
594  do { \
595  (pv)->data[index] = (pv)->data[(pv)->size-1]; \
596  (pv)->size--; \
597  } while(0)
598 
599 /**
600  * Return the index of an item.
601  *
602  * Iterate over all items to find a given item.
603  *
604  * Use only for vectors of primitive types or pointers.
605  *
606  * The result is written to `*(pidx)`:
607  * - the index of the item if it is found;
608  * - -1 if it is not found.
609  *
610  * \param pv a pointer to the vector
611  * \param item the item to find (compared with ==)
612  * \param a pointer to the result (ssize_t *) [OUT]
613  */
614 #define vlc_vector_index_of(pv, item, pidx) \
615  do { \
616  ssize_t *out = pidx; /* warning/error on type mismatch */ \
617  size_t vlc_vector_find_idx_; \
618  for (vlc_vector_find_idx_ = 0; \
619  vlc_vector_find_idx_ < (pv)->size; \
620  ++vlc_vector_find_idx_) \
621  if ((pv)->data[vlc_vector_find_idx_] == (item)) \
622  break; \
623  *out = vlc_vector_find_idx_ == (pv)->size ? -1 : \
624  (ssize_t) vlc_vector_find_idx_; \
625  } while (0)
626 
627 /**
628  * For-each loop.
629  *
630  * Use only for vectors of primitive types or pointers (every struct would be
631  * copied for a vector of structs).
632  *
633  * \param item the iteration variable [OUT]
634  * \param pv a pointer to the vector [OUT]
635  */
636 #define vlc_vector_foreach(item, pv) \
637  for (size_t vlc_vector_idx_##item = 0; \
638  vlc_vector_idx_##item < (pv)->size && \
639  ((item) = (pv)->data[vlc_vector_idx_##item], true); \
640  ++vlc_vector_idx_##item)
641 
642 /** @} */
643 
644 #endif
count
size_t count
Definition: core.c:401
vlc_vector_between_
static size_t vlc_vector_between_(size_t x, size_t min, size_t max)
Definition: vlc_vector.h:128
vlc_common.h
vlc_vector_enforce_size_t_
static size_t vlc_vector_enforce_size_t_(size_t value)
Definition: vlc_vector.h:134
vlc_vector_min_
static size_t vlc_vector_min_(size_t a, size_t b)
Definition: vlc_vector.h:116
vlc_vector_max_
static size_t vlc_vector_max_(size_t a, size_t b)
Definition: vlc_vector.h:122
vlc_vector_growsize_
static size_t vlc_vector_growsize_(size_t value)
Definition: vlc_vector.h:242
vlc_vector_rotate_array_right_
static void vlc_vector_rotate_array_right_(char *array, size_t len, size_t distance)
Right-rotate a (char) array in place.
Definition: vlc_vector.h:458
vlc_vector_test_and_reset_failflag_
static bool vlc_vector_test_and_reset_failflag_(size_t *pcap)
Test and reset the fail flag.
Definition: vlc_vector.h:192
vlc_reallocarray
static void * vlc_reallocarray(void *ptr, size_t count, size_t size)
Definition: vlc_common.h:1150
vlc_vector_reallocdata_
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
vlc_vector_move_
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_rotate_array_left_
static void vlc_vector_rotate_array_left_(char *array, size_t len, size_t distance)
Right-rotate a (char) array in place.
Definition: vlc_vector.h:442
vlc_vector_reverse_array_
static void vlc_vector_reverse_array_(char *array, size_t len)
Reverse a char array in place.
Definition: vlc_vector.h:423
VLC_VECTOR_FAILFLAG_
#define VLC_VECTOR_FAILFLAG_
Definition: vlc_vector.h:139