[FFmpeg-devel] [PATCH v2] [RFC] lavc, lavfmt: add FLIF decoding support

[Nicolas George]

Kartik K. Khullar (12020-08-03):
> > Mixing linked lists and indices is usually a sign you are doing
> > something wrong.
> >
> > Here, I believe you would do better with a doubly linked list and
> > pointers instead of indices.
> >
> > Note: there is a trick with doubly linked lists where you put the next
> > and prev pointers together alone in a struct, and have them point not to
> > the actual elements but to the next/prev struct of the elements. That
> > way, you can have the whole list itself as just another such struct, and
> > not have to make special cases for the ends of the list.
> >
> > If you do not know that trick and want to, I can explain.
> 
> Yes please explain more.

It is the combination of two tricks really.

When you have to write operations on a linked list, you frequently need
to check if you are at the beginning or the end of the list: if at the
beginning, update the list pointer, otherwise update the next pointer of
the prev element. This is annoying, and error prone. Doubly so with
doubly-linked lists.

The trick is to add an extra, special element to the list, to make it
circular. This extra element becomes your entry point to the list, it is
called sentinel node. Then, the first element of the list is
sentinel.next, and if the list is doubly-linked, its last element is
sentinel.prev. To test if you are at the end of the list, you do not
test element->next == NULL but element->next == &sentinel. The list is
considered empty if sentinel.next == &sentinel.

It makes many things simpler, because the list is never really empty, it
always contain the sentinel, and all elements have a valid next (and
prev) pointer. That way, inserting or deleting are done exactly the same
way for all elements, be they in the middle, at the end or at the
beginning: just update the prev and next fields of the neighbors, and if
one of them was the sentinel, it just works.

But there is a drawback: if your list elements are big, so is the
sentinel, but everything except its prev and next pointers is wasted.
This is where the second trick comes in.

  +--------+        +--------+        +--------+        +--------+
  | field1 |<-.  ,->| field1 |<-.  ,->| field1 |<-.  ,->| field1 |
  | field2 |  |  |  | field2 |  |  |  | field2 |  |  |  | field2 |
  | field3 |  |  |  | field3 |  |  |  | field3 |  |  |  | field3 |
  | next   |-----'  | next   |-----'  | next   |-----'  | next   |
  | prev   |  `-----| prev   |  `-----| prev   |  `-----| prev   |
  | field4 |        | field4 |        | field4 |        | field4 |
  | ...    |        | ...    |        | ...    |        | ...    |
  +--------+        +--------+        +--------+        +--------+


Make the list structure contain only the prev and next fields, nothing
else.

  +--------+         +--------+         +--------+         +--------+
  | pr,nx  |<------> | pr,nx  |<------> | pr,nx  |<------> | pr,nx  |
  +--------+         +--------+         +--------+         +--------+

At first glance, that makes the list pretty useless. But you can hang
the actual data around the elements:

  +--------+        +--------+        +--------+        +--------+
  | field1 |        | field1 |        | field1 |        | field1 |
  | field2 |        | field2 |        | field2 |        | field2 |
  | field3 |        | field3 |        | field3 |        | field3 |
  |[pr,nx] |<------>|[pr,nx] |<------>|[pr,nx] |<------>|[pr,nx] |
  | prev   |        | prev   |        | prev   |        | prev   |
  | field4 |        | field4 |        | field4 |        | field4 |
  | ...    |        | ...    |        | ...    |        | ...    |
  +--------+        +--------+        +--------+        +--------+

If you have a pointer to the list structure, you can convert it into a
pointer to the whole structure with just a little pointer arithmetic
using offsetof(). Something like this (very simplified):

    typedef struct List {
	List *prev, *next;
    } List;
    typedef struct Object {
	Type field1, field2;
	...
	List list;
    };

    next_object = (char *)object->list.next - offsetof(Object, list);

Note that you can have the same object part of several lists by having
several List fields with different names.

And if you do that, the sentinel can be just List, it does not need to
be Object.

I have attached a header I use in another project with macros that
define high-level type-safe list operations around these concepts. If
FFmpeg did use many linked lists, I would propose something similar, but
we usually make do with dynamic arrays.

IIRC, the Linux kernel makes heavy use of this structure.

> My apologies, I should have removed other parts of the quoted code which I
> was not replying to.

No need to apologize for doing like 80% of people here ;) But yes,
trimming replies makes the conversation easier to read.

Regards,

-- 
  Nicolas George
-------------- next part --------------
A non-text attachment was scrubbed...
Name: linkedlist.h
Type: text/x-chdr
Size: 1827 bytes
Desc: not available
URL: <https://ffmpeg.org/pipermail/ffmpeg-devel/attachments/20200803/d864ae1d/attachment.h>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 833 bytes
Desc: not available
URL: <https://ffmpeg.org/pipermail/ffmpeg-devel/attachments/20200803/d864ae1d/attachment.sig>