双链常用操作2

#ifndef LINKED_LIST_H
#define LINKED_LIST_H

typedef struct LinkedListNode {
    const void *data;
	struct LinkedListNode *prev;
    struct LinkedListNode *next;
} LinkedListNode; 

typedef struct {
    LinkedListNode *head;
    LinkedListNode *current;
    LinkedListNode *tail;
    int size;
} LinkedList;

#define SORT_CALLBACK(func) \
            ((int (*) (void *data, LinkedListNode *, LinkedListNode *)) func)

LinkedList *linked_list_construct();
LinkedList *linked_list_clone(LinkedList *list);
void linked_list_destroy_clone(LinkedList *list);
void linked_list_destroy(LinkedList *list);

void linked_list_prepend_node(LinkedList *list, LinkedListNode *node);
void linked_list_append_node(LinkedList *list, LinkedListNode *node);
void linked_list_remove_node(LinkedList *list, LinkedListNode *node);

void linked_list_seek_start(LinkedList *list);
void linked_list_seek_end(LinkedList *list);
LinkedListNode *linked_list_get_next_node(LinkedList *list);
LinkedListNode *linked_list_get_previous_node(LinkedList *list);

int linked_list_is_empty(LinkedList *list);
int linked_list_get_size(LinkedList *list);

void linked_list_sort(LinkedList *list, 
                      int (*) (void *data, LinkedListNode *, LinkedListNode *),
                      void *data); 

LinkedListNode *linked_list_node_construct(const void *data);
void linked_list_node_destroy(LinkedListNode *node);
const void *linked_list_node_get_data(LinkedListNode *node);

#endif

----------------------------

#include "linkedlist.h"
#include <stdio.h>
#include <stdlib.h>

#ifdef DMALLOC
#include "dmalloc.h"
#endif

LinkedList *linked_list_construct() {
	
    LinkedList *list = NULL;

	/*
     * Allocate space for the object and set all fields to zero.
     */
    list = calloc(1, sizeof(LinkedList));

    return list;
}

LinkedList *linked_list_clone(LinkedList *list) {

    LinkedList *construct_list = NULL;
    LinkedListNode *node = NULL;

    if (list == NULL) {
        return NULL;
    }

    construct_list = calloc(1, sizeof(LinkedList));
    
    linked_list_seek_start(list); 

    while ((node = linked_list_get_next_node(list)) != NULL) {

        node = linked_list_node_construct(linked_list_node_get_data(node));

        if (node == NULL) {
            linked_list_destroy_clone(construct_list);
            return NULL;
        }

        linked_list_append_node(construct_list, node);
        node = NULL;
    }

    return construct_list;
}

void linked_list_destroy_clone(LinkedList *list) {

    if (list == NULL) {
        return;
    }

    /*
     * FIXME: Free all the nodes. 
     */
    free(list);
}

void linked_list_destroy(LinkedList *list) {

    LinkedListNode *node = NULL, *next = NULL;

    if (list == NULL) {
        return;
    }

    linked_list_seek_start(list);
    node = linked_list_get_next_node(list);
    while (node != NULL) {
        next = linked_list_get_next_node(list);
        linked_list_node_destroy(node);
        node = next;
    }

    list->head = NULL;
    list->tail = NULL;
    list->current = NULL;
    list->size = 0;
    free(list);
}

void linked_list_prepend_node(LinkedList *list, LinkedListNode *node) {

    LinkedListNode *head = NULL;

    if (list == NULL || node == NULL) return;

    /*
     * Get a pointer to head of the linkedlist
     */
	head = list->head;
	
    /*
     * If the head is empty, then the tail is empty, too, so the node becomes
     * the list.  Otherwise, put the node at the beginning of the list and 
     * connect all the pointers appropriately
     */
	if (head == NULL) {

		list->head = list->tail = node;
	} else {
        head->prev = node;
	    node->next = head;
		list->head = node;
	}

    list->size++;

}

void linked_list_append_node(LinkedList *list, LinkedListNode *node) {

    LinkedListNode *tail = NULL;

    if (list == NULL || node == NULL) return;

    /*
     * Get a pointer to tail of the linkedlist
     */
	tail = list->tail;
	
    /*
     * If the tail is empty, then the head is empty, too, so the node becomes
     * the list.  Otherwise, put the node at the end of the list and connect
     * all the pointers appropriately
     */
	if (tail == NULL) {

		list->tail = list->head = node;
	} else {
        tail->next = node;
	    node->prev = tail;
		list->tail = node;
	}

    list->size++;
}

