Mercurial > illumos > onarm
comparison usr/src/cmd/lvm/metassist/common/volume_dlist.c @ 0:c9caec207d52 b86
Initial porting based on b86
author | Koji Uno <koji.uno@sun.com> |
---|---|
date | Tue, 02 Jun 2009 18:56:50 +0900 |
parents | |
children | 1a15d5aaf794 |
comparison
equal
deleted
inserted
replaced
-1:000000000000 | 0:c9caec207d52 |
---|---|
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 } |