Generic double circular linked list - 通用双向循环链表C语言实现

Generic double circular linked list - 通用双向循环链表C语言实现

cheungmine

双向循环链表是计算机数据结构里面最基础的一种。我采用C语言实现，可以存储任何数据类型。这个双向链表（dlist）用来替换单向链表（list），可以获得更好的效率。

本文内容不提供任何保障，任何人在不声明版权所有的前提下本文内容可以被用于任何目的。

双向链表文件：

unitype.h

dlist.h

dlist.c

测试项目文件：

main.c

下面是全部的源代码：

/****************************************************************************************
 * unitype.h                                                                             *
 * 2008-03-15 Last created by cheungmine.                                               *
 *  All rights reserved by cheungmine.                                                  *
 ****************************************************************************************/
#ifndef UNITYPE_H__
#define UNITYPE_H__
/* Standard C header files included */
#include <stdio.h>
#include <string.h>
#include <assert.h>
/*============================================================================*/
typedef	signed   char   int8_t;
typedef	unsigned char   uint8_t, uchar_t, byte_t;
typedef	short int16_t;
typedef unsigned short uint16_t, word_t, ushort_t;  /* sizeof (uint16) must == 2 */
typedef	int int32_t;
typedef	unsigned int uint32_t, dword_t;             /* sizeof (uint32) must == 4 */
#if defined(_WIN32) || defined(_WINCE)
    typedef __int64 int64_t;
    typedef unsigned __int64 uint64, qword_t;
#else /* linux */
    typedef long long int64_t;
    typedef unsigned long long uint64_t, qword_t;
#endif
typedef float  float32_t;
typedef double float64_t;
typedef int    bool_t, lresult_t;
#define        bool_true     1
#define        bool_false    0
#define        res_success   0
#define        res_error    -1
#define        res_false     1
#ifndef IN
#define IN
#endif
#ifndef OUT
    #define OUT
#endif
#ifndef INOUT
    #define INOUT
#endif
#ifndef OPTIONAL
    #define OPTIONAL
#endif
#ifdef _DEBUG
    #include <stdarg.h>
    static void DBG_TRACE(const char *fmt, ...) {
        va_list ap;
        va_start(ap, fmt);
        vprintf(fmt, ap);
        va_end(ap);
    }
#else
    static void DBG_TRACE(const char *fmt, ...){}
#endif
/*============================================================================*/
#endif  /* UNITYPE_H__ */

/*******************************************************************************
 * dlist.h                                                                     *
 *		Generic double circular linked list - can hold any type data.          *
 *		cheungmine                                                             *
 *      Mar. 22, 2008.  All Rights Reserved.                                   *
 *                                                                             *
 *                ...........................................                  *
 *     dlist     |   ______    ______    ______    ______    |                 *
 *   _________   +->| node |  | node |  | node |  | node |   |                 *
 *  |size/head|---->|  next+->|  next+->|  next+->|  next+----                 *
 *   ---------    --+prev  |<-+prev  |<-+prev  |<-+prev  |<--                  *
 *               |   ------    ------    ------    ------    |                 *
 *               | front/head                     back/tail  |                 *
 *               |             begin      end                |                 *
 *               |...........................................|                 *
 *                                                                             *
 ******************************************************************************/
