LinkedList.h

Go to the documentation of this file.
00001 /*******************************************************************************
00002  *
00003  * Copyright (c) 2000-2003 Intel Corporation 
00004  * All rights reserved. 
00005  *
00006  * Redistribution and use in source and binary forms, with or without 
00007  * modification, are permitted provided that the following conditions are met: 
00008  *
00009  * * Redistributions of source code must retain the above copyright notice, 
00010  * this list of conditions and the following disclaimer. 
00011  * * Redistributions in binary form must reproduce the above copyright notice, 
00012  * this list of conditions and the following disclaimer in the documentation 
00013  * and/or other materials provided with the distribution. 
00014  * * Neither name of Intel Corporation nor the names of its contributors 
00015  * may be used to endorse or promote products derived from this software 
00016  * without specific prior written permission.
00017  * 
00018  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 
00019  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 
00020  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 
00021  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL INTEL OR 
00022  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, 
00023  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 
00024  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 
00025  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY 
00026  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
00027  * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 
00028  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00029  *
00030  ******************************************************************************/
00031 
00032 
00033 #ifndef LINKED_LIST_H
00034 #define LINKED_LIST_H
00035 
00036 
00042 #include "FreeList.h"
00043 
00044 
00045 #ifdef __cplusplus
00046 extern "C" {
00047 #endif
00048 
00049 
00050 #define EOUTOFMEM (-7 & 1<<29)
00051 
00052 
00053 #define FREELISTSIZE 100
00054 #define LIST_SUCCESS 1
00055 #define LIST_FAIL 0
00056 
00057 
00058 /****************************************************************************
00059  * Name: free_routine
00060  *
00061  *  Description:
00062  *     Function for freeing list items
00063  *****************************************************************************/
00064 typedef void (*free_function)(void *arg);
00065 
00066 
00067 /****************************************************************************
00068  * Name: cmp_routine
00069  *
00070  *  Description:
00071  *     Function for comparing list items
00072  *     Returns 1 if itemA==itemB
00073  *****************************************************************************/
00074 typedef int (*cmp_routine)(void *itemA,void *itemB);
00075 
00076 
00077 /****************************************************************************
00078  * Name: ListNode
00079  *
00080  *  Description:
00081  *      linked list node. stores generic item and pointers to next and prev.
00082  *      Internal Use Only.
00083  *****************************************************************************/
00084 typedef struct LISTNODE
00085 {
00086   struct LISTNODE *prev;
00087   struct LISTNODE *next;
00088   void *item;
00089 } ListNode;
00090 
00091 
00092 /****************************************************************************
00093  * Name: LinkedList
00094  *
00095  *  Description:
00096  *      linked list (no protection). Internal Use Only.
00097  *      Because this is for internal use, parameters are NOT checked for 
00098  *      validity.
00099  *      The first item of the list is stored at node: head->next
00100  *      The last item of the list is stored at node: tail->prev
00101  *      If head->next=tail, then list is empty.
00102  *      To iterate through the list:
00103  *
00104  *       LinkedList g;
00105  *       ListNode *temp = NULL;
00106  *       for (temp = ListHead(g);temp!=NULL;temp = ListNext(g,temp))
00107  *       {
00108  *        }
00109  *
00110  *****************************************************************************/
00111 typedef struct LINKEDLIST
00112 {
00113   ListNode head; /* head, first item is stored at: head->next */
00114   ListNode tail; /* tail, last item is stored at: tail->prev  */
00115   long size;     /* size of list */
00116   FreeList freeNodeList;   /* free list to use */
00117   free_function free_func; /* free function to use */
00118   cmp_routine cmp_func;    /* compare function to use */
00119 } LinkedList;
00120 
00121 
00122 /****************************************************************************
00123  * Function: ListInit
00124  *
00125  *  Description:
00126  *      Initializes LinkedList. Must be called first.
00127  *      And only once for List.
00128  *  Parameters:
00129  *      list  - must be valid, non null, pointer to a linked list.
00130  *      cmp_func - function used to compare items. (May be NULL)
00131  *      free_func - function used to free items. (May be NULL)
00132  *  Returns:
00133  *      0 on success, EOUTOFMEM on failure.
00134  *****************************************************************************/
00135 int ListInit(LinkedList *list,cmp_routine cmp_func, free_function free_func);
00136 
00137 
00138 /****************************************************************************
00139  * Function: ListAddHead
00140  *
00141  *  Description:
00142  *      Adds a node to the head of the list.
00143  *      Node gets immediately after list.head.
00144  *  Parameters:
00145  *      LinkedList *list  - must be valid, non null, pointer to a linked list.
00146  *      void * item - item to be added
00147  *  Returns:
00148  *      The pointer to the ListNode on success, NULL on failure.
00149  *  Precondition:
00150  *      The list has been initialized.
00151  *****************************************************************************/
00152 ListNode *ListAddHead(LinkedList *list, void *item);
00153 
00154 
00155 /****************************************************************************
00156  * Function: ListAddTail
00157  *
00158  *  Description:
00159  *      Adds a node to the tail of the list.
00160  *      Node gets added immediately before list.tail.
00161  *  Parameters:
00162  *      LinkedList *list  - must be valid, non null, pointer to a linked list.
00163  *      void * item - item to be added
00164  *  Returns:
00165  *      The pointer to the ListNode on success, NULL on failure.
00166  *  Precondition:
00167  *      The list has been initialized.
00168  *****************************************************************************/
00169 ListNode *ListAddTail(LinkedList *list, void *item);
00170 
00171 
00172 /****************************************************************************
00173  * Function: ListAddAfter
00174  *
00175  *  Description:
00176  *      Adds a node after the specified node.
00177  *      Node gets added immediately after bnode.
00178  *  Parameters:
00179  *      LinkedList *list  - must be valid, non null, pointer to a linked list.
00180  *      void * item - item to be added
00181  *      ListNode * bnode - node to add after
00182  *  Returns:
00183  *      The pointer to the ListNode on success, NULL on failure.
00184  *  Precondition:
00185  *      The list has been initialized.
00186  *****************************************************************************/
00187 ListNode *ListAddAfter(LinkedList *list, void *item, ListNode *bnode);
00188 
00189 
00190 /****************************************************************************
00191  * Function: ListAddBefore
00192  *
00193  *  Description:
00194  *      Adds a node before the specified node.
00195  *      Node gets added immediately before anode.
00196  *  Parameters:
00197  *      LinkedList *list  - must be valid, non null, pointer to a linked list.
00198  *      ListNode * anode  - node to add the in front of.
00199  *      void * item - item to be added
00200  *  Returns:
00201  *      The pointer to the ListNode on success, NULL on failure.
00202  *  Precondition:
00203  *      The list has been initialized.
00204  *****************************************************************************/
00205 ListNode *ListAddBefore(LinkedList *list,void *item, ListNode *anode);
00206 
00207 
00208 /****************************************************************************
00209  * Function: ListDelNode
00210  *
00211  *  Description:
00212  *      Removes a node from the list
00213  *      The memory for the node is freed.
00214  *  Parameters:
00215  *      LinkedList *list  - must be valid, non null, pointer to a linked list.
00216  *      ListNode *dnode - done to delete.
00217  *      freeItem - if !0 then item is freed using free function.
00218  *                 if 0 (or free function is NULL) then item is not freed
00219  *  Returns:
00220  *      The pointer to the item stored in the node or NULL if the item is freed.
00221  *  Precondition:
00222  *      The list has been initialized.
00223  *****************************************************************************/
00224 void *ListDelNode(LinkedList *list,ListNode *dnode, int freeItem);
00225 
00226 
00227 /****************************************************************************
00228  * Function: ListDestroy
00229  *
00230  *  Description:
00231  *      Removes all memory associated with list nodes. 
00232  *      Does not free LinkedList *list. 
00233  *    
00234  *  Parameters:
00235  *      LinkedList *list  - must be valid, non null, pointer to a linked list.
00236  *      freeItem - if !0 then items are freed using the free_function.
00237  *                 if 0 (or free function is NULL) then items are not freed.
00238  *  Returns:
00239  *      0 on success. Always returns 0.
00240  *  Precondition:
00241  *      The list has been initialized.
00242  *****************************************************************************/
00243 int ListDestroy(LinkedList *list, int freeItem);
00244 
00245 
00246 /****************************************************************************
00247  * Function: ListHead
00248  *
00249  *  Description:
00250  *      Returns the head of the list.
00251  *    
00252  *  Parameters:
00253  *      LinkedList *list  - must be valid, non null, pointer to a linked list.
00254  *  
00255  *  Returns:
00256  *      The head of the list. NULL if list is empty.
00257  *  Precondition:
00258  *      The list has been initialized.
00259  *****************************************************************************/
00260 ListNode* ListHead(LinkedList *list);
00261 
00262 
00263 /****************************************************************************
00264  * Function: ListTail
00265  *
00266  *  Description:
00267  *      Returns the tail of the list.
00268  *    
00269  *  Parameters:
00270  *      LinkedList *list  - must be valid, non null, pointer to a linked list.
00271  *  
00272  *  Returns:
00273  *      The tail of the list. NULL if list is empty.
00274  *  Precondition:
00275  *      The list has been initialized.
00276  *****************************************************************************/
00277 ListNode* ListTail(LinkedList *list);
00278 
00279 
00280 /****************************************************************************
00281  * Function: ListNext
00282  *
00283  *  Description:
00284  *      Returns the next item in the list.
00285  *    
00286  *  Parameters:
00287  *      LinkedList *list  - must be valid, non null, pointer to a linked list.
00288  *  
00289  *  Returns:
00290  *      The next item in the list. NULL if there are no more items in list.
00291  *  Precondition:
00292  *      The list has been initialized.
00293  *****************************************************************************/
00294 ListNode* ListNext(LinkedList *list, ListNode * node);
00295 
00296 
00297 /****************************************************************************
00298  * Function: ListPrev
00299  *
00300  *  Description:
00301  *      Returns the previous item in the list.
00302  *    
00303  *  Parameters:
00304  *      LinkedList *list  - must be valid, non null, pointer to a linked list.
00305  *  
00306  *  Returns:
00307  *      The previous item in the list. NULL if there are no more items in list.
00308  *  Precondition:
00309  *      The list has been initialized.
00310  *****************************************************************************/
00311 ListNode* ListPrev(LinkedList *list, ListNode * node);
00312 
00313 
00314 /****************************************************************************
00315  * Function: ListFind
00316  *
00317  *  Description:
00318  *      Finds the specified item in the list.
00319  *      Uses the compare function specified in ListInit. If compare function
00320  *      is NULL then compares items as pointers.
00321  *  Parameters:
00322  *      LinkedList *list  - must be valid, non null, pointer to a linked list.
00323  *      ListNode *start - the node to start from, NULL if to start from 
00324  *                        beginning.
00325  *      void * item - the item to search for.
00326  *  Returns:
00327  *      The node containing the item. NULL if no node contains the item.
00328  *  Precondition:
00329  *      The list has been initialized.
00330  *****************************************************************************/
00331 ListNode* ListFind(LinkedList *list, ListNode *start, void * item);
00332 
00333 
00334 /****************************************************************************
00335  * Function: ListSize
00336  *
00337  *  Description:
00338  *     Returns the size of the list.
00339  *  Parameters:
00340  *      LinkedList *list  - must be valid, non null, pointer to a linked list.
00341  
00342  *  Returns:
00343  *      The number of items in the list.
00344  *  Precondition:
00345  *      The list has been initialized.
00346  *****************************************************************************/
00347 int ListSize(LinkedList* list);
00348 
00349 
00350 #ifdef __cplusplus
00351 }
00352 #endif
00353 
00354 #endif /* LINKED_LIST_H */
00355