summaryrefslogtreecommitdiff
path: root/doc/inline_list.rst
diff options
context:
space:
mode:
authorJörg Frings-Fürst <debian@jff-webhosting.net>2022-10-24 21:03:42 +0200
committerJörg Frings-Fürst <debian@jff-webhosting.net>2022-10-24 21:03:42 +0200
commit532d4a24e2013262dfa41fd85c06a9715c99abf7 (patch)
tree3b7f4fac1e983ead408c20a2f330b41aa2399ab1 /doc/inline_list.rst
parenta1bdcfa3ca8af4ddb69ee57d716aa943cf3fe94a (diff)
New upstream version 4.7upstream/4.7
Diffstat (limited to 'doc/inline_list.rst')
-rw-r--r--doc/inline_list.rst253
1 files changed, 253 insertions, 0 deletions
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 <libHX/list.h>
+
+ 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.