1 /* Libvisual - The audio visualisation framework.
2 *
3 * Copyright (C) 2004, 2005, 2006 Dennis Smit <ds@nerds-incorporated.org>
4 *
5 * List implementation from RCL.
6 * Copyright (C) 2002, 2003, 2004
7 * Dennis Smit <ds@nerds-incorporated.org>,
8 * Sepp Wijnands <mrrazz@nerds-incorporated.org>,
9 * Tom Wimmenhove <nohup@nerds-incorporated.org>
10 *
11 * Authors: Dennis Smit <ds@nerds-incorporated.org>
12 * Sepp Wijnands <mrrazz@nerds-incorporated.org>,
13 * Tom Wimmenhove <nohup@nerds-incorporated.org>
14 *
15 * $Id: lv_list.c,v 1.30 2006/01/22 13:23:37 synap Exp $
16 *
17 * This program is free software; you can redistribute it and/or modify
18 * it under the terms of the GNU Lesser General Public License as
19 * published by the Free Software Foundation; either version 2.1
20 * of the License, or (at your option) any later version.
21 *
22 * This program is distributed in the hope that it will be useful,
23 * but WITHOUT ANY WARRANTY; without even the implied warranty of
24 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
25 * GNU Lesser General Public License for more details.
26 *
27 * You should have received a copy of the GNU Lesser General Public License
28 * along with this program; if not, write to the Free Software
29 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
30 */
31
32 #include <stdio.h>
33 #include <stdlib.h>
34 #include <unistd.h>
35 #include <string.h>
36 #include <fcntl.h>
37
38 #include <lvconfig.h>
39 #include "lv_list.h"
40 #include "lv_log.h"
41 #include "lv_mem.h"
42
43 #define LIST_ITERCONTEXT(obj) (VISUAL_CHECK_CAST ((obj), ListIterContext))
44
45
46 typedef struct _ListIterContext ListIterContext;
47
48 struct _ListIterContext {
49 VisObject *object;
50
51 VisListEntry *cur;
52 };
53
54
55 static int list_destroy (VisCollection *collection);
56 static int list_size (VisCollection *collection);
57 static VisCollectionIter *list_iter (VisCollection *collection);
58
59 static void list_iter_assign (VisCollectionIter *iter, VisCollection *collection, VisObject *itercontext, int index);
60 static int list_iter_has_more (VisCollectionIter *iter, VisCollection *collection, VisObject *itercontext);
61 static void list_iter_next (VisCollectionIter *iter, VisCollection *collection, VisObject *itercontext);
62 static void *list_iter_getdata (VisCollectionIter *iter, VisCollection *collection, VisObject *itercontext);
63
64
list_destroy(VisCollection * collection)65 static int list_destroy (VisCollection *collection)
66 {
67 VisCollectionDestroyerFunc destroyer;
68 VisList *list = VISUAL_LIST (collection);
69 VisListEntry *le = NULL;
70 void *elem;
71
72 visual_log_return_val_if_fail (list != NULL, -VISUAL_ERROR_COLLECTION_NULL);
73
74 destroyer = visual_collection_get_destroyer (collection);
75
76 /* Walk through the given list, possibly calling the destroyer for it */
77 if (destroyer == NULL) {
78 while ((elem = visual_list_next (list, &le)) != NULL)
79 visual_list_delete (list, &le);
80 } else {
81 while ((elem = visual_list_next (list, &le)) != NULL) {
82 destroyer (elem);
83 visual_list_delete (list, &le);
84 }
85 }
86
87 return VISUAL_OK;
88 }
89
list_size(VisCollection * collection)90 static int list_size (VisCollection *collection)
91 {
92 VisList *list = VISUAL_LIST (collection);
93
94 visual_log_return_val_if_fail (list != NULL, -VISUAL_ERROR_COLLECTION_NULL);
95
96 return list->count;
97 }
98
list_iter(VisCollection * collection)99 static VisCollectionIter *list_iter (VisCollection *collection)
100 {
101 VisCollectionIter *iter;
102 ListIterContext *context;
103 VisList *list = VISUAL_LIST (collection);
104
105 context = visual_mem_new0 (ListIterContext, 1);
106
107 /* Do the VisObject initialization for the ListIterContext */
108 visual_object_initialize (VISUAL_OBJECT (context), TRUE, NULL);
109 context->cur = list->head;
110
111 iter = visual_collection_iter_new (list_iter_assign, list_iter_next, list_iter_has_more,
112 list_iter_getdata, collection, VISUAL_OBJECT (context));
113
114 return iter;
115 }
116
list_iter_assign(VisCollectionIter * iter,VisCollection * collection,VisObject * itercontext,int index)117 static void list_iter_assign (VisCollectionIter *iter, VisCollection *collection, VisObject *itercontext, int index)
118 {
119 ListIterContext *context = LIST_ITERCONTEXT (itercontext);
120 VisList *list = VISUAL_LIST (collection);
121 int i;
122
123 context->cur = list->head;
124
125 if (context->cur == NULL)
126 return;
127
128 for (i = 0; i < index; i++) {
129 context->cur = context->cur->next;
130
131 if (context->cur == NULL)
132 return;
133 }
134 }
135
list_iter_next(VisCollectionIter * iter,VisCollection * collection,VisObject * itercontext)136 static void list_iter_next (VisCollectionIter *iter, VisCollection *collection, VisObject *itercontext)
137 {
138 ListIterContext *context = LIST_ITERCONTEXT (itercontext);
139 VisListEntry *le = context->cur;
140
141 if (le == NULL)
142 return;
143
144 context->cur = le->next;
145 }
146
list_iter_has_more(VisCollectionIter * iter,VisCollection * collection,VisObject * itercontext)147 static int list_iter_has_more (VisCollectionIter *iter, VisCollection *collection, VisObject *itercontext)
148 {
149 ListIterContext *context = LIST_ITERCONTEXT (itercontext);
150
151 if (context->cur == NULL)
152 return FALSE;
153
154 return TRUE;
155 }
156
list_iter_getdata(VisCollectionIter * iter,VisCollection * collection,VisObject * itercontext)157 static void *list_iter_getdata (VisCollectionIter *iter, VisCollection *collection, VisObject *itercontext)
158 {
159 ListIterContext *context = LIST_ITERCONTEXT (itercontext);
160 VisListEntry *le = context->cur;
161
162 if (le == NULL)
163 return NULL;
164
165 return le->data;
166 }
167
168 /**
169 * @defgroup VisList VisList
170 * @{
171 */
172
173 /**
174 * Creates a new VisList structure.
175 * The VisList system is a double linked list implementation.
176 *
177 * @return A newly allocated VisList.
178 */
visual_list_new(VisCollectionDestroyerFunc destroyer)179 VisList *visual_list_new (VisCollectionDestroyerFunc destroyer)
180 {
181 VisList *list;
182
183 list = visual_mem_new0 (VisList, 1);
184
185 visual_list_init (list, destroyer);
186
187 /* do the visobject initialization */
188 visual_object_set_allocated (VISUAL_OBJECT (list), TRUE);
189 visual_object_ref (VISUAL_OBJECT (list));
190
191 return list;
192 }
193
194 /**
195 *
196 */
visual_list_init(VisList * list,VisCollectionDestroyerFunc destroyer)197 int visual_list_init (VisList *list, VisCollectionDestroyerFunc destroyer)
198 {
199 visual_log_return_val_if_fail (list != NULL, -VISUAL_ERROR_LIST_NULL);
200
201 /* Do the VisObject initialization */
202 visual_object_clear (VISUAL_OBJECT (list));
203 visual_object_set_dtor (VISUAL_OBJECT (list), visual_collection_dtor);
204 visual_object_set_allocated (VISUAL_OBJECT (list), FALSE);
205
206 /* Set the VisCollection data */
207 visual_collection_set_destroyer (VISUAL_COLLECTION (list), destroyer);
208 visual_collection_set_destroy_func (VISUAL_COLLECTION (list), list_destroy);
209 visual_collection_set_size_func (VISUAL_COLLECTION (list), list_size);
210 visual_collection_set_iter_func (VISUAL_COLLECTION (list), list_iter);
211
212 /* Set the VisList data */
213 list->head = NULL;
214 list->tail = NULL;
215 list->count = 0;
216
217 return VISUAL_OK;
218 }
219
220 /**
221 * Go to the next entry in the list and return it's data element.
222 * This function will load the next entry in le and return a pointer
223 * to the data element.
224 *
225 * @see visual_list_prev
226 *
227 * @param list Pointer to the VisList we're traversing.
228 * @param le Pointer to a VisListEntry to store the next entry within
229 * and also to use as a reference to determine at which entry we're
230 * currently. To begin traversing do: VisListEntry *le = NULL and pass
231 * it as &le in the argument.
232 *
233 * @return The data element of the next entry, or NULL.
234 */
visual_list_next(VisList * list,VisListEntry ** le)235 void *visual_list_next (VisList *list, VisListEntry **le)
236 {
237 visual_log_return_val_if_fail (list != NULL, NULL);
238 visual_log_return_val_if_fail (le != NULL, NULL);
239
240 if (*le == NULL)
241 *le = list->head;
242 else
243 *le = (*le)->next;
244
245 if (*le != NULL)
246 return (*le)->data;
247
248 return NULL;
249 }
250
251 /**
252 * Go to the previous entry in the list and return it's data element.
253 * This function will load the previous entry in le and return a pointer
254 * to the data element.
255 *
256 * @see visual_list_next
257 *
258 * @param list Pointer to the VisList we're traversing.
259 * @param le Pointer to a VisListEntry to store the previous entry within
260 * and also to use as a reference to determine at which entry we're
261 * currently. To begin traversing at the end of the list do:
262 * VisList *le = NULL and pass it as &le in the argument.
263 *
264 * @return The data element of the previous entry, or NULL.
265 */
visual_list_prev(VisList * list,VisListEntry ** le)266 void *visual_list_prev (VisList *list, VisListEntry **le)
267 {
268 visual_log_return_val_if_fail (list != NULL, NULL);
269 visual_log_return_val_if_fail (le != NULL, NULL);
270
271 if (!*le)
272 *le = list->tail;
273 else
274 *le = (*le)->prev;
275
276 if (*le)
277 return (*le)->data;
278
279 return NULL;
280 }
281
282 /**
283 * Get an data entry by index. This will give the pointer to an data
284 * element based on the index in the list.
285 *
286 * @param list Pointer to the VisList of which we want an element.
287 * @param index Index to determine which entry we want. The index starts at
288 * 1.
289 *
290 * @return The data element of the requested entry, or NULL.
291 */
visual_list_get(VisList * list,int index)292 void *visual_list_get (VisList *list, int index)
293 {
294 VisListEntry *le = NULL;
295 void *data = NULL;
296 int i, lc;
297
298 visual_log_return_val_if_fail (list != NULL, NULL);
299 visual_log_return_val_if_fail (index >= 0, NULL);
300
301 lc = visual_collection_size (VISUAL_COLLECTION (list));
302
303 if (lc - 1 < index)
304 return NULL;
305
306 for (i = 0; i <= index; i++) {
307 data = visual_list_next (list, &le);
308
309 if (data == NULL)
310 return NULL;
311 }
312
313 return data;
314 }
315
316 /**
317 * Adds an entry at the beginning of the list.
318 *
319 * @param list Pointer to the VisList to which an entry needs to be added
320 * at it's head.
321 * @param data A pointer to the data that needs to be added to the list.
322 *
323 * @return VISUAL_OK on succes, -VISUAL_ERROR_LIST_NULL on failure.
324 */
visual_list_add_at_begin(VisList * list,void * data)325 int visual_list_add_at_begin (VisList *list, void *data)
326 {
327 VisListEntry *le;
328
329 visual_log_return_val_if_fail (list != NULL, -VISUAL_ERROR_LIST_NULL);
330
331 /* Allocate memory for new list entry */
332 le = visual_mem_new0 (VisListEntry, 1);
333
334 /* Assign data element */
335 le->data = data;
336
337 visual_list_chain_at_begin (list, le);
338
339 return VISUAL_OK;
340 }
341
342 /**
343 * Adds an entry at the end of the list.
344 *
345 * @param list Pointer to the VisList to which an entry needs to be added
346 * at it's tail.
347 * @param data A pointer to the data that needs to be added to the list.
348 *
349 * @return VISUAL_OK on succes, -VISUAL_ERROR_LIST_NULL on failure.
350 */
visual_list_add(VisList * list,void * data)351 int visual_list_add (VisList *list, void *data)
352 {
353 VisListEntry *le;
354
355 visual_log_return_val_if_fail (list != NULL, -VISUAL_ERROR_LIST_NULL);
356
357 le = visual_mem_new0 (VisListEntry, 1);
358
359 /* Assign data element */
360 le->data = data;
361
362 visual_list_chain (list, le);
363
364 return VISUAL_OK;
365 }
366
367 /**
368 * Chains an VisListEntry at the beginning of the list.
369 *
370 * @param list Pointer to the VisList to which an entry needs to be added
371 * at it's tail.
372 * @param le A pointer to the VisListEntry that needs to be chained to the list.
373 *
374 * @return VISUAL_OK on succes, -VISUAL_ERROR_LIST_NULL or -VISUAL_ERROR_LIST_ENTRY_NULL on failure.
375 */
visual_list_chain_at_begin(VisList * list,VisListEntry * le)376 int visual_list_chain_at_begin (VisList *list, VisListEntry *le)
377 {
378 VisListEntry *next;
379
380 visual_log_return_val_if_fail (list != NULL, -VISUAL_ERROR_LIST_NULL);
381 visual_log_return_val_if_fail (le != NULL, -VISUAL_ERROR_LIST_ENTRY_NULL);
382
383 if (list->head == NULL) {
384 list->head = le;
385 list->tail = le;
386
387 le->prev = NULL;
388 le->next = NULL;
389 } else {
390 next = list->head;
391
392 le->next = next;
393 list->head = le;
394
395 le->prev = NULL;
396 }
397
398 /* Done */
399 list->count++;
400
401 return VISUAL_OK;
402 }
403
404 /**
405 * Chains an VisListEntry at the end of the list.
406 *
407 * @param list Pointer to the VisList to which an entry needs to be added
408 * at it's tail.
409 * @param le A pointer to the VisListEntry that needs to be chained to the list.
410 *
411 * @return VISUAL_OK on succes, -VISUAL_ERROR_LIST_NULL or -VISUAL_ERROR_LIST_ENTRY_NULL on failure.
412 */
visual_list_chain(VisList * list,VisListEntry * le)413 int visual_list_chain (VisList *list, VisListEntry *le)
414 {
415 VisListEntry *prev;
416
417 visual_log_return_val_if_fail (list != NULL, -VISUAL_ERROR_LIST_NULL);
418 visual_log_return_val_if_fail (le != NULL, -VISUAL_ERROR_LIST_ENTRY_NULL);
419
420 /* Add list entry to list */
421 /* Is this the first entry for this list ? */
422 if (list->head == NULL) {
423 list->head = le;
424 list->tail = le;
425
426 le->prev = NULL;
427 le->next = NULL;
428 } else {
429 /* Nope, add to tail of this list */
430 prev = list->tail;
431
432 /* Exchange pointers */
433 prev->next = le;
434 le->prev = prev;
435
436 le->next = NULL;
437
438 /* Point tail to new entry */
439 list->tail = le;
440 }
441
442 /* Done */
443 list->count++;
444
445 return VISUAL_OK;
446 }
447
448 /**
449 * Unchain a VisListEntry from a VisList, entry won't be deleted. This function will only remove the
450 * links with it's VisList.
451 *
452 * @param list Pointer to the VisList from which an entry is unchained.
453 * @param le Pointer to a VisListEntry that is being unchained.
454 *
455 * @return VISUAL_OK on succes, -VISUAL_ERROR_LIST_NULL or -VISUAL_ERROR_LIST_ENTRY_NULL
456 * on failure.
457 */
visual_list_unchain(VisList * list,VisListEntry * le)458 int visual_list_unchain (VisList *list, VisListEntry *le)
459 {
460 VisListEntry *prev;
461 VisListEntry *next;
462
463 visual_log_return_val_if_fail (list != NULL, -VISUAL_ERROR_LIST_NULL);
464 visual_log_return_val_if_fail (le != NULL, -VISUAL_ERROR_LIST_ENTRY_NULL);
465
466 /* Point new to le's previous entry */
467 prev = le->prev;
468 next = le->next;
469
470 /* Does it have a previous entry ? */
471 if (prev != NULL)
472 prev->next = next;
473 else
474 list->head = next;
475
476 if (next != NULL) /* It does have a next entry ? */
477 next->prev = prev;
478 else
479 list->tail = prev;
480
481 list->count--;
482
483 return VISUAL_OK;
484 }
485
486 /**
487 * Insert an entry in the middle of a list. By adding it
488 * after the le entry.
489 *
490 * @param list Pointer to the VisList in which an entry needs to be inserted.
491 * @param le Pointer to a VisListEntry after which the entry needs to be inserted.
492 * @param data Pointer to the data the new entry represents.
493 *
494 * @return VISUAL_OK on succes, -VISUAL_ERROR_LIST_NULL, -VISUAL_ERROR_LIST_ENTRY_NULL or
495 * -VISUAL_ERROR_NULL on failure.
496 */
visual_list_insert(VisList * list,VisListEntry ** le,void * data)497 int visual_list_insert (VisList *list, VisListEntry **le, void *data)
498 {
499 VisListEntry *prev, *next, *current;
500
501 visual_log_return_val_if_fail (list != NULL, -VISUAL_ERROR_LIST_NULL);
502 visual_log_return_val_if_fail (le != NULL, -VISUAL_ERROR_LIST_ENTRY_NULL);
503 visual_log_return_val_if_fail (data != NULL, -VISUAL_ERROR_NULL);
504
505 current = visual_mem_new0 (VisListEntry, 1);
506
507 /* Assign data element */
508 current->data = data;
509
510 /* Add entry to list */
511 if (list->head == NULL && *le == NULL) {
512 /* First entry */
513 list->head = current;
514 list->tail = current;
515 } else if (*le == NULL) {
516 /* Insert entry at first position */
517 next = list->head;
518 /* Exchange pointers */
519 current->next = next;
520 next->prev = current;
521 /* Point head to current pointer */
522 list->head = current;
523 } else {
524 /* Insert entry at *le's position */
525 prev = *le;
526 next = prev->next;
527
528 current->prev = prev;
529 current->next = next;
530
531 prev->next = current;
532 if (next != NULL)
533 next->prev = current;
534 else
535 list->tail = current;
536 }
537
538 /* Hop to new entry */
539 *le = current;
540
541 /* Done */
542 list->count++;
543
544 return VISUAL_OK;
545 }
546
547 /**
548 * Removes an entry from the list.
549 *
550 * @param list A pointer to the VisList in which an entry needs to be deleted.
551 * @param le A pointer to the entry that needs to be deleted.
552 *
553 * @return VISUAL_OK on succes, -VISUAL_ERROR_LIST_NULL or -VISUAL_ERROR_LIST_ENTRY_NULL on failure.
554 */
visual_list_delete(VisList * list,VisListEntry ** le)555 int visual_list_delete (VisList *list, VisListEntry **le)
556 {
557 VisListEntry *next;
558
559 visual_log_return_val_if_fail (list != NULL, -VISUAL_ERROR_LIST_NULL);
560 visual_log_return_val_if_fail (le != NULL, -VISUAL_ERROR_LIST_ENTRY_NULL);
561
562 /* Valid list entry ? */
563 if (*le == NULL) {
564 visual_log (VISUAL_LOG_CRITICAL, "There is no list entry to delete");
565
566 return -VISUAL_ERROR_LIST_ENTRY_INVALID; /* Nope */
567 }
568
569 next = (*le)->next;
570 visual_list_unchain (list, *le);
571
572 visual_mem_free (*le);
573
574 *le = next;
575
576 return VISUAL_OK;
577 }
578
579 /**
580 * Removes and entry from the list and uses the VisListDestroyerFunc when present to clean up the data.
581 *
582 * @param list A pointer to the VisList in which an entry needs to be destroyed.
583 * @param le A pointer to the entry that needs to be destroyed.
584 *
585 * @return VISUAL_OK on succes, -VISUAL_ERROR_LIST_NULL or -VISUAL_ERROR_LIST_ENTRY_NULL on failure.
586 */
visual_list_destroy(VisList * list,VisListEntry ** le)587 int visual_list_destroy (VisList *list, VisListEntry **le)
588 {
589 VisCollectionDestroyerFunc destroyer;
590
591 visual_log_return_val_if_fail (list != NULL, -VISUAL_ERROR_LIST_NULL);
592 visual_log_return_val_if_fail (le != NULL, -VISUAL_ERROR_LIST_ENTRY_NULL);
593
594 destroyer = visual_collection_get_destroyer (VISUAL_COLLECTION (list));
595
596 if (destroyer != NULL)
597 destroyer ((*le)->data);
598
599 return visual_list_delete (list, le);
600 }
601
602 /**
603 * @}
604 */
605
606