diff options
Diffstat (limited to 'Source')
| -rw-r--r-- | Source/charon/utils/linked_list.c | 453 | ||||
| -rw-r--r-- | Source/charon/utils/linked_list.h | 54 |
2 files changed, 226 insertions, 281 deletions
diff --git a/Source/charon/utils/linked_list.c b/Source/charon/utils/linked_list.c index a5188f344..5844c1b8a 100644 --- a/Source/charon/utils/linked_list.c +++ b/Source/charon/utils/linked_list.c @@ -36,15 +36,15 @@ typedef struct linked_list_element_t linked_list_element_t; */ struct linked_list_element_t { /** - * value of a list item + * Value of a list item. */ void *value; /** - * @brief Destroys a linked_list_element object + * Destroys a linked_list_element object. * - * @param linked_list_element_t calling object - * @returns SUCCESS if succeeded, FAILED otherwise + * @param linked_list_element_t calling object + * @returns SUCCESS in any case */ status_t (*destroy) (linked_list_element_t *this); @@ -61,26 +61,23 @@ struct linked_list_element_t { }; /** - * @brief implements function destroy of linked_list_item_t + * Implementation of linked_list_element_t.destroy. */ static status_t linked_list_element_destroy(linked_list_element_t *this) { - if (this == NULL) - { - return FAILED; - } allocator_free(this); return SUCCESS; } /** - * @brief Creates an empty linked list object + * @brief Creates an empty linked list object. * - * @param[in] value value of item to be set - * - * @warning only the pointer to the value is stored - * - * @return linked_list_element object + * @warning Only the pointer to the value is stored. + * + * @param[in] value value of item to be set + * @return + * - linked_list_element_t object + * - NULL if out of ressources */ linked_list_element_t *linked_list_element_create(void *value) @@ -101,66 +98,66 @@ linked_list_element_t *linked_list_element_create(void *value) return (this); } + +typedef struct private_linked_list_t private_linked_list_t; /** - * Private variables and functions of linked list + * Private variables and functions of linked list. * */ -typedef struct private_linked_list_t private_linked_list_t; - struct private_linked_list_t { /** - * Public part of linked list + * Public part of linked list. */ linked_list_t public; /** - * number of items in the list + * Number of items in the list. */ int count; /** - * First element in list - * NULL if no elements in list + * First element in list. + * NULL if no elements in list. */ linked_list_element_t *first; /** - * Last element in list - * NULL if no elements in list + * Last element in list. + * NULL if no elements in list. */ linked_list_element_t *last; }; +typedef struct private_iterator_t private_iterator_t; + /** - * Private variables and functions of linked list iterator + * Private variables and functions of linked list iterator. * */ -typedef struct private_iterator_t private_iterator_t; - struct private_iterator_t { /** - * Public part of linked list iterator + * Public part of linked list iterator. */ iterator_t public; /** - * associated linked list + * Associated linked list. */ private_linked_list_t * list; /** - * current element of the iterator + * Current element of the iterator. */ linked_list_element_t *current; /** - * direction of iterator + * Direction of iterator. */ bool forward; }; /** - * Implements function has_next of linked_list_iteratr + * Implementation of iterator_t.has_next. */ bool iterator_has_next(private_iterator_t *this) { @@ -192,50 +189,183 @@ bool iterator_has_next(private_iterator_t *this) } /** - * Implements function current of linked_list_iteratr + * Implementation of iterator_t.current. */ static status_t iterator_current(private_iterator_t *this, void **value) { - if (this == NULL) - { - return FAILED; - } if (this->current == NULL) { - return FAILED; + return NOT_FOUND; } *value = this->current->value; return SUCCESS; } /** - * Implements function current of linked_list_iteratr + * Implementation of iterator_t.reset. */ static status_t iterator_reset(private_iterator_t *this) { - if (this == NULL) + this->current = NULL; + return SUCCESS; +} + +/** + * Implementation of iterator_t.remove. + */ +static status_t remove(private_iterator_t *this) +{ + linked_list_element_t *new_current; + + if (this->current == NULL) { - return FAILED; + return NOT_FOUND; } - this->current = NULL; + + if (this->list->count == 0) + { + return NOT_FOUND; + } + /* find out the new iterator position */ + if (this ->current->previous != NULL) + { + new_current = this->current->previous; + } + else if (this->current->next != NULL) + { + new_current = this->current->next; + } + else + { + new_current = NULL; + } + + /* now delete the entry :-) */ + if (this->current->previous == NULL) + { + if (this->current->next == NULL) + { + this->list->first = NULL; + this->list->last = NULL; + } + else + { + this->current->next->previous = NULL; + this->list->first = this->current->next; + } + } + else if (this->current->next == NULL) + { + this->current->previous->next = NULL; + this->list->last = this->current->previous; + } + else + { + this->current->previous->next = this->current->next; + this->current->next->previous = this->current->previous; + } + + this->list->count--; + this->current->destroy(this->current); + /* set the new iterator position */ + this->current = new_current; return SUCCESS; } /** - * Implements function destroy of linked_list_iteratr + * Implementation of iterator_t.insert_before. */ -static status_t iterator_destroy(private_iterator_t *this) +static status_t insert_before(private_iterator_t * iterator, void *item) { - if (this == NULL) + if (iterator->current == NULL) + { + return (iterator->list->public.insert_first(&(iterator->list->public), item)); + } + + linked_list_element_t *element =(linked_list_element_t *) linked_list_element_create(item); + + if (element == NULL) + { + return OUT_OF_RES; + } + + if (iterator->current->previous == NULL) + { + if (iterator->list->first != iterator->current) + { + element->destroy(element); + return FAILED; + } + + iterator->current->previous = element; + element->next = iterator->current; + iterator->list->first = element; + } + else + { + iterator->current->previous->next = element; + element->previous = iterator->current->previous; + iterator->current->previous = element; + element->next = iterator->current; + } + + iterator->list->count++; + + return SUCCESS; +} + +/** + * Implementation of iterator_t.insert_after. + */ +static status_t insert_after(private_iterator_t * iterator, void *item) +{ + if (iterator->current == NULL) + { + return (iterator->list->public.insert_first(&(iterator->list->public),item)); + } + + linked_list_element_t *element =(linked_list_element_t *) linked_list_element_create(item); + + if (element == NULL) { - return FAILED; + return OUT_OF_RES; + } + + if (iterator->current->next == NULL) + { + if (iterator->list->last != iterator->current) + { + element->destroy(element); + return FAILED; + } + + iterator->current->next = element; + element->previous = iterator->current; + iterator->list->last = element; + } + else + { + iterator->current->next->previous = element; + element->next = iterator->current->next; + iterator->current->next = element; + element->previous = iterator->current; } + + iterator->list->count++; + return SUCCESS; +} + +/** + * Implementation of iterator_t.destroy. + */ +static status_t iterator_destroy(private_iterator_t *this) +{ allocator_free(this); return SUCCESS; } /** - * @brief implements function get_count of linked_list_t + * Implementation of linked_list_t.get_count. */ static int get_count(private_linked_list_t *this) { @@ -244,22 +374,17 @@ static int get_count(private_linked_list_t *this) /** - * @brief implements function insert_first of linked_list_t + * Implementation of linked_list_t.insert_first. */ static status_t insert_first(private_linked_list_t *this, void *item) { linked_list_element_t *element; - if (this == NULL) - { - return FAILED; - } - element =(linked_list_element_t *) linked_list_element_create(item); if (element == NULL) { - return FAILED; + return OUT_OF_RES; } if (this->count == 0) @@ -291,23 +416,13 @@ static status_t insert_first(private_linked_list_t *this, void *item) } /** - * @brief implements function remove_first of linked_list_t + * Implementation of linked_list_t.remove_first. */ static status_t remove_first(private_linked_list_t *this, void **item) { - if (this == NULL) - { - return FAILED; - } - if (this->count == 0) { - return FAILED; - } - - if (this->first == NULL) - { - return FAILED; + return NOT_FOUND; } linked_list_element_t *element = this->first; @@ -326,23 +441,13 @@ static status_t remove_first(private_linked_list_t *this, void **item) } /** - * @brief implements function get_first of linked_list_t + * Implementation of linked_list_t.get_first. */ static status_t get_first(private_linked_list_t *this, void **item) { - if (this == NULL) - { - return FAILED; - } - if (this->count == 0) { - return FAILED; - } - - if (this->first == NULL) - { - return FAILED; + return NOT_FOUND; } *item = this->first->value; @@ -351,7 +456,7 @@ static status_t get_first(private_linked_list_t *this, void **item) } /** - * @brief implements function insert_last of linked_list_t + * Implementation of linked_list_t.insert_last. */ static status_t insert_last(private_linked_list_t *this, void *item) { @@ -390,23 +495,13 @@ static status_t insert_last(private_linked_list_t *this, void *item) } /** - * @brief implements function remove_last of linked_list_t + * Implementation of linked_list_t.remove_last. */ static status_t remove_last(private_linked_list_t *this, void **item) { - if (this == NULL) - { - return FAILED; - } - if (this->count == 0) { - return FAILED; - } - - if (this->last == NULL) - { - return FAILED; + return NOT_FOUND; } linked_list_element_t *element = this->last; @@ -425,23 +520,13 @@ static status_t remove_last(private_linked_list_t *this, void **item) } /** - * @brief implements function get_last of linked_list_t + * Implementation of linked_list_t.get_last. */ static status_t get_last(private_linked_list_t *this, void **item) { - if (this == NULL) - { - return FAILED; - } - if (this->count == 0) { - return FAILED; - } - - if (this->last == NULL) - { - return FAILED; + return NOT_FOUND; } *item = this->last->value; @@ -450,151 +535,8 @@ static status_t get_last(private_linked_list_t *this, void **item) } /** - * @brief implements function insert_before of linked_list_t - */ -static status_t insert_before(private_iterator_t * iterator, void *item) -{ - if (iterator->current == NULL) - { - return (iterator->list->public.insert_first(&(iterator->list->public), item)); - } - - linked_list_element_t *element =(linked_list_element_t *) linked_list_element_create(item); - - if (element == NULL) - { - return FAILED; - } - - if (iterator->current->previous == NULL) - { - if (iterator->list->first != iterator->current) - { - element->destroy(element); - return FAILED; - } - - iterator->current->previous = element; - element->next = iterator->current; - iterator->list->first = element; - } - else - { - iterator->current->previous->next = element; - element->previous = iterator->current->previous; - iterator->current->previous = element; - element->next = iterator->current; - } - - iterator->list->count++; - - return SUCCESS; -} - -/** - * @brief implements function insert_after of linked_list_t - */ -static status_t insert_after(private_iterator_t * iterator, void *item) -{ - if (iterator->current == NULL) - { - return (iterator->list->public.insert_first(&(iterator->list->public),item)); - } - - linked_list_element_t *element =(linked_list_element_t *) linked_list_element_create(item); - - if (element == NULL) - { - return FAILED; - } - - if (iterator->current->next == NULL) - { - if (iterator->list->last != iterator->current) - { - element->destroy(element); - return FAILED; - } - - iterator->current->next = element; - element->previous = iterator->current; - iterator->list->last = element; - } - else - { - iterator->current->next->previous = element; - element->next = iterator->current->next; - iterator->current->next = element; - element->previous = iterator->current; - } - - iterator->list->count++; - return SUCCESS; -} - - -/** - * @brief implements function remove of linked_list_t. + * Implementation of linked_list_t.create_iterator. */ -static status_t remove(private_iterator_t *this) -{ - linked_list_element_t *new_current; - - if (this->current == NULL) - { - return FAILED; - } - - if (this->list->count == 0) - { - return FAILED; - } - /* find out the new iterator position */ - if (this ->current->previous != NULL) - { - new_current = this->current->previous; - } - else if (this->current->next != NULL) - { - new_current = this->current->next; - } - else - { - new_current = NULL; - } - - /* now delete the entry :-) */ - if (this->current->previous == NULL) - { - if (this->current->next == NULL) - { - this->list->first = NULL; - this->list->last = NULL; - } - else - { - this->current->next->previous = NULL; - this->list->first = this->current->next; - } - } - else if (this->current->next == NULL) - { - this->current->previous->next = NULL; - this->list->last = this->current->previous; - } - else - { - this->current->previous->next = this->current->next; - this->current->next->previous = this->current->previous; - } - - this->list->count--; - this->current->destroy(this->current); - /* set the new iterator position */ - this->current = new_current; - return SUCCESS; -} - static status_t create_iterator (private_linked_list_t *linked_list, iterator_t **iterator,bool forward) { private_iterator_t *this = allocator_alloc_thing(private_iterator_t); @@ -623,26 +565,17 @@ static status_t create_iterator (private_linked_list_t *linked_list, iterator_t } /** - * @brief implements function destroy of linked_list_t + * Implementation of linked_list_t.destroy. */ static status_t linked_list_destroy(private_linked_list_t *this) { - if (this == NULL) - { - return FAILED; - } - + void * value; /* Remove all list items before destroying list */ - while (this->count > 0) + while (this->public.remove_first(&(this->public),&value) != NOT_FOUND) { - void * value; + /* values are not destroyed so memory leaks are possible * if list is not empty when deleting */ - if (this->public.remove_first(&(this->public),&value) != SUCCESS) - { - allocator_free(this); - return FAILED; - } } allocator_free(this); return SUCCESS; diff --git a/Source/charon/utils/linked_list.h b/Source/charon/utils/linked_list.h index f59455050..57e5dde88 100644 --- a/Source/charon/utils/linked_list.h +++ b/Source/charon/utils/linked_list.h @@ -79,56 +79,68 @@ struct linked_list_t { * * @param linked_list calling object * @param[in] item returned value of first item - * @return SUCCESS if succeeded, FAILED otherwise + * @return + * - SUCCESS + * - NOT_FOUND, if list is empty */ status_t (*remove_first) (linked_list_t *linked_list, void **item); /** - * @brief returns the value of the first list item without removing it + * @brief Returns the value of the first list item without removing it. * - * @param linked_list calling object - * @param[out] item returned value of first item - * @return SUCCESS if succeeded, FAILED otherwise + * @param linked_list calling object + * @param[out] item returned value of first item + * @return + * - SUCCESS + * - NOT_FOUND, if list is empty */ status_t (*get_first) (linked_list_t *linked_list, void **item); /** - * @brief inserts a new item at the end of the list + * @brief Inserts a new item at the end of the list. * - * @param linked_list calling object - * @param[in] item value to insert into list - * @return SUCCESS if succeeded, FAILED otherwise + * @param linked_list calling object + * @param[in] item value to insert into list + * @return + * - SUCCESS + * - FAILED if internal list is corrupted. + * - OUT_OF_RES */ status_t (*insert_last) (linked_list_t *linked_list, void *item); /** - * @brief removes the last item in the list and returns its value + * @brief Removes the last item in the list and returns its value. * - * @param linked_list calling object - * @param[out] item returned value of last item - * @return SUCCESS if succeeded, FAILED otherwise + * @param linked_list calling object + * @param[out] item returned value of last item + * @return + * - SUCCESS + * - NOT_FOUND if list is empty */ status_t (*remove_last) (linked_list_t *linked_list, void **item); /** - * @brief Returns the value of the last list item without removing it + * @brief Returns the value of the last list item without removing it. * - * @param linked_list calling object - * @param[out] item returned value of last item - * @return SUCCESS if succeeded, FAILED otherwise + * @param linked_list calling object + * @param[out] item returned value of last item + * @return + * - SUCCESS + * - NOT_FOUND if list is empty */ status_t (*get_last) (linked_list_t *linked_list, void **item); /** - * @brief Destroys a linked_list object + * @brief Destroys a linked_list object. * - * @warning all items are removed before deleting the list. The + * @warning All items are removed before deleting the list. The * associated values are NOT destroyed. * Destroying an list which is not empty may cause * memory leaks! * - * @param linked_list calling object - * @return SUCCESS if succeeded, FAILED otherwise + * @param linked_list calling object + * @return + * - SUCCESS */ status_t (*destroy) (linked_list_t *linked_list); }; |