--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/usr/src/cmd/lvm/metassist/common/volume_dlist.c	Tue Jun 02 18:56:50 2009 +0900
@@ -0,0 +1,512 @@
+/*
+ * CDDL HEADER START
+ *
+ * The contents of this file are subject to the terms of the
+ * Common Development and Distribution License, Version 1.0 only
+ * (the "License").  You may not use this file except in compliance
+ * with the License.
+ *
+ * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
+ * or http://www.opensolaris.org/os/licensing.
+ * See the License for the specific language governing permissions
+ * and limitations under the License.
+ *
+ * When distributing Covered Code, include this CDDL HEADER in each
+ * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
+ * If applicable, add the following below this CDDL HEADER, with the
+ * fields enclosed by brackets "[]" replaced with your own identifying
+ * information: Portions Copyright [yyyy] [name of copyright owner]
+ *
+ * CDDL HEADER END
+ */
+/*
+ * Copyright 2003 Sun Microsystems, Inc.  All rights reserved.
+ * Use is subject to license terms.
+ */
+
+#pragma ident	"@(#)volume_dlist.c	1.2	05/06/08 SMI"
+
+#include <stdlib.h>
+#include <stdio.h>
+#include <string.h>
+#include <errno.h>
+
+#include "volume_dlist.h"
+
+#define	_volume_dlist_C
+
+/*
+ * public constant definitions
+ */
+const	boolean_t	ASCENDING	= TRUE;	/* list ordering */
+const	boolean_t	DESCENDING	= FALSE;
+const	boolean_t	AT_TAIL		= TRUE;	/* list insertion location */
+const	boolean_t	AT_HEAD		= FALSE;
+
+/*
+ * determine if the list contains an item
+ * that points at the object
+ */
+boolean_t
+dlist_contains(
+	dlist_t  *list,
+	void	 *obj,
+	int	(compare)(void *, void *))
+{
+	return (dlist_find(list, obj, compare) != NULL);
+}
+
+/*
+ * locate the item in the list that points at the object
+ */
+dlist_t *
+dlist_find(
+	dlist_t  *list,
+	void	 *obj,
+	int	(compare)(void *, void *))
+{
+	dlist_t  *iter;
+
+	for (iter = list; iter != NULL; iter = iter->next) {
+	    if ((compare)(obj, iter->obj) == 0) {
+		return (iter);
+	    }
+	}
+
+	return (NULL);
+}
+
+/*
+ * insert item into list in the desired order (ascending or descending)
+ * using the comparison function provided.
+ *
+ * In the for loop, iter marks current position in the list
+ * and item is the item to be inserted.
+ *
+ * Iterate the list and find the correct place to insert temp.
+ *
+ * if (ascending && compare(item, iter) <= 0 ||
+ *    (descending && compare(item, iter) >= 0)
+ *     item goes before iter
+ * else
+ *     item goes after iter
+ */
+dlist_t *
+dlist_insert_ordered(
+	dlist_t	*item,
+	dlist_t	*list,
+	boolean_t	ascending,
+	int	(compare)(void *, void *))
+{
+	dlist_t	*head   = NULL;
+	dlist_t	*iter   = NULL;
+	int	result = 0;
+
+	if (list == NULL) {
+
+	    head = item;
+
+	} else {
+
+	    head = list;
+
+	    for (iter = list; iter != NULL; iter = iter->next) {
+
+		result = (compare)(item->obj, iter->obj);
+
+		if ((ascending && (result <= 0)) ||
+			(!ascending && (result >= 0))) {
+
+		    if (iter == head) {
+			head = item;
+			item->next = iter;
+			iter->prev = item;
+		    } else {
+			item->prev = iter->prev;
+			item->prev->next = item;
+			iter->prev = item;
+			item->next = iter;
+		    }
+		    break;
+		}
+
+		if (iter->next == NULL) {
+		    /* end of list, so item becomes the new end */
+		    iter->next = item;
+		    item->prev = iter;
+		    break;
+		}
+	    }
+	}
+
+	return (head);
+}
+
+/*
+ * Remove the first node pointing to same content as item from list,
+ * clear it's next and prev pointers, return new list head.
+ *
+ * The caller is responsible for freeing the removed item if it is no
+ * longer needed.
+ *
+ * The comparison function should be of the form:
+ *
+ *     int compare(void *obj1, void* obj2);
+ *
+ * When called, obj1 will be the object passed into
+ * dlist_remove_equivalent_item and obj2 will be an object pointed to
+ * by an item in the list.
+ *
+ * The function should return 0 if the two objects are equivalent The
+ * function should return nonzero otherwise
+ *
+ * @param       list
+ *              the list containing the item to remove
+ *
+ * @param       obj
+ *              the object with which to compare each item
+ *
+ * @param       compare
+ *              the comparison function, passed obj and the obj member
+ *              of each item, to return 0 if item should be removed
+ *
+ * @param       removed
+ *              RETURN: the removed item, or NULL if none was found
+ *
+ * @return      the first element of the resulting list
+ */
+dlist_t *
+dlist_remove_equivalent_item(
+	dlist_t	*list,
+	void	*obj,
+	int	(compare)(void *, void *),
+	dlist_t **removed)
+{
+	dlist_t	*item;
+
+	*removed = NULL;
+
+	if (list == NULL) {
+	    return (list);
+	}
+
+	item = dlist_find(list, obj, compare);
+	if (item == NULL) {
+	    return (list);
+	}
+
+	*removed = item;
+
+	return (dlist_remove(item));
+}
+
+/*
+ * Remove an item from its list.  Return the resulting list.
+ *
+ * @param       item
+ *              the item to remove, with prev and next pointers
+ *              set to NULL
+ *
+ * @return      the first element of the resulting list
+ */
+dlist_t *
+dlist_remove(
+	dlist_t	*item)
+{
+	dlist_t *head = NULL;
+
+	if (item != NULL) {
+	    if (item->next != NULL) {
+		item->next->prev = item->prev;
+		head = item->next;
+	    }
+
+	    if (item->prev != NULL) {
+		item->prev->next = item->next;
+		head = item->prev;
+	    }
+
+	    item->next = NULL;
+	    item->prev = NULL;
+
+	    /* Find head of list */
+	    for (; head != NULL && head->prev != NULL; head = head->prev);
+	}
+
+	return (head);
+}
+
+/*
+ * append item to list, either beginning or end
+ */
+dlist_t *
+dlist_append(
+	dlist_t	*item,
+	dlist_t	*list,
+	boolean_t	attail)
+{
+	dlist_t	*head = list;
+
+	if (list == NULL) {
+
+	    head = item;
+
+	} else if (item == NULL) {
+
+	    head = list;
+
+	} else if (attail) {
+
+	    dlist_t *iter;
+
+	    /* append to end */
+	    for (iter = head; iter->next != NULL; iter = iter->next);
+
+	    iter->next = item;
+	    item->prev = iter;
+
+	} else {
+	    /* insert at begining */
+	    item->next = head;
+	    head->prev = item;
+	    head = item;
+	}
+
+	return (head);
+}
+
+/*
+ * Create a dlist_t element for the given object and append to list.
+ *
+ * @param       object
+ *              the obj member of the dlist_t element to be created
+ *
+ * @param       list
+ *              the list to which to append the new dlist_t element
+ *
+ * @param       attail
+ *              whether to append at the beginning (AT_HEAD) or end
+ *              (AT_TAIL) of the list
+ *
+ * @return      0
+ *              if successful
+ *
+ * @return      ENOMEM
+ *              if a dlist_t could not be allocated
+ */
+int
+dlist_append_object(
+	void *object,
+	dlist_t **list,
+	boolean_t attail)
+{
+	dlist_t *item = dlist_new_item(object);
+
+	if (item == NULL) {
+	    return (ENOMEM);
+	}
+
+	*list = dlist_append(item, *list, attail);
+
+	return (0);
+}
+
+/*
+ * Appends list2 to the end of list1.
+ *
+ * Returns the resulting list.
+ */
+dlist_t *
+dlist_append_list(
+	dlist_t *list1,
+	dlist_t *list2)
+{
+	dlist_t *iter;
+
+	if (list1 == NULL) {
+	    return (list2);
+	}
+
+	if (list2 != NULL) {
+	    /* Find last element of list1 */
+	    for (iter = list1; iter->next != NULL; iter = iter->next);
+
+	    iter->next = list2;
+	    list2->prev = iter;
+	}
+
+	return (list1);
+}
+
+/*
+ * compute number of items in list
+ */
+int
+dlist_length(
+	dlist_t	*list)
+{
+	dlist_t	*iter;
+	int	length = 0;
+
+	for (iter = list; iter != NULL; iter = iter->next)
+	    ++length;
+
+	return (length);
+}
+
+/*
+ * Allocate a new dlist_t structure and initialize the opaque object
+ * pointer the input object.
+ *
+ * @return      A new dlist_t structure for the given object, or NULL
+ *              if the memory could not be allocated.
+ */
+dlist_t *
+dlist_new_item(
+	void	*obj)
+{
+	dlist_t	*item = (dlist_t *)calloc(1, sizeof (dlist_t));
+
+	if (item != NULL) {
+	    item->obj = obj;
+	}
+
+	return (item);
+}
+
+/*
+ * Traverse the list pointed to by head and free each
+ * list node.  If freefunc is non-NULL, call freefunc
+ * for each node's object.
+ */
+void
+dlist_free_items(
+	dlist_t	*head,
+	void (freefunc(void *)))
+{
+	while (head != NULL) {
+	    dlist_t *item = head;
+	    head = head->next;
+
+	    if (freefunc != NULL) {
+		freefunc(item->obj);
+	    }
+
+	    free((void *) item);
+	}
+}
+
+/*
+ * Order the given list such that the number of similar elements
+ * adjacent to each other are minimized.
+ *
+ * The algorithm is:
+ *
+ * 1. Sort similar items into categories.  Two elements are considered
+ *    similar if the given compare function returns 0.
+ *
+ * 2. Create a new list by iterating through each category and
+ *    selecting an element from the category with the most elements.
+ *    Avoid choosing an element from the last category chosen.
+ *
+ * @param       list
+ *              the list to order
+ *
+ * @param       compare
+ *              the comparison function, passed the obj members
+ *              of two items, to return 0 if the items can be
+ *              considered similar
+ *
+ * @return      the first element of the resulting list
+ */
+dlist_t *
+dlist_separate_similar_elements(
+	dlist_t *list,
+	int(compare)(void *, void *))
+{
+	dlist_t **categories = NULL;
+	dlist_t *item;
+	int ncategories = 0;
+	int max_elements;
+	int lastcat;
+
+	/*
+	 * First, sort like items into categories, according to
+	 * the passed-in compare function
+	 */
+	for (item = list; item != NULL; ) {
+	    dlist_t *removed;
+
+	    /* Remove this item from the list */
+	    list = dlist_remove(item);
+
+	    /* Create new category */
+	    categories = (dlist_t **)realloc(
+		categories, ++ncategories * sizeof (dlist_t *));
+	    categories[ncategories - 1] = item;
+
+	    /* Add like items to same category */
+	    list = dlist_remove_equivalent_item(
+		list, item->obj, compare, &removed);
+	    while (removed != NULL) {
+		/* Add removed item to category */
+		dlist_append(removed, item, AT_TAIL);
+		list = dlist_remove_equivalent_item(
+		    list, item->obj, compare, &removed);
+	    }
+
+	    item = list;
+	}
+
+	/*
+	 * Next, create a new list, minimizing the number of adjacent
+	 * elements from the same category
+	 */
+	list = NULL;
+	lastcat = -1;
+	do {
+	    int i;
+	    int curcat;
+
+		/*
+		 * Find the category with the most elements, other than
+		 * the last category chosen
+		 */
+	    max_elements = 0;
+	    for (i = 0; i < ncategories; i++) {
+		int nelements;
+
+		if (i == lastcat) {
+		    continue;
+		}
+
+		nelements = dlist_length(categories[i]);
+		if (nelements > max_elements) {
+		    max_elements = nelements;
+		    curcat = i;
+		}
+	    }
+
+	    /* If no elements were found, use the last category chosen */
+	    if (max_elements == 0 && lastcat >= 0) {
+		max_elements = dlist_length(categories[lastcat]);
+		curcat = lastcat;
+	    }
+
+	    /* Was a category with elements found? */
+	    if (max_elements != 0) {
+		/* Remove first element of chosen category */
+		item = categories[curcat];
+		categories[curcat] = dlist_remove(item);
+
+		/* Add removed element to resulting list */
+		list = dlist_append(item, list, AT_TAIL);
+
+		lastcat = curcat;
+	    }
+	} while (max_elements != 0);
+
+	free(categories);
+
+	return (list);
+}