#ifndef DLIST_H_INCLUDED__
#define DLIST_H_INCLUDED__
#ifdef __cplusplus
extern "C" {
#endif
#include "unitype.h"
#include <malloc.h>
/**
 * dlist node type
 */
typedef struct _dlistnode_t
{
	struct _dlistnode_t	*_next;
    struct _dlistnode_t	*_prev;
	union{
		void            *data;
		struct _dlist_t	*list;
		const char		*str;
		int32_t          val;
	};
}dlistnode_t;

/**
 * dlist type
 */
typedef struct _dlist_t
{
	size_t		  _size;	 /* count of all nodes */
	dlistnode_t	 *_head; /* point to the front node of list */
}dlist_t, *dlist_p;

/**
 * A prototype of callbacke function called by:
 * 	- dlist_destroy()
 *	- dlist_traverse()
 *	- dlist_nodes_free()
 *	0 for no use 
 */
typedef void(*pfunc_dlist_callback)(dlistnode_t* node, void *param);

/**
 * A prototype of callback function called by:
 * 	- dlist_sort()
 * Returns:
 *    0: a = b
 *    1: a > b
 *   -1: a < b
 */
typedef int(*pfunc_dlist_compare_callback)(dlistnode_t* a, dlistnode_t* b, void *param);

/**
 * A prototype example of free node data function implemented by caller:
 */
static void my_dlistnode_data_free(dlistnode_t *node, void *param)
{
    printf("    free node: %d/n", node->val);
    /* free(node->data); */
}

/**
 * A prototype example of traverse implemented by caller:
 */
static void my_traverse_dlistnode_printf(dlistnode_t *node, void *param)
{
    printf("    node: %ld/n", node->val);
}

/**
 * An example of compare list node used by bubble sort ascend
 */
static int my_dlist_sort_nodes_ascend(dlistnode_t* a, dlistnode_t* b, void *param)
{
    if (a->val > b->val)
        return 1;
    else if (a->val < b->val)
        return -1;
    else
        return  0;
}

/**
 * An example of compare list node used by bubble sort descend
 */
static int my_dlist_sort_nodes_descend(dlistnode_t* a, dlistnode_t* b, void *param)
{
    if (a->val < b->val)
        return 1;
    else if (a->val > b->val)
        return -1;
    else
        return  0;
}
/*===============================================================================
 *                                                                              *
 *                           dlist public functions                             *
 *                                                                              *
 *==============================================================================*/
/**
 * Allocates a empty list from heap, this creates a new list 
 */
dlist_t* dlist_create();

/** 
 * Clears a list and free all memory, the list cannot be used later
 * Since the nodes data are allocated by caller, so caller MUST provide a callback 
 * function to free the node.
 */
void dlist_destroy(dlist_t *lst, pfunc_dlist_callback  pfcbFreeNodeData, void *param);

/**
 * Removes all nodes except for list itself 
 */
void dlist_clear(dlist_t *lst, pfunc_dlist_callback pfcb, void *param);

/**
 * Traverses a list, applied callback functionn for each node. So pfcbTraverseNode MUST be valid.
 * If tail_to_head is bool_true, traverse is make from tail to head otherwise is from head to tail
 */
void dlist_traverse(dlist_t *lst, pfunc_dlist_callback pfcbTraverseNode, void *param, bool_t tail_to_head);

/** 
 * Creates a new node assigned with data, not allocates for data
 */
dlistnode_t* dlist_node_create(void* data);

/** 
 * Free the nodes from begin to end. If end node is 0, only free the begin node
 */
void dlist_nodes_free(dlistnode_t* begin_node, dlistnode_t* end_node, pfunc_dlist_callback  pfcbFreeNodeData, void *param);

/** 
 * Calculate size of nodes from begin to end
 */
size_t dlist_nodes_size(dlistnode_t* begin_node, dlistnode_t* end_node);

/** 
 * Get head node of a list
 */
dlistnode_t* dlist_head_node(dlist_t *lst);

/** 
 * Get tail node of a list
 */
dlistnode_t* dlist_tail_node(dlist_t *lst);

/** 
 * Gets node by index: 0-based. 0 is head, -1 is tail.
 * If index isnot a valid index (==-1 || >=0 && <size), return 0
 */
dlistnode_t* dlist_node_at(const dlist_t* lst, size_t index);

/** 
 * Appends a node to the back of list
 */
void dlist_push_back(dlist_t *lst, dlistnode_t *back_node);

/** 
 * Inserts a node as head of list 
 */
void dlist_push_front(dlist_t *lst, dlistnode_t *front_node);

/** 
 * Removes the front node from a list and returns the node removed
 */
dlistnode_t* dlist_pop_front(dlist_t *lst);

/** 
 * Removes the back node from a list and returns the node removed
 */
dlistnode_t* dlist_pop_back(dlist_t *lst);

/**
 * Inserts a node after the node into a list 
 */
bool_t dlist_insert_after(dlist_t *lst, dlistnode_t *prev_node, dlistnode_t *ins_node);

/**
 * Inserts a node before the node into a list 
 */
bool_t dlist_insert_before(dlist_t *lst, dlistnode_t *back_node, dlistnode_t *ins_node);

/** 
 * Cut nodes from begin node to end node off the list, returns the node prior to 
 * the begin node cut off.
 * Caller should free the nodes lead by begin node.
 * When the begin and end nodes are the same one, it will only cut off that.
 * When return 0 indicates list is empty (size==0)
 * It can be explained that why not providing the way to cut off a single node here.
 * NOTE: begin node must be prior to end node in sequence. 
 *
 *    dlistnode_t  *begin = dlist_node_at(lst, 2);
 *    dlistnode_t  *end   = dlist_node_at(lst, 5);
 *    dlistnode_t  *node = dlist_slice(lst, begin, end);
 *    dlist_nodes_free(begin, end, 0, 0);
 *
 * YOU CAN NOT APPLY dlist_nodes_free TO NODE WHICH IS NOT SLICED FROM LIST
 * The following snippet is ILLEGITIMATE:
 *
 *    dlistnode_t  *begin = dlist_node_at(lst, 2);
 *    dlist_nodes_free(begin, begin, 0, 0);
 *
 * While the following snippet is correct:
 *    dlistnode_t  *begin = dlist_node_at(lst, 2);
 *    dlist_slice(lst, begin, 0);
 *    dlist_nodes_free(begin, begin, 0, 0);
 */
dlistnode_t* dlist_slice(dlist_t* lst, dlistnode_t* begin, dlistnode_t* end);

/** 
 * Gets count of nodes in the list 
 */
size_t dlist_size(const dlist_t* lst);

/**
 * Appends the second list to the first list
 */
void dlist_concat(dlist_t *first, dlist_t *second);

/**
 * Reverse list. For example the initial nodes are:0,1,2,3, 
 * after dlist_reverse will be: 3,2,1,0
 */
void dlist_reverse(dlist_t* lst);

/**
 * Swap two nodes in list: front node must preceding the back node, only the situations below can be accepted:
 *   1) a==b
 *   2) a->b
 *   3) a->...->b
 * NOTE:
 *   b->a or b->...->a is unaccepted, that will cause an exception
 */
void dlist_swap_nodes(dlist_t* lst, dlistnode_t *ahead, dlistnode_t *back);

/**
 * Bubble sort list nodes by ascend: 0,1,2,3,...,9
 */
void dlist_bubble_sort(dlist_t* lst, pfunc_dlist_compare_callback  pfcbCompareNodes, void *param);

/**
 * Merge sort src list to dst list. Caller can free src after merging.
 * dst and src lists MUST be sorted by the same dlist_compare_callback as dlist_merge_sort
 */
void dlist_merge_sort(dlist_t* dst, dlist_t* src, pfunc_dlist_compare_callback  pfcbCompareNodes, void *param);
#ifdef __cplusplus
}
#endif
#endif  /* DLIST_H_INCLUDED__ */

