/*
 *
 *   (C) Copyright IBM Corp. 2002, 2003
 *
 *   This program is free software;  you can redistribute it and/or modify
 *   it under the terms of the GNU General Public License as published by
 *   the Free Software Foundation; either version 2 of the License, or
 *   (at your option) any later version.
 *
 *   This program 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 General Public License for more details.
 *
 *   You should have received a copy of the GNU General Public License
 *   along with this program;  if not, write to the Free Software
 *   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
 *
 * Module: list.c
 *
 */

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <errno.h>
#include <unistd.h>
#include <pthread.h>

#include "fullengine.h"
#include "lists.h"
#include "engine.h"
#include "memman.h"


#define INTERNAL_LIST_FOR_EACH(list, el)				\
        for ((el) = ELEMENT_PTR((list)->links.next);			\
	    (((el) != NULL) && ((el) != ELEMENT_PTR(&(list)->links)));	\
	    (el) = ELEMENT_PTR(el->links.next))


/* Insert new_link before link. */
static inline void _insert_link_before(links_t * new_link, links_t * link) {
	link->prev->next = new_link;
	new_link->prev = link->prev;
	link->prev = new_link;
	new_link->next = link;
}

/* Insert new_link after link. */
static inline void _insert_link_after(links_t * new_link, links_t * link) {
	link->next->prev = new_link;
	new_link->next = link->next;
	link->next = new_link;
	new_link->prev = link;
}

static inline void _remove_link(links_t * link) {
	link->prev->next = link->next;
	link->next->prev = link->prev;
	link->next = NULL;
	link->prev = NULL;
}

static inline void set_list_owner(anchor_t * list) {

	list_element_t el;

	INTERNAL_LIST_FOR_EACH(list, el) {
		el->anchor = list;
	}
}

static boolean isa_valid_anchor(anchor_t * anchor) {

	LOG_PROC_EXTRA_ENTRY();

	if (anchor == NULL) {
		LOG_DEBUG("List is NULL.\n");
		LOG_PROC_EXTRA_EXIT_BOOLEAN(FALSE);
		return FALSE;
	}

	if ((anchor->links.next == NULL) ||
	    (anchor->links.prev == NULL)) {
		if (anchor->links.next == NULL) {
			LOG_ERROR("List's next pointer is NULL.\n");
		}
		if (anchor->links.next == NULL) {
			LOG_ERROR("List's previous pointer is NULL.\n");
		}
		LOG_PROC_EXTRA_EXIT_BOOLEAN(FALSE);
		return FALSE;
	}

	LOG_PROC_EXTRA_EXIT_BOOLEAN(TRUE);
	return TRUE;
}


/*
 * Allocate an anchor for a list.
 */
anchor_t * allocate_list(void) {

	anchor_t * anchor;

	LOG_PROC_EXTRA_ENTRY();

	anchor = engine_alloc(sizeof(anchor_t));

	if (anchor != NULL) {
		anchor->links.next = &anchor->links;
		anchor->links.prev = &anchor->links;
	}

	LOG_PROC_EXTRA_EXIT_PTR(anchor);
	return anchor;
}


/*
 * How many elements are in the list?
 */
uint list_count(anchor_t * anchor) {

	LOG_PROC_EXTRA_ENTRY();

	if (!isa_valid_anchor(anchor)) {
		LOG_PROC_EXTRA_EXIT_INT(0);
		return 0;
	}

	LOG_PROC_EXTRA_EXIT_INT(anchor->count);
	return anchor->count;
}


/*
 * Does this list have no elements?
 */
boolean list_empty(anchor_t * anchor) {

	boolean result;

	LOG_PROC_EXTRA_ENTRY();

	if (!isa_valid_anchor(anchor)) {
		LOG_PROC_EXTRA_EXIT_BOOLEAN(TRUE);
		return TRUE;
	}

	LOG_EXTRA("List has %u element%s.\n", anchor->count, (anchor->count) == 1 ? "" : "s");
	result = (anchor->count == 0);

	LOG_PROC_EXTRA_EXIT_BOOLEAN(result);
	return result;
}


