Line data Source code
1 : // SPDX-License-Identifier: BSD-2-Clause
2 : // Copyright (C) 2010 Andrea Mazzoleni
3 :
4 : /** \file
5 : * Double linked list for collisions into hashtables.
6 : *
7 : * This list is a **doubly** linked list mainly targeted for handling collisions
8 : * into an hashtable, but **usable** also as a generic list.
9 : *
10 : * The main feature of this list is to require only one pointer to represent the
11 : * list, compared to a classic implementation requiring a head **and** a tail pointers.
12 : * This reduces the memory usage in hashtables.
13 : *
14 : * Another feature is to support the insertion at the end of the list. This **allows** to store
15 : * collisions in a stable order. Where for stable order we mean that equal elements keep
16 : * their insertion order.
17 : *
18 : * To initialize the list, you have to call tommy_list_init(), or to simply assign
19 : * to it NULL, as an empty list is represented by the NULL value.
20 : *
21 : * \code
22 : * tommy_list list;
23 : *
24 : * tommy_list_init(&list); // initializes the list
25 : * \endcode
26 : *
27 : * To insert elements in the list you have to call tommy_list_insert_tail()
28 : * or tommy_list_insert_head() for each element.
29 : * In the insertion call you have to specify the address of the node and the
30 : * address of the object.
31 : * The address of the object is used to initialize the tommy_node::data field
32 : * of the node.
33 : *
34 : * \code
35 : * struct object {
36 : * int value;
37 : * // other fields
38 : * tommy_node node;
39 : * };
40 : *
41 : * struct object* obj = malloc(sizeof(struct object)); // creates the object
42 : *
43 : * obj->value = ...; // initializes the object
44 : *
45 : * tommy_list_insert_tail(&list, &obj->node, obj); // inserts the object
46 : * \endcode
47 : *
48 : * To iterate over all the elements in the list you have to call
49 : * tommy_list_head() to get the head of the list and follow the
50 : * tommy_node::next pointer until NULL.
51 : *
52 : * \code
53 : * tommy_node* i = tommy_list_head(&list);
54 : * while (i) {
55 : * struct object* obj = i->data; // gets the object pointer
56 : *
57 : * printf("%d\n", obj->value); // process the object
58 : *
59 : * i = i->next; // go to the next element
60 : * }
61 : * \endcode
62 : *
63 : * To destroy the list you have to remove all the elements,
64 : * as the list is completely inplace and it doesn't allocate memory.
65 : * This can be done with the tommy_list_foreach() function.
66 : *
67 : * \code
68 : * // deallocates all the objects iterating the list
69 : * tommy_list_foreach(&list, free);
70 : * \endcode
71 : */
72 :
73 : #ifndef __TOMMYLIST_H
74 : #define __TOMMYLIST_H
75 :
76 : #include "tommytypes.h"
77 :
78 : /******************************************************************************/
79 : /* list */
80 :
81 : /**
82 : * Doubly linked list type.
83 : */
84 : typedef tommy_node* tommy_list;
85 :
86 : /**
87 : * Initializes the list.
88 : * The list is completely inplace, so it doesn't need to be deinitialized.
89 : */
90 23403 : tommy_inline void tommy_list_init(tommy_list* list)
91 : {
92 23403 : *list = 0;
93 23403 : }
94 :
95 : /**
96 : * Gets the head of the list.
97 : * \return The head node. For empty lists 0 is returned.
98 : */
99 28869531 : tommy_inline tommy_node* tommy_list_head(tommy_list* list)
100 : {
101 28869531 : return *list;
102 : }
103 :
104 : /**
105 : * Gets the tail of the list.
106 : * \return The tail node. For empty lists 0 is returned.
107 : */
108 2 : tommy_inline tommy_node* tommy_list_tail(tommy_list* list)
109 : {
110 2 : tommy_node* head = tommy_list_head(list);
111 :
112 2 : if (!head)
113 1 : return 0;
114 :
115 1 : return head->prev;
116 : }
117 :
118 : /** \internal
119 : * Creates a new list with a single element.
120 : * \param list The list to initialize.
121 : * \param node The node to insert.
122 : */
123 25182043 : tommy_inline void tommy_list_insert_first(tommy_list* list, tommy_node* node)
124 : {
125 : /* one element "circular" prev list */
126 25182043 : node->prev = node;
127 :
128 : /* one element "0 terminated" next list */
129 25182043 : node->next = 0;
130 :
131 25182043 : *list = node;
132 25182043 : }
133 :
134 : /** \internal
135 : * Inserts an element at the head of a non-empty list.
136 : * The element is inserted at the head of the list. The list cannot be empty.
137 : * \param list The list. The list cannot be empty.
138 : * \param node The node to insert.
139 : */
140 : tommy_inline void tommy_list_insert_head_not_empty(tommy_list* list, tommy_node* node)
141 : {
142 : tommy_node* head = tommy_list_head(list);
143 :
144 : /* insert in the "circular" prev list */
145 : node->prev = head->prev;
146 : head->prev = node;
147 :
148 : /* insert in the "0 terminated" next list */
149 : node->next = head;
150 :
151 : *list = node;
152 : }
153 :
154 : /** \internal
155 : * Inserts an element at the tail of a non-empty list.
156 : * The element is inserted at the tail of the list. The list cannot be empty.
157 : * \param head The node at the list head. It cannot be 0.
158 : * \param node The node to insert.
159 : */
160 12207710 : tommy_inline void tommy_list_insert_tail_not_empty(tommy_node* head, tommy_node* node)
161 : {
162 : /* insert in the "circular" prev list */
163 12207710 : node->prev = head->prev;
164 12207710 : head->prev = node;
165 :
166 : /* insert in the "0 terminated" next list */
167 12207710 : node->next = 0;
168 12207710 : node->prev->next = node;
169 12207710 : }
170 :
171 : /**
172 : * Inserts an element at the head of a list.
173 : * \param list The list.
174 : * \param node The node to insert.
175 : * \param data The object containing the node. It's used to set the tommy_node::data field of the node.
176 : */
177 : tommy_inline void tommy_list_insert_head(tommy_list* list, tommy_node* node, void* data)
178 : {
179 : tommy_node* head = tommy_list_head(list);
180 :
181 : if (head)
182 : tommy_list_insert_head_not_empty(list, node);
183 : else
184 : tommy_list_insert_first(list, node);
185 :
186 : node->data = data;
187 : }
188 :
189 : /**
190 : * Inserts an element at the tail of a list.
191 : * \param list The list.
192 : * \param node The node to insert.
193 : * \param data The object containing the node. It's used to set the tommy_node::data field of the node.
194 : */
195 20056001 : tommy_inline void tommy_list_insert_tail(tommy_list* list, tommy_node* node, void* data)
196 : {
197 20056001 : tommy_node* head = tommy_list_head(list);
198 :
199 20056001 : if (head)
200 10139409 : tommy_list_insert_tail_not_empty(head, node);
201 : else
202 9916592 : tommy_list_insert_first(list, node);
203 :
204 20056001 : node->data = data;
205 20056001 : }
206 :
207 : /**
208 : * Inserts an element before the specified reference node.
209 : * \param list The list.
210 : * \param reference The reference node. The new node will be inserted before this node. The reference node must be in the list.
211 : * \param node The node to insert.
212 : * \param data The object containing the node. It's used to set the tommy_node::data field of the node.
213 : */
214 : tommy_inline void tommy_list_insert_before(tommy_list* list, tommy_node* reference, tommy_node* node, void* data)
215 : {
216 : tommy_node* head = tommy_list_head(list);
217 :
218 : /* if inserting before the head, update the list pointer */
219 : if (head == reference) {
220 : tommy_list_insert_head_not_empty(list, node);
221 : } else {
222 : /* insert in the "circular" prev list */
223 : node->prev = reference->prev;
224 : reference->prev = node;
225 :
226 : /* insert in the "0 terminated" next list */
227 : node->next = reference;
228 : node->prev->next = node;
229 : }
230 :
231 : node->data = data;
232 : }
233 :
234 : /**
235 : * Inserts an element after the specified reference node.
236 : * \param list The list.
237 : * \param reference The reference node. The new node will be inserted after this node. The reference node must be in the list.
238 : * \param node The node to insert.
239 : * \param data The object containing the node. It's used to set the tommy_node::data field of the node.
240 : */
241 : tommy_inline void tommy_list_insert_after(tommy_list* list, tommy_node* reference, tommy_node* node, void* data)
242 : {
243 : tommy_node* head = tommy_list_head(list);
244 :
245 : /* if inserting after the tail (reference->next == 0), handle specially */
246 : if (reference->next == 0) {
247 : tommy_list_insert_tail_not_empty(head, node);
248 : } else {
249 : /* insert in the "circular" prev list */
250 : node->prev = reference;
251 : reference->next->prev = node;
252 :
253 : /* insert in the "0 terminated" next list */
254 : node->next = reference->next;
255 : reference->next = node;
256 : }
257 :
258 : node->data = data;
259 : }
260 :
261 : /**
262 : * Removes an element from the list.
263 : * You must already have the address of the element to remove.
264 : * \note The node content is left unchanged, including the tommy_node::next
265 : * and tommy_node::prev fields that still contain pointers **in** the list.
266 : * \param list The list.
267 : * \param node The node to remove. The node must be in the list.
268 : * \return The tommy_node::data field of the node removed.
269 : */
270 365000 : tommy_inline void* tommy_list_remove_existing(tommy_list* list, tommy_node* node)
271 : {
272 365000 : tommy_node* head = tommy_list_head(list);
273 :
274 : /* remove from the "circular" prev list */
275 365000 : if (node->next)
276 123294 : node->next->prev = node->prev;
277 : else
278 241706 : head->prev = node->prev; /* the last */
279 :
280 : /* remove from the "0 terminated" next list */
281 365000 : if (head == node)
282 260765 : *list = node->next; /* the new head, in case 0 */
283 : else
284 104235 : node->prev->next = node->next;
285 :
286 365000 : return node->data;
287 : }
288 :
289 : /**
290 : * Concats two lists.
291 : * The second list is concatenated at the first list.
292 : * \param first The first list.
293 : * \param second The second list. After this call the list content is undefined,
294 : * and you should not use it anymore.
295 : */
296 79280 : tommy_inline void tommy_list_concat(tommy_list* first, tommy_list* second)
297 : {
298 : tommy_node* first_head;
299 : tommy_node* first_tail;
300 : tommy_node* second_head;
301 :
302 : /* if the second is empty, nothing to do */
303 79280 : second_head = tommy_list_head(second);
304 79280 : if (second_head == 0)
305 70191 : return;
306 :
307 : /* if the first is empty, copy the second */
308 9089 : first_head = tommy_list_head(first);
309 9089 : if (first_head == 0) {
310 8045 : *first = *second;
311 8045 : return;
312 : }
313 :
314 : /* tail of the first list */
315 1044 : first_tail = first_head->prev;
316 :
317 : /* set the "circular" prev list */
318 1044 : first_head->prev = second_head->prev;
319 1044 : second_head->prev = first_tail;
320 :
321 : /* set the "0 terminated" next list */
322 1044 : first_tail->next = second_head;
323 : }
324 :
325 : /**
326 : * Sorts a list.
327 : * It's a stable merge sort with O(N*log(N)) worst complexity.
328 : * It's faster on degenerated cases like partially ordered lists.
329 : * \param cmp Compare function called with two elements.
330 : * The function should return <0 if the first element is less than the second, ==0 if equal, and >0 if greater.
331 : */
332 : TOMMY_API void tommy_list_sort(tommy_list* list, tommy_compare_func* cmp);
333 :
334 : /**
335 : * Checks if empty.
336 : * \return If the list is empty.
337 : */
338 9685 : tommy_inline tommy_bool_t tommy_list_empty(tommy_list* list)
339 : {
340 9685 : return tommy_list_head(list) == 0;
341 : }
342 :
343 : /**
344 : * Gets the number of elements.
345 : * \note This operation is O(n).
346 : */
347 491 : tommy_inline tommy_size_t tommy_list_count(tommy_list* list)
348 : {
349 491 : tommy_size_t count = 0;
350 491 : tommy_node* i = tommy_list_head(list);
351 :
352 72005 : while (i) {
353 71514 : ++count;
354 71514 : i = i->next;
355 : }
356 :
357 491 : return count;
358 : }
359 :
360 : /**
361 : * Calls the specified function for each element in the list.
362 : *
363 : * You cannot add or remove elements from the inside of the callback,
364 : * but can use it to deallocate them.
365 : *
366 : * \code
367 : * tommy_list list;
368 : *
369 : * // initializes the list
370 : * tommy_list_init(&list);
371 : *
372 : * ...
373 : *
374 : * // creates an object
375 : * struct object* obj = malloc(sizeof(struct object));
376 : *
377 : * ...
378 : *
379 : * // insert it in the list
380 : * tommy_list_insert_tail(&list, &obj->node, obj);
381 : *
382 : * ...
383 : *
384 : * // deallocates all the objects iterating the list
385 : * tommy_list_foreach(&list, free);
386 : * \endcode
387 : */
388 18348 : tommy_inline void tommy_list_foreach(tommy_list* list, tommy_foreach_func* func)
389 : {
390 18348 : tommy_node* node = tommy_list_head(list);
391 :
392 4146369 : while (node) {
393 4128021 : void* data = node->data;
394 4128021 : node = node->next;
395 4128021 : func(data);
396 : }
397 18348 : }
398 :
399 : /**
400 : * Calls the specified function with an argument for each element in the list.
401 : */
402 5 : tommy_inline void tommy_list_foreach_arg(tommy_list* list, tommy_foreach_arg_func* func, void* arg)
403 : {
404 5 : tommy_node* node = tommy_list_head(list);
405 :
406 11272 : while (node) {
407 11267 : void* data = node->data;
408 11267 : node = node->next;
409 11267 : func(arg, data);
410 : }
411 5 : }
412 :
413 : #endif
|