/****************************************************************************************
 * dlist.c                                                                               *
 *		Generic sequential linked list node structure -- can hold any type data.        *
 *		cheungmine                                                                      *
 *      May. 22, 2008.  All rights reserved.                                            *
 ****************************************************************************************/
#include "dlist.h"
#include <assert.h>
#define DLIST_USE_TAIL_NODE(lst)     (lst->_head->_prev)
#define DLIST_IS_HEAD_NODE(lst, node)     (node==lst->_head)
#define DLIST_IS_TAIL_NODE(lst, node)     (node->_next==lst->_head)
/*===============================================================================
 *                                                                              *
 *                           dlist public functions                             *
 *                                                                              *
 *==============================================================================*/
dlist_t* dlist_create()
{
    dlist_t	*dl = (dlist_t*) malloc (sizeof(dlist_t));
    assert(dl);
	dl->_size = 0;
	dl->_head = 0;
	return dl;
}

void dlist_destroy(dlist_t *lst, pfunc_dlist_callback  pfcbFreeNodeData, void *param)
{
    dlist_clear(lst, pfcbFreeNodeData, param);	
	free(lst);
}

void dlist_clear(dlist_t *lst, pfunc_dlist_callback pfcb, void *param)
{
    dlistnode_t	*node;
    if (pfcb) {
        while((node = dlist_pop_front(lst)) != 0){
	        (*pfcb)(node, param);
            free(node);
        }
    }
    else {
        while((node = dlist_pop_front(lst)) != 0){
            free(node);
        }
    }
    assert (lst->_head==0 && lst->_size==0);
}
void dlist_traverse(dlist_t *lst, pfunc_dlist_callback pfcbTraverseNode, void *param, bool_t tail_to_head)
{
    dlistnode_t* node;
    assert(pfcbTraverseNode);
    if (tail_to_head) {
		node = DLIST_USE_TAIL_NODE(lst);
		while (node) {
			(*pfcbTraverseNode)(node, param);            
            if (DLIST_IS_HEAD_NODE(lst, node))
                break;
            node = node->_prev;            
		}
	}
    else {
        node = lst->_head;
		while (node) {
			(*pfcbTraverseNode)(node, param);            
            if (DLIST_IS_TAIL_NODE(lst, node))
                break;
            node = node->_next;           
		}
    }
}
dlistnode_t* dlist_pop_front(dlist_t *lst)
{
    dlistnode_t	*pop_node = 0;
	
    if (lst->_head)
	{
        if (lst->_size==1){
            pop_node = lst->_head;
            pop_node->_next = pop_node->_prev = 0;
            lst->_size = 0;
            lst->_head = 0;
        }
        else{
            assert(lst->_size>1);
            pop_node = lst->_head;
            lst->_head = pop_node->_next;
            DLIST_USE_TAIL_NODE(lst) = pop_node->_prev;
            DLIST_USE_TAIL_NODE(lst)->_next = lst->_head;
            pop_node->_next = pop_node->_prev = 0;
            lst->_size--;
        }
    }
    assert(lst->_size >= 0);
	return pop_node;
}

dlistnode_t* dlist_pop_back(dlist_t *lst)
{
    dlistnode_t	*pop_node = 0;
	
    if (lst->_head)
	{
        if (lst->_size==1){
            pop_node = lst->_head;
            pop_node->_next = pop_node->_prev = 0;
            lst->_size = 0;
            lst->_head = 0;
        }
        else{
            assert(lst->_size>1);
            pop_node = DLIST_USE_TAIL_NODE(lst);
            DLIST_USE_TAIL_NODE(lst) = pop_node->_prev;
            assert(pop_node->_next==lst->_head);
            pop_node->_prev->_next = pop_node->_next;
            pop_node->_next = pop_node->_prev = 0;
            lst->_size--;
        }
    }
    assert(lst->_size >= 0);
	return pop_node;
}

dlistnode_t* dlist_node_create(void* data)
{
    dlistnode_t	*node = (dlistnode_t*) malloc (sizeof(dlistnode_t));
    assert(node);
	node->_next = node->_prev = 0;
	node->data = data;
	return node;
}

void dlist_push_back(dlist_t *lst, dlistnode_t *back_node)
{
    dlistnode_t *tail;
    if (lst->_head) {
        assert(lst->_size>0);
        tail = DLIST_USE_TAIL_NODE(lst);
        back_node->_prev = tail;
        back_node->_next = tail->_next;
        tail->_next = back_node;
        lst->_head->_prev = back_node;
        lst->_size++;
    }
    else {
        assert(lst->_size==0);
        lst->_head = back_node->_next = back_node->_prev = back_node;
        lst->_size = 1;
    }
}

void dlist_push_front(dlist_t *lst, dlistnode_t *front_node)
{
    if (lst->_head) {
        assert(lst->_size>0);
        front_node->_next = lst->_head;
        DLIST_USE_TAIL_NODE(lst)->_next = front_node;
        front_node->_prev = DLIST_USE_TAIL_NODE(lst);
        lst->_head->_prev = front_node;
        lst->_head = front_node;
        lst->_size++;
    }
    else {
        assert(lst->_size==0);
        lst->_head = front_node->_next = front_node->_prev = front_node;
        lst->_size = 1;
    }
}

void dlist_nodes_free(dlistnode_t* node, dlistnode_t* end_node, pfunc_dlist_callback  pfcbFreeNodeData, void *param)
{
    dlistnode_t* free_node;
    while (node) {
        free_node = node;
        node = node->_next;
        
        if (pfcbFreeNodeData)
            (*pfcbFreeNodeData) (free_node, param);
        free(free_node);
        if (!end_node)  /* only free node */
            break;
        if (node==end_node) {
            if (pfcbFreeNodeData)
                (*pfcbFreeNodeData) (node, param);
            free(node);            
            break;
        }
    }
}

