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