summaryrefslogtreecommitdiff
path: root/lib/dlist.c
diff options
context:
space:
mode:
Diffstat (limited to 'lib/dlist.c')
-rw-r--r--lib/dlist.c620
1 files changed, 620 insertions, 0 deletions
diff --git a/lib/dlist.c b/lib/dlist.c
new file mode 100644
index 0000000..c4ee324
--- /dev/null
+++ b/lib/dlist.c
@@ -0,0 +1,620 @@
+/*
+ * dlist.c
+ *
+ * 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 021110307 USA
+ *
+ */
+
+
+/* Double linked list implementation.
+
+ * You allocate the data and give dlist the pointer.
+ * If your data is complex set the dlist->del_func to a an appropriate
+ * delete function. Otherwise dlist will just use free.
+
+*/
+#include "dlist.h"
+
+/*
+ * Return pointer to node at marker.
+ * else null if no nodes.
+ */
+
+inline void *dlist_mark(Dlist *list)
+{
+ if(list->marker!=NULL)
+ return(list->marker->data);
+ else
+ return(NULL);
+}
+
+/*
+ * Set marker to start.
+ */
+
+inline void dlist_start(Dlist *list)
+{
+ list->marker=list->head;
+}
+
+/*
+ * Set marker to end.
+ */
+
+inline void dlist_end(Dlist *list)
+{
+ list->marker=list->head;
+}
+
+/* internal use function
+ * quickie inline to consolidate the marker movement logic
+ * in one place
+ *
+ * when direction true it moves marker after
+ * when direction false it moves marker before.
+ * return pointer to data at new marker
+ * if nowhere to move the marker in desired direction return null
+ */
+inline void *_dlist_mark_move(Dlist *list,int direction)
+{
+ if(direction)
+ {
+ if( list->marker && list->marker->next!=NULL)
+ list->marker=list->marker->next;
+ else
+ return(NULL);
+ }
+ else
+ {
+ if( list->marker && list->marker->prev!=NULL)
+ list->marker=list->marker->prev;
+ else
+ return(NULL);
+ }
+ if(list->marker!=list->head)
+ return(list->marker->data);
+ else
+ return(NULL);
+}
+
+/*
+ * Create new linked list to store nodes of datasize.
+ * return null if list cannot be created.
+ */
+Dlist *dlist_new(size_t datasize)
+{
+ Dlist *list=NULL;
+ if((list=malloc(sizeof(Dlist))))
+ {
+ list->marker=NULL;
+ list->count=0L;
+ list->data_size=datasize;
+ list->del_func=free;
+ list->head=&(list->headnode);
+ list->head->prev=NULL;
+ list->head->next=NULL;
+ list->head->data=NULL;
+ }
+ return(list);
+}
+
+/*
+ * Create new linked list to store nodes of datasize set list
+ * data node delete function to the passed in del_func
+ * return null if list cannot be created.
+ */
+Dlist *dlist_new_with_delete(size_t datasize,void (*del_func)(void*))
+{
+ Dlist *list=NULL;
+ list=dlist_new(datasize);
+ if(list!=NULL)
+ list->del_func=del_func;
+ return(list);
+}
+
+
+/*
+ * remove marker node from list
+ * call data_delete function on data if registered.
+ * otherwise call free.
+ * when direction true it moves marker after
+ * when direction false it moves marker before.
+ * free marker node
+ * return nothing.
+ */
+void dlist_delete(Dlist *list,int direction)
+{
+ if((list->marker != list->head)&&(list->marker!=NULL))
+ {
+ DL_node *corpse;
+ corpse=list->marker;
+ _dlist_mark_move(list,direction);
+ if(list->head->next==corpse)
+ list->head->next=corpse->next;
+ if(list->head->prev==corpse)
+ list->head->prev=corpse->prev;
+ if(corpse->prev!=NULL) //should be impossible
+ corpse->prev->next=corpse->next;
+ if(corpse->next!=NULL) //should be impossible
+ corpse->next->prev=corpse->prev;
+ list->del_func(corpse->data);
+ list->count--;
+ free(corpse);
+ }
+}
+
+/*
+ * Insert node containing data at marker.
+ * If direction true it inserts after.
+ * If direction false it inserts before.
+ * move marker to inserted node
+ * return pointer to inserted node
+ */
+void *dlist_insert(Dlist *list,void *data,int direction)
+{
+ DL_node *new_node=NULL;
+ if(list==NULL || data==NULL)
+ return(NULL);
+ if(list->marker==NULL) //in case the marker ends up unset
+ list->marker=list->head;
+ if((new_node=malloc(sizeof(DL_node))))
+ {
+ new_node->data=data;
+ new_node->prev=NULL;
+ new_node->next=NULL;
+ list->count++;
+ if(list->head->next==NULL) //no l
+ {
+ list->head->next=list->head->prev=new_node;
+ new_node->prev=list->head;
+ new_node->next=list->head;
+ }
+ else if(direction)
+ {
+ new_node->next=list->marker->next;
+ new_node->prev=list->marker;
+ list->marker->next->prev=new_node;
+ list->marker->next=new_node;
+ }
+ else
+ {
+ new_node->prev=list->marker->prev;
+ new_node->next=list->marker;
+ list->marker->prev->next=new_node;
+ list->marker->prev=new_node;
+ }
+ list->marker=new_node;
+ }
+ else
+ {
+ return(NULL);
+ }
+ return(list->marker->data);
+}
+
+/* internal use only
+ * Insert dl_node at marker.
+ * If direction true it inserts after.
+ * If direction false it inserts before.
+ * move marker to inserted node
+ * return pointer to inserted node
+ */
+void *_dlist_insert_dlnode(struct dlist *list,struct dl_node *new_node,int direction)
+{
+ if(list==NULL || new_node==NULL)
+ return(NULL);
+ if(list->marker==NULL) //in case the marker ends up unset
+ list->marker=list->head;
+ list->count++;
+ if(list->head->next==NULL)
+ {
+ list->head->next=list->head->prev=new_node;
+ new_node->prev=list->head;
+ new_node->next=list->head;
+ }
+ else if(direction)
+ {
+ new_node->next=list->marker->next;
+ new_node->prev=list->marker;
+ list->marker->next->prev=new_node;
+ list->marker->next=new_node;
+ }
+ else
+ {
+ new_node->prev=list->marker->prev;
+ new_node->next=list->marker;
+ list->marker->prev->next=new_node;
+ list->marker->prev=new_node;
+ }
+ list->marker=new_node;
+ return(list->marker);
+}
+
+
+
+/*
+ * Remove DL_node from list without deallocating data.
+ * if marker == killme .
+ * when direction true it moves marker after
+ * when direction false it moves marker before.
+ * to previous if there is no next.
+ */
+void *_dlist_remove(Dlist *list,DL_node *killme,int direction)
+{
+ if(killme!=NULL)
+ {
+ void *killer_data=killme->data;
+ // take care of head and marker pointers.
+ if(list->marker==killme)
+ _dlist_mark_move(list,direction);
+ if(killme ==list->head->next)
+ list->head->next=killme->next;
+ if(killme==list->head->prev)
+ list->head->prev=killme->prev;
+ // remove from list
+ if(killme->prev !=NULL)
+ killme->prev->next=killme->next;
+ if(killme->next !=NULL)
+ killme->next->prev=killme->prev;
+ list->count--;
+ free(killme);
+ return(killer_data);
+ }
+ else
+ return (NULL);
+}
+
+/*
+ * move dl_node from source to dest
+ * if marker == target .
+ * when direction true it moves marker after
+ * when direction false it moves marker before.
+ * to previous if there is no next.
+ */
+void dlist_move(struct dlist *source, struct dlist *dest, struct dl_node *target,int direction)
+{
+
+ if(target!=NULL)
+ {
+ if(target==source->head)
+ {
+ //not even going to try
+ }
+ else
+ {
+ // take care of head and marker pointers.
+ if(source->marker==target)
+ _dlist_mark_move(source,direction);
+ if(target ==source->head->next)
+ source->head->next=target->next;
+ if(target==source->head->prev)
+ source->head->prev=target->prev;
+ // remove from list
+ if(source->count==1)
+ {
+ target->prev=NULL;
+ target->next=NULL;
+ source->head->next=NULL;
+ source->head->prev=NULL;
+ }
+ else
+ {
+ if(target->prev !=NULL)
+ target->prev->next=target->next;
+ if(target->next !=NULL)
+ target->next->prev=target->prev;
+ target->prev=NULL;
+ target->next=NULL;
+ }
+ source->count--;
+ _dlist_insert_dlnode(dest,target,direction);
+ }
+ }
+}
+
+
+/*
+ * Insert node containing data after end.
+ */
+void dlist_push(Dlist *list,void *data)
+{
+ list->marker=list->head->prev;
+ dlist_insert(list,data,1);
+}
+
+/*
+ * Insert node containing data at start.
+ */
+
+void dlist_unshift(Dlist *list,void *data)
+
+{
+ list->marker=list->head->next;
+ dlist_insert(list,data,0);
+}
+
+void dlist_unshift_sorted(Dlist *list, void *data,
+ int (*sorter)(void *new_elem, void *old_elem))
+{
+ if (list->count == 0)
+ dlist_unshift(list, data);
+ else {
+ list->marker=list->head->next;
+ dlist_insert_sorted(list, data, sorter);
+ }
+}
+
+/*
+ * Remove end node from list.
+ * Return pointer to data in removed node.
+ * Null if no nodes.
+ */
+
+void *dlist_pop(Dlist *list)
+{
+ return(_dlist_remove(list,list->head->prev,0));
+}
+
+/*
+ * Remove start node from list.
+ * Return pointer to data in removed node.
+ * Null if no nodes.
+ */
+
+void *dlist_shift(Dlist *list)
+{
+ return(_dlist_remove(list,list->head->next,1));
+}
+
+
+/*
+ * destroy the list freeing all memory
+ */
+
+
+void dlist_destroy(Dlist *list)
+{
+ if(list !=NULL)
+ {
+ dlist_start(list);
+ dlist_next(list);
+ while (dlist_mark(list)) {
+ dlist_delete(list,1);
+ }
+ free(list);
+ }
+}
+
+/**
+ * Return void pointer to list_data element matching comp function criteria
+ * else null
+ * Does not move the marker.
+ */
+
+void *dlist_find_custom(struct dlist *list, void *target, int (*comp)(void *, void *))
+{
+ /* test the comp function on each node */
+ struct dl_node *nodepointer;
+ dlist_for_each_nomark(list,nodepointer)
+ if(comp(target,nodepointer->data))
+ return(nodepointer->data);
+ return(NULL);
+}
+
+/**
+ * Apply the node_operation function to each data node in the list
+ */
+void dlist_transform(struct dlist *list, void (*node_operation)(void *))
+{
+ struct dl_node *nodepointer;
+ dlist_for_each_nomark(list,nodepointer)
+ node_operation(nodepointer->data);
+}
+
+/**
+ * insert new into list in sorted order
+ * sorter function in form int sorter(new,ith)
+ * must return 1 for when new should go before ith
+ * else 0
+ * return pointer to inserted node
+ * NOTE: assumes list is already sorted
+ */
+void *dlist_insert_sorted(struct dlist *list, void *new, int (*sorter)(void *, void *))
+{
+ for(dlist_start(list),dlist_next(list); \
+ list->marker!=list->head && !sorter(new,list->marker->data);dlist_next(list));
+ return(dlist_insert_before(list,new));
+}
+
+/*
+ * NOTE: internal use only
+ */
+int _dlist_merge(struct dlist *listsource, struct dlist *listdest, unsigned int passcount, int (*compare)(void *, void *))
+{
+
+ struct dl_node *l1head;
+ struct dl_node *l2head;
+ struct dl_node *target;
+ unsigned int l1count=0;
+ unsigned int l2count=0;
+ unsigned int mergecount=0;
+ while(listsource->count>0)
+ {
+ l1head=listsource->head->next;
+ l2head=l1head;
+ while((l1count<passcount)&&(l2head!=listsource->head))
+ {
+ l2head=l2head->next;
+ l1count++;
+ }
+ // so now we have two lists to merge
+
+ if(l2head==listsource->head)
+ {// l2count
+ l2count=0;
+ }
+ else
+ {
+ l2count=passcount;
+ }
+ while(l1count>0 || l2count>0)
+ {
+ mergecount++;
+ if((l2count>0)&&(l1count>0))
+ {
+ // we have things to merge
+ int result=compare(l1head->data,l2head->data);
+ if(result>0)
+ {
+ // move from l2
+ target=l2head;
+ l2head=l2head->next;
+ dlist_move(listsource,listdest,target,1);
+ l2count--;
+ if(l2head==listsource->head)
+ l2count=0;
+ }
+ else
+ {
+ // move from l1
+ target=l1head;
+ l1head=l1head->next;
+ dlist_move(listsource,listdest,target,1);
+ l1count--;
+ }
+ }
+ else if(l1count>0)
+ {
+ // only have l1 to work with
+ while(l1count>0)
+ {
+ target=l1head;
+ l1head=l1head->next;
+ dlist_move(listsource,listdest,target,1);
+ l1count--;
+ }
+ }
+ else if(l2count>0)
+ {
+ // only have l2 to work with
+ while(l2count>0)
+ {
+ if(l2head==listsource->head)
+ {
+ l2count=0;
+ }
+ else
+ {
+ target=l2head;
+ l2head=l2head->next;
+ dlist_move(listsource,listdest,target,1);
+ l2count--;
+ }
+ }
+ }
+ else
+ { //nothing left and this should be unreachable
+ }
+ }
+ }
+ return(mergecount);
+}
+
+/**
+ * mergesort the list based on compare
+ * compare function in form int sorter(void * a,void * b)
+ * must return >0 for a after b
+ * must return <0 for a before b
+ * else 0
+
+ * NOTE: mergesort changes the mark pointer
+ */
+void dlist_sort_custom(struct dlist *list, int (*compare)(void *, void *))
+{
+
+ struct dlist *listsource, *listdest, *swap;
+ struct dlist *templist;
+ unsigned int passcount = 1;
+ unsigned int mergecount = 1;
+
+ dlist_start(list);
+ templist = dlist_new(list->data_size);
+
+ // do nothing if there isn't anything to sort
+ listsource = list;
+ listdest = templist;
+ if(listsource->count<2)
+ { //nothing to do
+ return;
+ }
+ else
+ {
+ while(mergecount>0)
+ {
+ mergecount=_dlist_merge(listsource, listdest, passcount, compare);
+ if(mergecount>1)
+ {
+ passcount=passcount*2;
+ //start new pass
+ swap=listsource;
+ listsource=listdest;
+ listdest=swap;
+ }
+ }
+ }
+ // now put the input list pointers right
+ // list pointers = newlist pointers
+ // including the forward and next nodes prev and back pointers
+ if(list->count==0)
+ {//copy
+ list->marker = listdest->marker;
+ list->count = listdest->count;
+ list->data_size = listdest->data_size;
+ list->del_func = listdest->del_func;
+ list->head->prev = listdest->head->prev;
+ list->head->next = listdest->head->next;
+ list->head->data = listdest->head->data;
+ list->head->next->prev=list->head;
+ list->head->prev->next=list->head;
+ templist->head->next=NULL;
+ templist->head->prev=NULL;
+ templist->count=0;
+ }
+ else
+ {// no need to copy
+
+ }
+
+ dlist_destroy(templist);
+}
+
+
+
+/* internal use function
+ swaps elements a and b
+ No sense in juggling node pointers when we can just swap the data pointers
+*/
+
+void _dlist_swap(struct dlist *list, struct dl_node *a, struct dl_node *b)
+{
+
+ void *swap=a->data;
+ a->data=b->data;
+ b->data=swap;
+
+}
+
View Lorry Controller Status