size_t dlist_size(const dlist_t* lst)
{
    return lst->_size;
}

dlistnode_t* dlist_node_at(const dlist_t* lst, size_t index)
{
    size_t       i;
	dlistnode_t	*node;
    
    assert(index==-1 || index==0 || index < lst->_size);
    if (!lst->_head || index==0)
        return lst->_head;
    assert(lst->_head);
    if (index==-1)
        return lst->_head->_prev;
    /* bad index */
    if (index >= lst->_size)
        return 0;
    i = 0;
    if (index <= lst->_size/2) {
        /* To search from the head on */
        node = lst->_head;
	    while (i < index) {
		    node = node->_next;
		    i++;
	    }
    }
    else {
        /* It would be much quickly to search from the end on than the head */
        node = DLIST_USE_TAIL_NODE(lst);  /* tail node */
        index = lst->_size - index - 1;
        while (i < index) {
            node = node->_prev;
            i++;
        }
    }
	return node;
}

void dlist_reverse(dlist_t* lst)
{
    dlistnode_t *node;
    dlistnode_t *next;
    dlistnode_t *prev;
    node = lst->_head;
    while (node) {
        next = node->_next;
        prev = node->_prev;
        node->_next = prev;
        node->_prev = next; 
        prev = node;
        node = next;
        if (node==lst->_head) {
            lst->_head = prev;
            break;
        }
    }
}

size_t dlist_nodes_size(dlistnode_t* node, dlistnode_t* end_node)
{
    size_t       n = 0;
    if (node==end_node || !end_node)
        return 1;
    while (node) {
        n++;
        node = node->_next;
        if (node && node==end_node){
            n++;
            break;
        }
    }
    return n;
}

dlistnode_t* dlist_slice(dlist_t* lst, dlistnode_t* begin, dlistnode_t* end)
{
    dlistnode_t  *n1, *n2;   /* ...n1->begin->...->end->n2...*/
    size_t        c = dlist_nodes_size(begin, end);
    if (c==0)
        return lst->_head;
    assert(lst->_head);
    n1 = begin->_prev;
    n2 = end->_next;
    assert(n1 && n2);
    n1->_next = n2;
    n2->_prev = n1;
    /* cut nodes off list */
    begin->_prev = 0;
    end->_next = 0;
    if (lst->_head != begin) {
        lst->_size -= c;
        return n1;
    }
    else {
        assert(lst->_head==begin);
        if (DLIST_USE_TAIL_NODE(lst)==end) {
            lst->_head = 0;
            lst->_size = 0;
            return 0;
        }
        else {
            lst->_size -= c;
            lst->_head = n1;
            return n1;
        }        
    }
    return n1;
}

dlistnode_t* dlist_head_node(dlist_t *lst)
{
    return lst->_head;
}

dlistnode_t* dlist_tail_node(dlist_t *lst)
{
    return DLIST_USE_TAIL_NODE(lst);
}
bool_t dlist_insert_after(dlist_t *lst, dlistnode_t *prev_node, dlistnode_t *ins_node)
{
    assert(lst);
    if (!lst->_head) {
        if (prev_node)
            return bool_false;
        dlist_push_front(lst, ins_node);
        return bool_true;
    }
    else {
        assert(lst->_head);
        if (!prev_node)
            return bool_false;
        lst->_size++;
        ins_node->_prev = prev_node;
        ins_node->_next = prev_node->_next;
        prev_node->_next->_prev = ins_node;
        prev_node->_next = ins_node;
        return bool_true;
    }
}

bool_t dlist_insert_before(dlist_t *lst, dlistnode_t *back_node, dlistnode_t *ins_node)
{
    assert(lst);
    if (!lst->_head) {
        if (back_node)
            return bool_false;
        dlist_push_back(lst, ins_node);
        return bool_true;
    }
    else {
        assert(lst->_head);
        if (!back_node)
            return bool_false;
        if (lst->_head==back_node) {
            dlist_push_front(lst, ins_node);
        }
        else {
            lst->_size++;
            ins_node->_next = back_node;
            ins_node->_prev = back_node->_prev;
            back_node->_prev->_next = ins_node;
            back_node->_prev = ins_node;
        }
        return bool_true;
    }
}

void dlist_concat(dlist_t *first, dlist_t *second)
{
    assert(first && second);
    if (first->_head) {
        if (second->_head) {
            dlistnode_t *second_tail = DLIST_USE_TAIL_NODE(second);
            DLIST_USE_TAIL_NODE(first)->_next = second->_head;
            DLIST_USE_TAIL_NODE(second)->_next = first->_head;
            DLIST_USE_TAIL_NODE(second) = DLIST_USE_TAIL_NODE(first);
            DLIST_USE_TAIL_NODE(first) = second_tail;
            
            first->_size += second->_size;
            second->_head = 0;
            second->_size = 0;
        }
    }
    else {
        assert(!first->_head);
        if (second->_head) {
            first->_head = second->_head;
            first->_size = second->_size;
            second->_head = 0;
            second->_size = 0;
        }
    }
}

