summaryrefslogtreecommitdiff
path: root/doc/inline_list.rst
blob: 3e4cb7c83ecd1ba573947aba0ddf8cce452fbd0d (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
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, 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, 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.