diff options
Diffstat (limited to 'branches/1.0/tinySAK/src/tsk_list.c')
-rw-r--r-- | branches/1.0/tinySAK/src/tsk_list.c | 604 |
1 files changed, 0 insertions, 604 deletions
diff --git a/branches/1.0/tinySAK/src/tsk_list.c b/branches/1.0/tinySAK/src/tsk_list.c deleted file mode 100644 index d441bfc..0000000 --- a/branches/1.0/tinySAK/src/tsk_list.c +++ /dev/null @@ -1,604 +0,0 @@ -/* -* Copyright (C) 2009-2010 Mamadou Diop. -* -* Contact: Mamadou Diop <diopmamadou(at)doubango.org> -* -* This file is part of Open Source Doubango Framework. -* -* DOUBANGO is free software: you can redistribute it and/or modify -* it under the terms of the GNU General Public License as published by -* the Free Software Foundation, either version 3 of the License, or -* (at your option) any later version. -* -* DOUBANGO is distributed in the hope that it will be useful, -* but WITHOUT ANY WARRANTY; without even the implied warranty of -* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the -* GNU General Public License for more details. -* -* You should have received a copy of the GNU General Public License -* along with DOUBANGO. -* -*/ - -/**@file tsk_list.c - * @brief Linked list. - * - * @author Mamadou Diop <diopmamadou(at)doubango.org> - * - * @date Created: Sat Nov 8 16:54:58 2009 mdiop - */ -#include "tsk_list.h" -#include "tsk_memory.h" -#include "tsk_debug.h" - -//#include <assert.h> -#include <string.h> - -// FIXME: remove asserts - -/**@defgroup tsk_list_group Linked list. -* For more information about linked list you can visit http://en.wikipedia.org/wiki/Linked_list. -*/ - -/** tsk_list_find_by_item -*/ -static int tsk_list_find_by_item(const tsk_list_item_t* item, const void* _item) -{ - return (item == (const tsk_list_item_t*)_item) ? 0 : -1; -} - -/**@ingroup tsk_list_group -* Creates a linked list object. -* You MUST use @ref TSK_OBJECT_SAFE_FREE() to safely free the object. -*/ -tsk_list_t* tsk_list_create() -{ - return tsk_object_new(tsk_list_def_t); -} - -/**@ingroup tsk_list_group -* Create and initialize an item to be added to a linked list. -* You MUST use @ref TSK_OBJECT_SAFE_FREE() to safely free the object. -*/ -tsk_list_item_t* tsk_list_item_create() -{ - return tsk_object_new(tsk_list_item_def_t); -} - -/**@ingroup tsk_list_group -* Locks the list to avoid concurrent access. The list should be unlocked using -* @ref tsk_list_unlock. -* @param list The list to lock. -* @retval zero if succeed and non-zero error code otherwise. -* @sa @ref tsk_list_unlock -*/ -int tsk_list_lock(tsk_list_t* list) -{ - if(list){ - if(!list->mutex){ - list->mutex = tsk_mutex_create(); - } - return tsk_mutex_lock(list->mutex); - } - else{ - TSK_DEBUG_ERROR("Invalid parameter"); - return -1; - } -} - -/**@ingroup tsk_list_group -* UnLocks a previously locked list. -* @param list The list to unlock. -* @retval zero if succeed and non-zero error code otherwise. -* @sa @ref tsk_list_lock -*/ -int tsk_list_unlock(tsk_list_t* list) -{ - if(list && list->mutex){ - return tsk_mutex_unlock(list->mutex); - } - else{ - TSK_DEBUG_ERROR("Invalid parameter"); - return -1; - } -} - -/**@ingroup tsk_list_group -* Remove an free an item from the @a list. -* @param list the list from which to remove the @a item. -* @param item the item to remove (and free) from the @a list. -*/ -void tsk_list_remove_item(tsk_list_t* list, tsk_list_item_t* item) -{ - tsk_list_remove_item_by_pred(list, tsk_list_find_by_item, (const void*)item); -} - -/**@ingroup tsk_list_group -* Pops an object from the @a list. -* @param list The list from which to pop the object. -* @param tskobj Any valid object(declared using @ref TSK_DECLARE_OBJECT) to remove. -* @retval The item. -*/ -tsk_list_item_t* tsk_list_pop_item_by_data(tsk_list_t* list, const tsk_object_t * tskobj) -{ - if(list){ - tsk_list_item_t *prev = tsk_null; - tsk_list_item_t *curr = prev = list->head; - - while(curr){ - if(!tsk_object_cmp(curr->data, tskobj)){ - if(prev == curr){ - /* Found at first position. */ - if(list->head == list->tail){ - /* There was only one item */ - list->head = list->tail = tsk_null; - } - else{ - list->head = curr->next; - } - } - else { - if(curr == list->tail){ - /* Found at last position */ - list->tail = prev; - list->tail->next = tsk_null; - } - else{ - prev->next = curr->next; - } - } - - return curr; - } - - prev = curr; - curr = curr->next; - } - } - - return 0; -} - -/**@ingroup tsk_list_group -* Removes an object from the @a list. -* @param list The list from which to remove the object. -* @param tskobj Any valid object(declared using @ref TSK_DECLARE_OBJECT) to remove. -*/ -void tsk_list_remove_item_by_data(tsk_list_t* list, const tsk_object_t * tskobj) -{ - tsk_list_item_t* item; - if((item = tsk_list_pop_item_by_data(list, tskobj))){ - tsk_object_unref(item); - } -} - -/**@ingroup tsk_list_group -* Pops an item from the @a list using a predicate function. -* @param list The list from which to pop the item. -* @param predicate The predicate function used to match the item. -* @param data Arbitrary data to pass to the predicate function. -* @retval The item -*/ -tsk_list_item_t* tsk_list_pop_item_by_pred(tsk_list_t* list, tsk_list_func_predicate predicate, const void * data) -{ - if(list){ - tsk_list_item_t *prev = tsk_null; - tsk_list_item_t *curr = prev = list->head; - - while(curr){ - if(!predicate(curr, data)){ - if(prev == curr){ - /* Found at first position. */ - if(list->head == list->tail){ - /* There was only one item */ - list->head = list->tail = tsk_null; - } - else{ - list->head = curr->next; - } - } - else { - if(curr == list->tail){ - /* Found at last position */ - list->tail = prev; - list->tail->next = tsk_null; - } - else{ - prev->next = curr->next; - } - } - - return curr; - } - - prev = curr; - curr = curr->next; - } - } - - return 0; -} - -/**@ingroup tsk_list_group -* Removes an item from the @a list using a predicate function. -* @param list The list from which to remove the item. -* @param predicate The predicate function used to match the item. -* @param data Arbitrary data to pass to the predicate function. -*/ -void tsk_list_remove_item_by_pred(tsk_list_t* list, tsk_list_func_predicate predicate, const void * data) -{ - tsk_list_item_t* item; - if((item = tsk_list_pop_item_by_pred(list, predicate, data))){ - tsk_object_unref(item); - } -} - -/**@ingroup tsk_list_group -* Clean up and remove all items from the @a list. -* @param list The list ro clean up. -*/ -void tsk_list_clear_items(tsk_list_t* list) -{ - if(list){ - tsk_list_item_t* next = tsk_null; - tsk_list_item_t* curr = list->head; - - while(curr){ - next = curr->next; - tsk_object_unref(curr); - curr = next; - } - list->head = tsk_null; - list->tail = tsk_null; - } -} - -/**@ingroup tsk_list_group -* Pops first item from the @a list. The item will be definitely removed from the list. -* @param list The list from which to pop the item. -* @retval The first item. It is up to you to free the returned item (@ref TSK_OBJECT_SAFE_FREE(item)). -*/ -tsk_list_item_t* tsk_list_pop_first_item(tsk_list_t* list) -{ - tsk_list_item_t* item = tsk_null; - if(list){ - item = list->head; - if(list->head){ - if(list->head->next){ - list->head = list->head->next; - } - else{ - list->head = list->tail = tsk_null; - } - } - } - - return item; -} - -/**@ingroup tsk_list_group -* Add an item to the @a list. -* @param list The destination @a list. -* @param item The @a item to add. -* @param back Indicates whether to put the item back or not. -*/ -void tsk_list_push_item(tsk_list_t* list, tsk_list_item_t** item, tsk_bool_t back) -{ - // do not test - tsk_bool_t first = !list->head; - - if(back && list->tail){ - list->tail->next = *item, list->tail = *item, (*item)->next = tsk_null; - } - else { - (*item)->next = list->head, list->head = *item; - } - - if(first){ - list->tail = list->head = *item, list->tail->next = tsk_null; - } - (*item) = tsk_null; -} - -/**@ingroup tsk_list_group -* Add an item to the list in ascending or descending order. -* @param list The destination @a list. -* @param item The @a item to add. -* @param ascending Indicates whether to put the @a item in ascending order or not. -*/ -void tsk_list_push_filtered_item(tsk_list_t* list, tsk_list_item_t** item, tsk_bool_t ascending) -{ - if(list) - { - tsk_list_item_t *prev = tsk_null; - tsk_list_item_t *curr = prev = list->head; - - while(curr) - { - int diff = tsk_object_cmp((*item), curr); - if((diff </*=*/ 0 && ascending) || (diff >/*=*/0 && !ascending)){ - if(curr == list->head){ - tsk_list_push_front_item(list, item); - } - else{ - (*item)->next = curr; - prev->next = (*item); - } - - return; - } - - prev = curr; - curr = curr->next; - } - - tsk_list_push_back_item(list, item); - } -} - -/**@ingroup tsk_list_group -* Add all items in @a src into @a dest. -* @param dest The destination list. -* @param src The source list. -* @param back Indicates whether to put the list back or not. -**/ -int tsk_list_push_list(tsk_list_t* dest, const tsk_list_t* src, tsk_bool_t back) -{ - const tsk_list_item_t* curr = (src)->head; - tsk_object_t* copy; - - if(!dest || !src){ - TSK_DEBUG_ERROR("Invalid parameter"); - return -1; - } - - while(curr){ - copy = tsk_object_ref(curr->data); - tsk_list_push_data(dest, (void**)©, back); - - curr = curr->next; - } - return 0; -} - -/**@ingroup tsk_list_group -* Add an opaque data to the @a list. -* @param list The destination @a list. -* @param data The @a data to add. -* @param back Indicates whether to put the item back or not. -*/ -int tsk_list_push_data(tsk_list_t* list, void** data, tsk_bool_t back) -{ - if(list && data && *data){ - tsk_list_item_t *item = tsk_list_item_create(); - item->data = *data; - - tsk_list_push_item(list, &item, back); - (*data) = tsk_null; - - return 0; - } - else{ - TSK_DEBUG_ERROR("Invalid parameter"); - return -1; - } -} - -/**@ingroup tsk_list_group -* Add an opaque data to the list in ascending or descending order. -* @param list The destination @a list. -* @param data The @a data to add. -* @param ascending Indicates whether to put the @a data in ascending order or not. -*/ -int tsk_list_push_filtered_data(tsk_list_t* list, void** data, tsk_bool_t ascending) -{ - if(list && data && *data){ - tsk_list_item_t *item = tsk_list_item_create(); - item->data = *data; - - tsk_list_push_filtered_item(list, &item, ascending); - (*data) = tsk_null; - - return 0; - } - else{ - TSK_DEBUG_ERROR("Invalid parameter"); - return -1; - } -} - -/**@ingroup tsk_list_group -* Find an item from a list. -* @param list The @a list holding the item. -* @param tskobj The @a object to find. -* @retval A @ref tsk_list_item_t item if found and NULL otherwize. -*/ -const tsk_list_item_t* tsk_list_find_item_by_data(const tsk_list_t* list, const tsk_object_t* tskobj) -{ - if(list && tskobj){ - tsk_list_item_t *item; - tsk_list_foreach(item, list){ - if(!tsk_object_cmp(item->data, tskobj)){ - return item; - } - } - } - - return 0; -} - -/**@ingroup tsk_list_group -* Find first item matching criteria defined by the @a predicate. -* @param list the list to query -* @param predicate the predicate against which to test each item -* @param data data passed to the predicate function for comparaison -* @retval the item which match the criteria and NULL otherwise -* @sa @ref tsk_list_find_item_by_data -*/ -const tsk_list_item_t* tsk_list_find_item_by_pred(const tsk_list_t* list, tsk_list_func_predicate predicate, const void* data) -{ - if(predicate){ - const tsk_list_item_t *item; - tsk_list_foreach(item, list){ - if(!predicate(item, data)){ - return item; - } - } - } - else{ - TSK_DEBUG_WARN("Cannot use an uninitialized predicate function"); - } - return tsk_null; -} - -/**@ingroup tsk_list_group -* Find first item matching criteria defined by the @a predicate. -* @param list the list to query -* @param predicate the predicate against which to test each item -* @param data data passed to the predicate function for comparaison -* @retval the data holded by the item which match the criteria and NULL otherwise -* @sa @ref tsk_list_find_item_by_pred -*/ -const tsk_object_t* tsk_list_find_object_by_pred(const tsk_list_t* list, tsk_list_func_predicate predicate, const void* data) -{ - const tsk_list_item_t *item; - if((item = tsk_list_find_item_by_pred(list, predicate, data))){ - return item->data; - } - else{ - return tsk_null; - } -} - -/**@ingroup tsk_list_group -* Counts the number of item matching the predicate. -* @param list The list containing the items to count -* @param predicate The predicate to use to match the items -* @param data Data passed to the predicate function for comparaison -* @retval The number of item matching the predicate -*/ -tsk_size_t tsk_list_count(const tsk_list_t* list, tsk_list_func_predicate predicate, const void* data) -{ - tsk_size_t count = 0; - if(predicate && list){ - const tsk_list_item_t *item; - tsk_list_foreach(item, list){ - if(!predicate(item, data)){ - ++count; - } - } - } - else{ - TSK_DEBUG_ERROR("Invalid parameter"); - } - - return count; -} - - - - - - - - - - - -//================================================================================================= -// Item object definition -// -static tsk_object_t* tsk_list_item_ctor(tsk_object_t * self, va_list * app) -{ - tsk_list_item_t *item = self; - if(item){ - } - return self; -} - -static tsk_object_t* tsk_list_item_dtor(tsk_object_t *self) -{ - tsk_list_item_t *item = self; - if(item){ - item->data = tsk_object_unref(item->data); - } - else{ - TSK_DEBUG_WARN("Cannot free an uninitialized item"); - } - return item; -} - -static int tsk_list_item_cmp(const tsk_object_t *_item1, const tsk_object_t *_item2) -{ - const tsk_list_item_t* item1 = _item1; - const tsk_list_item_t* item2 = _item2; - - if(item1 && item2){ - return tsk_object_cmp(item1->data, item2->data); - } - else return -1; -} - -static const tsk_object_def_t tsk_list_item_def_s = -{ - sizeof(tsk_list_item_t), - tsk_list_item_ctor, - tsk_list_item_dtor, - tsk_list_item_cmp, -}; -const tsk_object_def_t *tsk_list_item_def_t = &tsk_list_item_def_s; - -//================================================================================================= -// List object definition -// -static tsk_object_t* tsk_list_ctor(tsk_object_t *self, va_list *app) -{ - tsk_list_t *list = self; - if(list){ - } - - return self; -} - -static tsk_object_t* tsk_list_dtor(tsk_object_t *self) -{ - tsk_list_t *list = self; - if(list){ -#if 0 - /* Not thread-safe */ - tsk_list_item_t* next = tsk_null; - tsk_list_item_t* curr = list->head; - - while(curr){ - next = curr->next; - /*curr =*/ tsk_object_unref(curr); - curr = next; - } -#else - /* Thread-safe method */ - tsk_list_item_t* item; - while((item = tsk_list_pop_first_item(list))){ - tsk_object_unref(item); - } -#endif - - /* destroy the on-demand mutex */ - if(list->mutex){ - tsk_mutex_destroy(&list->mutex); - } - } - else{ - TSK_DEBUG_WARN("Cannot free an uninitialized list"); - } - return list; -} - -static const tsk_object_def_t tsk_list_def_s = -{ - sizeof(tsk_list_t), - tsk_list_ctor, - tsk_list_dtor, - tsk_null, -}; -const tsk_object_def_t *tsk_list_def_t = &tsk_list_def_s; - |