void dlist_swap_nodes(dlist_t* lst, dlistnode_t *a, dlistnode_t *b)
{
    dlistnode_t *p, *n;
    assert(a && b);
    
    if (a==b) {
        /* [p]->[a|b]->[n] */
        return;
    }
    else if (a->_next==b && b->_next==a) {
        if (lst->_head==a)
            lst->_head = b;
        else
            lst->_head = a;
    }
    else if (a->_next==b) {
        /* [p]->[a]->[b]->[n] */
        p = a->_prev;
        n = b->_next;
        p->_next = b;
        b->_next = a;
        a->_next = n;
        n->_prev = a;
        a->_prev = b;
        b->_prev = p;
        if (lst->_head==a) {
            lst->_head = b;
        }
    }
    else if (b->_next==a) {
        /* [head:a]->...->[tail:b] */
        p = b->_prev;
        n = a->_next;
        p->_next = a;
        a->_next = b;
        b->_next = n;
        n->_prev = b;
        b->_prev = a;
        a->_prev = p;
        if (lst->_head==a) {
            lst->_head = b;
        }
    }
    else {
        /* [p]->[a]->[a1...b1]->[b]->[n] */
        dlistnode_t *a1, *b1;
        p = a->_prev;
        n = b->_next;
        a1 = a->_next;
        b1 = b->_prev;
        p->_next = b;
        b->_next = a1;
        b1->_next = a;
        a->_next = n;
        a1->_prev = b;
        b->_prev = p;
        n->_prev = a;
        a->_prev = b1;
    }
}

void dlist_sort_ascend(dlist_t* lst, pfunc_dlist_compare_callback  pfcbCompareNodes, void *param)
{
    int           flag   = 1;
    
    dlistnode_t  *first  = 0;
    dlistnode_t  *second = 0;
    dlistnode_t  *last_sink = 0;
    first = lst->_head;
    while (flag==1) {
        flag = 0;
        while(first) {
            second = first->_next;
            assert(second);
            if (second==lst->_head)
                break;
            if (second==last_sink)
                break;
            if (pfcbCompareNodes) {
                if ((*pfcbCompareNodes)(first, second, param) > 0) {
                    flag = 1;
                    dlist_swap_nodes(lst, first, second);
                    last_sink = first;
                }
            }
            else if (first->val > second->val) {
                flag = 1;
                dlist_swap_nodes(lst, first, second);
                last_sink = first;
            }
  
            first = second;
        }
    }    
}

void dlist_bubble_sort(dlist_t* lst, pfunc_dlist_compare_callback  pfcbCompareNodes, void *param)
{
    int           flag   = 1;
    
    dlistnode_t  *first  = 0;
    dlistnode_t  *second = 0;
    dlistnode_t  *last_sink = 0;
    while (flag==1) {
        flag = 0;
        first = lst->_head;
        while(first) {
            second = first->_next;
            assert(second);
            if (second==lst->_head)
                break;
            if (second==last_sink)
                break;
            if (pfcbCompareNodes) {
                if ((*pfcbCompareNodes)(first, second, param) > 0) {
                    flag = 1;
                    dlist_swap_nodes(lst, first, second);
                    last_sink = first;
                }
                else
                    first = second;
            }
            else {
                if (first->val > second->val) {
                    flag = 1;
                    dlist_swap_nodes(lst, first, second);
                    last_sink = first;
                }
                else
                    first = second;
            }
        }
    }
}

void dlist_merge_sort(dlist_t* dst, dlist_t* src, pfunc_dlist_compare_callback  pfcbCompareNodes, void *param)
{
    dlistnode_t *dst_node;
    dlistnode_t *src_node;
    assert(dst && src);
    if (!dst->_head) {
        dlist_concat(dst, src);
        return;
    }
    dst_node = dst->_head;
    src_node = src->_head;
        
    while (src_node) {
        if (pfcbCompareNodes) {
            if ((*pfcbCompareNodes)(dst_node, src_node, 0) > 0) {
                dlist_insert_before(dst, dst_node, dlist_pop_front(src));
                src_node = src->_head;
            }
            else {
                dst_node = dst_node->_next;
                if (dst_node==dst->_head) {
                    dlist_concat(dst, src);
                    return;
                }
            }
        }
        else {
            if (dst_node->val > src_node->val) {
                dlist_insert_before(dst, dst_node, dlist_pop_front(src));
                src_node = src->_head;
            }
            else {
                dst_node = dst_node->_next;
                
                if (dst_node==dst->_head) {
                    dlist_concat(dst, src);
                    return;
                }
            }
        }            
    }
}

测试文件：

// Test for dlist
// main.c
// by cheungmine
//
/* Detecting memory leaks only for windows . 
 * Place the following snippet where leak to be tested:
   #if defined(_CRTDBG_MAP_ALLOC)
     _CrtDumpMemoryLeaks();
   #endif
 */
#if defined(WIN32) && defined(_DEBUG)
  #ifndef   _CRTDBG_MAP_ALLOC
    #pragma message( __FILE__": _CRTDBG_MAP_ALLOC defined only for DEBUG on Win32." ) 
    #define _CRTDBG_MAP_ALLOC
    #include<stdlib.h> 
    #include<crtdbg.h>
  #endif
#endif
#include "../dlist.h"
void test_reverse();
void test_concat();
void test_slice();
void test_insert();
void test_swap();
void test_more_swap();
void test_sort_ascend();
void test_sort_descend();
void test_merge_sort();

