Line data Source code
1 : /* -*- Mode: C; tab-width: 8; indent-tabs-mode: t; c-basic-offset: 8 -*- */
2 : /*
3 : * lt-list.c
4 : * Copyright (C) 2011-2012 Akira TAGOH
5 : *
6 : * Authors:
7 : * Akira TAGOH <akira@tagoh.org>
8 : *
9 : * You may distribute under the terms of either the GNU
10 : * Lesser General Public License or the Mozilla Public
11 : * License, as specified in the README file.
12 : */
13 : #ifdef HAVE_CONFIG_H
14 : #include "config.h"
15 : #endif
16 :
17 : #include <stdlib.h>
18 : #include "lt-mem.h"
19 : #include "lt-messages.h"
20 : #include "lt-list.h"
21 :
22 :
23 : /**
24 : * SECTION: lt-list
25 : * @Short_Description: linked lists
26 : * @Title: Doubly-Linked Lists
27 : *
28 : * The #lt_list_t object and its associated functions provide a standard
29 : * doubly-linked list data structure.
30 : */
31 : struct _lt_list_t {
32 : lt_mem_t parent;
33 : lt_list_t *prev;
34 : lt_list_t *next;
35 : lt_pointer_t value;
36 : };
37 :
38 : /*< private >*/
39 : static void
40 582 : _lt_list_update(lt_pointer_t data)
41 : {
42 582 : lt_list_t *list = data;
43 :
44 582 : if (list->next)
45 112 : list->next->prev = list->prev;
46 582 : if (list->prev)
47 0 : list->prev->next = list->next;
48 582 : }
49 :
50 : static lt_list_t *
51 0 : _lt_list_sort_merge(lt_list_t *l1,
52 : lt_list_t *l2,
53 : lt_compare_func_t func)
54 : {
55 : int result;
56 0 : lt_list_t list, *l = &list, *lprev = NULL;
57 :
58 0 : while (l1 && l2) {
59 0 : result = func(lt_list_value(l1), lt_list_value(l2));
60 0 : if (result <= 0) {
61 0 : l->next = l1;
62 0 : l1 = lt_list_next(l1);
63 : } else {
64 0 : l->next = l2;
65 0 : l2 = lt_list_next(l2);
66 : }
67 0 : l = lt_list_next(l);
68 0 : l->prev = lprev;
69 0 : lprev = l;
70 : }
71 0 : l->next = l1 ? l1 : l2;
72 0 : l->next->prev = l;
73 :
74 0 : return list.next;
75 : }
76 :
77 : /*< protected >*/
78 : lt_list_t *
79 582 : lt_list_new(void)
80 : {
81 582 : return lt_mem_alloc_object(sizeof (lt_list_t));
82 : }
83 :
84 : /*< public >*/
85 :
86 : /**
87 : * lt_list_ref:
88 : * @list: a #lt_list_t.
89 : *
90 : * Increases the reference count of @list.
91 : *
92 : * Returns: (transfer none): the same @list object.
93 : */
94 : lt_list_t *
95 0 : lt_list_ref(lt_list_t *list)
96 : {
97 0 : lt_return_val_if_fail (list != NULL, NULL);
98 :
99 0 : return lt_mem_ref(&list->parent);
100 : }
101 :
102 : /**
103 : * lt_list_unref:
104 : * @list: a #lt_list_t.
105 : *
106 : * Decreases the reference count of @list. when its reference count
107 : * drops to 0, the object is finalized (i.e. its memory is freed).
108 : */
109 : void
110 582 : lt_list_unref(lt_list_t *list)
111 : {
112 582 : if (list)
113 582 : lt_mem_unref(&list->parent);
114 582 : }
115 :
116 : /**
117 : * lt_list_free:
118 : * @data: a #lt_list_t.
119 : *
120 : * Frees all of the memory used by a #lt_list_t.
121 : */
122 : void
123 486 : lt_list_free(lt_pointer_t data)
124 : {
125 486 : lt_list_t *l = data, *list;
126 :
127 1554 : while (l) {
128 582 : list = l;
129 582 : l = l->next;
130 582 : lt_list_unref(list);
131 : }
132 486 : }
133 :
134 : /**
135 : * lt_list_first:
136 : * @list: a #lt_list_t.
137 : *
138 : * Gets the first element in a #lt_list_t.
139 : *
140 : * Returns: (transfer none): the first element in the #lt_list_t
141 : * or %NULL if the #lt_list_t has no elements.
142 : */
143 : lt_list_t *
144 0 : lt_list_first(lt_list_t *list)
145 : {
146 0 : if (list) {
147 0 : while (list->prev)
148 0 : list = list->prev;
149 : }
150 :
151 0 : return list;
152 : }
153 :
154 : /**
155 : * lt_list_last:
156 : * @list: a #lt_list_t.
157 : *
158 : * Gets the last element in a #lt_list_t.
159 : *
160 : * Returns: (transfer none): the last element in the #lt_list_t
161 : * or %NULL if the #lt_list_t has no elements.
162 : */
163 : lt_list_t *
164 112 : lt_list_last(lt_list_t *list)
165 : {
166 112 : if (list) {
167 560 : while (list->next)
168 336 : list = list->next;
169 : }
170 :
171 112 : return list;
172 : }
173 :
174 : /**
175 : * lt_list_previous:
176 : * @list: a #lt_list_t.
177 : *
178 : * Gets the previous element in a #lt_list_t.
179 : *
180 : * Returns: (transfer none): the previous element, or %NULL if there are no previous elements.
181 : */
182 : lt_list_t *
183 0 : lt_list_previous(const lt_list_t *list)
184 : {
185 0 : return list ? list->prev : NULL;
186 : }
187 :
188 : /**
189 : * lt_list_next:
190 : * @list: a #lt_list_t.
191 : *
192 : * Gets the next element in a #lt_list_t.
193 : *
194 : * Returns: (transfer none): the next element, or %NULL if there are no more elements.
195 : */
196 : lt_list_t *
197 284 : lt_list_next(const lt_list_t *list)
198 : {
199 284 : return list ? list->next : NULL;
200 : }
201 :
202 : /**
203 : * lt_list_value:
204 : * @list: a #lt_list_t.
205 : *
206 : * Gets a value in a #lt_list_t.
207 : *
208 : * Returns: (transfer none): a pointer to be set to the #lt_list_t.
209 : */
210 : lt_pointer_t
211 284 : lt_list_value(const lt_list_t *list)
212 : {
213 284 : lt_return_val_if_fail (list != NULL, NULL);
214 :
215 284 : return list->value;
216 : }
217 :
218 : /**
219 : * lt_list_length:
220 : * @list: a #lt_list_t.
221 : *
222 : * Gets the number of elements in a #lt_list_t.
223 : *
224 : * Returns: the number of elements in the #lt_list_t.
225 : */
226 : size_t
227 0 : lt_list_length(const lt_list_t *list)
228 : {
229 0 : size_t retval = 0;
230 0 : const lt_list_t *l = list;
231 :
232 0 : while (l) {
233 0 : l = lt_list_next(l);
234 0 : retval++;
235 : }
236 :
237 0 : return retval;
238 : }
239 :
240 : /**
241 : * lt_list_append:
242 : * @list: a #lt_list_t.
243 : * @data: the data for the new element
244 : * @func: (scope async): the call back function to destroy @data or %NULL
245 : *
246 : * Adds a new element on to the end of the list.
247 : *
248 : * Returns: the new start of the #lt_list_t.
249 : */
250 : lt_list_t *
251 582 : lt_list_append(lt_list_t *list,
252 : lt_pointer_t data,
253 : lt_destroy_func_t func)
254 : {
255 582 : lt_list_t *l = lt_list_new();
256 : lt_list_t *last;
257 :
258 582 : l->value = data;
259 582 : l->next = NULL;
260 582 : lt_mem_add_ref(&l->parent, l, _lt_list_update);
261 582 : if (func)
262 582 : lt_mem_add_ref(&l->parent, data, func);
263 582 : if (list) {
264 112 : last = lt_list_last(list);
265 112 : last->next = l;
266 112 : l->prev = last;
267 : } else {
268 470 : l->prev = NULL;
269 470 : list = l;
270 : }
271 :
272 582 : return list;
273 : }
274 :
275 : #if 0
276 : /**
277 : * lt_list_remove:
278 : * @list: a #lt_list_t.
279 : * @data: the data of the element to remove.
280 : *
281 : * Removes an element from a #lt_list_t.
282 : * If two elements contain the same data, only the first is removed.
283 : * If none of the elements contain the data, the #lt_list_t is unchanged.
284 : * This works similar to lt_list_delete() though, the difference is
285 : * this won't calls the finalizer to destroy the data in the element.
286 : *
287 : * Returns: the new start of the #lt_list_t.
288 : */
289 : lt_list_t *
290 : lt_list_remove(lt_list_t *list,
291 : lt_pointer_t data)
292 : {
293 : lt_list_t *l = list;
294 :
295 : while (l) {
296 : if (l->value == data) {
297 : lt_mem_remove_ref(&l->parent, value);
298 : list = lt_list_delete_link(list, l);
299 : break;
300 : } else {
301 : l = l->next;
302 : }
303 : }
304 :
305 : return list;
306 : }
307 :
308 : /**
309 : * lt_list_delete:
310 : * @list: a #lt_list_t.
311 : * @data: the data of the element to remove.
312 : *
313 : * Removes an element from a #lt_list_t.
314 : * If two elements contain the same data, only the first is removed.
315 : * If none of the elements contain the data, the #lt_list_t is unchanged.
316 : *
317 : * Returns: the new start of the #lt_list_t.
318 : */
319 : lt_list_t *
320 : lt_list_delete(lt_list_t *list,
321 : lt_pointer_t data)
322 : {
323 : lt_list_t *l = list;
324 :
325 : while (l) {
326 : if (l->value == data) {
327 : list = lt_list_delete_link(list, l);
328 : break;
329 : } else {
330 : l = l->next;
331 : }
332 : }
333 :
334 : return list;
335 : }
336 : #endif
337 :
338 : /**
339 : * lt_list_delete_link:
340 : * @list: a #lt_list_t
341 : * @link_: node to delete from @list
342 : *
343 : * Removes the node @link_ from the @list and frees it.
344 : *
345 : * Returns: the new head of @list
346 : */
347 : lt_list_t *
348 0 : lt_list_delete_link(lt_list_t *list,
349 : lt_list_t *link_)
350 : {
351 0 : if (link_) {
352 0 : if (link_ == list)
353 0 : list = list->next;
354 0 : lt_list_unref(link_);
355 : }
356 :
357 0 : return list;
358 : }
359 :
360 : /**
361 : * lt_list_find:
362 : * @list: a #lt_list_t
363 : * @data: the element data to find
364 : *
365 : * Finds the element in a #lt_list_t which
366 : * contains the given data.
367 : *
368 : * Returns: the found #lt_list_t element, or %NULL if it's not found
369 : */
370 : lt_list_t *
371 0 : lt_list_find(lt_list_t *list,
372 : const lt_pointer_t data)
373 : {
374 0 : while (list) {
375 0 : if (list->value == data)
376 0 : break;
377 0 : list = list->next;
378 : }
379 :
380 0 : return list;
381 : }
382 :
383 : /**
384 : * lt_list_find_custom:
385 : * @list: a #lt_list_t
386 : * @data: the data passed to the function
387 : * @func: (scope call): the function to call for each element.
388 : * It should return 0 when the desired element is found
389 : *
390 : * Finds an element in a #lt_list_t, using a supplied function to
391 : * find the desired element. It iterates over the list, calling
392 : * the given function which should return 0 when the desired
393 : * element is found. The function takes two const #lt_pointer_t
394 : * arguments, the #lt_list_t element's data as the first argument
395 : * and the given data.
396 : *
397 : * Returns: the found #lt_list_t element, or %NULL if it's not found
398 : */
399 : lt_list_t *
400 0 : lt_list_find_custom(lt_list_t *list,
401 : const lt_pointer_t data,
402 : lt_compare_func_t func)
403 : {
404 0 : lt_return_val_if_fail (func != NULL, NULL);
405 :
406 0 : while (list) {
407 0 : if (!func(list->value, data))
408 0 : break;
409 0 : list = list->next;
410 : }
411 :
412 0 : return list;
413 : }
414 :
415 : /**
416 : * lt_list_sort:
417 : * @list: a #lt_list_t
418 : * @func: (scope call): the comparison function used to sort the #lt_list_t.
419 : * This function is passed the data from 2 elements of the #lt_list_t
420 : * and should return 0 if they are equal, a negative value if the
421 : * first element comes before the second, or a positive value if
422 : * the first element comes after the second.
423 : *
424 : * Sorts a #lt_list_t using the given comparison function.
425 : *
426 : * Returns: the start of the sorted #lt_list_t
427 : */
428 : lt_list_t *
429 0 : lt_list_sort(lt_list_t *list,
430 : lt_compare_func_t func)
431 : {
432 : lt_list_t *a, *b;
433 0 : size_t i = 0, j = 0;
434 :
435 0 : lt_return_val_if_fail (list != NULL, NULL);
436 :
437 0 : if (!list->next)
438 0 : return list;
439 :
440 0 : a = b = list;
441 0 : while (b->next) {
442 0 : b = lt_list_next(b);
443 0 : j++;
444 0 : if ((j / 2) > i) {
445 0 : a = lt_list_next(a);
446 0 : i++;
447 : }
448 : }
449 0 : b = a->next;
450 0 : a->next = NULL;
451 0 : b->prev = NULL;
452 :
453 0 : return _lt_list_sort_merge(lt_list_sort(list, func),
454 : lt_list_sort(b, func),
455 : func);
456 : }
457 :
458 : /**
459 : * lt_list_pop:
460 : * @list: a #lt_list_t
461 : * @data: a pointer to set the data in the first element
462 : *
463 : * Sets the data in the first element to @data and drop the element.
464 : *
465 : * Returns: the new head of @list.
466 : */
467 : lt_list_t *
468 0 : lt_list_pop(lt_list_t *list,
469 : lt_pointer_t *data)
470 : {
471 0 : lt_return_val_if_fail (list != NULL, NULL);
472 :
473 0 : lt_mem_remove_ref(&list->parent, list->value);
474 0 : if (data)
475 0 : *data = list->value;
476 0 : list = lt_list_delete_link(list, list);
477 :
478 0 : return list;
479 : }
|
