[vlc-devel] [PATCH 0/3] Doubly-linked list helpers

Rémi Denis-Courmont remi at remlab.net
Sun Jun 10 20:59:13 CEST 2018


Historically, VLC has used table helper macros to manipualte data sets.
They pose certain issues:
- Memory errors cannot be handled.
- Adding an item may require copying the whole table.
- Removing or inserting an item may also require copying.

In some cases, random indexed access is actually necessary, so using a
table makes sense. But in most cases it is not, so a doubly-linked list
makes more sense:
- No extra memory allocations, so no errors to (mis)handle.
- Inserting/removal is constant time; no copying.

Enumeration is linear time either way.

This patch sets introduce helpers for doubly-linked list manipulation,
no rocket science. Internally, a circular list is used, as it avoids
special cases for first/last elements.

The first patch is the actual implementation.
The second patch replaces the hand-coded linked list in the VLC objects
tree for demonstration purpose.
The third patch replaces tables in the input item infos, also for

The following changes since commit 8d9e7fdaa272fbf95404d4c0c7a753eb01f1b472:

  info: remove dead code (2018-06-10 21:48:35 +0300)

are available in the Git repository at:


for you to fetch changes up to e8aee545a5804c355ad15e86ae250d099842154c:

  input item: use vlc_list for per-category infos (2018-06-10 21:48:35 +0300)

Rémi Denis-Courmont (3):
      vlc_list: helpers for doubly linked lists
      objects: use vlc_list helpers
      input item: use vlc_list for per-category infos

 include/vlc_input_item.h                  |   8 +-
 include/vlc_list.h                        | 263 ++++++++++++++++++++++++++++++
 modules/control/oldrc.c                   |   9 +-
 modules/gui/macosx/VLCPlaylistInfo.m      |   8 +-
 modules/gui/ncurses.c                     |   7 +-
 modules/gui/qt/components/info_panels.cpp |  12 +-
 modules/lua/libs/input.c                  |  10 +-
 src/Makefile.am                           |   1 +
 src/input/info.h                          |  51 +++---
 src/input/item.c                          |  11 +-
 src/misc/objects.c                        |  72 ++++----
 src/misc/variables.h                      |   6 +-
 12 files changed, 363 insertions(+), 95 deletions(-)
 create mode 100644 include/vlc_list.h

Реми Дёни-Курмон

More information about the vlc-devel mailing list