///////////////////////////////////////////////////////////////////////////////
int main()
{
    // test_reverse();
    // test_concat();
    // test_slice();
    // test_insert();
    // test_swap();
    // test_more_swap();
    // test_sort_ascend();
    // test_sort_descend();
    test_merge_sort();
    return 0;
}
///////////////////////////////////////////////////////////////////////////////
void test_reverse()
{
    //////////////////////////////////////////
    // dlist_create                                                 
    // dlist_traverse
    // dlist_reverse
    // dlist_destroy
    //////////////////////////////////////////
    int  i;
    dlistnode_t *nod;
    dlist_p      A;
    
    printf("dlist_create A ok/n");
    A = dlist_create();
    for (i=0; i<10; i++){
        nod = dlist_node_create(i);
        dlist_push_back(A, nod);
    }
    printf("dlist_traverse A (%d nodes):/n", dlist_size(A));
    dlist_traverse(A, my_traverse_dlistnode_printf, 0, 0);
    dlist_reverse(A);
    printf("dlist_traverse A (%d nodes) after dlist_reverse called:/n", dlist_size(A));
    dlist_traverse(A, my_traverse_dlistnode_printf, 0, 0);
    dlist_destroy(A, 0, 0);
    printf("dlist_destroy/n");
#if defined(_CRTDBG_MAP_ALLOC)
    _CrtDumpMemoryLeaks();
#endif
}
void test_concat()
{
    //////////////////////////////////////////
    // dlist_create                                                 
    // dlist_traverse
    // dlist_concat
    // dlist_destroy
    //////////////////////////////////////////
 
    int  i;
    dlistnode_t *nod;
    dlist_p      A, B;

    A = dlist_create();
    for (i=0; i<5; i++){
        nod = dlist_node_create(i);
        dlist_push_back(A, nod);
    }
    printf("dlist_traverse A (%d nodes):/n", dlist_size(A));
    dlist_traverse(A, my_traverse_dlistnode_printf, 0, 0);

    B = dlist_create();
    for (i=0; i<4; i++){
        nod = dlist_node_create(i+10);
        dlist_push_back(B, nod);
    }
    printf("dlist_traverse B (%d nodes):/n", dlist_size(B));
    dlist_traverse(B, my_traverse_dlistnode_printf, 0, 0);
    dlist_concat(A, B);
    printf("dlist_traverse B after concat to A (%d nodes):/n", dlist_size(B));
    dlist_traverse(B, my_traverse_dlistnode_printf, 0, 0);
    dlist_destroy(B, 0, 0);
    printf("dlist_traverse A after dlist_concat with B (%d nodes):/n", dlist_size(A));
    dlist_traverse(A, my_traverse_dlistnode_printf, 0, 0);
    dlist_destroy(A, 0, 0);
#if defined(_CRTDBG_MAP_ALLOC)
    _CrtDumpMemoryLeaks();
#endif
}

void test_slice()
{
    //////////////////////////////////////////
    // dlist_node_at
    // dlist_slice
    //////////////////////////////////////////
 
    int  i;
    dlistnode_t *nod;
    dlist_p      A;

    A = dlist_create();
    for (i=0; i<10; i++){
        nod = dlist_node_create(i);
        dlist_push_back(A, nod);
    }
    printf("dlist_traverse A (%d nodes):/n", dlist_size(A));
    dlist_traverse(A, my_traverse_dlistnode_printf, 0, 0);
    nod = dlist_node_create(11);
    dlist_push_front(A, nod);
    nod = dlist_node_create(10);
    dlist_push_front(A, nod);
    nod = dlist_node_create(12);
    dlist_push_back(A, nod);
    nod = dlist_node_at(A, 0);
    printf("dlist_node_at 0: %d/n", nod->val);
    nod = dlist_node_at(A, 1);
    printf("dlist_node_at 1: %d/n", nod->val);
    nod = dlist_node_at(A, -1);
    printf("dlist_node_at -1: %d/n", nod->val);
    printf("dlist_traverse A after push nodes(%d nodes):/n", dlist_size(A));
    dlist_traverse(A, my_traverse_dlistnode_printf, 0, 0);
 
    nod = dlist_node_at(A, 1);
    dlist_slice(A, nod, nod);
    dlist_nodes_free(nod, 0, 0, 0);
    printf("dlist_traverse A after dlist_slice(%d nodes):/n", dlist_size(A));
    dlist_traverse(A, my_traverse_dlistnode_printf, 0, 0);

    dlist_destroy(A, 0, 0);
#if defined(_CRTDBG_MAP_ALLOC)
    _CrtDumpMemoryLeaks();
#endif
}

void test_insert()
{
    //////////////////////////////////////////
    // dlist_head_node
    // dlist_tail_node
    // dlist_insert_after
    // dlist_insert_before
    //////////////////////////////////////////
 
    int  i;
    dlistnode_t *nod;
    dlist_p      A;
    A = dlist_create();
    for (i=0; i<10; i++){
        nod = dlist_node_create(i);
        dlist_push_back(A, nod);
    }
    printf("dlist_traverse A (%d nodes):/n", dlist_size(A));
    dlist_traverse(A, my_traverse_dlistnode_printf, 0, 0);
    nod = dlist_node_create(100);
    dlist_insert_after(A, dlist_head_node(A), nod);
    
    nod = dlist_node_create(200);
    dlist_insert_after(A, dlist_tail_node(A), nod);
    nod = dlist_node_create(300);
    dlist_insert_before(A, dlist_head_node(A), nod);
    nod = dlist_node_create(400);
    dlist_insert_after(A, dlist_tail_node(A), nod);
    nod = dlist_node_create(350);
    dlist_insert_before(A, dlist_tail_node(A), nod);
    nod = dlist_node_create(99);
    dlist_insert_after(A, dlist_node_at(A, 5), nod);
    nod = dlist_node_create(60);
    dlist_insert_before(A, dlist_node_at(A, 6), nod);
    
    nod = dlist_pop_back(A);
    dlist_nodes_free(nod, nod, 0, 0);
    nod = dlist_pop_front(A);
    dlist_nodes_free(nod, 0, 0, 0);
    printf("dlist_traverse A after insertion (%d nodes):/n", dlist_size(A));
    dlist_traverse(A, my_traverse_dlistnode_printf, 0, 0);
    
  
    dlist_destroy(A, 0, 0);
#if defined(_CRTDBG_MAP_ALLOC)
    _CrtDumpMemoryLeaks();
#endif
}