/*
 * Find a given thing in the list.  If the thing is in the list, return
 * the element corresponding to the thing.  If the thing is not in the
 * list, return NULL.
 * The "compare" function is used for finding the thing in the list.
 * Each thing in the list will be compared against the thing passed to
 * find_in_list().  When the compare function returns 0, find_in_list()
 * will know that it has found the thing and will return the element
 * corresponding to the thing.  If "compare" is NULL, find_in_list()
 * will compare the given thing pointer agains the thing pointers in
 * the list.
 */
element_t * find_in_list(anchor_t         * anchor,
			 void             * thing,
			 compare_function_t compare,
			 void             * user_data) {

	element_t * element;

	LOG_PROC_EXTRA_ENTRY();

	if (!isa_valid_anchor(anchor)) {
		LOG_PROC_EXTRA_EXIT_PTR(NULL);
		return NULL;
	}

	if (compare != NULL) {
		INTERNAL_LIST_FOR_EACH(anchor, element) {
			if (compare(thing, element->thing, user_data) == 0) {
				LOG_PROC_EXTRA_EXIT_PTR(element);
				return element;
			}
		}
	} else {
		INTERNAL_LIST_FOR_EACH(anchor, element) {
			if (element->thing == thing) {
				LOG_PROC_EXTRA_EXIT_PTR(element);
				return element;
			}
		}
	}

	LOG_PROC_EXTRA_EXIT_PTR(NULL);
	return NULL;
}


/*
 * Delete all the elements in the list, but leave the list anchor.
 * The things in the list are not freed.
 */
void delete_all_elements(anchor_t * anchor) {

	element_t * el;

	LOG_PROC_EXTRA_ENTRY();

	if (!isa_valid_anchor(anchor)) {
		LOG_PROC_EXTRA_EXIT_VOID();
		return;
	}

	el = ELEMENT_PTR(anchor->links.next);
	while ((el != NULL) && (&el->links != &anchor->links)) {
		element_t * next_el = ELEMENT_PTR(el->links.next);

		_remove_link(&el->links);
		memset(el, 0, sizeof(*el));
		engine_free(el);

		el = next_el;
	}

	anchor->count = 0;

	LOG_PROC_EXTRA_EXIT_VOID();
	return;
}


/*
 * Destroy the list -- free the list anchor and all the list
 * elements.  The things in the list are not freed.
 */
void destroy_list(anchor_t * anchor) {

	LOG_PROC_EXTRA_ENTRY();

	if (!isa_valid_anchor(anchor)) {
		LOG_PROC_EXTRA_EXIT_VOID();
		return;
	}

	delete_all_elements(anchor);
	memset(anchor, 0, sizeof(*anchor));
	engine_free(anchor);

	LOG_PROC_EXTRA_EXIT_VOID();
	return;
}


/*
 * Get the thing corresponding to element.
 */
void * get_thing(element_t * element) {

	LOG_PROC_EXTRA_ENTRY();

	if (element == NULL) {
		LOG_PROC_EXTRA_EXIT_PTR(NULL);
		return NULL;
	}

	LOG_PROC_EXTRA_EXIT_PTR(element->thing);
	return element->thing;
}


/*
 * Get the element after the given element in the list.
 */
element_t * next_element(element_t * element) {

	element_t * next_el;

	LOG_PROC_EXTRA_ENTRY();

	if (element == NULL) {
		LOG_PROC_EXTRA_EXIT_PTR(NULL);
		return NULL;
	}

	next_el = ELEMENT_PTR(element->links.next);

	if (&next_el->links == &element->anchor->links) {
		LOG_PROC_EXTRA_EXIT_PTR(NULL);
		return NULL;
	}

	LOG_PROC_EXTRA_EXIT_PTR(next_el);
	return next_el;
}


/*
 * Get the next thing in the list.  *element will be replaced with the
 * element for the next thing.
 */
void * next_thing(element_t * * element) {

	element_t * next_el;
	void * thing;

	LOG_PROC_EXTRA_ENTRY();

	if (*element == NULL) {
		LOG_PROC_EXTRA_EXIT_PTR(NULL);
		return NULL;
	}

	next_el = next_element(*element);

	if (next_el != NULL) {
		*element = next_el;
		thing = next_el->thing;

	} else {
		*element = NULL;
		thing = NULL;
	}

	LOG_PROC_EXTRA_EXIT_PTR(thing);
	return thing;
}


/*
 * Get the element before the given element in the list.
 */
