include/vlc_vector.h

   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
 191 vlc_vector_test_and_reset_failflag_(size_t *pcap)
 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