void test_swap()
{
    //////////////////////////////////////////
    // dlist_swap_nodes
    //////////////////////////////////////////
 
    int  i;
    dlistnode_t *nod;
    dlist_p      A;
    A = dlist_create();
    for (i=0; i<10; i++){
        nod = dlist_node_create(i);
        dlist_push_back(A, nod);
    }
    printf("dlist_traverse A (%d nodes):/n", dlist_size(A));
    dlist_traverse(A, my_traverse_dlistnode_printf, 0, 0);
    dlist_swap_nodes(A, dlist_node_at(A, 3), dlist_node_at(A, 4));
    printf("dlist_traverse A after swap 3 with 4 (%d nodes):/n", dlist_size(A));
    dlist_traverse(A, my_traverse_dlistnode_printf, 0, 0);
    dlist_swap_nodes(A, dlist_node_at(A, 3), dlist_node_at(A, 4));    
    printf("dlist_traverse A after swap 3 with 4 (%d nodes):/n", dlist_size(A));
    dlist_traverse(A, my_traverse_dlistnode_printf, 0, 0);
    dlist_swap_nodes(A, dlist_node_at(A, 3), dlist_node_at(A, 7));    
    printf("dlist_traverse A after swap 3 with 7 (%d nodes):/n", dlist_size(A));
    dlist_traverse(A, my_traverse_dlistnode_printf, 0, 0);
    dlist_swap_nodes(A, dlist_node_at(A, 3), dlist_node_at(A, 7));    
    printf("dlist_traverse A after swap 3 with 7 (%d nodes):/n", dlist_size(A));
    dlist_traverse(A, my_traverse_dlistnode_printf, 0, 0);
    dlist_swap_nodes(A, dlist_node_at(A, 7), dlist_node_at(A, 9));    
    printf("dlist_traverse A after swap 7 with 9 (%d nodes):/n", dlist_size(A));
    dlist_traverse(A, my_traverse_dlistnode_printf, 0, 0);
    dlist_swap_nodes(A, dlist_node_at(A, 7), dlist_node_at(A, 9));    
    printf("dlist_traverse A after swap 7 with 9 (%d nodes):/n", dlist_size(A));
    dlist_traverse(A, my_traverse_dlistnode_printf, 0, 0);
    dlist_swap_nodes(A, dlist_node_at(A, 0), dlist_node_at(A, -1));    
    printf("dlist_traverse A after swap head with tail (%d nodes):/n", dlist_size(A));
    dlist_traverse(A, my_traverse_dlistnode_printf, 0, 0);
    dlist_swap_nodes(A, dlist_node_at(A, 0), dlist_node_at(A, -1));    
    printf("dlist_traverse A after swap head with tail (%d nodes):/n", dlist_size(A));
    dlist_traverse(A, my_traverse_dlistnode_printf, 0, 0);
  
    dlist_swap_nodes(A, dlist_node_at(A, -1)->_prev, dlist_node_at(A, -1));    
    printf("dlist_traverse A after swap pre-tail with tail (%d nodes):/n", dlist_size(A));
    dlist_traverse(A, my_traverse_dlistnode_printf, 0, 0);
  
    dlist_swap_nodes(A, dlist_node_at(A, 0), dlist_node_at(A, 0)->_next);    
    printf("dlist_traverse A after swap head with post-head (%d nodes):/n", dlist_size(A));
    dlist_traverse(A, my_traverse_dlistnode_printf, 0, 0);
  
    dlist_destroy(A, 0, 0);
#if defined(_CRTDBG_MAP_ALLOC)
    _CrtDumpMemoryLeaks();
#endif
}

void test_more_swap()
{
    //////////////////////////////////////////
    // dlist_clear
    // dlist_swap_nodes
    //////////////////////////////////////////
 
    int  i;
    dlistnode_t *nod;
    dlist_p      A;
    A = dlist_create();
    for (i=0; i<2; i++){
        nod = dlist_node_create(i);
        dlist_push_back(A, nod);
    }
    printf("dlist_traverse A (%d nodes):/n", dlist_size(A));
    dlist_traverse(A, my_traverse_dlistnode_printf, 0, 0);
    dlist_swap_nodes(A, dlist_head_node(A), dlist_tail_node(A));
    printf("dlist_traverse A after dlist_swap_nodes (%d nodes):/n", dlist_size(A));
    dlist_traverse(A, my_traverse_dlistnode_printf, 0, 0);
    /* Below is a bad call for we suppose that dlist_swap_nodes requires the swapped nodes: ahead precedes back */
    dlist_swap_nodes(A, dlist_tail_node(A), dlist_head_node(A));
    printf("dlist_traverse A after dlist_swap_nodes (%d nodes):/n", dlist_size(A));
    dlist_traverse(A, my_traverse_dlistnode_printf, 0, 0);
    dlist_clear(A, 0, 0);
    for (i=0; i<3; i++){
        nod = dlist_node_create(i);
        dlist_push_back(A, nod);
    }
    // 0,1,2
    printf("dlist_traverse A (%d nodes):/n", dlist_size(A));
    dlist_traverse(A, my_traverse_dlistnode_printf, 0, 0);
    // 1,0,2
    dlist_swap_nodes(A, dlist_node_at(A, 0), dlist_node_at(A, 1));
    printf("dlist_traverse A after dlist_swap_nodes (%d nodes):/n", dlist_size(A));
    dlist_traverse(A, my_traverse_dlistnode_printf, 0, 0);
    // 1,2,0
    dlist_swap_nodes(A, dlist_node_at(A, 1), dlist_node_at(A, 2));
    printf("dlist_traverse A after dlist_swap_nodes (%d nodes):/n", dlist_size(A));
    dlist_traverse(A, my_traverse_dlistnode_printf, 0, 0);
    // 1,0,2
    dlist_swap_nodes(A, dlist_node_at(A, 1), dlist_node_at(A, 2));
    printf("dlist_traverse A after dlist_swap_nodes (%d nodes):/n", dlist_size(A));
    dlist_traverse(A, my_traverse_dlistnode_printf, 0, 0);
    // 0,1,2
    dlist_swap_nodes(A, dlist_node_at(A, 0), dlist_node_at(A, 1));
    printf("dlist_traverse A after dlist_swap_nodes (%d nodes):/n", dlist_size(A));
    dlist_traverse(A, my_traverse_dlistnode_printf, 0, 0);
     
    dlist_destroy(A, 0, 0);
#if defined(_CRTDBG_MAP_ALLOC)
    _CrtDumpMemoryLeaks();
#endif
}

