+
+/*
+ * 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 *))
+{
+
+ dlist_start(list);
+ struct dlist *listsource, *listdest, *swap;
+ struct dlist *templist = dlist_new(list->data_size);
+ unsigned int passcount = 1;
+ unsigned int mergecount = 1;
+ // 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;
+
+}
+