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