element_t * previous_element(element_t * element) {

	element_t * prev_el;

	LOG_PROC_EXTRA_ENTRY();

	if (element == NULL) {
		LOG_PROC_EXTRA_EXIT_PTR(NULL);
		return NULL;
	}

	prev_el = ELEMENT_PTR(element->links.prev);

	if (&prev_el->links == &element->anchor->links) {
		LOG_PROC_EXTRA_EXIT_PTR(NULL);
		return NULL;
	}

	LOG_PROC_EXTRA_EXIT_PTR(prev_el);
	return prev_el;
}


/*
 * Get the previous thing in the list.  *element will be replaced with
 * the element for the previous thing.
 */
void * previous_thing(element_t * * element) {

	element_t * prev_el;
	void * thing;

	LOG_PROC_EXTRA_ENTRY();

	if (element == NULL) {
		LOG_PROC_EXTRA_EXIT_PTR(NULL);
		return NULL;
	}

	prev_el = previous_element(*element);

	if (prev_el != NULL) {
		*element = prev_el;
		thing = prev_el->thing;

	} else {
		*element = NULL;
		thing = NULL;
	}

	LOG_PROC_EXTRA_EXIT_PTR(thing);
	return thing;
}


/*
 * Get the first thing in the list.  *element will be set to the
 * element for the thing.
 */
void * first_thing(anchor_t    * anchor,
		   element_t * * element) {

	element_t * first_element;
	void * thing;

	LOG_PROC_EXTRA_ENTRY();

	if (!isa_valid_anchor(anchor)) {
		if (element != NULL) {
			*element = NULL;
		}
		LOG_PROC_EXTRA_EXIT_PTR(NULL);
		return NULL;
	}

	first_element = ELEMENT_PTR(anchor->links.next);

	if ((first_element != NULL) && (&first_element->links != &anchor->links)) {
		if (element != NULL) {
			*element = first_element;
		}
		thing = first_element->thing;

	} else {
		if (element != NULL) {
			*element = NULL;
		}
		thing = NULL;
	}

	LOG_PROC_EXTRA_EXIT_PTR(thing);
	return thing;
}


/*
 * Get the last thing in the list.  *element will be set to the
 * element for the thing.
 */
void * last_thing(anchor_t    * anchor,
		  element_t * * element) {

	element_t * last_element;
	void * thing;

	LOG_PROC_EXTRA_ENTRY();

	if (!isa_valid_anchor(anchor)) {
		if (element != NULL) {
			*element = NULL;
		}
		LOG_PROC_EXTRA_EXIT_PTR(NULL);
		return NULL;
	}

	last_element = ELEMENT_PTR(anchor->links.prev);

	if ((last_element != NULL) && (&last_element->links != &anchor->links)) {
		if (element != NULL) {
			*element = last_element;
		}
		thing = last_element->thing;

	} else {
		if (element != NULL) {
			*element = NULL;
		}
		thing = NULL;
	}

	LOG_PROC_EXTRA_EXIT_PTR(thing);
	return thing;
}


/*
 * An internal service routine to insert an element into a list.
 * As an internal function, it is guaranteed that anchor and element are
 * not NULL.
 */
static void _insert_element(anchor_t     * anchor,
			    element_t    * element,
			    insert_flags_t flags,
			    element_t    * ref_element) {

	LOG_PROC_EXTRA_ENTRY();

	if (flags & INSERT_BEFORE) {
		if (ref_element == NULL) {
			ref_element = ELEMENT_PTR(anchor->links.next);
		}
		_insert_link_before(&element->links, &ref_element->links);

	} else {
		if (ref_element == NULL) {
			ref_element = ELEMENT_PTR(anchor->links.prev);
		}
		_insert_link_after(&element->links, &ref_element->links);
	}

	element->anchor = anchor;

	anchor->count++;

	LOG_PROC_EXTRA_EXIT_VOID();
	return;
}


/*
 * Insert an element (with its thing) into the list.  The element MUST
 * NOT be in any list.  The flags indicate where and how the element is
 * inserted.  If the insert succeeds, the element is returned, else NULL
 * is returned.
 * If flags say INSERT_AFTER, the element will be inserted after the
 * ref_element.  If ref_element is NULL, the element will be inserted at
 * the end of the list.
 * If flags say INSERT_BEFORE, the element will be inserted before the
 * ref_element.  If ref_element is NULL, the element will be inserted at
 * the beginning of the list.
 * If the EXCLUSIVE_INSERT flag is set, the Engine will make sure there
 * is only one element in the list that contains the thing.  If there is
 * another element in the list that has the same thing as the element to
 * be inserted, the element in that is already the list is returned.
 */
