Section: libcprops - cp_list (3)
Updated: OCTOBER 2005
Index Return to Main Contents [view source]


cp_list - a doubly linked list implementation  


#include <cprops/linked_list.h>

cp_list *cp_list_create();
cp_list *cp_list_create_nosync();
cp_list *cp_list_create_list(int mode,
                              cp_compare_fn compare_fn,
                              cp_copy_fn copy_fn,
                              cp_destructor_fn item_destructor);
void cp_list_destroy(cp_list *list);
void cp_list_destroy_by_option(cp_list *list, int option);
void cp_list_destroy_custom(cp_list *list, cp_destructor_fn fn);

void *cp_list_insert(cp_list *list, void *item);
void *cp_list_append(cp_list *list, void *item);
void *cp_list_insert_after(cp_list *list, void *item, void *existing);
void *cp_list_insert_before(cp_list *list, void *item, void *existing);

void *cp_list_remove(cp_list *list, void *item);
void *cp_list_remove_head(cp_list *list);
void *cp_list_remove_tail(cp_list *list);

void *cp_list_search(cp_list *list, void *item);
int cp_list_callback(cp_list *list,
                      int (*action)(void *, void *),
                      void *identifier);
void *cp_list_get_head(cp_list *list);
void *cp_list_get_tail(cp_list *list);

int cp_list_lock(cp_list *list, int mode);
int cp_list_rdlock(cp_list *list);
int cp_list_wrlock(cp_list *list);
int cp_list_unlock(cp_list *list);

long cp_list_item_count(cp_list *list);
int cp_list_is_empty(cp_list *list);


cp_list is a doubly linked list implementation.  


the zero parameter constructor function cp_list_create is equivalent to cp_list_create(COLLECTION_MODE_MULTIPLE_VALUES, NULL, NULL) and is What You Usually Want.
Lists can also be created with the COLLECTION_MODE_COPY and COLLECTION_MODE_DEEP bits set. This requires a pointer to a cp_copy_fn function defined as

      void *fn(void *value)

to be passed as the copy_fn parameter to cp_list_create_list. the copy function should be capable of duplicating entries and would be used to delegate the responsibility for memory management to the cp_list. A list created with the COLLECTION_MODE_DEEP flag will call the item_destructor if not NULL on all elements upon calling cp_list_destroy. It is possible to invoke a different destructor function on list items upon list deallocation by calling cp_list_destroy_custom with the fn parameter pointing to a custom destructor function for list items. To avoid any destructor call on list items on a list instantiated with COLLECTION_MODE_DEEP, call cp_list_destroy_by_option with the COLLECTION_MODE_DEEP bit unset.

NOTE: be sure to instantiate lists with COLLECTION_MODE_MULTIPLE_VALUES - unless you want a list that contains unique values. This will require a non-null compare_fn parameter to be passed to cp_list_create_list. the comparison function should be defined as

      int *fn(void *a, void *b)

and return 0 for matching entries, non-zero otherwise (``strcmp semantics''). On lists instantiated without COLLECTION_MODE_MULTIPLE_VALUES set, every insert operation entails a full list scan to avoid duplicates. This could represent a serious performance hit for large sets. If you really need a linked list with no duplicates, consider using a cp_hashlist instead.



cp_list_insert adds an item at the top of the list. cp_list_append adds an item at the end of the list. The cp_list_insert_before and cp_list_insert_after functions can only be used if the list was instantiated with a cp_compare_fn function. If the existing item can't be matched, cp_list_insert_before adds the new item is added at the first position in the list and cp_list_insert_after at the last position.



cp_list_remove scans the list for the item item and removes it if found. This function can only be used if the list was instantiated with a cp_compare_fn function. The cp_list_remove_head and cp_list_remove_tail functions remove the item from the top or bottom of the list, respectively.
for lists defined with COLLECTION_MODE_DEEP, the removal functions will free the memory for the removed item. The pointer returned will be pointing to deallocated space. It can be used to tell whether the removal operation succeeded or not, but should probably not be dereferenced.



cp_list_get_head returns the item at the top of the list and cp_list_get_tail returns the item at the end of the list. cp_list_search attempts to find an item matching the item parameter and can only be used if the list was instantiated with a cp_compare_fn function. cp_list_callback iterates over the list calling action on each item. The first parameter to the callback function is the list item, the second is the identifier specified by the caller. A non-zero return value from the callback stops the iteration.



call cp_list_lock with the mode parameter set to COLLECTION_LOCK_READ to obtain a read-lock, or to COLLECTION_LOCK_WRITE to obtain a write-lock on a list. The macros cp_list_rdlock and cp_list_wrlock may also be used to the same effect. Calls to locking functions must be coupled with a call to cp_list_unlock to release the lock. Unless COLLECTION_MODE_NOSYNC is set tree operations are synchronized and to not require explicit locking. This is however necessary in a transaction-like scenario in which several consecutive operations must be executed while locking the collection for access by other threads. When a thread obtains a lock with cp_list_lock or its equivalents subsequent list operations on this thread do not attempt to obtain the list lock (which would cause a deadlock), while list operations on other threads do. It is the responsibility of the application to perform the right kind of locking for the operations that may occur while the list is locked. If there is any chance that items may be added or removed, the list must be write-locked. Otherwise the list may be read-locked.

cp_list instances are synchronized by default. That is, read operations obtain a read-lock and insertion or removal operations obtain a write lock on the list. If you're creating a list that will only be used within a single thread, or will only be accessed in code which is synchronized externally, avoid the overhead by creating the list with cp_create_list_nosync(), which is equivalent to cp_list_create_list(COLLECTION_MODE_MULTIPLE_VALUES | COLLECTION_MODE_NOSYNC)



cp_list_item_count returns the number of items currently in the list.
cp_list_is_empty returns non-zero is the list is empty, 0 otherwise.



constructor functions return a pointer to a newly allocated cp_list or NULL on failure.
insertion, retrieval and removal functions return a pointer to the relevant item or NULL if the operation failed.
synchronization functions return 0 on success, non-zero on error.



cp_list_iterator(3), cp_priority_list(3), cp_hashlist(3)




This document was created by man2html, using the manual pages.
Time: 12:01:45 GMT, May 23, 2006
SourceForge.net Logo