1 /***************************************************************************
2  $RCSfile$
3                              -------------------
4     cvs         : $Id$
5     begin       : Sat Nov 15 2003
6     copyright   : (C) 2003 by Martin Preuss
7     email       : martin@libchipcard.de
8 
9  ***************************************************************************
10  *                                                                         *
11  *   This library is free software; you can redistribute it and/or         *
12  *   modify it under the terms of the GNU Lesser General Public            *
13  *   License as published by the Free Software Foundation; either          *
14  *   version 2.1 of the License, or (at your option) any later version.    *
15  *                                                                         *
16  *   This library is distributed in the hope that it will be useful,       *
17  *   but WITHOUT ANY WARRANTY; without even the implied warranty of        *
18  *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU     *
19  *   Lesser General Public License for more details.                       *
20  *                                                                         *
21  *   You should have received a copy of the GNU Lesser General Public      *
22  *   License along with this library; if not, write to the Free Software   *
23  *   Foundation, Inc., 59 Temple Place, Suite 330, Boston,                 *
24  *   MA  02111-1307  USA                                                   *
25  *                                                                         *
26  ***************************************************************************/
27 
28 
29 #ifndef GWENHYWFAR_LIST_H
30 #define GWENHYWFAR_LIST_H
31 
32 
33 #ifdef __cplusplus
34 extern "C" {
35 #endif
36 
37 #include <gwenhywfar/gwenhywfarapi.h>
38 #include <gwenhywfar/inherit.h>
39 #include <gwenhywfar/refptr.h>
40 /* This is needed for PalmOS, because it define some functions needed */
41 #include <string.h>
42 #include <stdio.h>
43 
44 
45 /** @defgroup GWEN_LIST Generic List Handling
46  *  @ingroup MOD_BASE
47  * The macros of this group facilitates typesafe use of lists.
48  */
49 /*@{*/
50 
51 /** @brief Doubly-linked list.
52  *
53  * The list contains pointer to data objects, with the ability to
54  * iterate over the list in both directions. */
55 typedef struct GWEN_LIST GWEN_LIST;
56 
57 /** Callback function for one list element. */
58 typedef void *(*GWEN_LIST_FOREACH_CB)(void *element, void *user_data);
59 
60 /** @brief Doubly-linked list with const objects.
61  *
62  * The list contains pointer to const data objects, with the ability
63  * to iterate over the list in both directions. */
64 typedef struct GWEN_LIST GWEN_CONSTLIST;
65 
66 /** Callback function for one const list element. */
67 typedef const void *(*GWEN_CONSTLIST_FOREACH_CB)(const void *element,
68                                                  void *user_data);
69 
70 /** An iterator for the doubly-linked list, i.e. a pointer to a
71     specific element */
72 typedef struct GWEN_LIST_ITERATOR GWEN_LIST_ITERATOR;
73 
74 /** An iterator for the const doubly-linked list, i.e. a pointer to a
75     specific element */
76 typedef struct GWEN_LIST_ITERATOR GWEN_CONSTLIST_ITERATOR;
77 
78 
79 /** allow inheriting of lists */
80 GWEN_INHERIT_FUNCTION_LIB_DEFS(GWEN_LIST, GWENHYWFAR_API)
81 
82 
83 /** Constructor. Returns a new empty list. */
84 GWENHYWFAR_API
85 GWEN_LIST *GWEN_List_new(void);
86 
87 /** Destructor. Frees all of the memory used by this list. The list
88  * elements are not freed. */
89 GWENHYWFAR_API
90 void GWEN_List_free(GWEN_LIST *l);
91 
92 /** Duplicates a list by returning a reference and using
93  * reference-counting. */
94 GWENHYWFAR_API
95 GWEN_LIST *GWEN_List_dup(const GWEN_LIST *l);
96 
97 
98 GWENHYWFAR_API
99 void GWEN_List_Unshare(GWEN_LIST *l);
100 
101 
102 /**
103  * Dumps the contents of the list to an open file (e.g. stderr).
104  */
105 GWENHYWFAR_API
106 void GWEN_List_Dump(const GWEN_LIST *l, FILE *f, unsigned int indent);
107 
108 /**
109  * Appends an element to a list, making it the new last element.
110  */
111 GWENHYWFAR_API
112 void GWEN_List_PushBack(GWEN_LIST *l, void *p);
113 
114 /**
115  * Appends an element to a list, making it the new last element.
116  */
117 GWENHYWFAR_API
118 void GWEN_List_PushBackRefPtr(GWEN_LIST *l, GWEN_REFPTR *rp);
119 
120 /**
121  * Inserts an element at the start of the list, making it the new
122  * first element.
123  */
124 GWENHYWFAR_API
125 void GWEN_List_PushFront(GWEN_LIST *l, void *p);
126 
127 /**
128  * Inserts an element at the start of the list, making it the new
129  * first element.
130  */
131 GWENHYWFAR_API
132 void GWEN_List_PushFrontRefPtr(GWEN_LIST *l, GWEN_REFPTR *rp);
133 
134 /**
135  * Returns the first element of the list. (The element is not
136  * removed from the list.)
137  */
138 GWENHYWFAR_API
139 void *GWEN_List_GetFront(const GWEN_LIST *l);
140 
141 /**
142  * Returns the first element of the list. (The element is not
143  * removed from the list.)
144  */
145 GWENHYWFAR_API
146 GWEN_REFPTR *GWEN_List_GetFrontRefPtr(const GWEN_LIST *l);
147 
148 /**
149  * Returns the last element of the list. (The element is not
150  * removed from the list.)
151  */
152 GWENHYWFAR_API
153 void *GWEN_List_GetBack(const GWEN_LIST *l);
154 
155 /**
156  * Returns the last element of the list. (The element is not
157  * removed from the list.)
158  */
159 GWENHYWFAR_API
160 GWEN_REFPTR *GWEN_List_GetBackRefPtr(const GWEN_LIST *l);
161 
162 /**
163  * Removes the element currently pointed to by the given iterator
164  * from the list. (The element is not freed.)
165  * The given iterator is move toward the next element in any case (if there
166  * is no next element then the iterator will point to 0).
167  */
168 GWENHYWFAR_API
169 void GWEN_List_Erase(GWEN_LIST *l, GWEN_LIST_ITERATOR *it);
170 
171 /**
172  * Searches for the first occurrence of the "element" pointer and
173  * erases that element from the list. (The element itself is not
174  * freed.) I.e. this function calls GWEN_List_Erase on the first
175  * occurrence found of "element".
176  */
177 GWENHYWFAR_API
178 void GWEN_List_Remove(GWEN_LIST *l, const void *element);
179 
180 
181 /** Returns the size of this list, i.e. the number of elements in this
182  * list.
183  *
184  * This number is counted in the list metadata, so this is a cheap
185  * operation. */
186 GWENHYWFAR_API
187 unsigned int GWEN_List_GetSize(const GWEN_LIST *l);
188 
189 /** Returns nonzero (TRUE) if this list is empty, and zero (FALSE) if
190  * this list is not empty. */
191 GWENHYWFAR_API
192 int GWEN_List_IsEmpty(const GWEN_LIST *l);
193 
194 GWENHYWFAR_API
195 GWEN_REFPTR_INFO *GWEN_List_GetRefPtrInfo(const GWEN_LIST *l);
196 
197 GWENHYWFAR_API
198 void GWEN_List_SetRefPtrInfo(GWEN_LIST *l, GWEN_REFPTR_INFO *rpi);
199 
200 /**
201  * Removes the list's last element from the list. (The element is not
202  * freed.)
203  */
204 GWENHYWFAR_API
205 void GWEN_List_PopBack(GWEN_LIST *l);
206 
207 /**
208  * Removes the list's first element from the list. (The element is not
209  * freed.)
210  */
211 GWENHYWFAR_API
212 void GWEN_List_PopFront(GWEN_LIST *l);
213 
214 /**
215  * Removes all list elements from the list. The elements are not
216  * freed.
217  */
218 GWENHYWFAR_API
219 void GWEN_List_Clear(GWEN_LIST *l);
220 
221 /**
222  * Finds the LIST_ITERATOR position of the given element. The
223  * returned LIST_ITERATOR will be owned by the caller and must be
224  * freed when no longer in use. If the list does not contain the
225  * element, NULL will be returned.
226  */
227 GWENHYWFAR_API
228 GWEN_LIST_ITERATOR *GWEN_List_FindIter(GWEN_LIST *l, const void *element);
229 
230 /**
231  * Searches whether the list contains the given element. If it does,
232  * the pointer to the element is returned. Otherwise, NULL is
233  * returned.
234  */
235 GWENHYWFAR_API
236 const void *GWEN_List_Contains(GWEN_LIST *l, const void *element);
237 
238 /** Traverses the list, calling the callback function 'func' on
239  * each list element.  Traversal will stop when 'func' returns a
240  * non-NULL value, and the routine will return with that
241  * value. Otherwise the routine will return NULL.
242  *
243  * @param list The list to traverse.
244  * @param func The function to be called with each list element.
245  * @param user_data A pointer passed on to the function 'func'.
246  * @return The non-NULL pointer returned by 'func' as soon as it
247  * returns one. Otherwise (i.e. 'func' always returns NULL)
248  * returns NULL.
249  */
250 GWENHYWFAR_API
251 void *GWEN_List_ForEach(GWEN_LIST *list, GWEN_LIST_FOREACH_CB func,
252                         void *user_data);
253 
254 /** Return an iterator pointing to the first element in the list */
255 GWENHYWFAR_API
256 GWEN_LIST_ITERATOR *GWEN_List_First(const GWEN_LIST *l);
257 
258 /** Returns an iterator pointing to the last element in the list. */
259 GWENHYWFAR_API
260 GWEN_LIST_ITERATOR *GWEN_List_Last(const GWEN_LIST *l);
261 
262 /**
263  * Creates a list iterator for the given list.
264  */
265 GWENHYWFAR_API
266 GWEN_LIST_ITERATOR *GWEN_ListIterator_new(const GWEN_LIST *l);
267 
268 /** Frees a list iterator. */
269 GWENHYWFAR_API
270 void GWEN_ListIterator_free(GWEN_LIST_ITERATOR *li);
271 
272 /**
273  * Moves the list iterator to the predecessor of the currenty selected
274  * element and returns that predecessor element.
275  */
276 GWENHYWFAR_API
277 void *GWEN_ListIterator_Previous(GWEN_LIST_ITERATOR *li);
278 
279 /**
280  * Moves the list iterator to the predecessor of the currenty selected
281  * element and returns that predecessor element.
282  */
283 GWENHYWFAR_API
284 GWEN_REFPTR *GWEN_ListIterator_PreviousRefPtr(GWEN_LIST_ITERATOR *li);
285 
286 /**
287  * Moves the list iterator to the successor of the currenty selected
288  * element and returns that successor element.
289  */
290 GWENHYWFAR_API
291 void *GWEN_ListIterator_Next(GWEN_LIST_ITERATOR *li);
292 
293 /**
294  * Moves the list iterator to the successor of the currenty selected
295  * element and returns that successor element.
296  */
297 GWENHYWFAR_API
298 GWEN_REFPTR *GWEN_ListIterator_NextRefPtr(GWEN_LIST_ITERATOR *li);
299 
300 /**
301  * Returns the pointer to the element stored at the list position the
302  * iterator currently points to.
303  */
304 GWENHYWFAR_API
305 void *GWEN_ListIterator_Data(GWEN_LIST_ITERATOR *li);
306 
307 /**
308  * Returns the pointer to the element stored at the list position the
309  * iterator currently points to.
310  */
311 GWENHYWFAR_API
312 GWEN_REFPTR *GWEN_ListIterator_DataRefPtr(GWEN_LIST_ITERATOR *li);
313 
314 GWENHYWFAR_API
315 void GWEN_ListIterator_IncLinkCount(GWEN_LIST_ITERATOR *li);
316 
317 GWENHYWFAR_API
318 unsigned int GWEN_ListIterator_GetLinkCount(const GWEN_LIST_ITERATOR *li);
319 
320 
321 
322 
323 /** Constructor. Returns a new empty list. */
324 GWENHYWFAR_API
325 GWEN_CONSTLIST *GWEN_ConstList_new(void);
326 
327 /** Destructor. Frees all of the memory used by this list. The list
328  * elements are not freed
329  */
330 GWENHYWFAR_API
331 void GWEN_ConstList_free(GWEN_CONSTLIST *l);
332 
333 /**
334  * Appends an element to a list, making it the new last element.
335  */
336 GWENHYWFAR_API
337 void GWEN_ConstList_PushBack(GWEN_CONSTLIST *l, const void *p);
338 
339 /**
340  * Inserts an element at the start of the list, making it the new
341  * first element.
342  */
343 GWENHYWFAR_API
344 void GWEN_ConstList_PushFront(GWEN_CONSTLIST *l, const void *p);
345 
346 /**
347  * Returns the first element of the list. (The element is not
348  * removed from the list.)
349  */
350 GWENHYWFAR_API
351 const void *GWEN_ConstList_GetFront(const GWEN_CONSTLIST *l);
352 
353 /**
354  * Returns the last element of the list. (The element is not
355  * removed from the list.)
356  */
357 GWENHYWFAR_API
358 const void *GWEN_ConstList_GetBack(const GWEN_CONSTLIST *l);
359 
360 /** Returns the size of this list, i.e. the number of elements in this
361  * list.
362  *
363  * This number is counted in the list metadata, so this is a cheap
364  * operation. */
365 GWENHYWFAR_API
366 unsigned int GWEN_ConstList_GetSize(const GWEN_CONSTLIST *l);
367 
368 /** Returns nonzero (TRUE) if this list is empty, and zero (FALSE) if
369  * this list is not empty. */
370 GWENHYWFAR_API
371 int GWEN_ConstList_IsEmpty(const GWEN_LIST *l);
372 
373 /**
374  * Removes the list's last element from the list. (The element is not
375  * freed.)
376  */
377 GWENHYWFAR_API
378 void GWEN_ConstList_PopBack(GWEN_CONSTLIST *l);
379 
380 /**
381  * Removes the list's first element from the list. (The element is not
382  * freed.)
383  */
384 GWENHYWFAR_API
385 void GWEN_ConstList_PopFront(GWEN_CONSTLIST *l);
386 
387 /**
388  * Removes all list elements from the list. The elements are not
389  * freed.
390  */
391 GWENHYWFAR_API
392 void GWEN_ConstList_Clear(GWEN_CONSTLIST *l);
393 
394 /** Traverses the list, calling the callback function 'func' on
395  * each list element.  Traversal will stop when 'func' returns a
396  * non-NULL value, and the routine will return with that
397  * value. Otherwise the routine will return NULL.
398  *
399  * @param list The list to traverse.
400  * @param func The function to be called with each list element.
401  * @param user_data A pointer passed on to the function 'func'.
402  * @return The non-NULL pointer returned by 'func' as soon as it
403  * returns one. Otherwise (i.e. 'func' always returns NULL)
404  * returns NULL.
405  */
406 GWENHYWFAR_API
407 const void *GWEN_ConstList_ForEach(GWEN_CONSTLIST *list,
408                                    GWEN_CONSTLIST_FOREACH_CB func,
409                                    void *user_data);
410 
411 /**
412  * Finds the LIST_ITERATOR position of the given element. The
413  * returned LIST_ITERATOR will be owned by the caller and must be
414  * freed when no longer in use. If the list does not contain the
415  * element, NULL will be returned.
416  */
417 GWENHYWFAR_API
418 GWEN_CONSTLIST_ITERATOR *GWEN_ConstList_FindIter(const GWEN_CONSTLIST *l, const void *element);
419 
420 /**
421  * Searches whether the list contains the given element. If it does,
422  * the pointer to the element is returned. Otherwise, NULL is
423  * returned.
424  */
425 GWENHYWFAR_API
426 const void *GWEN_ConstList_Contains(const GWEN_CONSTLIST *l, const void *element);
427 
428 
429 /**
430  * Removes the element currently pointed to by the given iterator
431  * from the list. (The element is not freed.)
432  * The given iterator is move toward the next element in any case (if there
433  * is no next element then the iterator will point to 0).
434  */
435 GWENHYWFAR_API
436 void GWEN_ConstList_Erase(GWEN_CONSTLIST *l, GWEN_CONSTLIST_ITERATOR *it);
437 
438 /**
439  * Searches for the first occurrence of the "element" pointer and
440  * erases that element from the list. (The element itself is not
441  * freed.) I.e. this function calls GWEN_List_Erase on the first
442  * occurrence found of "element".
443  */
444 GWENHYWFAR_API
445 void GWEN_ConstList_Remove(GWEN_CONSTLIST *l, const void *element);
446 
447 /** Return an iterator pointing to the first element in the list */
448 GWENHYWFAR_API
449 GWEN_CONSTLIST_ITERATOR *GWEN_ConstList_First(const GWEN_CONSTLIST *l);
450 
451 /** Returns an iterator pointing to the last element in the list. */
452 GWENHYWFAR_API
453 GWEN_CONSTLIST_ITERATOR *GWEN_ConstList_Last(const GWEN_CONSTLIST *l);
454 
455 /**
456  * Creates a list iterator for the given list.
457  */
458 GWENHYWFAR_API
459 GWEN_CONSTLIST_ITERATOR *GWEN_ConstListIterator_new(const GWEN_CONSTLIST *l);
460 
461 /** Frees a list iterator. */
462 GWENHYWFAR_API
463 void GWEN_ConstListIterator_free(GWEN_CONSTLIST_ITERATOR *li);
464 
465 /**
466  * Moves the list iterator to the predecessor of the currenty selected
467  * element and returns that predecessor element.
468  */
469 GWENHYWFAR_API
470 const void *GWEN_ConstListIterator_Previous(GWEN_CONSTLIST_ITERATOR *li);
471 
472 /**
473  * Moves the list iterator to the successor of the currenty selected
474  * element and returns that successor element.
475  */
476 GWENHYWFAR_API
477 const void *GWEN_ConstListIterator_Next(GWEN_CONSTLIST_ITERATOR *li);
478 
479 /**
480  * Returns the pointer to the element stored at the list position the
481  * iterator currently points to.
482  */
483 GWENHYWFAR_API
484 const void *GWEN_ConstListIterator_Data(GWEN_CONSTLIST_ITERATOR *li);
485 
486 
487 
488 /*@}*/ /* defgroup */
489 
490 
491 #ifdef __cplusplus
492 }
493 #endif
494 
495 
496 #endif
497 
498 
499 
500