1/////////////////////////////////////////////////////////////////////////// 2// 3// Copyright (c) 2000-2003 Intel Corporation 4// All rights reserved. 5// 6// Redistribution and use in source and binary forms, with or without 7// modification, are permitted provided that the following conditions are met: 8// 9// * Redistributions of source code must retain the above copyright notice, 10// this list of conditions and the following disclaimer. 11// * Redistributions in binary form must reproduce the above copyright notice, 12// this list of conditions and the following disclaimer in the documentation 13// and/or other materials provided with the distribution. 14// * Neither name of Intel Corporation nor the names of its contributors 15// may be used to endorse or promote products derived from this software 16// without specific prior written permission. 17// 18// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 19// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 20// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 21// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL INTEL OR 22// CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, 23// EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 24// PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 25// PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY 26// OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 27// NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 28// SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 29// 30/////////////////////////////////////////////////////////////////////////// 31 32#ifndef LINKED_LIST_H 33#define LINKED_LIST_H 34 35#include "FreeList.h" 36 37#ifdef __cplusplus 38extern "C" { 39#endif 40 41#define EOUTOFMEM (-7 & 1<<29) 42 43#define FREELISTSIZE 100 44#define LIST_SUCCESS 1 45#define LIST_FAIL 0 46 47/**************************************************************************** 48 * Name: free_routine 49 * 50 * Description: 51 * Function for freeing list items 52 *****************************************************************************/ 53typedef void (*free_function)(void *arg); 54 55/**************************************************************************** 56 * Name: cmp_routine 57 * 58 * Description: 59 * Function for comparing list items 60 * Returns 1 if itemA==itemB 61 *****************************************************************************/ 62typedef int (*cmp_routine)(void *itemA,void *itemB); 63 64/**************************************************************************** 65 * Name: ListNode 66 * 67 * Description: 68 * linked list node. stores generic item and pointers to next and prev. 69 * Internal Use Only. 70 *****************************************************************************/ 71typedef struct LISTNODE 72{ 73 struct LISTNODE *prev; //previous node 74 struct LISTNODE *next; //next node 75 void *item; //item 76} ListNode; 77 78/**************************************************************************** 79 * Name: LinkedList 80 * 81 * Description: 82 * linked list (no protection). Internal Use Only. 83 * Because this is for internal use, parameters are NOT checked for 84 * validity. 85 * The first item of the list is stored at node: head->next 86 * The last item of the list is stored at node: tail->prev 87 * If head->next=tail, then list is empty. 88 * To iterate through the list: 89 * 90 * LinkedList g; 91 * ListNode *temp = NULL; 92 * for (temp = ListHead(g);temp!=NULL;temp = ListNext(g,temp)) 93 * { 94 * } 95 * 96 *****************************************************************************/ 97typedef struct LINKEDLIST 98{ 99 ListNode head; //head, first item is stored at: head->next 100 ListNode tail; //tail, last item is stored at: tail->prev 101 long size; //size of list 102 FreeList freeNodeList; //free list to use 103 free_function free_func; //free function to use 104 cmp_routine cmp_func; //compare function to use 105} LinkedList; 106 107/**************************************************************************** 108 * Function: ListInit 109 * 110 * Description: 111 * Initializes LinkedList. Must be called first. 112 * And only once for List. 113 * Parameters: 114 * list - must be valid, non null, pointer to a linked list. 115 * cmp_func - function used to compare items. (May be NULL) 116 * free_func - function used to free items. (May be NULL) 117 * Returns: 118 * 0 on success, EOUTOFMEM on failure. 119 *****************************************************************************/ 120int ListInit(LinkedList *list,cmp_routine cmp_func, free_function free_func); 121 122/**************************************************************************** 123 * Function: ListAddHead 124 * 125 * Description: 126 * Adds a node to the head of the list. 127 * Node gets immediately after list.head. 128 * Parameters: 129 * LinkedList *list - must be valid, non null, pointer to a linked list. 130 * void * item - item to be added 131 * Returns: 132 * The pointer to the ListNode on success, NULL on failure. 133 * Precondition: 134 * The list has been initialized. 135 *****************************************************************************/ 136ListNode *ListAddHead(LinkedList *list, void *item); 137 138/**************************************************************************** 139 * Function: ListAddTail 140 * 141 * Description: 142 * Adds a node to the tail of the list. 143 * Node gets added immediately before list.tail. 144 * Parameters: 145 * LinkedList *list - must be valid, non null, pointer to a linked list. 146 * void * item - item to be added 147 * Returns: 148 * The pointer to the ListNode on success, NULL on failure. 149 * Precondition: 150 * The list has been initialized. 151 *****************************************************************************/ 152ListNode *ListAddTail(LinkedList *list, void *item); 153 154/**************************************************************************** 155 * Function: ListAddAfter 156 * 157 * Description: 158 * Adds a node after the specified node. 159 * Node gets added immediately after bnode. 160 * Parameters: 161 * LinkedList *list - must be valid, non null, pointer to a linked list. 162 * void * item - item to be added 163 * ListNode * bnode - node to add after 164 * Returns: 165 * The pointer to the ListNode on success, NULL on failure. 166 * Precondition: 167 * The list has been initialized. 168 *****************************************************************************/ 169ListNode *ListAddAfter(LinkedList *list, void *item, ListNode *bnode); 170 171 172/**************************************************************************** 173 * Function: ListAddBefore 174 * 175 * Description: 176 * Adds a node before the specified node. 177 * Node gets added immediately before anode. 178 * Parameters: 179 * LinkedList *list - must be valid, non null, pointer to a linked list. 180 * ListNode * anode - node to add the in front of. 181 * void * item - item to be added 182 * Returns: 183 * The pointer to the ListNode on success, NULL on failure. 184 * Precondition: 185 * The list has been initialized. 186 *****************************************************************************/ 187ListNode *ListAddBefore(LinkedList *list,void *item, ListNode *anode); 188 189 190/**************************************************************************** 191 * Function: ListDelNode 192 * 193 * Description: 194 * Removes a node from the list 195 * The memory for the node is freed. 196 * Parameters: 197 * LinkedList *list - must be valid, non null, pointer to a linked list. 198 * ListNode *dnode - done to delete. 199 * freeItem - if !0 then item is freed using free function. 200 * if 0 (or free function is NULL) then item is not freed 201 * Returns: 202 * The pointer to the item stored in the node or NULL if the item is freed. 203 * Precondition: 204 * The list has been initialized. 205 *****************************************************************************/ 206void *ListDelNode(LinkedList *list,ListNode *dnode, int freeItem); 207 208/**************************************************************************** 209 * Function: ListDestroy 210 * 211 * Description: 212 * Removes all memory associated with list nodes. 213 * Does not free LinkedList *list. 214 * 215 * Parameters: 216 * LinkedList *list - must be valid, non null, pointer to a linked list. 217 * freeItem - if !0 then items are freed using the free_function. 218 * if 0 (or free function is NULL) then items are not freed. 219 * Returns: 220 * 0 on success. Always returns 0. 221 * Precondition: 222 * The list has been initialized. 223 *****************************************************************************/ 224int ListDestroy(LinkedList *list, int freeItem); 225 226 227/**************************************************************************** 228 * Function: ListHead 229 * 230 * Description: 231 * Returns the head of the list. 232 * 233 * Parameters: 234 * LinkedList *list - must be valid, non null, pointer to a linked list. 235 * 236 * Returns: 237 * The head of the list. NULL if list is empty. 238 * Precondition: 239 * The list has been initialized. 240 *****************************************************************************/ 241ListNode* ListHead(LinkedList *list); 242 243/**************************************************************************** 244 * Function: ListTail 245 * 246 * Description: 247 * Returns the tail of the list. 248 * 249 * Parameters: 250 * LinkedList *list - must be valid, non null, pointer to a linked list. 251 * 252 * Returns: 253 * The tail of the list. NULL if list is empty. 254 * Precondition: 255 * The list has been initialized. 256 *****************************************************************************/ 257ListNode* ListTail(LinkedList *list); 258 259/**************************************************************************** 260 * Function: ListNext 261 * 262 * Description: 263 * Returns the next item in the list. 264 * 265 * Parameters: 266 * LinkedList *list - must be valid, non null, pointer to a linked list. 267 * 268 * Returns: 269 * The next item in the list. NULL if there are no more items in list. 270 * Precondition: 271 * The list has been initialized. 272 *****************************************************************************/ 273ListNode* ListNext(LinkedList *list, ListNode * node); 274 275/**************************************************************************** 276 * Function: ListPrev 277 * 278 * Description: 279 * Returns the previous item in the list. 280 * 281 * Parameters: 282 * LinkedList *list - must be valid, non null, pointer to a linked list. 283 * 284 * Returns: 285 * The previous item in the list. NULL if there are no more items in list. 286 * Precondition: 287 * The list has been initialized. 288 *****************************************************************************/ 289ListNode* ListPrev(LinkedList *list, ListNode * node); 290 291/**************************************************************************** 292 * Function: ListFind 293 * 294 * Description: 295 * Finds the specified item in the list. 296 * Uses the compare function specified in ListInit. If compare function 297 * is NULL then compares items as pointers. 298 * Parameters: 299 * LinkedList *list - must be valid, non null, pointer to a linked list. 300 * ListNode *start - the node to start from, NULL if to start from 301 * beginning. 302 * void * item - the item to search for. 303 * Returns: 304 * The node containing the item. NULL if no node contains the item. 305 * Precondition: 306 * The list has been initialized. 307 *****************************************************************************/ 308ListNode* ListFind(LinkedList *list, ListNode *start, void * item); 309 310/**************************************************************************** 311 * Function: ListSize 312 * 313 * Description: 314 * Returns the size of the list. 315 * Parameters: 316 * LinkedList *list - must be valid, non null, pointer to a linked list. 317 318 * Returns: 319 * The number of items in the list. 320 * Precondition: 321 * The list has been initialized. 322 *****************************************************************************/ 323int ListSize(LinkedList* list); 324 325 326#ifdef __cplusplus 327} 328#endif 329 330#endif //LINKED_LIST_H 331