1 /*======================================================================
3 CREATOR: eric November, 1995
6 (C) COPYRIGHT 2000, Eric Busboom <eric@softwarestudio.org>
7 http://www.softwarestudio.org
9 This program is free software; you can redistribute it and/or modify
10 it under the terms of either:
12 The LGPL as published by the Free Software Foundation, version
13 2.1, available at: http://www.fsf.org/copyleft/lesser.html
17 The Mozilla Public License Version 1.0. You may obtain a copy of
18 the License at http://www.mozilla.org/MPL/
20 ======================================================================*/
34 The list structure. This is the hanlde for the entire list
36 This type is also private. Use pvl_list instead
40 typedef struct pvl_list_t
42 int MAGIC; /**< Magic Identifier */
43 struct pvl_elem_t *head; /**< Head of list */
44 struct pvl_elem_t *tail; /**< Tail of list */
45 int count; /**< Number of items in the list */
46 struct pvl_elem_t *p; /**< Pointer used for iterators */
53 * This global is incremented for each call to pvl_new_element(); it gives each
54 * list a unique identifer
57 int pvl_elem_count = 0;
58 int pvl_list_count = 0;
62 * @brief Creates a new list, clears the pointers and assigns a magic number
64 * @return Pointer to the new list, 0 if there is no available memory.
72 if ( ( L = (struct pvl_list_t*)malloc(sizeof(struct pvl_list_t))) == 0)
78 L->MAGIC = pvl_list_count;
91 struct pvl_list_t *L = (struct pvl_list_t *)l;
99 * @brief Creates a new list element, assigns a magic number, and assigns
100 * the next and previous pointers.
102 * Passing in the next and previous points may seem odd, but it allos the user
103 * to set them while keeping the internal data hidden. In nearly all cases,
104 * the user is the pvl library itself.
106 * @param d The data item to be stored in the list
107 * @param next Pointer value to assign to the member "next"
108 * @param prior Pointer value to assign to the member "prior"
110 * @return A pointer to the new element, 0 if there is no memory available.
114 pvl_new_element(void *d, pvl_elem next, pvl_elem prior)
116 struct pvl_elem_t *E;
118 if ( ( E = (struct pvl_elem_t*)malloc(sizeof(struct pvl_elem_t))) == 0)
124 E->MAGIC = pvl_elem_count++;
133 * @brief Add a new element to the from of the list
135 * @param L The list to add the item to
136 * @param d Pointer to the item to add
140 pvl_unshift(pvl_list L,void *d)
142 struct pvl_elem_t *E = pvl_new_element(d,L->head,0);
146 /* Link the head node to it */
153 /* maybe move the tail */
164 * @brief Remove an element from the front of the list
166 * @param L The list to operate on
168 * @return the entry on the front of the list
172 pvl_shift(pvl_list L)
179 return pvl_remove(L,(void*)L->head);
184 * @brief Add a new item to the tail of the list
186 * @param L The list to operate on
187 * @param d Pointer to the item to add
192 pvl_push(pvl_list L,void *d)
194 struct pvl_elem_t *E = pvl_new_element(d,0,L->tail);
196 /* These are done in pvl_new_element
218 * @brief Remove an element from the tail of the list
220 * @param L The list to operate on
231 return pvl_remove(L,(void*) L->tail);;
237 * Add a new item to a list that is ordered by a comparison function.
238 * This routine assumes that the list is properly ordered.
240 * @param L The list to operate on
241 * @param f Pointer to a comparison function
242 * @param d Pointer to data to pass to the comparison function
246 pvl_insert_ordered(pvl_list L,pvl_comparef f,void *d)
248 struct pvl_elem_t *P;
252 /* Empty list, add to head */
260 /* smaller than head, add to head */
262 if ( ((*f)(d,L->head->d)) <= 0)
268 /* larger than tail, add to tail */
269 if ( (*f)(d,L->tail->d) >= 0)
276 /* Search for the first element that is smaller, and add before it */
278 for (P=L->head; P != 0; P = P->next)
280 if ( (*f)(P->d,d) >= 0)
282 pvl_insert_before(L,P,d);
294 * @brief Add a new item after the referenced element.
295 * @param L The list to operate on
296 * @param P The list element to add the item after
297 * @param d Pointer to the item to add.
301 pvl_insert_after(pvl_list L,pvl_elem P,void *d)
303 struct pvl_elem_t *E = 0;
315 E = pvl_new_element(d,0,P);
321 E = pvl_new_element(d,P->next,P);
328 * @brief Add an item after a referenced item
330 * @param L The list to operate on
331 * @param P The list element to add the item before
332 * @param d Pointer to the data to be added.
336 pvl_insert_before(pvl_list L,pvl_elem P,void *d)
338 struct pvl_elem_t *E = 0;
350 E = pvl_new_element(d,P,0);
356 E = pvl_new_element(d,P,P->prior);
363 * @brief Remove the referenced item from the list.
365 * This routine will free the element, but not the data item that the
368 * @param L The list to operate on
369 * @param E The element to remove.
373 pvl_remove(pvl_list L,pvl_elem E)
384 /* E Also points to tail -> only one element in list */
389 else if (E == L->tail)
396 /* E points to the head, so it was the last element */
397 /* This case should be taken care of in the previous clause */
404 E->prior->next = E->next;
405 E->next->prior = E->prior;
424 * @brief Return a pointer to data that satisfies a function.
426 * This routine will interate through the entire list and call the
427 * find function for each item. It will break and return a pointer to the
428 * data that causes the find function to return 1.
430 * @param l The list to operate on
431 * @param f Pointer to the find function
432 * @param v Pointer to constant data to pass into the function
434 * @return Pointer to the element that the find function found.
438 pvl_find(pvl_list l,pvl_findf f,void* v)
442 for (e=pvl_head(l); e!= 0; e = pvl_next(e))
444 if ( (*f)(((struct pvl_elem_t *)e)->d,v) == 1)
446 /* Save this elem for a call to find_next */
447 ((struct pvl_list_t *)l)->p = e;
457 * @brief Like pvl_find(), but continues the search where the last find() or
458 * find_next() left off.
460 * @param l The list to operate on
461 * @param f Pointer to the find function
462 * @param v Pointer to constant data to pass into the function
464 * @return Pointer to the element that the find function found.
468 pvl_find_next(pvl_list l,pvl_findf f,void* v)
473 for (e=pvl_head(l); e!= 0; e = pvl_next(e))
475 if ( (*f)(((struct pvl_elem_t *)e)->d,v) == 1)
477 /* Save this elem for a call to find_next */
478 ((struct pvl_list_t *)l)->p = e;
488 * @brief Remove the all the elements in the list. The does not free
489 * the data items the elements hold.
493 pvl_clear(pvl_list l)
495 pvl_elem e = pvl_head(l);
512 * @brief Returns the number of items in the list.
516 pvl_count(pvl_list L)
523 * @brief Returns a pointer to the given element
533 return (pvl_elem)E->next;
538 * @brief Returns a pointer to the element previous to the element given.
542 pvl_prior(pvl_elem E)
544 return (pvl_elem)E->prior;
549 * @brief Returns a pointer to the first item in the list.
553 pvl_head(pvl_list L )
555 return (pvl_elem)L->head;
559 * @brief Returns a pointer to the last item in the list.
564 return (pvl_elem)L->tail;
567 #ifndef PVL_USE_MACROS
580 * @brief Call a function for every item in the list.
582 * @param l The list to operate on
583 * @param f Pointer to the function to call
584 * @param v Data to pass to the function on every iteration
588 pvl_apply(pvl_list l,pvl_applyf f, void *v)
592 for (e=pvl_head(l); e!= 0; e = pvl_next(e))
594 (*f)(((struct pvl_elem_t *)e)->d,v);