list.h

Go to the documentation of this file.

/*! \file
  \brief  The List_c class.  Generic linked list.

  \par Copyright Information

  Copyright (c) 2017 by The DiSTI Corporation.<br>
  11301 Corporate Blvd; Suite 100<br>
  Orlando, Florida 32817<br>
  USA<br>
  <br>
  All rights reserved.<br>

  This Software contains proprietary trade secrets of DiSTI and may not be
reproduced, in whole or part, in any form, or by any means of electronic,
mechanical, or otherwise, without the written permission of DiSTI.  Said
permission may be derived through the purchase of applicable DiSTI product
licenses which detail the distribution rights of this content and any
Derivative Works based on this or other copyrighted DiSTI Software.

  NO WARRANTY. THE SOFTWARE IS PROVIDED "AS-IS," WITHOUT WARRANTY OF ANY KIND,
AND ANY USE OF THIS SOFTWARE PRODUCT IS AT YOUR OWN RISK. TO THE MAXIMUM EXTENT
PERMITTED BY APPLICABLE LAW, DISTI AND ITS SUPPLIERS DISCLAIM ALL WARRANTIES
AND CONDITIONS, EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE
IMPLIED WARRANTIES AND CONDITIONS OF MERCHANTABILITY AND/OR FITNESS FOR A
PARTICULAR PURPOSE, TITLE, AND NON-INFRINGEMENT, WITH REGARD TO THE SOFTWARE.

  LIMITATION OF LIABILITY. TO THE MAXIMUM EXTENT PERMITTED BY APPLICABLE LAW,
IN NO EVENT SHALL DISTI OR ITS SUPPLIERS BE LIABLE FOR ANY SPECIAL, INCIDENTAL,
INDIRECT, OR CONSEQUENTIAL DAMAGES WHATSOEVER (INCLUDING, WITHOUT LIMITATION,
DAMAGES FOR LOSS OF BUSINESS PROFITS, BUSINESS INTERRUPTION, LOSS OF BUSINESS
INFORMATION, OR ANY OTHER PECUNIARY LOSS) ARISING OUT OF THE USE OF OR
INABILITY TO USE THE SOFTWARE, EVEN IF DISTI HAS BEEN ADVISED OF THE POSSIBILITY
OF SUCH DAMAGES.  DISTI'S ENTIRE LIABILITY AND YOUR EXCLUSIVE REMEDY SHALL NOT
EXCEED FIVE DOLLARS (US$5.00).

  The aforementioned terms and restrictions are governed by the laws of the
State of Florida and the United States of America.

*/
#ifndef INCLUDED_GLS_LIST_H
#define INCLUDED_GLS_LIST_H

/* Includes */
#include "disti_include.h"
#include <stdio.h>

namespace disti
{
/** \class ListItem
  * Implements a list item for use in a List_c
  */
class ListItem
{
public:
    /** Creates a ListItem given data.  This method will allocate storage
      * for the data passed in.
      * \param data  A pointer to data to copy
      * \param len   Length of data to copy
      */
    DISTI_EXPORT ListItem( const void* data, int len );

    /** Creates a ListItem without allocating internal storage.  */
    DISTI_EXPORT ListItem();

    /** Destroys a ListItem, deallocating any storage the item has allocated */
    virtual DISTI_EXPORT ~ListItem();

    /** \return The data member of this ListItem.  */
    DISTI_EXPORT void* Data();

    /** \return What the data member of this ListItem is pointing to (a double indirection)  */
    DISTI_EXPORT void* DataPtr();

    /** \return The ListItem after this in the list, or NULL if there is no next ListItem */
    DISTI_EXPORT ListItem* Next();

    /** \return The ListItem before this in the list, or NULL if there is no previous ListItem */
    DISTI_EXPORT ListItem* Prev();

    /** \return The priority of this ListItem */
    DISTI_EXPORT int Priority() const { return _priority; }

