/** * @file linkedList.c * @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 */ #define __LINKEDLIST_C__ #include "base.h" #include "linkedList.h" #include "log.h" #include "memory.h" /* * linked 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) { if (list == NULL) { log("linkedList_clear(): invalid 'list' linkedList_t."); } else { while (list->size) { /* Save off the first list entry. */ linkedListEntry_t *entry = list->firstEntry; /* Unlink the linked list entry. */ linkedListPrivate_removeEntry(list, entry, TRUE); } } } /** * 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) { if (list == NULL) { log("linkedList_contains(): invalid 'list' linkedList_t."); } else { /* Declare an iterator variable. */ register linkedListEntry_t *entry = NULL; /* Search the linked list for the desired element. */ for (entry = list->firstEntry; entry; entry = entry->nextEntry) { if (entry->element == element) { return (TRUE); } } } return (FALSE); } /** * 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) { /* Allocate a new linkedList_t. */ linkedList_t *list = CIRCLE_ALLOCN(linkedList_t, 1); if (list == NULL) { log("linkedList_create(): CIRCLE_ALLOCN() failed."); } else { /* Initialize the new linkedList_t. */ list->firstEntry = NULL; list->freeFunction = freeFunction; list->lastEntry = NULL; list->size = (size_t) 0UL; } return (list); } /** * Frees a linked list. * @param list the linked list to be freed * @return none */ void linkedList_free(linkedList_t *list) { if (list == NULL) { log("linkedList_free(): invalid 'list' linkedList_t."); } else { /* Clear the linked list. */ linkedList_clear(list); /* Free the linked list structure. */ free(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) { size_t retval = (size_t) 0UL; if (list == NULL) { log("linkedList_getSize(): invalid 'list' linkedList_t."); } else { retval = list->size; } return (retval); } /** * 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) { return (list == NULL || list->size == (size_t) 0UL); } /** * 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) { void *retval = defaultValue; if (list == NULL) { log("linkedList_peekBack(): invalid 'list' linkedList_t."); } else { if (list->size && list->lastEntry) { retval = list->lastEntry->element; } } return (retval); } /** * 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) { void *retval = defaultValue; if (list == NULL) { log("linkedList_peekFront(): invalid 'list' linkedList_t."); } else { if (list->size && list->firstEntry) { retval = list->firstEntry->element; } } return (retval); } /** * 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) { void *retval = defaultValue; if (list == NULL) { log("linkedList_popBack(): invalid 'list' linkedList_t."); } else { if (list->size && list->lastEntry) { /* Save off the last list entry. */ linkedListEntry_t *entry = list->lastEntry; /* Save off the last element. */ retval = entry->element; /* Unlink the linked list entry. */ linkedListPrivate_removeEntry(list, entry, FALSE); } } return (retval); } /** * 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) { void *retval = defaultValue; if (list == NULL) { log("linkedList_popFront(): invalid 'list' linkedList_t."); } else { if (list->size && list->firstEntry) { /* Save off the first list entry. */ linkedListEntry_t *entry = list->firstEntry; /* Save off the first element. */ retval = entry->element; /* Unlink the linked list entry. */ linkedListPrivate_removeEntry(list, entry, FALSE); } } return (retval); } /** * 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) { bool retval = FALSE; if (list == NULL) { log("linkedList_pushBack(): invalid 'list' linkedList_t."); } else { /* Allocate a new linkedListEntry_t. */ linkedListEntry_t *entry = CIRCLE_ALLOCN(linkedListEntry_t, 1); if (entry == NULL) { log("linkedList_pushBack(): CIRCLE_ALLOCN() failed."); } else { /* At this point, we know the operation will succeed. */ retval = TRUE; /* Initialize the new entry. */ entry->element = element; entry->nextEntry = NULL; entry->previousEntry = list->lastEntry; /* * Link the new entry into the linked list. */ if (list->lastEntry) { list->lastEntry->nextEntry = entry; } if (list->firstEntry == NULL) { list->firstEntry = entry; } list->lastEntry = entry; /* Increment the size of the linked list by one (1). */ list->size++; } } return (retval); } /** * 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) { bool retval = FALSE; if (list == NULL) { log("linkedList_pushFront(): invalid 'list' linkedList_t."); } else { /* Allocate a new linkedListEntry_t. */ linkedListEntry_t *entry = CIRCLE_ALLOCN(linkedListEntry_t, 1); if (entry == NULL) { log("linkedList_pushFront(): CIRCLE_ALLOCN() failed."); } else { /* At this point, we know the operation will succeed. */ retval = TRUE; /* Initialize the new entry. */ entry->element = element; entry->nextEntry = list->firstEntry; entry->previousEntry = NULL; /* * Link the new entry into the linked list. */ if (list->firstEntry) { list->firstEntry->previousEntry = entry; } if (list->lastEntry == NULL) { list->lastEntry = entry; } list->firstEntry = entry; /* Increment the size of the linked list by one (1). */ list->size++; } } return (retval); } /** * 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) { bool retval = FALSE; if (list == NULL) { log("linkedList_remove(): invalid 'list' linkedList_t."); } else { /* Declare an iterator variable. */ register linkedListEntry_t *entry = NULL; /* Search for the element in the linked list. */ for (entry = list->firstEntry; entry && entry->element != element; entry = entry->nextEntry); if (entry) { /* If we made it this far, we've succeeded. */ retval = TRUE; /* Unlink the entry from the linked list. */ linkedListPrivate_removeEntry(list, entry, TRUE); } } return (retval); } /* * 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) { linkedListIterator_t *iter = NULL; if (list == NULL) { log("linkedListIterator_create(): invalid 'list' linkedList_t."); } else { /* Allocate a new linked list iterator. */ iter = CIRCLE_ALLOCN(linkedListIterator_t, 1); if (iter == NULL) { log("linkedListIterator_create(): CIRCLE_ALLOCN() failed."); } else { /* Initialize the new linked list iterator. */ iter->currentEntry = list->firstEntry; iter->lastReturned = NULL; iter->list = list; } } return (iter); } /** * Frees a linked list iterator. * @param iter the linked list iterator to be freed * @return none */ void linkedListIterator_free(linkedListIterator_t *iter) { if (iter == NULL) { log("linkedListIterator_free(): invalid 'iter' linkedListIterator_t."); } else { free(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) { bool retval = FALSE; if (iter == NULL) { log("linkedListIterator_hasNext(): invalid 'iter' linkedListIterator_t."); } else { if (iter->currentEntry) { retval = TRUE; } } return (retval); } /** * 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) { void *element = NULL; if (iter == NULL) { log("linkedListIterator_next(): invalid 'iter' linkedListIterator_t."); } else if (iter->currentEntry) { /* Save off the current element. */ element = iter->currentEntry->element; /* Save off the last entry. */ iter->lastReturned = iter->currentEntry; /* Advance the linked list iterator to the next entry. */ iter->currentEntry = iter->currentEntry->nextEntry; } return (element); } /** * 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) { if (iter == NULL) { log("linkedListIterator_remove(): invalid 'iter' linkedListIterator_t."); } else if (iter->lastReturned == NULL) { log("linkedListIterator_remove(): iterator has no last entry."); } else { /* Save off the last returned entry's next entry. */ linkedListEntry_t *lastNext = iter->lastReturned->nextEntry; /* Unlink the last returned entry. */ linkedListPrivate_removeEntry(iter->list, iter->lastReturned, TRUE); /* And now, a quick fix up. */ if (iter->currentEntry == iter->lastReturned) { iter->currentEntry = lastNext; } /* Reset the iterator's last entry. */ iter->lastReturned = NULL; } } /** * 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) { if (list == NULL) { log("linkedListPrivate_removeEntry(): invalid 'list' linkedList_t."); } else if (entry == NULL) { log("linkedListPrivate_removeEntry(): invalid 'entry' linkedListEntry_t."); } else { /* Relink the previous entry. */ if (entry->previousEntry) { entry->previousEntry->nextEntry = entry->nextEntry; } else { list->firstEntry = entry->nextEntry; } /* Relink the next entry. */ if (entry->nextEntry) { entry->nextEntry->previousEntry = entry->previousEntry; } else { list->lastEntry = entry->previousEntry; } /* Free the linked list entry element. */ if (freeIt && list->freeFunction) { list->freeFunction(entry->element); } /* Free the linked list entry. */ free(entry); /* Decrement the linked list size by one (1). */ list->size--; } }