/* * dlist.h * * Copyright (C) 2003 Eric J Bohm * * This library is free software; you can redistribute it and/or * modify it under the terms of the GNU Lesser General Public * License as published by the Free Software Foundation; either * version 2.1 of the License, or (at your option) any later version. * * This library is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU * Lesser General Public License for more details. * * You should have received a copy of the GNU Lesser General Public * License along with this library; if not, write to the Free Software * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA * */ #ifndef _DLIST_H_ #define _DLIST_H_ /* Double linked list header. * navigate your list with DLIST_PREV and DLIST_NEXT. These are macros * so function call overhead is minimized. * Supports perl style push, pop, shift, unshift list semantics. * You allocate the data and give dlist the pointer. If your data is * complex set the dlist->del_func to a an appropriate delete using * dlist_new_with_delete. Your delete function must match (void * )(del(void *) *Otherwise dlist will just use free. * NOTE: The small amount of pain involved in doing that allows us to * avoid copy in copy out semantics. * Dlist uses an internal mark pointer to keep track of where you are * in the list. * insert and delete take a directional parameter. Where direction * corresponds to the direction in which you want the list to go. * true direction corresponded to progressing forward in the last * false to regressing in the list. * so a dlist_insert(yourlist,item,1) will insert it after the mark * so a dlist_insert(yourlist,item,0) will insert it before the mark * any insert will move the mark to the new node regardless of the direction. * Just use the dlist_(insert|delete)_(before|after) macros if you do not want * to think about it. */ #include <malloc.h> typedef struct dl_node { struct dl_node *prev; struct dl_node *next; void *data; } DL_node; typedef struct dlist { DL_node *marker; unsigned long count; size_t data_size; void (*del_func)(void *); DL_node headnode; DL_node *head; } Dlist; Dlist *dlist_new(size_t datasize); Dlist *dlist_new_with_delete(size_t datasize,void (*del_func)(void*)); void *_dlist_mark_move(Dlist *list,int direction); void *dlist_mark(Dlist *); void dlist_start(Dlist *); void dlist_end(Dlist *); void dlist_move(struct dlist *source, struct dlist *dest, struct dl_node *target,int direction); void *dlist_insert(Dlist *,void *,int) ; void *dlist_insert_sorted(struct dlist *list, void *new_elem, int (*sorter)(void *, void *)); void dlist_delete(Dlist *,int); void dlist_push(Dlist *,void *); void dlist_unshift(Dlist *,void *); void dlist_unshift_sorted(Dlist *,void *,int (*sorter)(void *, void *)); void *dlist_pop(Dlist *); void *dlist_shift(Dlist *); void dlist_destroy(Dlist *); int _dlist_merge(struct dlist *listsource, struct dlist *listdest, unsigned int passcount, int (*compare)(void *, void *)); void *dlist_find_custom(struct dlist *list, void *target, int (*comp)(void *, void *)); void dlist_sort_custom(struct dlist *list, int (*compare)(void *, void *)); void _dlist_swap(struct dlist *list, struct dl_node *a, struct dl_node *b); void dlist_transform(struct dlist *list, void (*node_operation)(void *)); /* * _dlist_remove is for internal use only * _dlist_mark_move is for internal use only */ void *_dlist_remove(struct dlist *,struct dl_node *,int ); void *_dlist_insert_dlnode(struct dlist *list,struct dl_node *new_node,int direction); #define dlist_prev(A) _dlist_mark_move((A),0) #define dlist_next(A) _dlist_mark_move((A),1) #define dlist_insert_before(A,B) dlist_insert((A),(B),0) #define dlist_insert_after(A,B) dlist_insert((A),(B),1) #define dlist_delete_before(A) dlist_delete((A),0) #define dlist_delete_after(A) dlist_delete((A),1) /** * provide for loop header which iterates the mark from start to end * list: the dlist pointer, use dlist_mark(list) to get iterator */ #define dlist_for_each(list) \ for(dlist_start(list),dlist_next(list); \ (list)->marker!=(list)->head;dlist_next(list)) /** * provide for loop header which iterates the mark from end to start * list: the dlist pointer, use dlist_mark(list) to get iterator */ #define dlist_for_each_rev(list) \ for(dlist_end(list),dlist_prev(list); \ (list)->marker!=(list)->head;dlist_prev(list)) /** * provide for loop header which iterates through the list without moving mark * list: the dlist_pointer * iterator: dl_node pointer to iterate */ #define dlist_for_each_nomark(list,iterator) \ for((iterator)=(list)->head->next; (iterator)!=(list)->head; \ (iterator)=(iterator)->next) /** * provide for loop header which iterates through the list without moving mark * in reverse * list: the dlist_pointer * iterator: dl_node pointer to iterate */ #define dlist_for_each_nomark_rev(list,iterator) \ for((iterator)=(list)->head->prev; (iterator)!=(list)->head; \ (iterator)=(iterator)->prev) /** * provide for loop header which iterates through the list providing a * data iterator * list: the dlist pointer * data_iterator: the pointer of type datatype to iterate * datatype: actual type of the contents in the dl_node->data */ #define dlist_for_each_data(list,data_iterator,datatype) \ for(dlist_start(list), (data_iterator)=(datatype *) dlist_next(list); \ (list)->marker!=(list)->head;(data_iterator)=(datatype *) dlist_next(list)) /** * provide for loop header which iterates through the list providing a * data iterator in reverse * list: the dlist pointer * data_iterator: the pointer of type datatype to iterate * datatype: actual type of the contents in the dl_node->data */ #define dlist_for_each_data_rev(list,data_iterator,datatype) \ for(dlist_end(list), (data_iterator)=(datatype *) dlist_prev(list); \ (list)->marker!=(list)->head;(data_iterator)=(datatype *) dlist_prev(list)) /** * provide for loop header which iterates through the list providing a * data iterator without moving the mark * list: the dlist pointer * iterator: the dl_node pointer to iterate * data_iterator: the pointer of type datatype to iterate * datatype: actual type of the contents in the dl_node->data */ #define dlist_for_each_data_nomark(list,iterator,data_iterator,datatype) \ for((iterator)=(list)->head->next, (data_iterator)=(datatype *) (iterator)->data; \ (iterator)!=(list)->head;(iterator)=(iterator)->next,(data_iterator)=(datatype *) (iterator)) /** * provide for loop header which iterates through the list providing a * data iterator in reverse without moving the mark * list: the dlist pointer * iterator: the dl_node pointer to iterate * data_iterator: the pointer of type datatype to iterate * datatype: actual type of the contents in the dl_node->data */ #define dlist_for_each_data_nomark_rev(list,iterator, data_iterator,datatype) \ for((iterator)=(list)->head->prev, (data_iterator)=(datatype *) (iterator)->data; \ (iterator)!=(list)->head;(iterator)=(iterator)->prev,(data_iterator)=(datatype *) (iterator)) #endif /* _DLIST_H_ */