Line data Source code
1 : /*
2 : * Copyright (c) 2010, Andrea Mazzoleni. All rights reserved.
3 : *
4 : * Redistribution and use in source and binary forms, with or without
5 : * modification, are permitted provided that the following conditions
6 : * are met:
7 : *
8 : * 1. Redistributions of source code must retain the above copyright
9 : * notice, this list of conditions and the following disclaimer.
10 : *
11 : * 2. Redistributions in binary form must reproduce the above copyright
12 : * notice, this list of conditions and the following disclaimer in the
13 : * documentation and/or other materials provided with the distribution.
14 : *
15 : * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
16 : * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
17 : * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
18 : * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
19 : * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
20 : * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
21 : * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
22 : * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
23 : * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
24 : * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
25 : * POSSIBILITY OF SUCH DAMAGE.
26 : */
27 :
28 : /** \file
29 : * Double linked list for collisions into hashtables.
30 : *
31 : * This list is a **doubly** linked list mainly targeted for handling collisions
32 : * into an hashtable, but **usable** also as a generic list.
33 : *
34 : * The main feature of this list is to require only one pointer to represent the
35 : * list, compared to a classic implementation requiring a head **and** a tail pointers.
36 : * This reduces the memory usage in hashtables.
37 : *
38 : * Another feature is to support the insertion at the end of the list. This **allows** to store
39 : * collisions in a stable order. Where for stable order we mean that equal elements keep
40 : * their insertion order.
41 : *
42 : * To initialize the list, you have to call tommy_list_init(), or to simply assign
43 : * to it NULL, as an empty list is represented by the NULL value.
44 : *
45 : * \code
46 : * tommy_list list;
47 : *
48 : * tommy_list_init(&list); // initializes the list
49 : * \endcode
50 : *
51 : * To insert elements in the list you have to call tommy_list_insert_tail()
52 : * or tommy_list_insert_head() for each element.
53 : * In the insertion call you have to specify the address of the node and the
54 : * address of the object.
55 : * The address of the object is used to initialize the tommy_node::data field
56 : * of the node.
57 : *
58 : * \code
59 : * struct object {
60 : * int value;
61 : * // other fields
62 : * tommy_node node;
63 : * };
64 : *
65 : * struct object* obj = malloc(sizeof(struct object)); // creates the object
66 : *
67 : * obj->value = ...; // initializes the object
68 : *
69 : * tommy_list_insert_tail(&list, &obj->node, obj); // inserts the object
70 : * \endcode
71 : *
72 : * To iterate over all the elements in the list you have to call
73 : * tommy_list_head() to get the head of the list and follow the
74 : * tommy_node::next pointer until NULL.
75 : *
76 : * \code
77 : * tommy_node* i = tommy_list_head(&list);
78 : * while (i) {
79 : * struct object* obj = i->data; // gets the object pointer
80 : *
81 : * printf("%d\n", obj->value); // process the object
82 : *
83 : * i = i->next; // go to the next element
84 : * }
85 : * \endcode
86 : *
87 : * To destroy the list you have to remove all the elements,
88 : * as the list is completely inplace and it doesn't allocate memory.
89 : * This can be done with the tommy_list_foreach() function.
90 : *
91 : * \code
92 : * // deallocates all the objects iterating the list
93 : * tommy_list_foreach(&list, free);
94 : * \endcode
95 : */
96 :
97 : #ifndef __TOMMYLIST_H
98 : #define __TOMMYLIST_H
99 :
100 : #include "tommytypes.h"
101 :
102 : /******************************************************************************/
103 : /* list */
104 :
105 : /**
106 : * Doubly linked list type.
107 : */
108 : typedef tommy_node* tommy_list;
109 :
110 : /**
111 : * Initializes the list.
112 : * The list is completely inplace, so it doesn't need to be deinitialized.
113 : */
114 20001 : tommy_inline void tommy_list_init(tommy_list* list)
115 : {
116 20001 : *list = 0;
117 20001 : }
118 :
119 : /**
120 : * Gets the head of the list.
121 : * \return The head node. For empty lists 0 is returned.
122 : */
123 28328430 : tommy_inline tommy_node* tommy_list_head(tommy_list* list)
124 : {
125 28328430 : return *list;
126 : }
127 :
128 : /**
129 : * Gets the tail of the list.
130 : * \return The tail node. For empty lists 0 is returned.
131 : */
132 2 : tommy_inline tommy_node* tommy_list_tail(tommy_list* list)
133 : {
134 2 : tommy_node* head = tommy_list_head(list);
135 :
136 2 : if (!head)
137 1 : return 0;
138 :
139 1 : return head->prev;
140 : }
141 :
142 : /** \internal
143 : * Creates a new list with a single element.
144 : * \param list The list to initialize.
145 : * \param node The node to insert.
146 : */
147 24828958 : tommy_inline void tommy_list_insert_first(tommy_list* list, tommy_node* node)
148 : {
149 : /* one element "circular" prev list */
150 24828958 : node->prev = node;
151 :
152 : /* one element "0 terminated" next list */
153 24828958 : node->next = 0;
154 :
155 24828958 : *list = node;
156 24828958 : }
157 :
158 : /** \internal
159 : * Inserts an element at the head of a non-empty list.
160 : * The element is inserted at the head of the list. The list cannot be empty.
161 : * \param list The list. The list cannot be empty.
162 : * \param node The node to insert.
163 : */
164 : tommy_inline void tommy_list_insert_head_not_empty(tommy_list* list, tommy_node* node)
165 : {
166 : tommy_node* head = tommy_list_head(list);
167 :
168 : /* insert in the "circular" prev list */
169 : node->prev = head->prev;
170 : head->prev = node;
171 :
172 : /* insert in the "0 terminated" next list */
173 : node->next = head;
174 :
175 : *list = node;
176 : }
177 :
178 : /** \internal
179 : * Inserts an element at the tail of a non-empty list.
180 : * The element is inserted at the tail of the list. The list cannot be empty.
181 : * \param head The node at the list head. It cannot be 0.
182 : * \param node The node to insert.
183 : */
184 11932624 : tommy_inline void tommy_list_insert_tail_not_empty(tommy_node* head, tommy_node* node)
185 : {
186 : /* insert in the "circular" prev list */
187 11932624 : node->prev = head->prev;
188 11932624 : head->prev = node;
189 :
190 : /* insert in the "0 terminated" next list */
191 11932624 : node->next = 0;
192 11932624 : node->prev->next = node;
193 11932624 : }
194 :
195 : /**
196 : * Inserts an element at the head of a list.
197 : * \param list The list.
198 : * \param node The node to insert.
199 : * \param data The object containing the node. It's used to set the tommy_node::data field of the node.
200 : */
201 : tommy_inline void tommy_list_insert_head(tommy_list* list, tommy_node* node, void* data)
202 : {
203 : tommy_node* head = tommy_list_head(list);
204 :
205 : if (head)
206 : tommy_list_insert_head_not_empty(list, node);
207 : else
208 : tommy_list_insert_first(list, node);
209 :
210 : node->data = data;
211 : }
212 :
213 : /**
214 : * Inserts an element at the tail of a list.
215 : * \param list The list.
216 : * \param node The node to insert.
217 : * \param data The object containing the node. It's used to set the tommy_node::data field of the node.
218 : */
219 19676726 : tommy_inline void tommy_list_insert_tail(tommy_list* list, tommy_node* node, void* data)
220 : {
221 19676726 : tommy_node* head = tommy_list_head(list);
222 :
223 19676726 : if (head)
224 9918292 : tommy_list_insert_tail_not_empty(head, node);
225 : else
226 9758434 : tommy_list_insert_first(list, node);
227 :
228 19676726 : node->data = data;
229 19676726 : }
230 :
231 : /**
232 : * Removes an element from the list.
233 : * You must already have the address of the element to remove.
234 : * \note The node content is left unchanged, including the tommy_node::next
235 : * and tommy_node::prev fields that still contain pointers **in** the list.
236 : * \param list The list.
237 : * \param node The node to remove. The node must be in the list.
238 : * \return The tommy_node::data field of the node removed.
239 : */
240 351968 : tommy_inline void* tommy_list_remove_existing(tommy_list* list, tommy_node* node)
241 : {
242 351968 : tommy_node* head = tommy_list_head(list);
243 :
244 : /* remove from the "circular" prev list */
245 351968 : if (node->next)
246 116429 : node->next->prev = node->prev;
247 : else
248 235539 : head->prev = node->prev; /* the last */
249 :
250 : /* remove from the "0 terminated" next list */
251 351968 : if (head == node)
252 252008 : *list = node->next; /* the new head, in case 0 */
253 : else
254 99960 : node->prev->next = node->next;
255 :
256 351968 : return node->data;
257 : }
258 :
259 : /**
260 : * Concats two lists.
261 : * The second list is concatenated at the first list.
262 : * \param first The first list.
263 : * \param second The second list. After this call the list content is undefined,
264 : * and you should not use it anymore.
265 : */
266 79280 : tommy_inline void tommy_list_concat(tommy_list* first, tommy_list* second)
267 : {
268 : tommy_node* first_head;
269 : tommy_node* first_tail;
270 : tommy_node* second_head;
271 :
272 : /* if the second is empty, nothing to do */
273 79280 : second_head = tommy_list_head(second);
274 79280 : if (second_head == 0)
275 70038 : return;
276 :
277 : /* if the first is empty, copy the second */
278 9242 : first_head = tommy_list_head(first);
279 9242 : if (first_head == 0) {
280 8199 : *first = *second;
281 8199 : return;
282 : }
283 :
284 : /* tail of the first list */
285 1043 : first_tail = first_head->prev;
286 :
287 : /* set the "circular" prev list */
288 1043 : first_head->prev = second_head->prev;
289 1043 : second_head->prev = first_tail;
290 :
291 : /* set the "0 terminated" next list */
292 1043 : first_tail->next = second_head;
293 : }
294 :
295 : /**
296 : * Sorts a list.
297 : * It's a stable merge sort with O(N*log(N)) worst complexity.
298 : * It's faster on degenerated cases like partially ordered lists.
299 : * \param cmp Compare function called with two elements.
300 : * The function should return <0 if the first element is less than the second, ==0 if equal, and >0 if greater.
301 : */
302 : TOMMY_API void tommy_list_sort(tommy_list* list, tommy_compare_func* cmp);
303 :
304 : /**
305 : * Checks if empty.
306 : * \return If the list is empty.
307 : */
308 7646 : tommy_inline tommy_bool_t tommy_list_empty(tommy_list* list)
309 : {
310 7646 : return tommy_list_head(list) == 0;
311 : }
312 :
313 : /**
314 : * Gets the number of elements.
315 : * \note This operation is O(n).
316 : */
317 287 : tommy_inline tommy_size_t tommy_list_count(tommy_list* list)
318 : {
319 287 : tommy_size_t count = 0;
320 287 : tommy_node* i = tommy_list_head(list);
321 :
322 24491 : while (i) {
323 24204 : ++count;
324 24204 : i = i->next;
325 : }
326 :
327 287 : return count;
328 : }
329 :
330 : /**
331 : * Calls the specified function for each element in the list.
332 : *
333 : * You cannot add or remove elements from the inside of the callback,
334 : * but can use it to deallocate them.
335 : *
336 : * \code
337 : * tommy_list list;
338 : *
339 : * // initializes the list
340 : * tommy_list_init(&list);
341 : *
342 : * ...
343 : *
344 : * // creates an object
345 : * struct object* obj = malloc(sizeof(struct object));
346 : *
347 : * ...
348 : *
349 : * // insert it in the list
350 : * tommy_list_insert_tail(&list, &obj->node, obj);
351 : *
352 : * ...
353 : *
354 : * // deallocates all the objects iterating the list
355 : * tommy_list_foreach(&list, free);
356 : * \endcode
357 : */
358 15688 : tommy_inline void tommy_list_foreach(tommy_list* list, tommy_foreach_func* func)
359 : {
360 15688 : tommy_node* node = tommy_list_head(list);
361 :
362 4229331 : while (node) {
363 4213643 : void* data = node->data;
364 4213643 : node = node->next;
365 4213643 : func(data);
366 : }
367 15688 : }
368 :
369 : /**
370 : * Calls the specified function with an argument for each element in the list.
371 : */
372 5 : tommy_inline void tommy_list_foreach_arg(tommy_list* list, tommy_foreach_arg_func* func, void* arg)
373 : {
374 5 : tommy_node* node = tommy_list_head(list);
375 :
376 11272 : while (node) {
377 11267 : void* data = node->data;
378 11267 : node = node->next;
379 11267 : func(arg, data);
380 : }
381 5 : }
382 :
383 : #endif
|
