New upstream version 4.7upstream/4.7

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.