========================= 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.