element_t * insert_element(anchor_t     * anchor,
			   element_t    * element,
			   insert_flags_t flags,
			   element_t    * ref_element) {

	LOG_PROC_EXTRA_ENTRY();

	if (!isa_valid_anchor(anchor)) {
		LOG_PROC_EXTRA_EXIT_PTR(NULL);
		return NULL;
	}

	if (element == NULL) {
		LOG_ERROR("Element to insert is NULL.\n");
		LOG_PROC_EXTRA_EXIT_PTR(NULL);
		return NULL;
	}

	if ((element->links.next != NULL) || (element->links.prev != NULL)) {
		LOG_ERROR("Element is already in a list.\n");
		if (element->links.next != NULL) {
			LOG_EXTRA("Element's next pointer is not NULL.\n");
		}
		if (element->links.prev != NULL) {
			LOG_EXTRA("Element's previous pointer is not NULL.\n");
		}
		LOG_PROC_EXTRA_EXIT_PTR(NULL);
		return NULL;
	}

	if (flags & EXCLUSIVE_INSERT) {
		element_t * el = find_in_list(anchor, element->thing, NULL, NULL);

		if (el != NULL) {
			/* Found the thing in the list.  Return its element. */
			LOG_PROC_EXTRA_EXIT_PTR(el);
			return el;
		}
	}

	_insert_element(anchor, element, flags, ref_element);

	LOG_PROC_EXTRA_EXIT_PTR(element);
	return element;
}


/*
 * Insert a thing into the list.  The flags indicate where and how the
 * thing is inserted.  The list element for the new thing is returned.
 * If flags say INSERT_AFTER, the thing will be inserted after the given
 * element.  If ref_element is NULL, the thing will be inserted at the
 * end of the list.
 * If flags say INSERT_BEFORE, the thing will be inserted before the
 * given element.  If ref_element is NULL, the thing will be inserted at
 * the beginning of the list.
 * If the EXCLUSIVE_INSERT flag is set, the Engine will make sure there
 * is only one element in the list that contains the thing.
 */
element_t * insert_thing(anchor_t     * anchor,
			 void         * thing,
			 insert_flags_t flags,
			 element_t    * ref_element) {

	element_t * new_element;

	LOG_PROC_EXTRA_ENTRY();

	if (!isa_valid_anchor(anchor)) {
		LOG_PROC_EXTRA_EXIT_PTR(NULL);
		return NULL;
	}

	if (flags & EXCLUSIVE_INSERT) {
		element_t * el = find_in_list(anchor, thing, NULL, NULL);

		if (el != NULL) {
			/* Found the thing in the list.  Return its element. */
			LOG_PROC_EXTRA_EXIT_PTR(el);
			return el;
		}
	}

	/* Need to make a new element for the thing. */
	new_element = engine_alloc(sizeof(element_t));

	if (new_element == NULL) {
		LOG_CRITICAL("Error getting memory for a new element.\n");
		LOG_PROC_EXTRA_EXIT_PTR(NULL);
		return NULL;
	}

	new_element->thing = thing;

	_insert_element(anchor, new_element, flags, ref_element);

	LOG_PROC_EXTRA_EXIT_PTR(new_element);
	return new_element;
}


/*
 * Remove the given element from its list.  The element is not freed.
 */
void remove_element(element_t * element) {

	LOG_PROC_EXTRA_ENTRY();

	if (element == NULL) {
		LOG_PROC_EXTRA_EXIT_VOID();
		return;
	}

	if ((element->links.next != NULL) &&
	    (element->links.prev != NULL)) {
		_remove_link(&element->links);

	} else {
		element->links.next = NULL;
		element->links.prev = NULL;
	}

	if (element->anchor != NULL) {
		element->anchor->count--;
		element->anchor = NULL;
	}

	LOG_PROC_EXTRA_EXIT_VOID();
	return;
}


/*
 * Remove the given element from its list, if it is in one, and free it.
 */
