From 532d4a24e2013262dfa41fd85c06a9715c99abf7 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?J=C3=B6rg=20Frings-F=C3=BCrst?= Date: Mon, 24 Oct 2022 21:03:42 +0200 Subject: New upstream version 4.7 --- doc/inline_list.rst | 253 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 253 insertions(+) create mode 100644 doc/inline_list.rst (limited to 'doc/inline_list.rst') diff --git a/doc/inline_list.rst b/doc/inline_list.rst new file mode 100644 index 0000000..e60e89f --- /dev/null +++ b/doc/inline_list.rst @@ -0,0 +1,253 @@ +========================= +Inline doubly-linked list +========================= + +Classical linked-list implementations, such as HXdeque, either store the actual +data within a node, or indirectly through a pointer, but the “inline +doubly-linked list” instead does it reverse and has the list head within the +data structure. + +A classic linked-list implementations with direct/indirect data blocks may look +like so: + +.. code-block:: c + + struct package_desc { + char *package_name; + int version; + + }; + + struct classic_direct_node { + struct classic_direct_node *next, *prev; + struct package_desc direct_data; + }; + struct classic_indirect_node { + struct classic_indirect_node *next, *prev; + void *indirect_data; + }; + +Whereas in an inline list, the list head (next,prev pointers) inlined into the data +block: + +.. code-block:: c + + struct package_desc { + struct HXlist_head list; + char *package_name; + int version; + }; + +At first glance, an inline list does not look much different from ``struct +classic_direct_data``, it is mostly a viewpoint decision which struct is in the +foreground. + + +Synopsis +======== + +.. code-block:: c + + #include + + struct HXlist_head {struct HXlist_head + /* All fields considered private */ + }; + + HXLIST_HEAD_INIT(name); + HXLIST_HEAD(name); + void HXlist_init(struct HXlist_head *list); + void HXlist_add(struct HXlist_head *list, struct HXlist_head *elem); + void HXlist_add_tail(struct HXlist_head *list, struct HXlist_head *elem); + void HXlist_del(struct HXlist_head *element); + bool HXlist_empty(const struct HXlist_head *list); + +``HXLIST_HEAD_INIT`` + This macro expands to the static initializer for a list head. + +``HXLIST_HEAD`` + This macro expands to the definition of a list head (i.e. ``struct + HXlist_head name = HXLIST_HEAD_INIT;``). + +``HXlist_init`` + Initializes the list head. This function is generally used when the + list head is on the heap where the static initializer cannot be used. + +``HXlist_add`` + Adds ``elem`` to the front of the list. + +``HXlist_add_tail`` + Adds ``elem`` to the end of the list. + +``HXlist_del`` + Deletes the given element from the list. + +``HXlist_empty`` + Tests whether the list is empty. (Note: For clists, you could also use + ``clist->items == 0``). + + +Traversal +========= + +Traversal is implemented using macros that expand to ``for()`` statements which +can syntactically be used like them, i.e. curly braces may be omitted if only +a single statement is in the body of the loop. + +The head parameter specifies the list head (``struct HXlist_head``), ``pos`` +specifies an iterator, also of type ``struct HXlist_head``. Lists can either be +traversed in forward direction, or, using the ``*_rev`` variants, in reverse +direction. The ``*_safe`` variants use a temporary ``n`` to hold the next +object in the list, which is needed when ``pos`` itself is going to be +inaccessible at the end of the block, through, for example, freeing its +encompassing object. + +.. code-block:: c + + HXlist_for_each(pos, head) + HXlist_for_each_rev(pos, head) + HXlist_for_each_safe(pos, n, head) + HXlist_for_each_rev_safe(pos, n, head) + +``HXlist_for_each`` + Forward iteration over the list heads. + +``HXlist_for_each_rev`` + Reverse iteration over the list heads. + +``HXlist_for_each_safe`` + Forward iteration over the list heads that is safe against freeing pos. + +``HXlist_for_each_rev_safe`` + Reverse iteration over the list heads that is safe against freeing pos. + +The ``*_entry`` variants use an iterator ``pos`` of the type of the +encompassing object (e.g. ``struct item`` in below's example), so that the +manual ``HXlist_entry`` invocation is not needed. ``member`` is the name of the +list structure embedded into the item. + +.. code-block:: c + + HXlist_for_each_entry(pos, head, member)HXlist_for_each_entry + HXlist_for_each_entry_rev(pos, head, member)HXlist_for_each_entry_rev + HXlist_for_each_entry_safe(pos, n, head, member)HXlist_for_each_entry_safe + +``HXlist_for_each_entry`` + Forward iteration over the list elements. + +``HXlist_for_each_entry_rev`` + Reverse iteration over the list elements. + +``HXlist_for_each_entry_safe`` + Forward iteration over the list elements that is safe against freeing + ``pos``. + + +Examples +======== + +.. code-block:: c + + struct item { + struct HXlist_head anchor; + char name[32]; + }; + + struct HXlist_head *e; + struct item *i, *j; + HXLIST_HEAD(list); + + i = malloc(sizeof(*i)); + HXlist_init(&e->anchor); + strcpy(i->name, "foo"); + HXlist_add_tail(&list, &i->anchor); + + i = malloc(sizeof(*i)); + HXlist_init(&e->anchor); + strcpy(i->name, "bar"); + HXlist_add_tail(&list, &i->anchor); + + HXlist_for_each(e, &list) { + i = HXlist_entry(e, typeof(*i), anchor); + printf("e=%p i=%p name=%s\n", e, i, i->name); + } + + HXlist_for_each_entry(i, &list, anchor) + printf("i=%p name=%s\n", i, i->name); + + HXlist_for_each_entry_rev(i, &list, anchor) + printf("i=%p name=%s\n", i, i->name); + + HXlist_for_each_entry_safe(i, j, &list, anchor) { + printf("i=%p name=%s\n", i, i->name); + free(i); + } + + +When to use HXdeque/HXlist +========================== + +The choice whether to use HXdeque or HXlist/HXclist depends on whether one +wants the list head handling on the developer or on the library. Especially for +“atomic” and “small” data, it might be easier to just let HXdeque do the +management. Compare the following two code examples to store strings in a +HXdeque: + +.. code-block:: c + + int main(int argc, const char **argv) + { + struct HXdeque *dq = HXdeque_init(); + while (--argc) + HXdeque_push(dq, ++argv); + return 0; + } + +...and to store strings in a HXlist: + +.. code-block:: c + + struct element { + struct HXlist_head list; + char *data; + }; + + int main(int main, const char **argv) + { + HXLIST_HEAD(lh); + while (--argc) { + struct element *e = malloc(sizeof(*e)); + e->data = *++argv; + HXlist_init(&e->list); + HXlist_add_tail(&e->list); + } + return 0; + } + +These examples assume that ``argv`` is persistent, which, for the sample, is +true. + +With HXlist, one needs to have a struct with a ``HXlist_head`` in it, and if +one does not already have such a struct, e.g. by means of wanting to store more +than just one value, one will need to create it first, as shown, and this may +lead to an expansion of code. + +This however does not mean that HXlist is the better solution over HXdeque for +data already available in a struct. As each struct has a ``list_head`` that is +unique to the node, it is not possible to share this data. Trying to add a +HXlist_head to another list is not going to end well, while HXdeque has no +problem with this as list heads are detached from the actual data in HXdeque. + +Data can be added multiple times in a HXdeque without ill effects: + +.. code-block:: c + + struct point p = {15, 30}; + HXdeque_push(dq, &p); + HXdeque_push(dq, &p); + +To support this, an extra allocation is needed on the other hand. In a HXlist, +to store *n* elements of compound data (e.g. ``struct point``), *n* allocations +are needed, assuming the list head is a stack object, and the points are not. +HXdeque will need at least *2n+1* allocations, *n* for the nodes, *n* for the +points and another for the head. -- cgit v1.2.3