void test_sort_ascend()
{
    //////////////////////////////////////////
    // dlist_bubble_sort
    //////////////////////////////////////////
 
    int  i;
    dlistnode_t *nod;
    dlist_p      A;
    int  v[] = {2,46,5,17,1,2,3,99,12,56,66,21};
    A = dlist_create();
    for (i=0; i<sizeof(v)/sizeof(v[0]); i++){
        nod = dlist_node_create(v[i]);
        dlist_push_back(A, nod);
    }
    printf("dlist_traverse A (%d nodes):/n", dlist_size(A));
    dlist_traverse(A, my_traverse_dlistnode_printf, 0, 0);
    dlist_bubble_sort(A, 0, 0);
    printf("dlist_traverse A after dlist_bubble_sort (%d nodes):/n", dlist_size(A));
    dlist_traverse(A, my_traverse_dlistnode_printf, 0, 0);

    dlist_destroy(A, 0, 0);
#if defined(_CRTDBG_MAP_ALLOC)
    _CrtDumpMemoryLeaks();
#endif
}

void test_sort_descend()
{
    //////////////////////////////////////////
    // dlist_bubble_sort
    //////////////////////////////////////////
 
    int  i;
    dlistnode_t *nod;
    dlist_p      A;
    int  v[] = {2,46,5,17,1,2,3,99,12,56,66,21};
    A = dlist_create();
    for (i=0; i<sizeof(v)/sizeof(v[0]); i++){
        nod = dlist_node_create(v[i]);
        dlist_push_back(A, nod);
    }
    printf("dlist_traverse A (%d nodes):/n", dlist_size(A));
    dlist_traverse(A, my_traverse_dlistnode_printf, 0, 0);
    dlist_bubble_sort(A, my_dlist_sort_nodes_descend, 0);
    printf("dlist_traverse A after dlist_bubble_sort (%d nodes):/n", dlist_size(A));
    dlist_traverse(A, my_traverse_dlistnode_printf, 0, 0);

    dlist_destroy(A, 0, 0);
#if defined(_CRTDBG_MAP_ALLOC)
    _CrtDumpMemoryLeaks();
#endif
}
void test_merge_sort()
{
    //////////////////////////////////////////
    // dlist_bubble_sort
    // dlist_merge_sort
    //////////////////////////////////////////
 
    int  i;
    dlistnode_t *nod;
    dlist_p      A, B;
    int  vA[] = {2,46,5,17,1,2,3,99,12,56,66,21};
    int  vB[] = {67,54,32,97,11,12,23,9,112,46,37,22};
    // create list A
    A = dlist_create();
    for (i=0; i<sizeof(vA)/sizeof(vA[0]); i++){
        nod = dlist_node_create(vA[i]);
        dlist_push_back(A, nod);
    }
    printf("dlist_traverse A (%d nodes):/n", dlist_size(A));
    dlist_traverse(A, my_traverse_dlistnode_printf, 0, 0);
    // create list B
    B = dlist_create();
    for (i=0; i<sizeof(vB)/sizeof(vB[0]); i++){
        nod = dlist_node_create(vB[i]);
        dlist_push_back(B, nod);
    }
    printf("dlist_traverse B (%d nodes):/n", dlist_size(B));
    dlist_traverse(B, my_traverse_dlistnode_printf, 0, 0);
    // sort A and B with same compare function
    dlist_bubble_sort(A, my_dlist_sort_nodes_ascend, 0);
    dlist_bubble_sort(B, my_dlist_sort_nodes_ascend, 0);
    printf("dlist_traverse A after dlist_bubble_sort (%d nodes):/n", dlist_size(A));
    dlist_traverse(A, my_traverse_dlistnode_printf, 0, 0);
    printf("dlist_traverse B after dlist_bubble_sort (%d nodes):/n", dlist_size(B));
    dlist_traverse(B, my_traverse_dlistnode_printf, 0, 0);
    // merge sort A with B
    dlist_merge_sort(A, B, my_dlist_sort_nodes_ascend, 0);
    printf("dlist_traverse A after dlist_merge_sort (%d nodes):/n", dlist_size(A));
    dlist_traverse(A, my_traverse_dlistnode_printf, 0, 0);
    printf("dlist_traverse B after dlist_merge_sort (%d nodes):/n", dlist_size(B));
    dlist_traverse(B, my_traverse_dlistnode_printf, 0, 0);

    dlist_destroy(B, 0, 0);
    dlist_destroy(A, 0, 0);
#if defined(_CRTDBG_MAP_ALLOC)
    _CrtDumpMemoryLeaks();
#endif
}