void delete_element(element_t * element) {

	LOG_PROC_EXTRA_ENTRY();

	if (element == NULL) {
		LOG_PROC_EXTRA_EXIT_VOID();
		return;
	}

	if ((element->links.next != NULL) &&
	    (element->links.prev != NULL)) {
		_remove_link(&element->links);

	} else {
		element->links.next = NULL;
		element->links.prev = NULL;
	}

	if (element->anchor != NULL) {
		element->anchor->count--;
		element->anchor = NULL;
	}

	memset(element, 0, sizeof(*element));
	engine_free(element);

	LOG_PROC_EXTRA_EXIT_VOID();
	return;
}


/*
 * Remove the given thing from the list.  The thing is not freed.
 * If the thing appears multiple times in the list, all occurrences will
 * be removed.
 */
void remove_thing(anchor_t * anchor,
		  void     * thing) {

	element_t * el;

	LOG_PROC_EXTRA_ENTRY();

	if (!isa_valid_anchor(anchor)) {
		LOG_PROC_EXTRA_EXIT_VOID();
		return;
	}

	el = ELEMENT_PTR(anchor->links.next);
	while (&el->links != &anchor->links) {
		element_t * next_el = ELEMENT_PTR(el->links.next);

		if (el->thing == thing) {
			delete_element(el);
		}

		el = next_el;
	}

	LOG_PROC_EXTRA_EXIT_VOID();
	return;
}


/*
 * Replace the thing in the list with the new_thing.  If thing
 * appears multiple times in the list, all occurrences will
 * be replaced.
 */
int replace_thing(anchor_t * anchor,
		  void     * thing,
		  void     * new_thing) {

	int rc = ENOENT;
	links_t * link;

	LOG_PROC_EXTRA_ENTRY();

	if (!isa_valid_anchor(anchor)) {
		LOG_PROC_EXTRA_EXIT_INT(EINVAL);
		return EINVAL;
	}

	for (link = anchor->links.next; link != &anchor->links; link = link->next) {
		element_t * element = (element_t *) link;
		if (element->thing == thing) {
			element->thing = new_thing;
			rc = 0;
		}
	}

	LOG_PROC_EXTRA_EXIT_INT(rc);
	return rc;
}


/*
 * Make a copy of the given list.
 */
anchor_t * copy_list(anchor_t * anchor) {

	anchor_t  * new_anchor;
	element_t * element;
	element_t * new_element;

	LOG_PROC_EXTRA_ENTRY();

	if (!isa_valid_anchor(anchor)) {
		LOG_PROC_EXTRA_EXIT_PTR(NULL);
		return NULL;
	}

	new_anchor = allocate_list();

	if (new_anchor != NULL) {
		INTERNAL_LIST_FOR_EACH(anchor, element) {
			new_element = engine_alloc(sizeof(element_t));

			if (new_element == NULL) {
				LOG_CRITICAL("Unable to get memory for a new list element.\n");
				destroy_list(new_anchor);
				new_anchor = NULL;
				break;
			}

			new_element->thing = element->thing;
			new_element->anchor = new_anchor;

			_insert_link_before(&new_element->links, &new_anchor->links);
			new_anchor->count++;
		}

	} else {
		LOG_CRITICAL("Unable to get memory for a new list anchor.\n");
	}

	LOG_PROC_EXTRA_EXIT_PTR(new_anchor);
	return new_anchor;
}


/*
 * Staple list2 onto the end of list1.
 * As an internal function, it is guaranteed that anchor1 and anchor2 are
 * not NULL.
 */
static inline void _append_list(anchor_t * anchor1,
				anchor_t * anchor2) {

	LOG_PROC_EXTRA_ENTRY();

	if (list_empty(anchor2)) {
		/* Nothing to append */
                LOG_PROC_EXTRA_EXIT_VOID();
		return;
	}

	if (list_empty(anchor1)) {
		/* Just move the elements from anchor2 to anchor1 */
		*anchor1 = *anchor2;

		anchor2->links.prev->next = &anchor1->links;
		anchor2->links.next->prev = &anchor1->links;

		anchor2->links.next = &anchor2->links;
		anchor2->links.prev = &anchor2->links;

		anchor2->count = 0;

	} else {
		anchor2->links.next->prev = anchor1->links.prev;
		anchor2->links.prev->next = &anchor1->links;

		anchor1->links.prev->next = anchor2->links.next;
		anchor1->links.prev = anchor2->links.prev;

		anchor1->count += anchor2->count;
	}

	/* Mark all the elements in list1 to as belonging to list1. */
	set_list_owner(anchor1);

	/* Make list 2 an empty list. */
	anchor2->links.next = &anchor2->links;
	anchor2->links.prev = &anchor2->links;
	anchor2->count = 0;

	LOG_PROC_EXTRA_EXIT_VOID();
	return;
}


