4 * The contents of this file are subject to the terms of the
5 * Common Development and Distribution License, Version 1.0 only
6 * (the "License"). You may not use this file except in compliance
9 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
10 * or http://www.opensolaris.org/os/licensing.
11 * See the License for the specific language governing permissions
12 * and limitations under the License.
14 * When distributing Covered Code, include this CDDL HEADER in each
15 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
16 * If applicable, add the following below this CDDL HEADER, with the
17 * fields enclosed by brackets "[]" replaced with your own identifying
18 * information: Portions Copyright [yyyy] [name of copyright owner]
23 * Copyright 2003 Sun Microsystems, Inc. All rights reserved.
24 * Use is subject to license terms.
27 #pragma ident "%Z%%M% %I% %E% SMI"
34 #include "volume_dlist.h"
36 #define _volume_dlist_C
39 * public constant definitions
41 const boolean_t ASCENDING
= TRUE
; /* list ordering */
42 const boolean_t DESCENDING
= FALSE
;
43 const boolean_t AT_TAIL
= TRUE
; /* list insertion location */
44 const boolean_t AT_HEAD
= FALSE
;
47 * determine if the list contains an item
48 * that points at the object
54 int (compare
)(void *, void *))
56 return (dlist_find(list
, obj
, compare
) != NULL
);
60 * locate the item in the list that points at the object
66 int (compare
)(void *, void *))
70 for (iter
= list
; iter
!= NULL
; iter
= iter
->next
) {
71 if ((compare
)(obj
, iter
->obj
) == 0) {
80 * insert item into list in the desired order (ascending or descending)
81 * using the comparison function provided.
83 * In the for loop, iter marks current position in the list
84 * and item is the item to be inserted.
86 * Iterate the list and find the correct place to insert temp.
88 * if (ascending && compare(item, iter) <= 0 ||
89 * (descending && compare(item, iter) >= 0)
90 * item goes before iter
92 * item goes after iter
99 int (compare
)(void *, void *))
101 dlist_t
*head
= NULL
;
102 dlist_t
*iter
= NULL
;
113 for (iter
= list
; iter
!= NULL
; iter
= iter
->next
) {
115 result
= (compare
)(item
->obj
, iter
->obj
);
117 if ((ascending
&& (result
<= 0)) ||
118 (!ascending
&& (result
>= 0))) {
125 item
->prev
= iter
->prev
;
126 item
->prev
->next
= item
;
133 if (iter
->next
== NULL
) {
134 /* end of list, so item becomes the new end */
146 * Remove the first node pointing to same content as item from list,
147 * clear it's next and prev pointers, return new list head.
149 * The caller is responsible for freeing the removed item if it is no
152 * The comparison function should be of the form:
154 * int compare(void *obj1, void* obj2);
156 * When called, obj1 will be the object passed into
157 * dlist_remove_equivalent_item and obj2 will be an object pointed to
158 * by an item in the list.
160 * The function should return 0 if the two objects are equivalent The
161 * function should return nonzero otherwise
164 * the list containing the item to remove
167 * the object with which to compare each item
170 * the comparison function, passed obj and the obj member
171 * of each item, to return 0 if item should be removed
174 * RETURN: the removed item, or NULL if none was found
176 * @return the first element of the resulting list
179 dlist_remove_equivalent_item(
182 int (compare
)(void *, void *),
193 item
= dlist_find(list
, obj
, compare
);
200 return (dlist_remove(item
));
204 * Remove an item from its list. Return the resulting list.
207 * the item to remove, with prev and next pointers
210 * @return the first element of the resulting list
216 dlist_t
*head
= NULL
;
219 if (item
->next
!= NULL
) {
220 item
->next
->prev
= item
->prev
;
224 if (item
->prev
!= NULL
) {
225 item
->prev
->next
= item
->next
;
232 /* Find head of list */
233 for (; head
!= NULL
&& head
->prev
!= NULL
; head
= head
->prev
);
240 * append item to list, either beginning or end
248 dlist_t
*head
= list
;
254 } else if (item
== NULL
) {
263 for (iter
= head
; iter
->next
!= NULL
; iter
= iter
->next
);
269 /* insert at begining */
279 * Create a dlist_t element for the given object and append to list.
282 * the obj member of the dlist_t element to be created
285 * the list to which to append the new dlist_t element
288 * whether to append at the beginning (AT_HEAD) or end
289 * (AT_TAIL) of the list
295 * if a dlist_t could not be allocated
303 dlist_t
*item
= dlist_new_item(object
);
309 *list
= dlist_append(item
, *list
, attail
);
315 * Appends list2 to the end of list1.
317 * Returns the resulting list.
331 /* Find last element of list1 */
332 for (iter
= list1
; iter
->next
!= NULL
; iter
= iter
->next
);
342 * compute number of items in list
351 for (iter
= list
; iter
!= NULL
; iter
= iter
->next
)
358 * Allocate a new dlist_t structure and initialize the opaque object
359 * pointer the input object.
361 * @return A new dlist_t structure for the given object, or NULL
362 * if the memory could not be allocated.
368 dlist_t
*item
= (dlist_t
*)calloc(1, sizeof (dlist_t
));
378 * Traverse the list pointed to by head and free each
379 * list node. If freefunc is non-NULL, call freefunc
380 * for each node's object.
385 void (freefunc(void *)))
387 while (head
!= NULL
) {
388 dlist_t
*item
= head
;
391 if (freefunc
!= NULL
) {
400 * Order the given list such that the number of similar elements
401 * adjacent to each other are minimized.
405 * 1. Sort similar items into categories. Two elements are considered
406 * similar if the given compare function returns 0.
408 * 2. Create a new list by iterating through each category and
409 * selecting an element from the category with the most elements.
410 * Avoid choosing an element from the last category chosen.
416 * the comparison function, passed the obj members
417 * of two items, to return 0 if the items can be
420 * @return the first element of the resulting list
423 dlist_separate_similar_elements(
425 int(compare
)(void *, void *))
427 dlist_t
**categories
= NULL
;
434 * First, sort like items into categories, according to
435 * the passed-in compare function
437 for (item
= list
; item
!= NULL
; ) {
440 /* Remove this item from the list */
441 list
= dlist_remove(item
);
443 /* Create new category */
444 categories
= (dlist_t
**)realloc(
445 categories
, ++ncategories
* sizeof (dlist_t
*));
446 categories
[ncategories
- 1] = item
;
448 /* Add like items to same category */
449 list
= dlist_remove_equivalent_item(
450 list
, item
->obj
, compare
, &removed
);
451 while (removed
!= NULL
) {
452 /* Add removed item to category */
453 dlist_append(removed
, item
, AT_TAIL
);
454 list
= dlist_remove_equivalent_item(
455 list
, item
->obj
, compare
, &removed
);
462 * Next, create a new list, minimizing the number of adjacent
463 * elements from the same category
472 * Find the category with the most elements, other than
473 * the last category chosen
476 for (i
= 0; i
< ncategories
; i
++) {
483 nelements
= dlist_length(categories
[i
]);
484 if (nelements
> max_elements
) {
485 max_elements
= nelements
;
490 /* If no elements were found, use the last category chosen */
491 if (max_elements
== 0 && lastcat
>= 0) {
492 max_elements
= dlist_length(categories
[lastcat
]);
496 /* Was a category with elements found? */
497 if (max_elements
!= 0) {
498 /* Remove first element of chosen category */
499 item
= categories
[curcat
];
500 categories
[curcat
] = dlist_remove(item
);
502 /* Add removed element to resulting list */
503 list
= dlist_append(item
, list
, AT_TAIL
);
507 } while (max_elements
!= 0);