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 double linked list mainly targetted for handling collisions
32 : * into an hashtables, but useable 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 an 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 allow 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 : * Double 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 11929 : tommy_inline void tommy_list_init(tommy_list* list)
115 : {
116 11929 : *list = 0;
117 11929 : }
118 :
119 : /**
120 : * Gets the head of the list.
121 : * \return The head node. For empty lists 0 is returned.
122 : */
123 25358302 : tommy_inline tommy_node* tommy_list_head(tommy_list* list)
124 : {
125 25358302 : 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 23435424 : tommy_inline void tommy_list_insert_first(tommy_list* list, tommy_node* node)
148 : {
149 : /* one element "circular" prev list */
150 23435424 : node->prev = node;
151 :
152 : /* one element "0 terminated" next list */
153 23435424 : node->next = 0;
154 :
155 23435424 : *list = node;
156 23435424 : }
157 :
158 : /** \internal
159 : * Inserts an element at the head of a not 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 not 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 11044827 : tommy_inline void tommy_list_insert_tail_not_empty(tommy_node* head, tommy_node* node)
185 : {
186 : /* insert in the "circular" prev list */
187 11044827 : node->prev = head->prev;
188 11044827 : head->prev = node;
189 :
190 : /* insert in the "0 terminated" next list */
191 11044827 : node->next = 0;
192 11044827 : node->prev->next = node;
193 11044827 : }
194 :
195 : /**
196 : * Inserts an element at the head of a list.
197 : * \param node The node to insert.
198 : * \param data The object containing the node. It's used to set the tommy_node::data field of the node.
199 : */
200 : tommy_inline void tommy_list_insert_head(tommy_list* list, tommy_node* node, void* data)
201 : {
202 : tommy_node* head = tommy_list_head(list);
203 :
204 : if (head)
205 : tommy_list_insert_head_not_empty(list, node);
206 : else
207 : tommy_list_insert_first(list, node);
208 :
209 : node->data = data;
210 : }
211 :
212 : /**
213 : * Inserts an element at the tail of a list.
214 : * \param node The node to insert.
215 : * \param data The object containing the node. It's used to set the tommy_node::data field of the node.
216 : */
217 18395051 : tommy_inline void tommy_list_insert_tail(tommy_list* list, tommy_node* node, void* data)
218 : {
219 18395051 : tommy_node* head = tommy_list_head(list);
220 :
221 18395051 : if (head)
222 9156460 : tommy_list_insert_tail_not_empty(head, node);
223 : else
224 9238591 : tommy_list_insert_first(list, node);
225 :
226 18395051 : node->data = data;
227 18395051 : }
228 :
229 : /** \internal
230 : * Removes an element from the head of a not empty list.
231 : * \param list The list. The list cannot be empty.
232 : * \return The node removed.
233 : */
234 : tommy_inline tommy_node* tommy_list_remove_head_not_empty(tommy_list* list)
235 : {
236 : tommy_node* head = tommy_list_head(list);
237 :
238 : /* remove from the "circular" prev list */
239 : head->next->prev = head->prev;
240 :
241 : /* remove from the "0 terminated" next list */
242 : *list = head->next; /* the new head, in case 0 */
243 :
244 : return head;
245 : }
246 :
247 : /**
248 : * Removes an element from the list.
249 : * You must already have the address of the element to remove.
250 : * \note The node content is left unchanged, including the tommy_node::next
251 : * and tommy_node::prev fields that still contain pointers at the list.
252 : * \param node The node to remove. The node must be in the list.
253 : * \return The tommy_node::data field of the node removed.
254 : */
255 353399 : tommy_inline void* tommy_list_remove_existing(tommy_list* list, tommy_node* node)
256 : {
257 353399 : tommy_node* head = tommy_list_head(list);
258 :
259 : /* remove from the "circular" prev list */
260 353399 : if (node->next)
261 118100 : node->next->prev = node->prev;
262 : else
263 235299 : head->prev = node->prev; /* the last */
264 :
265 : /* remove from the "0 terminated" next list */
266 353399 : if (head == node)
267 249521 : *list = node->next; /* the new head, in case 0 */
268 : else
269 103878 : node->prev->next = node->next;
270 :
271 353399 : return node->data;
272 : }
273 :
274 : /**
275 : * Concats two lists.
276 : * The second list is concatenated at the first list.
277 : * \param first The first list.
278 : * \param second The second list. After this call the list content is undefined,
279 : * and you should not use it anymore.
280 : */
281 79280 : tommy_inline void tommy_list_concat(tommy_list* first, tommy_list* second)
282 : {
283 : tommy_node* first_head;
284 : tommy_node* first_tail;
285 : tommy_node* second_head;
286 :
287 : /* if the second is empty, nothing to do */
288 79280 : second_head = tommy_list_head(second);
289 79280 : if (second_head == 0)
290 70002 : return;
291 :
292 : /* if the first is empty, copy the second */
293 9278 : first_head = tommy_list_head(first);
294 9278 : if (first_head == 0) {
295 8209 : *first = *second;
296 8209 : return;
297 : }
298 :
299 : /* tail of the first list */
300 1069 : first_tail = first_head->prev;
301 :
302 : /* set the "circular" prev list */
303 1069 : first_head->prev = second_head->prev;
304 1069 : second_head->prev = first_tail;
305 :
306 : /* set the "0 terminated" next list */
307 1069 : first_tail->next = second_head;
308 : }
309 :
310 : /**
311 : * Sorts a list.
312 : * It's a stable merge sort with O(N*log(N)) worst complexity.
313 : * It's faster on degenerated cases like partially ordered lists.
314 : * \param cmp Compare function called with two elements.
315 : * The function should return <0 if the first element is less than the second, ==0 if equal, and >0 if greather.
316 : */
317 : void tommy_list_sort(tommy_list* list, tommy_compare_func* cmp);
318 :
319 : /**
320 : * Checks if empty.
321 : * \return If the list is empty.
322 : */
323 4387 : tommy_inline tommy_bool_t tommy_list_empty(tommy_list* list)
324 : {
325 4387 : return tommy_list_head(list) == 0;
326 : }
327 :
328 : /**
329 : * Gets the number of elements.
330 : * \note This operation is O(n).
331 : */
332 260 : tommy_inline tommy_count_t tommy_list_count(tommy_list* list)
333 : {
334 260 : tommy_count_t count = 0;
335 260 : tommy_node* i = tommy_list_head(list);
336 :
337 2075 : while (i) {
338 1555 : ++count;
339 1555 : i = i->next;
340 : }
341 :
342 260 : return count;
343 : }
344 :
345 : /**
346 : * Calls the specified function for each element in the list.
347 : *
348 : * You cannot add or remove elements from the inside of the callback,
349 : * but can use it to deallocate them.
350 : *
351 : * \code
352 : * tommy_list list;
353 : *
354 : * // initializes the list
355 : * tommy_list_init(&list);
356 : *
357 : * ...
358 : *
359 : * // creates an object
360 : * struct object* obj = malloc(sizeof(struct object));
361 : *
362 : * ...
363 : *
364 : * // insert it in the list
365 : * tommy_list_insert_tail(&list, &obj->node, obj);
366 : *
367 : * ...
368 : *
369 : * // deallocates all the objects iterating the list
370 : * tommy_list_foreach(&list, free);
371 : * \endcode
372 : */
373 7645 : tommy_inline void tommy_list_foreach(tommy_list* list, tommy_foreach_func* func)
374 : {
375 7645 : tommy_node* node = tommy_list_head(list);
376 :
377 3679911 : while (node) {
378 3664621 : void* data = node->data;
379 3664621 : node = node->next;
380 3664621 : func(data);
381 : }
382 7645 : }
383 :
384 : /**
385 : * Calls the specified function with an argument for each element in the list.
386 : */
387 : tommy_inline void tommy_list_foreach_arg(tommy_list* list, tommy_foreach_arg_func* func, void* arg)
388 : {
389 : tommy_node* node = tommy_list_head(list);
390 :
391 : while (node) {
392 : void* data = node->data;
393 : node = node->next;
394 : func(arg, data);
395 : }
396 : }
397 :
398 : #endif
399 :
|