/*
 * Append a copy of the elements in list2 to list1.
 */
int concatenate_lists(anchor_t * anchor1,
		      anchor_t * anchor2) {

	anchor_t * copy_anchor;

	LOG_PROC_EXTRA_ENTRY();

	if (!isa_valid_anchor(anchor1) || !isa_valid_anchor(anchor2)) {
		LOG_PROC_EXTRA_EXIT_INT(EINVAL);
		return EINVAL;
	}

	copy_anchor = copy_list(anchor2);

	if (copy_anchor != NULL) {
		_append_list(anchor1, copy_anchor);
		destroy_list(copy_anchor);

	} else {
		LOG_CRITICAL("Error copying list2.\n");
		LOG_PROC_EXTRA_EXIT_INT(ENOMEM);
		return ENOMEM;
	}

	LOG_PROC_EXTRA_EXIT_INT(0);
	return 0;
}


/*
 * Merge list2 into list1.  If the compare function is NULL, list2 is
 * appended to list1.
 * As an internal function, it is guaranteed that anchor1 and anchor2 are
 * not NULL.
 */
static int _merge_lists(anchor_t         * anchor1,
			anchor_t         * anchor2,
			compare_function_t compare,
			void             * user_data) {

	anchor_t  * tmp_anchor;
	element_t * element1;
	element_t * element2;
	element_t * insert_element;

	LOG_PROC_EXTRA_ENTRY();

	if (list_empty(anchor1) || list_empty(anchor2)) {
		/* One of the lists is empty.  The merge is a simple append. */
		_append_list(anchor1, anchor2);
		LOG_PROC_EXTRA_EXIT_INT(0);
		return 0;
	}

	tmp_anchor = allocate_list();
	
	if (tmp_anchor == NULL) {
		LOG_CRITICAL("Unable to allocate a temporary list anchor.\n");
		LOG_PROC_EXTRA_EXIT_INT(ENOMEM);
		return ENOMEM;
	}

	/*
	 * Transfer the first list to the temporary list anchor and
	 * clear the list from the first list anchor.
	 */
	*tmp_anchor = *anchor1;
	anchor1->links.next->prev = &tmp_anchor->links;
	anchor1->links.prev->next = &tmp_anchor->links;
	anchor1->links.next = &anchor1->links;
	anchor1->links.prev = &anchor1->links;
	anchor1->count = 0;

	/* Mark all the elements in temp list to as belonging to tmp_anchor. */
	set_list_owner(tmp_anchor);

	/*
	 * Insert members of either list, based on the comparison,
	 * back into the first list.
	 */
	element1 = ELEMENT_PTR(tmp_anchor->links.next);
	element2 = ELEMENT_PTR(anchor2->links.next);

	while ((&element1->links != &tmp_anchor->links) ||
	       (&element2->links != &anchor2->links)) {
		if (&element1->links == &tmp_anchor->links) {
			/* List one is empty.  The link to insert
			 * is the one from list two.
			 */
			insert_element = element2;
			element2 = ELEMENT_PTR(element2->links.next);

		} else if (&element2->links == &anchor2->links) {
			/* List two is empty.  The link to insert
			 * is the one from list one.
			 */
			insert_element = element1;
			element1 = ELEMENT_PTR(element1->links.next);

		} else {
			/*
			 * Must compare the two things to see which
			 * one goes first.
			 */
			if (compare(element1->thing, element2->thing, user_data) <= 0) {
				insert_element = element1;
				element1 = ELEMENT_PTR(element1->links.next);

			} else {
				insert_element = element2;
				element2 = ELEMENT_PTR(element2->links.next);
			}
		}

		remove_element(insert_element);
		_insert_element(anchor1,
				insert_element,
				INSERT_BEFORE,
				ELEMENT_PTR(&anchor1->links));
	}

	destroy_list(tmp_anchor);

	LOG_PROC_EXTRA_EXIT_INT(0);
	return 0;
}