    /** Set the Next ListItem in the List 
      * \param pNext  Pointer to the item that will become this item's next item
      */
    DISTI_EXPORT void Next( ListItem* pNext );

    /** Set the Previous ListItem in the List 
      * \param pPrev  Pointer to the item that will become this item's previous item
      */
    DISTI_EXPORT void Prev( ListItem* pPrev );

    /** Set the data associated with this item.
      * This merely changes the value of the Data pointer, it does not allocate or copy data
      * \param item  The new data for this item
      */
    DISTI_EXPORT void Data( void* item );

    /** Change the priority of this list item.
      * NOTE:  Changing an item's priority does not resort the list.
      * \param priority  The new priority of the list item
      */
    DISTI_EXPORT void Priority( int priority );

    /** Allocates the specified amount of data for the item.  Does not
      * deallocate the old data!
      * \param size  Size of the data to allocate
      */
    DISTI_EXPORT void AllocateItemData( int size );

private:
    ListItem* _next;     /** Pointer to next list item */
    ListItem* _prev;     /** Pointer to previous list item */
    int       _priority; /** Item priority, used for priority queue behavior */

protected:
    void* _data; /** Pointer to list item data */
};

typedef void ( *ListIterator )( void* obj, void* data );

/**
    List Iterator Direction
*/
typedef enum
{
    FORWARD,
    BACKWARD
} ListIteratorDirection;

/** \class List_c
  * Implements a doubly Linked List
  */
class List_c
{
public:
    DISTI_EXPORT List_c();
    virtual DISTI_EXPORT ~List_c();

    int _count; /** Number of items in the list */

    /** Returns whether or not the list is empty
      * \return Whether or not the list is empty 
      */
    DISTI_EXPORT int IsEmpty();

    /** Empties the list (deletes all the elements) */
    DISTI_EXPORT void Empty();

    /** Get a pointer to the first ListItem in the list
      * \return Pointer to the first ListItem in the list or NULL if the list
      * is empty
      */
    DISTI_EXPORT ListItem* First();

    /** Get a pointer to the first ListItem in the list
      * \return Pointer to the first ListItem in the list or NULL if the list
      * is empty
      */
    DISTI_EXPORT ListItem* Last();

    /** Get a pointer to the ListItem for the Nth element
      * \param where 0 based array index
      * \return Pointer to the ListItem at that index  or NULL if the list is empty
      */
    DISTI_EXPORT ListItem* Nth( int where );

    /** Inserts the given data at designated index in the list.  If the index is greater than the 
      * list size, the element will be inserted at the end of the list
      * A new ListItem will be allocated, space will be allocated for the data passed in
      * \param where The zero based index
      * \param data  Pointer to the data to insert
      * \param size  Size of the data to insert
      * \param parentPtr Will be filled in with a pointer to the ListItem that this method allocates
      */
    DISTI_EXPORT void InsertAfter( int where, const void* data, int size, void** parentPtr );

    /** Inserts the given data after the specified list item
      * A new ListItem will be allocated, space will be allocated for the data passed in
      * \param after Pointer to the list element to insert after
      * \param data  Pointer to the data to insert
      * \param size  Size of the data to insert
      * \param parentPtr Will be filled in with a pointer to the ListItem that this method allocates
      */
    DISTI_EXPORT void InsertAfter( ListItem* after, const void* data, int size, void** parentPtr );

    /** Inserts the given list element after the specified list element
      * \param after Pointer to the list element to insert after
      * \param pNewNode  A previously allocated ListItem to insert
      */
    DISTI_EXPORT void InsertAfter( ListItem* after, ListItem* pNewNode );

    /** Inserts the given list element before the specified list element
      * \param before Pointer to the list element to insert before
      * \param pNewNode  A previously allocated ListItem to insert
      */
    DISTI_EXPORT void InsertBefore( ListItem* before, ListItem* pNewNode );

