|
0
|
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 "@(#)volume_dlist.c 1.2 05/06/08 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
|
|
|
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 *
|
|
|
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 *
|
|
|
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 *
|
|
|
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 *
|
|
|
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 *
|
|
|
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
|
|
|
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 *
|
|
|
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
|
|
|
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 *
|
|
|
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
|
|
|
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 *
|
|
|
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 }
|
