libUPnP  1.8.0
LinkedList.h
Go to the documentation of this file.
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 
33 #ifndef LINKED_LIST_H
34 #define LINKED_LIST_H
35 
36 
42 #include "FreeList.h"
43 
44 
45 #ifdef __cplusplus
46 extern "C" {
47 #endif
48 
49 
50 #define EOUTOFMEM (-7 & 1<<29)
51 
52 
53 #define FREELISTSIZE 100
54 #define LIST_SUCCESS 1
55 #define LIST_FAIL 0
56 
57 
58 /****************************************************************************
59  * Name: free_routine
60  *
61  * Description:
62  * Function for freeing list items
63  *****************************************************************************/
64 typedef void (*free_function)(void *arg);
65 
66 
67 /****************************************************************************
68  * Name: cmp_routine
69  *
70  * Description:
71  * Function for comparing list items
72  * Returns 1 if itemA==itemB
73  *****************************************************************************/
74 typedef int (*cmp_routine)(void *itemA,void *itemB);
75 
76 
77 /****************************************************************************
78  * Name: ListNode
79  *
80  * Description:
81  * linked list node. stores generic item and pointers to next and prev.
82  * Internal Use Only.
83  *****************************************************************************/
84 typedef struct LISTNODE
85 {
86  struct LISTNODE *prev;
87  struct LISTNODE *next;
88  void *item;
89 } ListNode;
90 
91 
92 /****************************************************************************
93  * Name: LinkedList
94  *
95  * Description:
96  * linked list (no protection). Internal Use Only.
97  * Because this is for internal use, parameters are NOT checked for
98  * validity.
99  * The first item of the list is stored at node: head->next
100  * The last item of the list is stored at node: tail->prev
101  * If head->next=tail, then list is empty.
102  * To iterate through the list:
103  *
104  * LinkedList g;
105  * ListNode *temp = NULL;
106  * for (temp = ListHead(g);temp!=NULL;temp = ListNext(g,temp))
107  * {
108  * }
109  *
110  *****************************************************************************/
111 typedef struct LINKEDLIST
112 {
113  ListNode head; /* head, first item is stored at: head->next */
114  ListNode tail; /* tail, last item is stored at: tail->prev */
115  long size; /* size of list */
116  FreeList freeNodeList; /* free list to use */
117  free_function free_func; /* free function to use */
118  cmp_routine cmp_func; /* compare function to use */
119 } LinkedList;
120 
121 
122 /****************************************************************************
123  * Function: ListInit
124  *
125  * Description:
126  * Initializes LinkedList. Must be called first.
127  * And only once for List.
128  * Parameters:
129  * list - must be valid, non null, pointer to a linked list.
130  * cmp_func - function used to compare items. (May be NULL)
131  * free_func - function used to free items. (May be NULL)
132  * Returns:
133  * 0 on success, EOUTOFMEM on failure.
134  *****************************************************************************/
135 int ListInit(LinkedList *list,cmp_routine cmp_func, free_function free_func);
136 
137 
138 /****************************************************************************
139  * Function: ListAddHead
140  *
141  * Description:
142  * Adds a node to the head of the list.
143  * Node gets immediately after list.head.
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  *****************************************************************************/
152 ListNode *ListAddHead(LinkedList *list, void *item);
153 
154 
155 /****************************************************************************
156  * Function: ListAddTail
157  *
158  * Description:
159  * Adds a node to the tail of the list.
160  * Node gets added immediately before list.tail.
161  * Parameters:
162  * LinkedList *list - must be valid, non null, pointer to a linked list.
163  * void * item - item to be added
164  * Returns:
165  * The pointer to the ListNode on success, NULL on failure.
166  * Precondition:
167  * The list has been initialized.
168  *****************************************************************************/
169 ListNode *ListAddTail(LinkedList *list, void *item);
170 
171 
172 /****************************************************************************
173  * Function: ListAddAfter
174  *
175  * Description:
176  * Adds a node after the specified node.
177  * Node gets added immediately after bnode.
178  * Parameters:
179  * LinkedList *list - must be valid, non null, pointer to a linked list.
180  * void * item - item to be added
181  * ListNode * bnode - node to add after
182  * Returns:
183  * The pointer to the ListNode on success, NULL on failure.
184  * Precondition:
185  * The list has been initialized.
186  *****************************************************************************/
187 ListNode *ListAddAfter(LinkedList *list, void *item, ListNode *bnode);
188 
189 
190 /****************************************************************************
191  * Function: ListAddBefore
192  *
193  * Description:
194  * Adds a node before the specified node.
195  * Node gets added immediately before anode.
196  * Parameters:
197  * LinkedList *list - must be valid, non null, pointer to a linked list.
198  * ListNode * anode - node to add the in front of.
199  * void * item - item to be added
200  * Returns:
201  * The pointer to the ListNode on success, NULL on failure.
202  * Precondition:
203  * The list has been initialized.
204  *****************************************************************************/
205 ListNode *ListAddBefore(LinkedList *list,void *item, ListNode *anode);
206 
207 
208 /****************************************************************************
209  * Function: ListDelNode
210  *
211  * Description:
212  * Removes a node from the list
213  * The memory for the node is freed.
214  * Parameters:
215  * LinkedList *list - must be valid, non null, pointer to a linked list.
216  * ListNode *dnode - done to delete.
217  * freeItem - if !0 then item is freed using free function.
218  * if 0 (or free function is NULL) then item is not freed
219  * Returns:
220  * The pointer to the item stored in the node or NULL if the item is freed.
221  * Precondition:
222  * The list has been initialized.
223  *****************************************************************************/
224 void *ListDelNode(LinkedList *list,ListNode *dnode, int freeItem);
225 
226 
227 /****************************************************************************
228  * Function: ListDestroy
229  *
230  * Description:
231  * Removes all memory associated with list nodes.
232  * Does not free LinkedList *list.
233  *
234  * Parameters:
235  * LinkedList *list - must be valid, non null, pointer to a linked list.
236  * freeItem - if !0 then items are freed using the free_function.
237  * if 0 (or free function is NULL) then items are not freed.
238  * Returns:
239  * 0 on success. Always returns 0.
240  * Precondition:
241  * The list has been initialized.
242  *****************************************************************************/
243 int ListDestroy(LinkedList *list, int freeItem);
244 
245 
246 /****************************************************************************
247  * Function: ListHead
248  *
249  * Description:
250  * Returns the head of the list.
251  *
252  * Parameters:
253  * LinkedList *list - must be valid, non null, pointer to a linked list.
254  *
255  * Returns:
256  * The head of the list. NULL if list is empty.
257  * Precondition:
258  * The list has been initialized.
259  *****************************************************************************/
260 ListNode* ListHead(LinkedList *list);
261 
262 
263 /****************************************************************************
264  * Function: ListTail
265  *
266  * Description:
267  * Returns the tail of the list.
268  *
269  * Parameters:
270  * LinkedList *list - must be valid, non null, pointer to a linked list.
271  *
272  * Returns:
273  * The tail of the list. NULL if list is empty.
274  * Precondition:
275  * The list has been initialized.
276  *****************************************************************************/
277 ListNode* ListTail(LinkedList *list);
278 
279 
280 /****************************************************************************
281  * Function: ListNext
282  *
283  * Description:
284  * Returns the next item in the list.
285  *
286  * Parameters:
287  * LinkedList *list - must be valid, non null, pointer to a linked list.
288  *
289  * Returns:
290  * The next item in the list. NULL if there are no more items in list.
291  * Precondition:
292  * The list has been initialized.
293  *****************************************************************************/
294 ListNode* ListNext(LinkedList *list, ListNode * node);
295 
296 
297 /****************************************************************************
298  * Function: ListPrev
299  *
300  * Description:
301  * Returns the previous item in the list.
302  *
303  * Parameters:
304  * LinkedList *list - must be valid, non null, pointer to a linked list.
305  *
306  * Returns:
307  * The previous item in the list. NULL if there are no more items in list.
308  * Precondition:
309  * The list has been initialized.
310  *****************************************************************************/
311 ListNode* ListPrev(LinkedList *list, ListNode * node);
312 
313 
314 /****************************************************************************
315  * Function: ListFind
316  *
317  * Description:
318  * Finds the specified item in the list.
319  * Uses the compare function specified in ListInit. If compare function
320  * is NULL then compares items as pointers.
321  * Parameters:
322  * LinkedList *list - must be valid, non null, pointer to a linked list.
323  * ListNode *start - the node to start from, NULL if to start from
324  * beginning.
325  * void * item - the item to search for.
326  * Returns:
327  * The node containing the item. NULL if no node contains the item.
328  * Precondition:
329  * The list has been initialized.
330  *****************************************************************************/
331 ListNode* ListFind(LinkedList *list, ListNode *start, void * item);
332 
333 
334 /****************************************************************************
335  * Function: ListSize
336  *
337  * Description:
338  * Returns the size of the list.
339  * Parameters:
340  * LinkedList *list - must be valid, non null, pointer to a linked list.
341 
342  * Returns:
343  * The number of items in the list.
344  * Precondition:
345  * The list has been initialized.
346  *****************************************************************************/
347 int ListSize(LinkedList* list);
348 
349 
350 #ifdef __cplusplus
351 }
352 #endif
353 
354 #endif /* LINKED_LIST_H */
355 
Definition: LinkedList.h:84
Definition: FreeList.h:73
Definition: LinkedList.h:111