[vlc-devel] [RFC 0/3] Improving vlc_array_t

[Romain Vimont]

There are 3 arrays API in vlc_arrays.h:
 1. TAB_* macros
 2. ARRAY_* macros
 3. vlc_array_t + functions

When we want a dynamic array of pointers, the vlc_array_t seems more
appropriate. Moreover, the macro versions abort() on allocation failure.

To make it more user-friendly, I suggest to rename:
 - vlc_array_item_at_index() by vlc_array_get() (patch 1)
 - vlc_array_index_of_item() by vlc_array_find() (patch 2)

To make it more general (suitable for more cases), I suggest to change
its growth strategy so that we can append items in amortized constant
time (similar to what ARRAY_* macros use, or, FWIW, C++ std::vector,
Java ArrayList, Rust std::vec, etc.). (patch 3)

Currently, appending n items involves n realloc(). I would like to use
vlc_array_t for the playlist+shuffle stuff, but this behavior looks
undesirable to me.

I also suggest to expose vlc_array_reserve() to avoid unnecessary
reallocations when we know we will add many items, and
vlc_array_shrink_to_fit() to shrink the array to its content size.

In my patch, vlc_array_remove() may realloc to shrink the array (like
ARRAY_* does). I don't know if we should do that (neither C++
std::vector, Java ArrayList nor Rust std::vec shrink on removal).

Thank you for your feedbacks.

Note: this patchset has been written above this one:
<https://mailman.videolan.org/pipermail/vlc-devel/2018-July/120425.html>


Romain Vimont (3):
  vlc_arrays: rename item_at_index() to get()
  vlc_arrays: rename index_of_item() to find()
  vlc_arrays: append items in amortized O(1)

 include/vlc_arrays.h                         | 119 +++++++++----
 include/vlc_common.h                         |   9 +-
 include/vlc_fingerprinter.h                  |   2 +-
 lib/event.c                                  |   6 +-
 lib/media_list.c                             |   8 +-
 modules/access/bluray.c                      |  10 +-
 modules/access/dsm/sd.c                      |   4 +-
 modules/access_output/livehttp.c             |  14 +-
 modules/codec/webvtt/subsvtt.c               |   6 +-
 modules/control/dbus/dbus.c                  |  18 +-
 modules/gui/qt/dialogs/fingerprintdialog.cpp |   2 +-
 modules/misc/fingerprinter.c                 |  14 +-
 modules/mux/asf.c                            |  18 +-
 modules/services_discovery/microdns.c        |   6 +-
 src/input/mrl_helpers.h                      |   2 +-
 src/input/stream_extractor.c                 |   4 +-
 src/interface/dialog.c                       |   4 +-
 src/misc/background_worker.c                 |   4 +-
 src/misc/httpcookies.c                       |   6 +-
 src/stream_output/stream_output.c            |  10 +-
 src/test/arrays.c                            | 168 ++++++++++++++++++-
 src/test/mrl_helpers.c                       |   2 +-
 src/video_output/video_output.c              |   2 +-
 23 files changed, 336 insertions(+), 102 deletions(-)

-- 
2.18.0