    /** Inserts the given data at the front of the list. 
      * A new ListItem will be allocated, space will be allocated for the data passed in
      * \param data  Pointer to the data to insert
      * \param size  Size of the data to insert
      * \param parentPtr Will be filled in with a pointer to the ListItem that this method allocates
      */
    DISTI_EXPORT void Push( const void* data, int size, void** parentPtr );

    /** Inserts the given data at the front of the list. 
      * A new ListItem will be allocated, space will be allocated for the data passed in
      * \param data  Pointer to the data to insert
      * \param size  Size of the data to insert
      */
    DISTI_EXPORT void Push( const void* data, int size );

    /** Inserts the given list element at the front of the list
      * \param pNewNode  A previously allocated ListItem to insert
      */
    DISTI_EXPORT void Push( ListItem* pNewNode );

    /** Inserts the given data at the end of the list. 
      * A new ListItem will be allocated, space will be allocated for the data passed in
      * \param data  Pointer to the data to insert
      * \param size  Size of the data to insert
      * \param parentPtr Will be filled in with a pointer to the ListItem that this method allocates
      */
    DISTI_EXPORT void Enqueue( const void* data, int size, void** parentPtr );

    /** Inserts the given data  at the end of the list. 
      * A new ListItem will be allocated, space will be allocated for the data passed in
      * \param data  Pointer to the data to insert
      * \param size  Size of the data to insert
      */
    DISTI_EXPORT void Enqueue( const void* data, int size );

    /** Inserts the given list element at the end of the list
      * \param pNewNode  A previously allocated ListItem to insert
      */
    DISTI_EXPORT void Enqueue( ListItem* pNewNode );

    /** Gets a pointer to the data in the first element of the list.
      * The list element will be freed.  The user should free the data 
      * returned by this call.
      * \return Data pointed to by the first element in the list or NULL
      *         if the list is empty
      */
    DISTI_EXPORT void* Dequeue();

    /** Gets a pointer to the data at the given "index" into the list
      * \return  A pointer to the data or NULL if the index is invalid
      */
    DISTI_EXPORT void* GetElement( int where );

    /** \return  The number of items in this list */
    DISTI_EXPORT int Count();

    /** Deletes the specified list element.  Frees the data pointed to by the element.
      * \param element  The element to delete
      */
    DISTI_EXPORT void Delete( ListItem* element );

    /** Adds a new node (item) to the list.  The item position will be determined based on its priority.
      * \param pNewNode  A previously allocated list node containing the data to add
      * \param priority  Sorting priority
      */
    DISTI_EXPORT void AddNodeWithPriority( ListItem* pNewNode, int priority );

    /** Adds a new node (item) to the list.  The item position will be determined based on its priority.
      * This method will dynamically allocate space for the data  
      * \param data  Pointer to the data to be added
      * \param size  Size of the data to be added
      * \param priority  Sorting priority
      */
    DISTI_EXPORT void AddNodeWithPriority( const void* data, int size, int priority );

    /** Iterates through the list from head to tail, calling the supplied function on each element
      * and passing the supplied data to that function
      * \param func ListIterator function to call
      * \param data Data that will be supplied to each call of the list iterator function
      */
    DISTI_EXPORT void ForwardIterator( ListIterator func, void* data = NULL );

    /** Iterates through the list in reverse order, calling the supplied function on each element
      * and passing the supplied data to that function
      * \param func ListIterator function to call
      * \param data Data that will be supplied to each call of the list iterator function
      */
    DISTI_EXPORT void BackwardIterator( ListIterator func, void* data = NULL );

    /** Iterates through the list in the specified direction, calling the supplied function on each element
      * and passing the supplied data to that function
      * \param func ListIterator function to call
      * \param data Data that will be supplied to each call of the list iterator function
      * \param direction  Which directon to iterate
      */
    DISTI_EXPORT void Iterator( ListIterator func, void* data, ListIteratorDirection direction );

protected:
    ListItem* _pHead; /** Pointer to the head (first item) of the list */
    ListItem* _pTail; /** Pointer to the tail (last item) of the list */
};

} // namespace disti

#endif