void linked_list_remove_node(LinkedList *list, LinkedListNode *node) {

	LinkedListNode *prev = NULL;
	
	if (list == NULL || node == NULL) {
        return;
    }
	
	prev = node->prev;
	
    /*
     * If the node is not first one in the list, then connect its
     * predecessor node to its successor node (next direction).
     */
	if (prev != NULL) {
        prev->next = node->next;
    }

    /*
     * If the node is not the last one in the list, then connect its
     * predecessor node to its successor node (prev direction).
     */
	if (node->next != NULL) {
        node->next->prev = prev;
    }

    /*
     * If the node is the first one in the list, then point the head to 
     * the next node in the list.
     *
     * FIXME: Why is this separated from above?
     */
    if (node == list->head) {
        list->head = node->next;
    }

    /*
     * If the node is the last one in the list, then point the tail to
     * the previous node in the list.
     *
     * FIXME: Why is this separated from above?
     */
	if (node == list->tail) {
		if (prev != NULL) {
		    list->tail = prev;
		} else {
			list->tail = list->head;
		}
	}
	
	node->prev = NULL;
	node->next = NULL;

    list->size--;
}

void linked_list_seek_start(LinkedList *list) {

	if (list == NULL) {
        return;
    }
	
	list->current = list->head;
}

void linked_list_seek_end(LinkedList *list) {

    if (list == NULL) {
        return;
    }

    list->current = list->tail;
}

LinkedListNode *linked_list_get_next_node(LinkedList *list) {

	LinkedListNode *node = NULL;
	
	if (list == NULL) {
        return NULL;
    }
	
	if (list->current == NULL) {
        return NULL;
    }
		
	node = list->current;
		
	list->current = list->current->next;
	
	return node;
}

LinkedListNode *linked_list_get_previous_node(LinkedList *list) {

	LinkedListNode *node = NULL;
	
	if (list == NULL) {
        return NULL;
    }
	
	if (list->current == NULL) {
        return NULL;
    }
		
	node = list->current;
		
	list->current = list->current->prev;
	
	return node;
}

int linked_list_is_empty(LinkedList *list) {

	if (list == NULL) {
        return 1;
    }
	
    return list->head == NULL;
}

int linked_list_get_size(LinkedList *list) {

    if (list == NULL) {
        return 0;
    }

    return list->size;
}

LinkedListNode *linked_list_node_construct(const void *data) {

	LinkedListNode *node = NULL;

    node = calloc(1, sizeof(LinkedListNode));

	node->data = data;
	
    return node;
}

void linked_list_node_destroy(LinkedListNode *node) {
	
	if (node == NULL) {
        return;
    }
		
	free(node);
}

const void *linked_list_node_get_data(LinkedListNode *node) {

	if (node == NULL) {
        return NULL;
    }
		
    return node->data;
}

/*
 * FIXME: This is taken and adapted from some site on the net that made it 
 *        freely available.  As far as I can tell it's doing an in place 
 *        merge sort.  I don't really understand the code though.  I should 
 *        clean it up and comment it so that it makes sense to me.
 */
void linked_list_sort(LinkedList *list, 
                      int (*compare) 
                      (void *data, LinkedListNode *, LinkedListNode *), 
                      void *data) {

    LinkedListNode *node1 = NULL, *node2 = NULL, *e = NULL, *tail = NULL;
    int insize = 1, nmerges = 0, node1_size = 0, node2_size = 0, i = 0;

    if (list == NULL) {
        return;
    }

    if (compare == NULL) {
        return;
    }

    while (1) {

        node1 = list->head;
        list->head = NULL;
        tail = NULL;

        nmerges = 0;

        while (node1 != NULL) {
            nmerges++;
            node2 = node1;
            node1_size = 0;
            for (i = 0; i < insize; i++) {
                node1_size++;
                node2 = node2->next;

                if (node2 == NULL) {
                    break;
                }
            }

            node2_size = insize;

            while (node1_size > 0 || (node2_size > 0 && node2 != NULL)) {

                if (node1_size == 0) {
                    e = node2;
                    node2 = node2->next; 
                    node2_size--;
                } else if (node2_size == 0 || node2 == NULL) {
                    e = node1; 
                    node1 = node1->next; 
                    node1_size--;
                } else if (compare(data, node1, node2) <= 0) {
                    e = node1; 
                    node1 = node1->next; 
                    node1_size--;
                } else {
                    e = node2; 
                    node2 = node2->next; 
                    node2_size--;
                }

                if (tail != NULL) {
                    tail->next = e;
                } else {
                    list->head = e;
                }

                e->prev = tail;
                tail = e;
            }
            
            node1 = node2;
        }

        tail->next = NULL;

        if (nmerges <= 1) {
            return;
        }

        insize *= 2;
    }
}