1*0Sstevel@tonic-gate /*
2*0Sstevel@tonic-gate * CDDL HEADER START
3*0Sstevel@tonic-gate *
4*0Sstevel@tonic-gate * The contents of this file are subject to the terms of the
5*0Sstevel@tonic-gate * Common Development and Distribution License, Version 1.0 only
6*0Sstevel@tonic-gate * (the "License"). You may not use this file except in compliance
7*0Sstevel@tonic-gate * with the License.
8*0Sstevel@tonic-gate *
9*0Sstevel@tonic-gate * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
10*0Sstevel@tonic-gate * or http://www.opensolaris.org/os/licensing.
11*0Sstevel@tonic-gate * See the License for the specific language governing permissions
12*0Sstevel@tonic-gate * and limitations under the License.
13*0Sstevel@tonic-gate *
14*0Sstevel@tonic-gate * When distributing Covered Code, include this CDDL HEADER in each
15*0Sstevel@tonic-gate * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
16*0Sstevel@tonic-gate * If applicable, add the following below this CDDL HEADER, with the
17*0Sstevel@tonic-gate * fields enclosed by brackets "[]" replaced with your own identifying
18*0Sstevel@tonic-gate * information: Portions Copyright [yyyy] [name of copyright owner]
19*0Sstevel@tonic-gate *
20*0Sstevel@tonic-gate * CDDL HEADER END
21*0Sstevel@tonic-gate */
22*0Sstevel@tonic-gate /*
23*0Sstevel@tonic-gate * Copyright 2003 Sun Microsystems, Inc. All rights reserved.
24*0Sstevel@tonic-gate * Use is subject to license terms.
25*0Sstevel@tonic-gate */
26*0Sstevel@tonic-gate
27*0Sstevel@tonic-gate #pragma ident "%Z%%M% %I% %E% SMI"
28*0Sstevel@tonic-gate
29*0Sstevel@tonic-gate #include <stdlib.h>
30*0Sstevel@tonic-gate #include <stdio.h>
31*0Sstevel@tonic-gate #include <string.h>
32*0Sstevel@tonic-gate #include <errno.h>
33*0Sstevel@tonic-gate
34*0Sstevel@tonic-gate #include "volume_dlist.h"
35*0Sstevel@tonic-gate
36*0Sstevel@tonic-gate #define _volume_dlist_C
37*0Sstevel@tonic-gate
38*0Sstevel@tonic-gate /*
39*0Sstevel@tonic-gate * public constant definitions
40*0Sstevel@tonic-gate */
41*0Sstevel@tonic-gate const boolean_t ASCENDING = TRUE; /* list ordering */
42*0Sstevel@tonic-gate const boolean_t DESCENDING = FALSE;
43*0Sstevel@tonic-gate const boolean_t AT_TAIL = TRUE; /* list insertion location */
44*0Sstevel@tonic-gate const boolean_t AT_HEAD = FALSE;
45*0Sstevel@tonic-gate
46*0Sstevel@tonic-gate /*
47*0Sstevel@tonic-gate * determine if the list contains an item
48*0Sstevel@tonic-gate * that points at the object
49*0Sstevel@tonic-gate */
50*0Sstevel@tonic-gate boolean_t
dlist_contains(dlist_t * list,void * obj,int (compare)(void *,void *))51*0Sstevel@tonic-gate dlist_contains(
52*0Sstevel@tonic-gate dlist_t *list,
53*0Sstevel@tonic-gate void *obj,
54*0Sstevel@tonic-gate int (compare)(void *, void *))
55*0Sstevel@tonic-gate {
56*0Sstevel@tonic-gate return (dlist_find(list, obj, compare) != NULL);
57*0Sstevel@tonic-gate }
58*0Sstevel@tonic-gate
59*0Sstevel@tonic-gate /*
60*0Sstevel@tonic-gate * locate the item in the list that points at the object
61*0Sstevel@tonic-gate */
62*0Sstevel@tonic-gate dlist_t *
dlist_find(dlist_t * list,void * obj,int (compare)(void *,void *))63*0Sstevel@tonic-gate dlist_find(
64*0Sstevel@tonic-gate dlist_t *list,
65*0Sstevel@tonic-gate void *obj,
66*0Sstevel@tonic-gate int (compare)(void *, void *))
67*0Sstevel@tonic-gate {
68*0Sstevel@tonic-gate dlist_t *iter;
69*0Sstevel@tonic-gate
70*0Sstevel@tonic-gate for (iter = list; iter != NULL; iter = iter->next) {
71*0Sstevel@tonic-gate if ((compare)(obj, iter->obj) == 0) {
72*0Sstevel@tonic-gate return (iter);
73*0Sstevel@tonic-gate }
74*0Sstevel@tonic-gate }
75*0Sstevel@tonic-gate
76*0Sstevel@tonic-gate return (NULL);
77*0Sstevel@tonic-gate }
78*0Sstevel@tonic-gate
79*0Sstevel@tonic-gate /*
80*0Sstevel@tonic-gate * insert item into list in the desired order (ascending or descending)
81*0Sstevel@tonic-gate * using the comparison function provided.
82*0Sstevel@tonic-gate *
83*0Sstevel@tonic-gate * In the for loop, iter marks current position in the list
84*0Sstevel@tonic-gate * and item is the item to be inserted.
85*0Sstevel@tonic-gate *
86*0Sstevel@tonic-gate * Iterate the list and find the correct place to insert temp.
87*0Sstevel@tonic-gate *
88*0Sstevel@tonic-gate * if (ascending && compare(item, iter) <= 0 ||
89*0Sstevel@tonic-gate * (descending && compare(item, iter) >= 0)
90*0Sstevel@tonic-gate * item goes before iter
91*0Sstevel@tonic-gate * else
92*0Sstevel@tonic-gate * item goes after iter
93*0Sstevel@tonic-gate */
94*0Sstevel@tonic-gate dlist_t *
dlist_insert_ordered(dlist_t * item,dlist_t * list,boolean_t ascending,int (compare)(void *,void *))95*0Sstevel@tonic-gate dlist_insert_ordered(
96*0Sstevel@tonic-gate dlist_t *item,
97*0Sstevel@tonic-gate dlist_t *list,
98*0Sstevel@tonic-gate boolean_t ascending,
99*0Sstevel@tonic-gate int (compare)(void *, void *))
100*0Sstevel@tonic-gate {
101*0Sstevel@tonic-gate dlist_t *head = NULL;
102*0Sstevel@tonic-gate dlist_t *iter = NULL;
103*0Sstevel@tonic-gate int result = 0;
104*0Sstevel@tonic-gate
105*0Sstevel@tonic-gate if (list == NULL) {
106*0Sstevel@tonic-gate
107*0Sstevel@tonic-gate head = item;
108*0Sstevel@tonic-gate
109*0Sstevel@tonic-gate } else {
110*0Sstevel@tonic-gate
111*0Sstevel@tonic-gate head = list;
112*0Sstevel@tonic-gate
113*0Sstevel@tonic-gate for (iter = list; iter != NULL; iter = iter->next) {
114*0Sstevel@tonic-gate
115*0Sstevel@tonic-gate result = (compare)(item->obj, iter->obj);
116*0Sstevel@tonic-gate
117*0Sstevel@tonic-gate if ((ascending && (result <= 0)) ||
118*0Sstevel@tonic-gate (!ascending && (result >= 0))) {
119*0Sstevel@tonic-gate
120*0Sstevel@tonic-gate if (iter == head) {
121*0Sstevel@tonic-gate head = item;
122*0Sstevel@tonic-gate item->next = iter;
123*0Sstevel@tonic-gate iter->prev = item;
124*0Sstevel@tonic-gate } else {
125*0Sstevel@tonic-gate item->prev = iter->prev;
126*0Sstevel@tonic-gate item->prev->next = item;
127*0Sstevel@tonic-gate iter->prev = item;
128*0Sstevel@tonic-gate item->next = iter;
129*0Sstevel@tonic-gate }
130*0Sstevel@tonic-gate break;
131*0Sstevel@tonic-gate }
132*0Sstevel@tonic-gate
133*0Sstevel@tonic-gate if (iter->next == NULL) {
134*0Sstevel@tonic-gate /* end of list, so item becomes the new end */
135*0Sstevel@tonic-gate iter->next = item;
136*0Sstevel@tonic-gate item->prev = iter;
137*0Sstevel@tonic-gate break;
138*0Sstevel@tonic-gate }
139*0Sstevel@tonic-gate }
140*0Sstevel@tonic-gate }
141*0Sstevel@tonic-gate
142*0Sstevel@tonic-gate return (head);
143*0Sstevel@tonic-gate }
144*0Sstevel@tonic-gate
145*0Sstevel@tonic-gate /*
146*0Sstevel@tonic-gate * Remove the first node pointing to same content as item from list,
147*0Sstevel@tonic-gate * clear it's next and prev pointers, return new list head.
148*0Sstevel@tonic-gate *
149*0Sstevel@tonic-gate * The caller is responsible for freeing the removed item if it is no
150*0Sstevel@tonic-gate * longer needed.
151*0Sstevel@tonic-gate *
152*0Sstevel@tonic-gate * The comparison function should be of the form:
153*0Sstevel@tonic-gate *
154*0Sstevel@tonic-gate * int compare(void *obj1, void* obj2);
155*0Sstevel@tonic-gate *
156*0Sstevel@tonic-gate * When called, obj1 will be the object passed into
157*0Sstevel@tonic-gate * dlist_remove_equivalent_item and obj2 will be an object pointed to
158*0Sstevel@tonic-gate * by an item in the list.
159*0Sstevel@tonic-gate *
160*0Sstevel@tonic-gate * The function should return 0 if the two objects are equivalent The
161*0Sstevel@tonic-gate * function should return nonzero otherwise
162*0Sstevel@tonic-gate *
163*0Sstevel@tonic-gate * @param list
164*0Sstevel@tonic-gate * the list containing the item to remove
165*0Sstevel@tonic-gate *
166*0Sstevel@tonic-gate * @param obj
167*0Sstevel@tonic-gate * the object with which to compare each item
168*0Sstevel@tonic-gate *
169*0Sstevel@tonic-gate * @param compare
170*0Sstevel@tonic-gate * the comparison function, passed obj and the obj member
171*0Sstevel@tonic-gate * of each item, to return 0 if item should be removed
172*0Sstevel@tonic-gate *
173*0Sstevel@tonic-gate * @param removed
174*0Sstevel@tonic-gate * RETURN: the removed item, or NULL if none was found
175*0Sstevel@tonic-gate *
176*0Sstevel@tonic-gate * @return the first element of the resulting list
177*0Sstevel@tonic-gate */
178*0Sstevel@tonic-gate dlist_t *
dlist_remove_equivalent_item(dlist_t * list,void * obj,int (compare)(void *,void *),dlist_t ** removed)179*0Sstevel@tonic-gate dlist_remove_equivalent_item(
180*0Sstevel@tonic-gate dlist_t *list,
181*0Sstevel@tonic-gate void *obj,
182*0Sstevel@tonic-gate int (compare)(void *, void *),
183*0Sstevel@tonic-gate dlist_t **removed)
184*0Sstevel@tonic-gate {
185*0Sstevel@tonic-gate dlist_t *item;
186*0Sstevel@tonic-gate
187*0Sstevel@tonic-gate *removed = NULL;
188*0Sstevel@tonic-gate
189*0Sstevel@tonic-gate if (list == NULL) {
190*0Sstevel@tonic-gate return (list);
191*0Sstevel@tonic-gate }
192*0Sstevel@tonic-gate
193*0Sstevel@tonic-gate item = dlist_find(list, obj, compare);
194*0Sstevel@tonic-gate if (item == NULL) {
195*0Sstevel@tonic-gate return (list);
196*0Sstevel@tonic-gate }
197*0Sstevel@tonic-gate
198*0Sstevel@tonic-gate *removed = item;
199*0Sstevel@tonic-gate
200*0Sstevel@tonic-gate return (dlist_remove(item));
201*0Sstevel@tonic-gate }
202*0Sstevel@tonic-gate
203*0Sstevel@tonic-gate /*
204*0Sstevel@tonic-gate * Remove an item from its list. Return the resulting list.
205*0Sstevel@tonic-gate *
206*0Sstevel@tonic-gate * @param item
207*0Sstevel@tonic-gate * the item to remove, with prev and next pointers
208*0Sstevel@tonic-gate * set to NULL
209*0Sstevel@tonic-gate *
210*0Sstevel@tonic-gate * @return the first element of the resulting list
211*0Sstevel@tonic-gate */
212*0Sstevel@tonic-gate dlist_t *
dlist_remove(dlist_t * item)213*0Sstevel@tonic-gate dlist_remove(
214*0Sstevel@tonic-gate dlist_t *item)
215*0Sstevel@tonic-gate {
216*0Sstevel@tonic-gate dlist_t *head = NULL;
217*0Sstevel@tonic-gate
218*0Sstevel@tonic-gate if (item != NULL) {
219*0Sstevel@tonic-gate if (item->next != NULL) {
220*0Sstevel@tonic-gate item->next->prev = item->prev;
221*0Sstevel@tonic-gate head = item->next;
222*0Sstevel@tonic-gate }
223*0Sstevel@tonic-gate
224*0Sstevel@tonic-gate if (item->prev != NULL) {
225*0Sstevel@tonic-gate item->prev->next = item->next;
226*0Sstevel@tonic-gate head = item->prev;
227*0Sstevel@tonic-gate }
228*0Sstevel@tonic-gate
229*0Sstevel@tonic-gate item->next = NULL;
230*0Sstevel@tonic-gate item->prev = NULL;
231*0Sstevel@tonic-gate
232*0Sstevel@tonic-gate /* Find head of list */
233*0Sstevel@tonic-gate for (; head != NULL && head->prev != NULL; head = head->prev);
234*0Sstevel@tonic-gate }
235*0Sstevel@tonic-gate
236*0Sstevel@tonic-gate return (head);
237*0Sstevel@tonic-gate }
238*0Sstevel@tonic-gate
239*0Sstevel@tonic-gate /*
240*0Sstevel@tonic-gate * append item to list, either beginning or end
241*0Sstevel@tonic-gate */
242*0Sstevel@tonic-gate dlist_t *
dlist_append(dlist_t * item,dlist_t * list,boolean_t attail)243*0Sstevel@tonic-gate dlist_append(
244*0Sstevel@tonic-gate dlist_t *item,
245*0Sstevel@tonic-gate dlist_t *list,
246*0Sstevel@tonic-gate boolean_t attail)
247*0Sstevel@tonic-gate {
248*0Sstevel@tonic-gate dlist_t *head = list;
249*0Sstevel@tonic-gate
250*0Sstevel@tonic-gate if (list == NULL) {
251*0Sstevel@tonic-gate
252*0Sstevel@tonic-gate head = item;
253*0Sstevel@tonic-gate
254*0Sstevel@tonic-gate } else if (item == NULL) {
255*0Sstevel@tonic-gate
256*0Sstevel@tonic-gate head = list;
257*0Sstevel@tonic-gate
258*0Sstevel@tonic-gate } else if (attail) {
259*0Sstevel@tonic-gate
260*0Sstevel@tonic-gate dlist_t *iter;
261*0Sstevel@tonic-gate
262*0Sstevel@tonic-gate /* append to end */
263*0Sstevel@tonic-gate for (iter = head; iter->next != NULL; iter = iter->next);
264*0Sstevel@tonic-gate
265*0Sstevel@tonic-gate iter->next = item;
266*0Sstevel@tonic-gate item->prev = iter;
267*0Sstevel@tonic-gate
268*0Sstevel@tonic-gate } else {
269*0Sstevel@tonic-gate /* insert at begining */
270*0Sstevel@tonic-gate item->next = head;
271*0Sstevel@tonic-gate head->prev = item;
272*0Sstevel@tonic-gate head = item;
273*0Sstevel@tonic-gate }
274*0Sstevel@tonic-gate
275*0Sstevel@tonic-gate return (head);
276*0Sstevel@tonic-gate }
277*0Sstevel@tonic-gate
278*0Sstevel@tonic-gate /*
279*0Sstevel@tonic-gate * Create a dlist_t element for the given object and append to list.
280*0Sstevel@tonic-gate *
281*0Sstevel@tonic-gate * @param object
282*0Sstevel@tonic-gate * the obj member of the dlist_t element to be created
283*0Sstevel@tonic-gate *
284*0Sstevel@tonic-gate * @param list
285*0Sstevel@tonic-gate * the list to which to append the new dlist_t element
286*0Sstevel@tonic-gate *
287*0Sstevel@tonic-gate * @param attail
288*0Sstevel@tonic-gate * whether to append at the beginning (AT_HEAD) or end
289*0Sstevel@tonic-gate * (AT_TAIL) of the list
290*0Sstevel@tonic-gate *
291*0Sstevel@tonic-gate * @return 0
292*0Sstevel@tonic-gate * if successful
293*0Sstevel@tonic-gate *
294*0Sstevel@tonic-gate * @return ENOMEM
295*0Sstevel@tonic-gate * if a dlist_t could not be allocated
296*0Sstevel@tonic-gate */
297*0Sstevel@tonic-gate int
dlist_append_object(void * object,dlist_t ** list,boolean_t attail)298*0Sstevel@tonic-gate dlist_append_object(
299*0Sstevel@tonic-gate void *object,
300*0Sstevel@tonic-gate dlist_t **list,
301*0Sstevel@tonic-gate boolean_t attail)
302*0Sstevel@tonic-gate {
303*0Sstevel@tonic-gate dlist_t *item = dlist_new_item(object);
304*0Sstevel@tonic-gate
305*0Sstevel@tonic-gate if (item == NULL) {
306*0Sstevel@tonic-gate return (ENOMEM);
307*0Sstevel@tonic-gate }
308*0Sstevel@tonic-gate
309*0Sstevel@tonic-gate *list = dlist_append(item, *list, attail);
310*0Sstevel@tonic-gate
311*0Sstevel@tonic-gate return (0);
312*0Sstevel@tonic-gate }
313*0Sstevel@tonic-gate
314*0Sstevel@tonic-gate /*
315*0Sstevel@tonic-gate * Appends list2 to the end of list1.
316*0Sstevel@tonic-gate *
317*0Sstevel@tonic-gate * Returns the resulting list.
318*0Sstevel@tonic-gate */
319*0Sstevel@tonic-gate dlist_t *
dlist_append_list(dlist_t * list1,dlist_t * list2)320*0Sstevel@tonic-gate dlist_append_list(
321*0Sstevel@tonic-gate dlist_t *list1,
322*0Sstevel@tonic-gate dlist_t *list2)
323*0Sstevel@tonic-gate {
324*0Sstevel@tonic-gate dlist_t *iter;
325*0Sstevel@tonic-gate
326*0Sstevel@tonic-gate if (list1 == NULL) {
327*0Sstevel@tonic-gate return (list2);
328*0Sstevel@tonic-gate }
329*0Sstevel@tonic-gate
330*0Sstevel@tonic-gate if (list2 != NULL) {
331*0Sstevel@tonic-gate /* Find last element of list1 */
332*0Sstevel@tonic-gate for (iter = list1; iter->next != NULL; iter = iter->next);
333*0Sstevel@tonic-gate
334*0Sstevel@tonic-gate iter->next = list2;
335*0Sstevel@tonic-gate list2->prev = iter;
336*0Sstevel@tonic-gate }
337*0Sstevel@tonic-gate
338*0Sstevel@tonic-gate return (list1);
339*0Sstevel@tonic-gate }
340*0Sstevel@tonic-gate
341*0Sstevel@tonic-gate /*
342*0Sstevel@tonic-gate * compute number of items in list
343*0Sstevel@tonic-gate */
344*0Sstevel@tonic-gate int
dlist_length(dlist_t * list)345*0Sstevel@tonic-gate dlist_length(
346*0Sstevel@tonic-gate dlist_t *list)
347*0Sstevel@tonic-gate {
348*0Sstevel@tonic-gate dlist_t *iter;
349*0Sstevel@tonic-gate int length = 0;
350*0Sstevel@tonic-gate
351*0Sstevel@tonic-gate for (iter = list; iter != NULL; iter = iter->next)
352*0Sstevel@tonic-gate ++length;
353*0Sstevel@tonic-gate
354*0Sstevel@tonic-gate return (length);
355*0Sstevel@tonic-gate }
356*0Sstevel@tonic-gate
357*0Sstevel@tonic-gate /*
358*0Sstevel@tonic-gate * Allocate a new dlist_t structure and initialize the opaque object
359*0Sstevel@tonic-gate * pointer the input object.
360*0Sstevel@tonic-gate *
361*0Sstevel@tonic-gate * @return A new dlist_t structure for the given object, or NULL
362*0Sstevel@tonic-gate * if the memory could not be allocated.
363*0Sstevel@tonic-gate */
364*0Sstevel@tonic-gate dlist_t *
dlist_new_item(void * obj)365*0Sstevel@tonic-gate dlist_new_item(
366*0Sstevel@tonic-gate void *obj)
367*0Sstevel@tonic-gate {
368*0Sstevel@tonic-gate dlist_t *item = (dlist_t *)calloc(1, sizeof (dlist_t));
369*0Sstevel@tonic-gate
370*0Sstevel@tonic-gate if (item != NULL) {
371*0Sstevel@tonic-gate item->obj = obj;
372*0Sstevel@tonic-gate }
373*0Sstevel@tonic-gate
374*0Sstevel@tonic-gate return (item);
375*0Sstevel@tonic-gate }
376*0Sstevel@tonic-gate
377*0Sstevel@tonic-gate /*
378*0Sstevel@tonic-gate * Traverse the list pointed to by head and free each
379*0Sstevel@tonic-gate * list node. If freefunc is non-NULL, call freefunc
380*0Sstevel@tonic-gate * for each node's object.
381*0Sstevel@tonic-gate */
382*0Sstevel@tonic-gate void
dlist_free_items(dlist_t * head,void (freefunc (void *)))383*0Sstevel@tonic-gate dlist_free_items(
384*0Sstevel@tonic-gate dlist_t *head,
385*0Sstevel@tonic-gate void (freefunc(void *)))
386*0Sstevel@tonic-gate {
387*0Sstevel@tonic-gate while (head != NULL) {
388*0Sstevel@tonic-gate dlist_t *item = head;
389*0Sstevel@tonic-gate head = head->next;
390*0Sstevel@tonic-gate
391*0Sstevel@tonic-gate if (freefunc != NULL) {
392*0Sstevel@tonic-gate freefunc(item->obj);
393*0Sstevel@tonic-gate }
394*0Sstevel@tonic-gate
395*0Sstevel@tonic-gate free((void *) item);
396*0Sstevel@tonic-gate }
397*0Sstevel@tonic-gate }
398*0Sstevel@tonic-gate
399*0Sstevel@tonic-gate /*
400*0Sstevel@tonic-gate * Order the given list such that the number of similar elements
401*0Sstevel@tonic-gate * adjacent to each other are minimized.
402*0Sstevel@tonic-gate *
403*0Sstevel@tonic-gate * The algorithm is:
404*0Sstevel@tonic-gate *
405*0Sstevel@tonic-gate * 1. Sort similar items into categories. Two elements are considered
406*0Sstevel@tonic-gate * similar if the given compare function returns 0.
407*0Sstevel@tonic-gate *
408*0Sstevel@tonic-gate * 2. Create a new list by iterating through each category and
409*0Sstevel@tonic-gate * selecting an element from the category with the most elements.
410*0Sstevel@tonic-gate * Avoid choosing an element from the last category chosen.
411*0Sstevel@tonic-gate *
412*0Sstevel@tonic-gate * @param list
413*0Sstevel@tonic-gate * the list to order
414*0Sstevel@tonic-gate *
415*0Sstevel@tonic-gate * @param compare
416*0Sstevel@tonic-gate * the comparison function, passed the obj members
417*0Sstevel@tonic-gate * of two items, to return 0 if the items can be
418*0Sstevel@tonic-gate * considered similar
419*0Sstevel@tonic-gate *
420*0Sstevel@tonic-gate * @return the first element of the resulting list
421*0Sstevel@tonic-gate */
422*0Sstevel@tonic-gate dlist_t *
dlist_separate_similar_elements(dlist_t * list,int (compare)(void *,void *))423*0Sstevel@tonic-gate dlist_separate_similar_elements(
424*0Sstevel@tonic-gate dlist_t *list,
425*0Sstevel@tonic-gate int(compare)(void *, void *))
426*0Sstevel@tonic-gate {
427*0Sstevel@tonic-gate dlist_t **categories = NULL;
428*0Sstevel@tonic-gate dlist_t *item;
429*0Sstevel@tonic-gate int ncategories = 0;
430*0Sstevel@tonic-gate int max_elements;
431*0Sstevel@tonic-gate int lastcat;
432*0Sstevel@tonic-gate
433*0Sstevel@tonic-gate /*
434*0Sstevel@tonic-gate * First, sort like items into categories, according to
435*0Sstevel@tonic-gate * the passed-in compare function
436*0Sstevel@tonic-gate */
437*0Sstevel@tonic-gate for (item = list; item != NULL; ) {
438*0Sstevel@tonic-gate dlist_t *removed;
439*0Sstevel@tonic-gate
440*0Sstevel@tonic-gate /* Remove this item from the list */
441*0Sstevel@tonic-gate list = dlist_remove(item);
442*0Sstevel@tonic-gate
443*0Sstevel@tonic-gate /* Create new category */
444*0Sstevel@tonic-gate categories = (dlist_t **)realloc(
445*0Sstevel@tonic-gate categories, ++ncategories * sizeof (dlist_t *));
446*0Sstevel@tonic-gate categories[ncategories - 1] = item;
447*0Sstevel@tonic-gate
448*0Sstevel@tonic-gate /* Add like items to same category */
449*0Sstevel@tonic-gate list = dlist_remove_equivalent_item(
450*0Sstevel@tonic-gate list, item->obj, compare, &removed);
451*0Sstevel@tonic-gate while (removed != NULL) {
452*0Sstevel@tonic-gate /* Add removed item to category */
453*0Sstevel@tonic-gate dlist_append(removed, item, AT_TAIL);
454*0Sstevel@tonic-gate list = dlist_remove_equivalent_item(
455*0Sstevel@tonic-gate list, item->obj, compare, &removed);
456*0Sstevel@tonic-gate }
457*0Sstevel@tonic-gate
458*0Sstevel@tonic-gate item = list;
459*0Sstevel@tonic-gate }
460*0Sstevel@tonic-gate
461*0Sstevel@tonic-gate /*
462*0Sstevel@tonic-gate * Next, create a new list, minimizing the number of adjacent
463*0Sstevel@tonic-gate * elements from the same category
464*0Sstevel@tonic-gate */
465*0Sstevel@tonic-gate list = NULL;
466*0Sstevel@tonic-gate lastcat = -1;
467*0Sstevel@tonic-gate do {
468*0Sstevel@tonic-gate int i;
469*0Sstevel@tonic-gate int curcat;
470*0Sstevel@tonic-gate
471*0Sstevel@tonic-gate /*
472*0Sstevel@tonic-gate * Find the category with the most elements, other than
473*0Sstevel@tonic-gate * the last category chosen
474*0Sstevel@tonic-gate */
475*0Sstevel@tonic-gate max_elements = 0;
476*0Sstevel@tonic-gate for (i = 0; i < ncategories; i++) {
477*0Sstevel@tonic-gate int nelements;
478*0Sstevel@tonic-gate
479*0Sstevel@tonic-gate if (i == lastcat) {
480*0Sstevel@tonic-gate continue;
481*0Sstevel@tonic-gate }
482*0Sstevel@tonic-gate
483*0Sstevel@tonic-gate nelements = dlist_length(categories[i]);
484*0Sstevel@tonic-gate if (nelements > max_elements) {
485*0Sstevel@tonic-gate max_elements = nelements;
486*0Sstevel@tonic-gate curcat = i;
487*0Sstevel@tonic-gate }
488*0Sstevel@tonic-gate }
489*0Sstevel@tonic-gate
490*0Sstevel@tonic-gate /* If no elements were found, use the last category chosen */
491*0Sstevel@tonic-gate if (max_elements == 0 && lastcat >= 0) {
492*0Sstevel@tonic-gate max_elements = dlist_length(categories[lastcat]);
493*0Sstevel@tonic-gate curcat = lastcat;
494*0Sstevel@tonic-gate }
495*0Sstevel@tonic-gate
496*0Sstevel@tonic-gate /* Was a category with elements found? */
497*0Sstevel@tonic-gate if (max_elements != 0) {
498*0Sstevel@tonic-gate /* Remove first element of chosen category */
499*0Sstevel@tonic-gate item = categories[curcat];
500*0Sstevel@tonic-gate categories[curcat] = dlist_remove(item);
501*0Sstevel@tonic-gate
502*0Sstevel@tonic-gate /* Add removed element to resulting list */
503*0Sstevel@tonic-gate list = dlist_append(item, list, AT_TAIL);
504*0Sstevel@tonic-gate
505*0Sstevel@tonic-gate lastcat = curcat;
506*0Sstevel@tonic-gate }
507*0Sstevel@tonic-gate } while (max_elements != 0);
508*0Sstevel@tonic-gate
509*0Sstevel@tonic-gate free(categories);
510*0Sstevel@tonic-gate
511*0Sstevel@tonic-gate return (list);
512*0Sstevel@tonic-gate }
513