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