1 files changed, 171 insertions, 0 deletions
diff --git a/doc/linked_list.rst b/doc/linked_list.rst
new file mode 100644
index 0000000..accf7d4
--- /dev/null
+++ b/doc/linked_list.rst
@@ -0,0 +1,171 @@
+==================
+Doubly-linked list
+==================
+
+HXdeque is a data structure for a doubly-linked non-circular
+``NULL``-sentineled list. Despite being named a deque, which is short for
+double-ended queue, and which may be implemented using an array, HXdeque is in
+fact using a linked list to provide its deque functionality. Furthermore, a
+dedicated root structure and decidated node structures with indirect data
+referencing are used.
+
+
+Structural definition
+=====================
+
+.. code-block:: c
+
+	#include <libHX/deque.h>
+
+	struct HXdeque {
+		struct HXdeque_node *first, *last;
+		unsigned int items;
+		void *ptr;
+	};
+
+	struct HXdeque_node {
+		struct HXdeque_node *next, *prev;
+		struct HXdeque *parent;
+		void *ptr;
+	};
+
+The ``ptr`` member in ``struct HXdeque`` provides room for an arbitrary custom
+user-supplied pointer. items will reflect the number of elements in the list,
+and must not be modified. ``first`` and ``last`` provide entrypoints to the
+list's ends.
+
+``ptr`` within ``struct HXdeque_node`` is the pointer to the user's data. It
+may be modified and used at will by the user. See example section.
+
+
+Constructor, destructors
+========================
+
+.. code-block:: c
+
+	struct HXdeque *HXdeque_init(void);
+	void HXdeque_free(struct HXdeque *dq);
+	void HXdeque_genocide(struct HXdeque *dq);
+	void HXdeque_genocide2(struct HXdeque *dq, void (*xfree)(void *));
+	void **HXdeque_to_vec(struct HXdeque *dq, unsigned int *num);
+
+To allocate a new empty list, use ``HXdeque_init``. ``HXdeque_free`` will free
+the list (including all nodes owned by the list), but not the data pointers.
+
+``HXdeque_genocide`` is a variant that will not only destroy the list, but also
+calls a freeing function ``free``() on all stored data pointers. This puts a
+number of restrictions on the characteristics of the list: all data pointers
+must have been obtained with ``malloc``, ``calloc`` or ``realloc`` before, and
+no data pointer must exist twice in the list. The function is more efficient
+than an open-coded loop over all nodes calling ``HXdeque_del``.
+
+A generic variant is available with ``HXdeque_genocide2``, which takes a
+pointer to an appropriate freeing function. ``HXdeque_genocide`` is thus
+equivalent to ``HXdeque_genocide2(dq, free)``.
+
+To convert a linked list to a ``NULL``-terminated array, ``HXdeque_to_vec`` can
+be used. If ``num`` is not ``NULL``, the number of elements excluding the
+``NULL`` sentinel, is stored in ``*num``.
+
+
+Addition and removal
+====================
+
+.. code-block:: c
+
+	struct HXdeque_node *HXdeque_push(struct HXdeque *dq, void *ptr);
+	struct HXdeque_node *HXdeque_unshift(struct HXdeque *dq, void *ptr);
+	void *HXdeque_pop(struct HXdeque *dq);
+	void *HXdeque_shift(struct HXdeque *dq);
+	struct HXdeque *HXdeque_move(struct HXdeque_node *target, struct HXdeque_node *node);
+	void *HXdeque_del(struct HXdeque_node *node);
+
+``HXdeque_push`` and ``HXdeque_unshift`` add the data item in a new node at the
+end (“push”) or as the new first element (“unshift” as Perl calls it),
+respectively. The functions will return the new node on success, or ``NULL`` on
+failure and errno will be set. The node is owned by the list.
+
+``HXdeque_pop`` and ``HXdeque_shift`` remove the last (“pop”) or first
+(“shift”) node, respectively, and return the data pointer that was stored in
+the data.
+
+``HXdeque_move`` will unlink a node from its list, and reinsert it after the
+given target node, which may be in a different list.
+
+Deleting a node is accomplished by calling ``HXdeque_del`` on it. The data
+pointer stored in the node is not freed, but returned.
+
+
+Iteration
+=========
+
+Iterating over a HXdeque linked list is done manually and without additional
+overhead of function calls:
+
+.. code-block:: c
+
+	const struct HXdeque_node *node;
+	for (node = dq->first; node != NULL; node = node->next)
+		do_something(node->ptr);
+
+
+Searching
+=========
+
+.. code-block:: c
+
+	struct HXdeque_node *HXdeque_find(struct HXdeque *dq, const void *ptr);
+	void *HXdeque_get(struct HXdeque *dq, void *ptr);
+
+``HXdeque_find`` searches for the node which contains ``ptr``, and does so by
+beginning at the start of the list. If no node is found, ``NULL`` is returned.
+If a pointer is more than once in the list, any node may be returned.
+
+``HXdeque_get`` will further return the data pointer stored in the node —
+however, since that is just what the ptr argument is, the function practically
+only checks for existence of ``ptr`` in the list.
+
+
+Example: Using HXdeque to store and sort a list
+===============================================
+
+.. code-block:: c
+
+	#include <stdio.h>
+	#include <stdlib.h>
+	#include <string.h>
+	#include <libHX/defs.h>
+	#include <libHX/deque.h>
+	#include <libHX/string.h>
+	#include <pwd.h>
+
+	int main(void)
+	{
+		struct HXdeque *dq = HXdeque_init();
+		struct passwd *pw;
+		unsigned int elem;
+		char **users;
+
+		setpwent();
+		while ((pw = getpwent()) != NULL)
+			HXdeque_push(dq, HX_strdup(pw->pw_name));
+		endpwent();
+
+		users = reinterpret_cast(char **, HXdeque_to_vec(dq, &elem));
+		HXdeque_free(dq);
+
+		qsort(users, elem, sizeof(*users), static_cast(void *, strcmp));
+		return 0;
+	}
+
+In this example, all usernames are obtained from NSS, and put into a list.
+``HX_strdup`` is used, because ``getpwent`` will overwrite the buffer it uses
+to store its results. The list is then converted to an array, and the list is
+freed (because it is not need it anymore). ``HXdeque_genocide`` must not be
+used here, because it would free all the data pointers (strings here) that were
+just inserted into the list. Finally, the list is sorted. Because ``strcmp``
+takes two ``const char *`` arguments, but qsort mandates a function taking two
+``const void *``, a cast can be used to silence the compiler. This only works
+if and when ``char *`` pointers have the same size as ``void *``, and because
+we know that the array consists of ``char *`` pointers, and not somehting else;
+therefore, ``strcmp`` will work.