int merge_lists(anchor_t         * anchor1,
		anchor_t         * anchor2,
		compare_function_t compare,
		void             * user_data) {

	LOG_PROC_EXTRA_ENTRY();

	if (!isa_valid_anchor(anchor1)) {
		LOG_PROC_EXTRA_EXIT_INT(EINVAL);
		return EINVAL;
	}

	if (!isa_valid_anchor(anchor2)) {
		LOG_ERROR("list2 is not valid.  Nothing to merge.\n");
		LOG_PROC_EXTRA_EXIT_INT(0);
		return 0;
	}

	if (compare == NULL) {
		/* No compare function given.  Append list2 to list1. */
		_append_list(anchor1, anchor2);
		LOG_PROC_EXTRA_EXIT_INT(0);
		return 0;

	} else {
		int rc = _merge_lists(anchor1, anchor2, compare, user_data);
		LOG_PROC_EXTRA_EXIT_INT(rc);
		return rc;
	}
}


/*
 * Quick sort the list.
 * As an internal function, it is guaranteed that anchor is valid and
 * compare is not NULL.
 */
static int _qsort_list(anchor_t         * anchor,
		       compare_function_t compare,
		       void             * user_data) {

	int rc = 0;
	anchor_t * tmp_anchor;

	links_t * link;
	uint list_count;
	uint i;

	LOG_PROC_EXTRA_ENTRY();

	if (anchor->count <= 1) {
		/* This sort is easy.  We're already done. */
		LOG_PROC_EXTRA_EXIT_INT(0);
		return 0;
	}

	tmp_anchor = allocate_list();
	if (tmp_anchor == NULL) {
		LOG_CRITICAL("Error getting memory for a temporary anchor.\n");
		LOG_PROC_EXTRA_EXIT_INT(ENOMEM);
		return ENOMEM;
	}

	/*
	 * Split the list into two (nearly) equal lists.
	 */
	list_count = anchor->count / 2;

	for (i = 0, link = anchor->links.next;
	    i < list_count;
	    i++, link = link->next);

	tmp_anchor->links.next = link;
	tmp_anchor->links.prev = anchor->links.prev;
	anchor->links.prev->next = &tmp_anchor->links;
	anchor->links.prev = link->prev;
	link->prev->next = &anchor->links;
	link->prev = &tmp_anchor->links;

	tmp_anchor->count = anchor->count - list_count;
	anchor->count = list_count;

	/* Mark all the elements in temp list to as belonging to tmp_anchor. */
	set_list_owner(tmp_anchor);

	/* Sort the two sub-lists. */
	rc = _qsort_list(anchor, compare, user_data);

	if (rc == 0) {
		rc = _qsort_list(tmp_anchor, compare, user_data);
	}

	if (rc == 0) {
		/*
		 * Merge the lists back together using the comparison function provided.
		 */
		rc = _merge_lists(anchor, tmp_anchor, compare, user_data);
	}

	LOG_PROC_EXTRA_EXIT_INT(rc);
	return rc;
}


/*
 * Sort the elements in the list.
 */
int sort_list(anchor_t         * anchor,
	      compare_function_t compare,
	      void             * user_data) {

	int rc = 0;
	anchor_t * copy;

	LOG_PROC_EXTRA_ENTRY();

	if (!isa_valid_anchor(anchor)) {
		LOG_PROC_EXTRA_EXIT_INT(0);
		return 0;
	}

	if (compare == NULL) {
		LOG_ERROR("A compare function was not given.\n");
		LOG_PROC_EXTRA_EXIT_INT(EINVAL);
		return EINVAL;
	}

	/* Make a copy of the list in case something goes wrong. */
	copy = copy_list(anchor);
	if (copy == NULL) {
		LOG_CRITICAL("Error making a backup copy of the list.\n");
		LOG_PROC_EXTRA_EXIT_INT(ENOMEM);
		return ENOMEM;
	}

	rc = _qsort_list(anchor, compare, user_data);

	if (rc != 0) {
		/*
		 * The sort failed.  Throw out the working list and replace it
		 * with the backup copy.
		 */
		delete_all_elements(anchor);
		_append_list(anchor, copy);
	}

	destroy_list(copy);

	LOG_PROC_EXTRA_EXIT_INT(0);
	return rc;
}