4 * @brief Implementation of linked_list_t.
9 * Copyright (C) 2005 Jan Hutter, Martin Willi
10 * Hochschule fuer Technik Rapperswil
12 * This program is free software; you can redistribute it and/or modify it
13 * under the terms of the GNU General Public License as published by the
14 * Free Software Foundation; either version 2 of the License, or (at your
15 * option) any later version. See <http://www.fsf.org/copyleft/gpl.txt>.
17 * This program is distributed in the hope that it will be useful, but
18 * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
19 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
25 #include "linked_list.h"
29 typedef struct linked_list_element_t linked_list_element_t
;
32 * @brief Element in a linked list.
34 * This element holds a pointer to the value it represents.
36 struct linked_list_element_t
{
39 * Value of a list item.
44 * Previous list element.
46 * NULL if first element in list.
48 linked_list_element_t
*previous
;
53 * NULL if last element in list.
55 linked_list_element_t
*next
;
58 * Destroys a linked_list_element object.
60 * @param linked_list_element_t calling object
62 void (*destroy
) (linked_list_element_t
*this);
66 * Implementation of linked_list_element_t.destroy.
68 static void linked_list_element_destroy(linked_list_element_t
*this)
74 * @brief Creates an empty linked list object.
76 * @warning Only the pointer to the value is stored.
78 * @param[in] value value of item to be set
79 * @return linked_list_element_t object
82 linked_list_element_t
*linked_list_element_create(void *value
)
84 linked_list_element_t
*this = malloc_thing(linked_list_element_t
);
86 this->destroy
= linked_list_element_destroy
;
96 typedef struct private_linked_list_t private_linked_list_t
;
99 * Private data of a linked_list_t object.
102 struct private_linked_list_t
{
104 * Public part of linked list.
106 linked_list_t
public;
109 * Number of items in the list.
114 * First element in list.
115 * NULL if no elements in list.
117 linked_list_element_t
*first
;
120 * Last element in list.
121 * NULL if no elements in list.
123 linked_list_element_t
*last
;
127 typedef struct private_iterator_t private_iterator_t
;
130 * Private variables and functions of linked list iterator.
132 struct private_iterator_t
{
134 * Public part of linked list iterator.
139 * Associated linked list.
141 private_linked_list_t
* list
;
144 * Current element of the iterator.
146 linked_list_element_t
*current
;
149 * Direction of iterator.
155 * Implementation of iterator_t.get_count.
157 static int get_list_count(private_iterator_t
*this)
159 return this->list
->count
;
163 * Implementation of iterator_t.iterate.
165 static bool iterate(private_iterator_t
*this, void** value
)
167 if (this->list
->count
== 0)
171 if (this->current
== NULL
)
173 this->current
= (this->forward
) ?
this->list
->first
: this->list
->last
;
174 *value
= this->current
->value
;
179 if (this->current
->next
== NULL
)
183 this->current
= this->current
->next
;
184 *value
= this->current
->value
;
188 if (this->current
->previous
== NULL
)
192 this->current
= this->current
->previous
;
193 *value
= this->current
->value
;
198 * Implementation of iterator_t.has_next.
200 static bool iterator_has_next(private_iterator_t
*this)
202 if (this->list
->count
== 0)
206 if (this->current
== NULL
)
208 this->current
= (this->forward
) ?
this->list
->first
: this->list
->last
;
213 if (this->current
->next
== NULL
)
217 this->current
= this->current
->next
;
221 if (this->current
->previous
== NULL
)
225 this->current
= this->current
->previous
;
230 * Implementation of iterator_t.current.
232 static status_t
iterator_current(private_iterator_t
*this, void **value
)
234 if (this->current
== NULL
)
238 *value
= this->current
->value
;
243 * Implementation of iterator_t.reset.
245 static void iterator_reset(private_iterator_t
*this)
247 this->current
= NULL
;
251 * Implementation of iterator_t.remove.
253 static status_t
remove(private_iterator_t
*this)
255 linked_list_element_t
*new_current
;
257 if (this->current
== NULL
)
262 if (this->list
->count
== 0)
266 /* find out the new iterator position */
267 if (this->current
->previous
!= NULL
)
269 new_current
= this->current
->previous
;
271 else if (this->current
->next
!= NULL
)
273 new_current
= this->current
->next
;
280 /* now delete the entry :-) */
281 if (this->current
->previous
== NULL
)
283 if (this->current
->next
== NULL
)
285 this->list
->first
= NULL
;
286 this->list
->last
= NULL
;
290 this->current
->next
->previous
= NULL
;
291 this->list
->first
= this->current
->next
;
294 else if (this->current
->next
== NULL
)
296 this->current
->previous
->next
= NULL
;
297 this->list
->last
= this->current
->previous
;
301 this->current
->previous
->next
= this->current
->next
;
302 this->current
->next
->previous
= this->current
->previous
;
306 this->current
->destroy(this->current
);
307 /* set the new iterator position */
308 this->current
= new_current
;
313 * Implementation of iterator_t.insert_before.
315 static void insert_before(private_iterator_t
* iterator
, void *item
)
317 if (iterator
->current
== NULL
)
319 iterator
->list
->public.insert_first(&(iterator
->list
->public), item
);
322 linked_list_element_t
*element
=(linked_list_element_t
*) linked_list_element_create(item
);
324 if (iterator
->current
->previous
== NULL
)
326 iterator
->current
->previous
= element
;
327 element
->next
= iterator
->current
;
328 iterator
->list
->first
= element
;
332 iterator
->current
->previous
->next
= element
;
333 element
->previous
= iterator
->current
->previous
;
334 iterator
->current
->previous
= element
;
335 element
->next
= iterator
->current
;
338 iterator
->list
->count
++;
342 * Implementation of iterator_t.replace.
344 static status_t
replace (private_iterator_t
*this, void **old_item
, void *new_item
)
346 if (this->current
== NULL
)
350 if (old_item
!= NULL
)
352 *old_item
= this->current
->value
;
354 this->current
->value
= new_item
;
360 * Implementation of iterator_t.insert_after.
362 static void insert_after(private_iterator_t
* iterator
, void *item
)
364 if (iterator
->current
== NULL
)
366 iterator
->list
->public.insert_first(&(iterator
->list
->public),item
);
370 linked_list_element_t
*element
=(linked_list_element_t
*) linked_list_element_create(item
);
372 if (iterator
->current
->next
== NULL
)
374 iterator
->current
->next
= element
;
375 element
->previous
= iterator
->current
;
376 iterator
->list
->last
= element
;
380 iterator
->current
->next
->previous
= element
;
381 element
->next
= iterator
->current
->next
;
382 iterator
->current
->next
= element
;
383 element
->previous
= iterator
->current
;
385 iterator
->list
->count
++;
389 * Implementation of iterator_t.destroy.
391 static void iterator_destroy(private_iterator_t
*this)
397 * Implementation of linked_list_t.get_count.
399 static int get_count(private_linked_list_t
*this)
405 * Implementation of linked_list_t.call_on_items.
407 static void call_on_items(private_linked_list_t
*this, void(*func
)(void*))
409 iterator_t
*iterator
;
412 iterator
= this->public.create_iterator(&(this->public),TRUE
);
414 while (iterator
->has_next(iterator
))
416 iterator
->current(iterator
, &item
);
419 iterator
->destroy(iterator
);
423 * Implementation of linked_list_t.insert_first.
425 static void insert_first(private_linked_list_t
*this, void *item
)
427 linked_list_element_t
*element
;
429 element
=(linked_list_element_t
*) linked_list_element_create(item
);
431 if (this->count
== 0)
433 /* first entry in list */
434 this->first
= element
;
435 this->last
= element
;
436 element
->previous
= NULL
;
437 element
->next
= NULL
;
441 linked_list_element_t
*old_first_element
= this->first
;
442 element
->next
= old_first_element
;
443 element
->previous
= NULL
;
444 old_first_element
->previous
= element
;
445 this->first
= element
;
452 * Implementation of linked_list_t.remove_first.
454 static status_t
remove_first(private_linked_list_t
*this, void **item
)
456 if (this->count
== 0)
461 linked_list_element_t
*element
= this->first
;
463 if (element
->next
!= NULL
)
465 element
->next
->previous
= NULL
;
467 this->first
= element
->next
;
471 *item
= element
->value
;
476 element
->destroy(element
);
482 * Implementation of linked_list_t.get_first.
484 static status_t
get_first(private_linked_list_t
*this, void **item
)
486 if (this->count
== 0)
491 *item
= this->first
->value
;
497 * Implementation of linked_list_t.insert_last.
499 static void insert_last(private_linked_list_t
*this, void *item
)
501 linked_list_element_t
*element
= (linked_list_element_t
*) linked_list_element_create(item
);
503 if (this->count
== 0)
505 /* first entry in list */
506 this->first
= element
;
507 this->last
= element
;
508 element
->previous
= NULL
;
509 element
->next
= NULL
;
514 linked_list_element_t
*old_last_element
= this->last
;
515 element
->previous
= old_last_element
;
516 element
->next
= NULL
;
517 old_last_element
->next
= element
;
518 this->last
= element
;
525 * Implementation of linked_list_t.remove_last.
527 static status_t
remove_last(private_linked_list_t
*this, void **item
)
529 if (this->count
== 0)
534 linked_list_element_t
*element
= this->last
;
536 if (element
->previous
!= NULL
)
538 element
->previous
->next
= NULL
;
540 this->last
= element
->previous
;
544 *item
= element
->value
;
549 element
->destroy(element
);
555 * Implementation of linked_list_t.insert_at_position.
557 static status_t
insert_at_position (private_linked_list_t
*this,size_t position
, void *item
)
559 linked_list_element_t
*current_element
;
562 if (this->count
<= position
)
567 current_element
= this->first
;
569 for (i
= 0; i
< position
;i
++)
571 current_element
= current_element
->next
;
574 if (current_element
== NULL
)
576 this->public.insert_last(&(this->public),item
);
580 linked_list_element_t
*element
=(linked_list_element_t
*) linked_list_element_create(item
);
583 if (current_element
->previous
== NULL
)
585 current_element
->previous
= element
;
586 element
->next
= current_element
;
587 this->first
= element
;
591 current_element
->previous
->next
= element
;
592 element
->previous
= current_element
->previous
;
593 current_element
->previous
= element
;
594 element
->next
= current_element
;
603 * Implementation of linked_list_t.remove_at_position.
605 static status_t
remove_at_position (private_linked_list_t
*this,size_t position
, void **item
)
607 iterator_t
*iterator
;
610 if (this->count
<= position
)
615 iterator
= this->public.create_iterator(&(this->public),TRUE
);
617 iterator
->has_next(iterator
);
618 for (i
= 0; i
< position
;i
++)
620 iterator
->has_next(iterator
);
622 iterator
->current(iterator
,item
);
623 iterator
->remove(iterator
);
624 iterator
->destroy(iterator
);
630 * Implementation of linked_list_t.get_at_position.
632 static status_t
get_at_position (private_linked_list_t
*this,size_t position
, void **item
)
635 iterator_t
*iterator
;
637 if (this->count
<= position
)
642 iterator
= this->public.create_iterator(&(this->public),TRUE
);
644 iterator
->has_next(iterator
);
645 for (i
= 0; i
< position
;i
++)
647 iterator
->has_next(iterator
);
649 status
= iterator
->current(iterator
,item
);
650 iterator
->destroy(iterator
);
655 * Implementation of linked_list_t.get_last.
657 static status_t
get_last(private_linked_list_t
*this, void **item
)
659 if (this->count
== 0)
664 *item
= this->last
->value
;
670 * Implementation of linked_list_t.create_iterator.
672 static iterator_t
*create_iterator (private_linked_list_t
*linked_list
,bool forward
)
674 private_iterator_t
*this = malloc_thing(private_iterator_t
);
676 this->public.get_count
= (bool (*) (iterator_t
*this)) get_list_count
;
677 this->public.iterate
= (bool (*) (iterator_t
*this, void **value
)) iterate
;
678 this->public.has_next
= (bool (*) (iterator_t
*this)) iterator_has_next
;
679 this->public.current
= (status_t (*) (iterator_t
*this, void **value
)) iterator_current
;
680 this->public.insert_before
= (void (*) (iterator_t
*this, void *item
)) insert_before
;
681 this->public.insert_after
= (void (*) (iterator_t
*this, void *item
)) insert_after
;
682 this->public.replace
= (status_t (*) (iterator_t
*, void **, void *)) replace
;
683 this->public.remove
= (status_t (*) (iterator_t
*this)) remove
;
684 this->public.reset
= (void (*) (iterator_t
*this)) iterator_reset
;
685 this->public.destroy
= (void (*) (iterator_t
*this)) iterator_destroy
;
687 this->forward
= forward
;
688 this->current
= NULL
;
689 this->list
= linked_list
;
691 return &(this->public);
695 * Implementation of linked_list_t.destroy.
697 static void linked_list_destroy(private_linked_list_t
*this)
700 /* Remove all list items before destroying list */
701 while (this->public.remove_first(&(this->public),&value
) != NOT_FOUND
)
703 /* values are not destroyed so memory leaks are possible
704 * if list is not empty when deleting */
710 * Described in header.
712 linked_list_t
*linked_list_create()
714 private_linked_list_t
*this = malloc_thing(private_linked_list_t
);
716 this->public.get_count
= (int (*) (linked_list_t
*)) get_count
;
717 this->public.create_iterator
= (iterator_t
* (*) (linked_list_t
*,bool )) create_iterator
;
718 this->public.call_on_items
= (void (*) (linked_list_t
*, void(*func
)(void*)))call_on_items
;
719 this->public.get_first
= (status_t (*) (linked_list_t
*, void **item
)) get_first
;
720 this->public.get_last
= (status_t (*) (linked_list_t
*, void **item
)) get_last
;
721 this->public.insert_first
= (void (*) (linked_list_t
*, void *item
)) insert_first
;
722 this->public.insert_last
= (void (*) (linked_list_t
*, void *item
)) insert_last
;
723 this->public.remove_first
= (status_t (*) (linked_list_t
*, void **item
)) remove_first
;
724 this->public.remove_last
= (status_t (*) (linked_list_t
*, void **item
)) remove_last
;
725 this->public.insert_at_position
=(status_t (*) (linked_list_t
*,size_t, void *)) insert_at_position
;
726 this->public.remove_at_position
=(status_t (*) (linked_list_t
*,size_t, void **)) remove_at_position
;
727 this->public.get_at_position
=(status_t (*) (linked_list_t
*,size_t, void **)) get_at_position
;
729 this->public.destroy
= (void (*) (linked_list_t
*)) linked_list_destroy
;
735 return (&(this->public));