/** * @file linkedList.h * @ingroup collection * * Linked list module. * * @author Geoff Davis <geoff@circlemudsquared.org> * * @par Copyright: * Copyright (C) 2006 Geoff Davis <geoff@circlemudsquared.org><br> * Greg Buxton <greg@circlemudsquared.org> * * @par * Copyright (C) 1993, 94 by the Trustees of the Johns Hopkins University<br> * CircleMUD is based on DikuMUD, Copyright (C) 1990, 1991. * * @par * All rights reserved. See license.doc for complete information. * * @package cs * @version 1.0 */ #ifndef __LINKEDLIST_H__ #define __LINKEDLIST_H__ #include "base.h" /** * An alias for struct _linkedList_t. * @typedef struct _linkedList_t */ typedef struct _linkedList_t linkedList_t; /** * An alias for struct _linkedListEntry_t. * @typedef struct _linkedListEntry_t */ typedef struct _linkedListEntry_t linkedListEntry_t; /** * An alias for struct _linkedListIterator_t. * @typedef struct _linkedListIterator_t */ typedef struct _linkedListIterator_t linkedListIterator_t; /** * The linked list structure. * @{ */ struct _linkedList_t { linkedListEntry_t *firstEntry; /**< the first entry in the list */ freeFunction_t freeFunction; /**< the function to free elements. */ linkedListEntry_t *lastEntry; /**< the last entry in the list. */ size_t size; /**< the number of list entries. */ }; /** @} */ /** * The linked list entry structure. * @{ */ struct _linkedListEntry_t { void *element; /**< the element. */ linkedListEntry_t *nextEntry; /**< the next entry in the list. */ linkedListEntry_t *previousEntry; /**< the previous entry in the list.*/ }; /** @} */ /** * The list iterator structure. * @{ */ struct _linkedListIterator_t { linkedListEntry_t *currentEntry; /**< the current entry in the list. */ linkedListEntry_t *lastReturned; /**< the last entry returned by iter*/ linkedList_t *list; /**< the list being iterated over. */ }; /** @} */ /* * list functions */ /** * Removes all elements from a linked list. * @param list the linked list to be cleared * @return none */ void linkedList_clear(linkedList_t *list); /** * Returns whether a linked list contains a particular element. * @param list the linked list to be tested * @param element the element for which to test * @return TRUE if the linked list contains a matching element; * FALSE otherwise */ bool linkedList_contains(linkedList_t *list, void *element); /** * Constructs a new linked list. * @param freeFunction the function to be called to free elements * @return a new linked list or NULL */ linkedList_t *linkedList_create(freeFunction_t freeFunction); /** * Frees a linked list. * @param list the linked list to be freed * @return none */ void linkedList_free(linkedList_t *list); /** * Returns the size of a linked list. * @param list the linked list to be tested * @return the size of the linked list, or zero (0) */ size_t linkedList_getSize(linkedList_t *list); /** * Returns whether a linked list is empty. * @param list the linked list to be tested * @return TRUE if the linked list is empty; FALSE otherwise */ bool linkedList_isEmpty(linkedList_t *list); /** * Returns the last element in a linked list. * @param list the linked list whose last element is to be retreived * @param defaultValue the value to be returned if the linked list is empty * @return the last element, or NULL */ void *linkedList_peekBack(linkedList_t *list, void *defaultValue); /** * Returns the first element in a linked list. * @param list the linked list whose first element is to be retreived * @param defaultValue the value to be returned if the linked list is empty * @return the first element, or NULL */ void *linkedList_peekFront(linkedList_t *list, void *defaultValue); /** * Removes and returns the last element in a linked list. * @param list the linked list whose last element is to be popped * @param defaultValue the value to be returned if the linked list is empty * @return the last element, or NULL */ void *linkedList_popBack(linkedList_t *list, void *defaultValue); /** * Removes and returns the first element in a linked list. * @param list the linked list whose first element is to be popped * @param defaultValue the value to be returned if the linked list is empty * @return the first element, or NULL */ void *linkedList_popFront(linkedList_t *list, void *defaultValue); /** * Adds an element at the end of a linked list. * @param list the linked list into which an element is to be inserted * @param element the element to be inserted * @return TRUE if the size of the linked list was changed by this function; * FALSE otherwise */ bool linkedList_pushBack(linkedList_t *list, void *element); /** * Adds an element at the beginning of a linked list. * @param list the linked list into which an element is to be inserted * @param element the element to be inserted * @return TRUE if the size of the linked list was changed by this function; * FALSE otherwise */ bool linkedList_pushFront(linkedList_t *list, void *element); /** * Removes an element from a linked list. * @param list the linked list from which to remove an element * @param element the element to be removed * @return TRUE if the size of the linked list was changed by this function; * FALSE otherwise */ bool linkedList_remove(linkedList_t *list, void *element); /* * linked list iterator functions */ /** * @ingroup collection * @example linkedListIterator_example.c */ /** * Constructs a new linked list iterator. * @param list the linked list to be iterated * @return a new linked list iterator, or NULL */ linkedListIterator_t *linkedListIterator_create(linkedList_t *list); /** * Frees a linked list iterator. * @param iter the linked list iterator to be freed * @return none */ void linkedListIterator_free(linkedListIterator_t *iter); /** * Returns whether a linked list iterator has more elements. * @param iter the linked list iterator to be tested * @return TRUE if there are more elements to be iterated; * FALSE otherwise */ bool linkedListIterator_hasNext(linkedListIterator_t *iter); /** * Returns the current element and advances the linked list iterator. * @param iter the linked list iterator * @return the current element, or NULL */ void *linkedListIterator_next(linkedListIterator_t *iter); /** * Removes the last element returned by a linked list iterator. * @param iter the linked list iterator from which to remove an element * @return none */ void linkedListIterator_remove(linkedListIterator_t *iter); /** * Removes a linked list entry from a linked list and updates the linked list * size. * @param list the linked list whose entry is to be unlinked * @param entry the entry to be removed * @param freeIt if the linked list entry element is to be freed * @return none */ void linkedListPrivate_removeEntry(linkedList_t *list, linkedListEntry_t *entry, bool freeIt); #endif /* __LINKEDLIST_H__ */