OpenMPI 0.1.1

- Main Page
- Related Pages
- Modules
- Data Structures
- Files

- File List
- Globals

opal_list.h
Go to the documentation of this file.
1 /*
2 * Copyright (c) 2004-2005 The Trustees of Indiana University and Indiana
3 * University Research and Technology
4 * Corporation. All rights reserved.
5 * Copyright (c) 2004-2006 The University of Tennessee and The University
6 * of Tennessee Research Foundation. All rights
7 * reserved.
8 * Copyright (c) 2004-2005 High Performance Computing Center Stuttgart,
9 * University of Stuttgart. All rights reserved.
10 * Copyright (c) 2004-2005 The Regents of the University of California.
11 * All rights reserved.
12 * Copyright (c) 2007 Voltaire All rights reserved.
13 * $COPYRIGHT$
14 *
15 * Additional copyrights may follow
16 *
17 * $HEADER$
18 */
19 /**
20 * @file
21 *
22 * The opal_list_t interface is used to provide a generic
23 * doubly-linked list container for Open MPI. It was inspired by (but
24 * is slightly different than) the Stantard Template Library (STL)
25 * std::list class. One notable difference from std::list is that
26 * when an opal_list_t is destroyed, all of the opal_list_item_t
27 * objects that it contains are orphaned -- they are \em not
28 * destroyed.
29 *
30 * The general idea is that opal_list_item_t objects can be put on an
31 * opal_list_t. Hence, you create a new type that derives from
32 * opal_list_item_t; this new type can then be used with opal_list_t
33 * containers.
34 *
35 * NOTE: opal_list_item_t instances can only be on \em one list at a
36 * time. Specifically, if you add an opal_list_item_t to one list,
37 * and then add it to another list (without first removing it from the
38 * first list), you will effectively be hosing the first list. You
39 * have been warned.
40 *
41 * If OPAL_ENABLE_DEBUG is true, a bunch of checks occur, including
42 * some spot checks for a debugging reference count in an attempt to
43 * ensure that an opal_list_item_t is only one *one* list at a time.
44 * Given the highly concurrent nature of this class, these spot checks
45 * cannot guarantee that an item is only one list at a time.
46 * Specifically, since it is a desirable attribute of this class to
47 * not use locks for normal operations, it is possible that two
48 * threads may [erroneously] modify an opal_list_item_t concurrently.
49 *
50 * The only way to guarantee that a debugging reference count is valid
51 * for the duration of an operation is to lock the item_t during the
52 * operation. But this fundamentally changes the desirable attribute
53 * of this class (i.e., no locks). So all we can do is spot-check the
54 * reference count in a bunch of places and check that it is still the
55 * value that we think it should be. But this doesn't mean that you
56 * can run into "unlucky" cases where two threads are concurrently
57 * modifying an item_t, but all the spot checks still return the
58 * "right" values. All we can do is hope that we have enough spot
59 * checks to statistically drive down the possibility of the unlucky
60 * cases happening.
61 */
62
63 #ifndef OPAL_LIST_H
64 #define OPAL_LIST_H
65
66 #include "opal_config.h"
67 #include <stdio.h>
68 #include <stdlib.h>
69 #include "opal/class/opal_object.h"
70
71 #if OPAL_ENABLE_DEBUG
72 /* Need atomics for debugging (reference counting) */
73 #include "opal/sys/atomic.h"
74 #include "opal/threads/mutex.h"
75 #endif
76
77 BEGIN_C_DECLS
78
79 /**
80 * \internal
81 *
82 * The class for the list container.
83 */
84 OPAL_DECLSPEC OBJ_CLASS_DECLARATION(opal_list_t);
85 /**
86 * \internal
87 *
88 * Base class for items that are put in list (opal_list_t) containers.
89 */
90 OPAL_DECLSPEC OBJ_CLASS_DECLARATION(opal_list_item_t);
91
92
93 /**
94 * \internal
95 *
96 * Struct of an opal_list_item_t
97 */
98 struct opal_list_item_t
99 {
100 opal_object_t super;
101 /**< Generic parent class for all Open MPI objects */
102 volatile struct opal_list_item_t *opal_list_next;
103 /**< Pointer to next list item */
104 volatile struct opal_list_item_t *opal_list_prev;
105 /**< Pointer to previous list item */
106 int32_t item_free;
107
108 #if OPAL_ENABLE_DEBUG
109 /** Atomic reference count for debugging */
110 volatile int32_t opal_list_item_refcount;
111 /** The list this item belong to */
112 volatile struct opal_list_t* opal_list_item_belong_to;
113 #endif
114 };
115 /**
116 * Base type for items that are put in a list (opal_list_t) containers.
117 */
118 typedef struct opal_list_item_t opal_list_item_t;
119
120
121 /**
122 * Get the next item in a list.
123 *
124 * @param item A list item.
125 *
126 * @returns The next item in the list
127 */
128 #define opal_list_get_next(item) \
129 ((item) ? ((opal_list_item_t*) ((opal_list_item_t*)(item))->opal_list_next) : NULL)
130
131 /**
132 * Get the next item in a list.
133 *
134 * @param item A list item.
135 *
136 * @returns The next item in the list
137 */
138 #define opal_list_get_prev(item) \
139 ((item) ? ((opal_list_item_t*) ((opal_list_item_t*)(item))->opal_list_prev) : NULL)
140
141
142 /**
143 * \internal
144 *
145 * Struct of an opal_list_t
146 */
147 struct opal_list_t
148 {
149 opal_object_t super;
150 /**< Generic parent class for all Open MPI objects */
151 opal_list_item_t opal_list_sentinel;
152 /**< Head and tail item of the list */
153 volatile size_t opal_list_length;
154 /**< Quick reference to the number of items in the list */
155 };
156 /**
157 * List container type.
158 */
159 typedef struct opal_list_t opal_list_t;
160
161
162 /**
163 * Check for empty list
164 *
165 * @param list The list container
166 *
167 * @returns true if list's size is 0, false otherwise
168 *
169 * This is an O(1) operation.
170 *
171 * This is an inlined function in compilers that support inlining,
172 * so it's usually a cheap operation.
173 */
174 static inline bool opal_list_is_empty(opal_list_t* list)
175 {
176 return (list->opal_list_sentinel.opal_list_next ==
177 &(list->opal_list_sentinel) ? true : false);
178 }
179
180
181 /**
182 * Return the first item on the list (does not remove it).
183 *
184 * @param list The list container
185 *
186 * @returns A pointer to the first item on the list
187 *
188 * This is an O(1) operation to return the first item on the list. It
189 * should be compared against the returned value from
190 * opal_list_get_end() to ensure that the list is not empty.
191 *
192 * This is an inlined function in compilers that support inlining, so
193 * it's usually a cheap operation.
194 */
195 static inline opal_list_item_t* opal_list_get_first(opal_list_t* list)
196 {
197 opal_list_item_t* item = (opal_list_item_t*)list->opal_list_sentinel.opal_list_next;
198 #if OPAL_ENABLE_DEBUG
199 /* Spot check: ensure that the first item is only on one list */
200
201 assert(1 == item->opal_list_item_refcount);
202 assert( list == item->opal_list_item_belong_to );
203 #endif
204
205 return item;
206 }
207
208 /**
209 * Return the last item on the list (does not remove it).
210 *
211 * @param list The list container
212 *
213 * @returns A pointer to the last item on the list
214 *
215 * This is an O(1) operation to return the last item on the list. It
216 * should be compared against the returned value from
217 * opal_list_get_begin() to ensure that the list is not empty.
218 *
219 * This is an inlined function in compilers that support inlining, so
220 * it's usually a cheap operation.
221 */
222 static inline opal_list_item_t* opal_list_get_last(opal_list_t* list)
223 {
224 opal_list_item_t* item = (opal_list_item_t *)list->opal_list_sentinel.opal_list_prev;
225 #if OPAL_ENABLE_DEBUG
226 /* Spot check: ensure that the last item is only on one list */
227
228 assert( 1 == item->opal_list_item_refcount );
229 assert( list == item->opal_list_item_belong_to );
230 #endif
231
232 return item;
233 }
234
235 /**
236 * Return the beginning of the list; an invalid list entry suitable
237 * for comparison only.
238 *
239 * @param list The list container
240 *
241 * @returns A pointer to the beginning of the list.
242 *
243 * This is an O(1) operation to return the beginning of the list.
244 * Similar to the STL, this is a special invalid list item -- it
245 * should \em not be used for storage. It is only suitable for
246 * comparison to other items in the list to see if they are valid or
247 * not; it's ususally used when iterating through the items in a list.
248 *
249 * This is an inlined function in compilers that support inlining, so
250 * it's usually a cheap operation.
251 */
252 static inline opal_list_item_t* opal_list_get_begin(opal_list_t* list)
253 {
254 return &(list->opal_list_sentinel);
255 }
256
257 /**
258 * Return the end of the list; an invalid list entry suitable for
259 * comparison only.
260 *
261 * @param list The list container
262 *
263 * @returns A pointer to the end of the list.
264 *
265 * This is an O(1) operation to return the end of the list.
266 * Similar to the STL, this is a special invalid list item -- it
267 * should \em not be used for storage. It is only suitable for
268 * comparison to other items in the list to see if they are valid or
269 * not; it's ususally used when iterating through the items in a list.
270 *
271 * This is an inlined function in compilers that support inlining, so
272 * it's usually a cheap operation.
273 */
274 static inline opal_list_item_t* opal_list_get_end(opal_list_t* list)
275 {
276 return &(list->opal_list_sentinel);
277 }
278
279
280 /**
281 * Return the number of items in a list
282 *
283 * @param list The list container
284 *
285 * @returns The size of the list (size_t)
286 *
287 * This is an O(1) lookup to return the size of the list.
288 *
289 * This is an inlined function in compilers that support inlining, so
290 * it's usually a cheap operation.
291 *
292 * \warning The size of the list is cached as part of the list. In
293 * the future, calling \c opal_list_splice or \c opal_list_join may
294 * result in this function recomputing the list size, which would be
295 * an O(N) operation. If \c opal_list_splice or \c opal_list_join is
296 * never called on the specified list, this function will always be
297 * O(1).
298 */
299 static inline size_t opal_list_get_size(opal_list_t* list)
300 {
301 #if OPAL_ENABLE_DEBUG && 0
302 /* not sure if we really want this running in devel, as it does
303 * slow things down. Wanted for development of splice / join to
304 * make sure length was reset properly
305 */
306 size_t check_len = 0;
307 opal_list_item_t *item;
308
309 for (item = opal_list_get_first(list) ;
310 item != opal_list_get_end(list) ;
311 item = opal_list_get_next(item)) {
312 check_len++;
313 }
314
315 if (check_len != list->opal_list_length) {
316 fprintf(stderr," Error :: opal_list_get_size - opal_list_length does not match actual list length\n");
317 fflush(stderr);
318 abort();
319 }
320 #endif
321
322 return list->opal_list_length;
323 }
324
325
326 /**
327 * Remove an item from a list.
328 *
329 * @param list The list container
330 * @param item The item to remove
331 *
332 * @returns A pointer to the item on the list previous to the one
333 * that was removed.
334 *
335 * This is an O(1) operation to remove an item from the list. The
336 * forward / reverse pointers in the list are updated and the item is
337 * removed. The list item that is returned is now "owned" by the
338 * caller -- they are responsible for OBJ_RELEASE()'ing it.
339 *
340 * If debugging is enabled (specifically, if --enable-debug was used
341 * to configure Open MPI), this is an O(N) operation because it checks
342 * to see if the item is actually in the list first.
343 *
344 * This is an inlined function in compilers that support inlining, so
345 * it's usually a cheap operation.
346 */
347 static inline opal_list_item_t *opal_list_remove_item
348 (opal_list_t *list, opal_list_item_t *item)
349 {
350 #if OPAL_ENABLE_DEBUG
351 opal_list_item_t *item_ptr;
352 bool found = false;
353
354 /* check to see that the item is in the list */
355 for (item_ptr = opal_list_get_first(list);
356 item_ptr != opal_list_get_end(list);
357 item_ptr = (opal_list_item_t *)(item_ptr->opal_list_next)) {
358 if (item_ptr == (opal_list_item_t *) item) {
359 found = true;
360 break;
361 }
362 }
363 if (!found) {
364 fprintf(stderr," Warning :: opal_list_remove_item - the item %p is not on the list %p \n",(void*) item, (void*) list);
365 fflush(stderr);
366 return (opal_list_item_t *)NULL;
367 }
368
369 assert( list == item->opal_list_item_belong_to );
370 #endif
371
372 /* reset next pointer of previous element */
373 item->opal_list_prev->opal_list_next=item->opal_list_next;
374
375 /* reset previous pointer of next element */
376 item->opal_list_next->opal_list_prev=item->opal_list_prev;
377
378 list->opal_list_length--;
379
380 #if OPAL_ENABLE_DEBUG
381 /* Spot check: ensure that this item is still only on one list */
382
383 OPAL_THREAD_ADD32( &(item->opal_list_item_refcount), -1 );
384 assert(0 == item->opal_list_item_refcount);
385 item->opal_list_item_belong_to = NULL;
386 #endif
387
388 return (opal_list_item_t *)item->opal_list_prev;
389 }
390
391
392 /**
393 * Append an item to the end of the list.
394 *
395 * @param list The list container
396 * @param item The item to append
397 *
398 * This is an O(1) operation to append an item to the end of a list.
399 * The opal_list_item_t is not OBJ_RETAIN()'ed; it is assumed that
400 * "ownership" of the item is passed from the caller to the list.
401 *
402 * This is an inlined function in compilers that support inlining, so
403 * it's usually a cheap operation.
404 */
405
406 #if OPAL_ENABLE_DEBUG
407 #define opal_list_append(l,i) \
408 _opal_list_append(l,i,__FILE__,__LINE__)
409 #else
410 #define opal_list_append(l,i) \
411 _opal_list_append(l,i)
412 #endif /* OPAL_ENABLE_DEBUG */
413
414 static inline void _opal_list_append(opal_list_t *list, opal_list_item_t *item
415 #if OPAL_ENABLE_DEBUG
416 , const char* FILE_NAME, int LINENO
417 #endif /* OPAL_ENABLE_DEBUG */
418 )
419 {
420 opal_list_item_t* sentinel = &(list->opal_list_sentinel);
421 #if OPAL_ENABLE_DEBUG
422 /* Spot check: ensure that this item is previously on no lists */
423
424 assert(0 == item->opal_list_item_refcount);
425 assert( NULL == item->opal_list_item_belong_to );
426 item->super.cls_init_file_name = FILE_NAME;
427 item->super.cls_init_lineno = LINENO;
428 #endif
429
430 /* set new element's previous pointer */
431 item->opal_list_prev = sentinel->opal_list_prev;
432
433 /* reset previous pointer on current last element */
434 sentinel->opal_list_prev->opal_list_next = item;
435
436 /* reset new element's next pointer */
437 item->opal_list_next = sentinel;
438
439 /* reset the list's tail element previous pointer */
440 sentinel->opal_list_prev = item;
441
442 /* increment list element counter */
443 list->opal_list_length++;
444
445 #if OPAL_ENABLE_DEBUG
446 /* Spot check: ensure this item is only on the list that we just
447 appended it to */
448
449 OPAL_THREAD_ADD32( &(item->opal_list_item_refcount), 1 );
450 assert(1 == item->opal_list_item_refcount);
451 item->opal_list_item_belong_to = list;
452 #endif
453 }
454
455
456 /**
457 * Prepend an item to the beginning of the list.
458 *
459 * @param list The list container
460 * @param item The item to prepend
461 *
462 * This is an O(1) operation to prepend an item to the beginning of a
463 * list. The opal_list_item_t is not OBJ_RETAIN()'ed; it is assumed
464 * that "ownership" of the item is passed from the caller to the list.
465 *
466 * This is an inlined function in compilers that support inlining, so
467 * it's usually a cheap operation.
468 */
469 static inline void opal_list_prepend(opal_list_t *list,
470 opal_list_item_t *item)
471 {
472 opal_list_item_t* sentinel = &(list->opal_list_sentinel);
473 #if OPAL_ENABLE_DEBUG
474 /* Spot check: ensure that this item is previously on no lists */
475
476 assert(0 == item->opal_list_item_refcount);
477 assert( NULL == item->opal_list_item_belong_to );
478 #endif
479
480 /* reset item's next pointer */
481 item->opal_list_next = sentinel->opal_list_next;
482
483 /* reset item's previous pointer */
484 item->opal_list_prev = sentinel;
485
486 /* reset previous first element's previous poiner */
487 sentinel->opal_list_next->opal_list_prev = item;
488
489 /* reset head's next pointer */
490 sentinel->opal_list_next = item;
491
492 /* increment list element counter */
493 list->opal_list_length++;
494
495 #if OPAL_ENABLE_DEBUG
496 /* Spot check: ensure this item is only on the list that we just
497 prepended it to */
498
499 OPAL_THREAD_ADD32( &(item->opal_list_item_refcount), 1 );
500 assert(1 == item->opal_list_item_refcount);
501 item->opal_list_item_belong_to = list;
502 #endif
503 }
504
505
506 /**
507 * Remove the first item from the list and return it.
508 *
509 * @param list The list container
510 *
511 * @returns The first item on the list. If the list is empty,
512 * NULL will be returned
513 *
514 * This is an O(1) operation to return the first item on the list. If
515 * the list is not empty, a pointer to the first item in the list will
516 * be returned. Ownership of the item is transferred from the list to
517 * the caller; no calls to OBJ_RETAIN() or OBJ_RELEASE() are invoked.
518 *
519 * This is an inlined function in compilers that support inlining, so
520 * it's usually a cheap operation.
521 */
522 static inline opal_list_item_t *opal_list_remove_first(opal_list_t *list)
523 {
524 /* Removes and returns first item on list.
525 Caller now owns the item and should release the item
526 when caller is done with it.
527 */
528 volatile opal_list_item_t *item;
529 if ( 0 == list->opal_list_length ) {
530 return (opal_list_item_t *)NULL;
531 }
532
533 #if OPAL_ENABLE_DEBUG
534 /* Spot check: ensure that the first item is only on this list */
535
536 assert(1 == list->opal_list_sentinel.opal_list_next->opal_list_item_refcount);
537 #endif
538
539 /* reset list length counter */
540 list->opal_list_length--;
541
542 /* get pointer to first element on the list */
543 item = list->opal_list_sentinel.opal_list_next;
544
545 /* reset previous pointer of next item on the list */
546 item->opal_list_next->opal_list_prev = item->opal_list_prev;
547
548 /* reset the head next pointer */
549 list->opal_list_sentinel.opal_list_next = item->opal_list_next;
550
551 #if OPAL_ENABLE_DEBUG
552 assert( list == item->opal_list_item_belong_to );
553 item->opal_list_item_belong_to = NULL;
554 item->opal_list_prev=(opal_list_item_t *)NULL;
555 item->opal_list_next=(opal_list_item_t *)NULL;
556
557 /* Spot check: ensure that the item we're returning is now on no
558 lists */
559
560 OPAL_THREAD_ADD32( &(item->opal_list_item_refcount), -1 );
561 assert(0 == item->opal_list_item_refcount);
562 #endif
563
564 return (opal_list_item_t *) item;
565 }
566
567
568 /**
569 * Remove the last item from the list and return it.
570 *
571 * @param list The list container
572 *
573 * @returns The last item on the list. If the list is empty,
574 * NULL will be returned
575 *
576 * This is an O(1) operation to return the last item on the list. If
577 * the list is not empty, a pointer to the last item in the list will
578 * be returned. Ownership of the item is transferred from the list to
579 * the caller; no calls to OBJ_RETAIN() or OBJ_RELEASE() are invoked.
580 *
581 * This is an inlined function in compilers that support inlining, so
582 * it's usually a cheap operation.
583 */
584 static inline opal_list_item_t *opal_list_remove_last(opal_list_t *list)
585 {
586 /* Removes, releases and returns last item on list.
587 Caller now owns the item and should release the item
588 when caller is done with it.
589 */
590 volatile opal_list_item_t *item;
591 if ( 0 == list->opal_list_length ) {
592 return (opal_list_item_t *)NULL;
593 }
594
595 #if OPAL_ENABLE_DEBUG
596 /* Spot check: ensure that the first item is only on this list */
597
598 assert(1 == list->opal_list_sentinel.opal_list_prev->opal_list_item_refcount);
599 #endif
600
601 /* reset list length counter */
602 list->opal_list_length--;
603
604 /* get item */
605 item = list->opal_list_sentinel.opal_list_prev;
606
607 /* reset previous pointer on next to last pointer */
608 item->opal_list_prev->opal_list_next = item->opal_list_next;
609
610 /* reset tail's previous pointer */
611 list->opal_list_sentinel.opal_list_prev = item->opal_list_prev;
612
613 #if OPAL_ENABLE_DEBUG
614 assert( list == item->opal_list_item_belong_to );
615 item->opal_list_next = item->opal_list_prev = (opal_list_item_t *)NULL;
616
617 /* Spot check: ensure that the item we're returning is now on no
618 lists */
619
620 OPAL_THREAD_ADD32( &(item->opal_list_item_refcount), -1 );
621 assert(0 == item->opal_list_item_refcount);
622 item->opal_list_item_belong_to = NULL;
623 #endif
624
625 return (opal_list_item_t *) item;
626 }
627
628 /**
629 * Add an item to the list before a given element
630 *
631 * @param list The list container
632 * @param pos List element to insert \c item before
633 * @param item The item to insert
634 *
635 * Inserts \c item before \c pos. This is an O(1) operation.
636 */
637 static inline void opal_list_insert_pos(opal_list_t *list, opal_list_item_t *pos,
638 opal_list_item_t *item)
639 {
640 #if OPAL_ENABLE_DEBUG
641 /* Spot check: ensure that the item we're insertting is currently
642 not on any list */
643
644 assert(0 == item->opal_list_item_refcount);
645 assert( NULL == item->opal_list_item_belong_to );
646 #endif
647
648 /* point item at the existing elements */
649 item->opal_list_next = pos;
650 item->opal_list_prev = pos->opal_list_prev;
651
652 /* splice into the list */
653 pos->opal_list_prev->opal_list_next = item;
654 pos->opal_list_prev = item;
655
656 /* reset list length counter */
657 list->opal_list_length++;
658
659 #if OPAL_ENABLE_DEBUG
660 /* Spot check: double check that this item is only on the list
661 that we just added it to */
662
663 OPAL_THREAD_ADD32( &(item->opal_list_item_refcount), 1 );
664 assert(1 == item->opal_list_item_refcount);
665 item->opal_list_item_belong_to = list;
666 #endif
667 }
668
669 /**
670 * Add an item to the list at a specific index location in the list.
671 *
672 * @param list The list container
673 * @param item The item to insert
674 * @param index Location to add the item
675 *
676 * @returns true if insertion succeeded; otherwise false
677 *
678 * This is potentially an O(N) operation to traverse down to the
679 * correct location in the list and add an item.
680 *
681 * Example: if idx = 2 and list = item1->item2->item3->item4, then
682 * after insert, list = item1->item2->item->item3->item4.
683 *
684 * If index is greater than the length of the list, no action is
685 * performed and false is returned.
686 */
687 OPAL_DECLSPEC bool opal_list_insert(opal_list_t *list, opal_list_item_t *item,
688 long long idx);
689
690
691 /**
692 * Join a list into another list
693 *
694 * @param thislist List container for list being operated on
695 * @param pos List item in \c thislist marking the position before
696 * which items are inserted
697 * @param xlist List container for list being spliced from
698 *
699 * Join a list into another list. All of the elements of \c xlist
700 * are inserted before \c pos and removed from \c xlist.
701 *
702 * This operation is an O(1) operation. Both \c thislist and \c
703 * xlist must be valid list containsers. \c xlist will be empty
704 * but valid after the call. All pointers to \c opal_list_item_t
705 * containers remain valid, including those that point to elements
706 * in \c xlist.
707 */
708 OPAL_DECLSPEC void opal_list_join(opal_list_t *thislist, opal_list_item_t *pos,
709 opal_list_t *xlist);
710
711
712 /**
713 * Splice a list into another list
714 *
715 * @param thislist List container for list being operated on
716 * @param pos List item in \c thislist marking the position before
717 * which items are inserted
718 * @param xlist List container for list being spliced from
719 * @param first List item in \c xlist marking the start of elements
720 * to be copied into \c thislist
721 * @param last List item in \c xlist marking the end of elements
722 * to be copied into \c thislist
723 *
724 * Splice a subset of a list into another list. The \c [first,
725 * last) elements of \c xlist are moved into \c thislist,
726 * inserting them before \c pos. \c pos must be a valid iterator
727 * in \c thislist and \c [first, last) must be a valid range in \c
728 * xlist. \c postition must not be in the range \c [first, last).
729 * It is, however, valid for \c xlist and \c thislist to be the
730 * same list.
731 *
732 * This is an O(N) operation because the length of both lists must
733 * be recomputed.
734 */
735 OPAL_DECLSPEC void opal_list_splice(opal_list_t *thislist, opal_list_item_t *pos,
736 opal_list_t *xlist, opal_list_item_t *first,
737 opal_list_item_t *last);
738
739 /**
740 * Comparison function for opal_list_sort(), below.
741 *
742 * @param a Pointer to a pointer to an opal_list_item_t.
743 * Explanation below.
744 * @param b Pointer to a pointer to an opal_list_item_t.
745 * Explanation below.
746 * @retval 1 if \em a is greater than \em b
747 * @retval 0 if \em a is equal to \em b
748 * @retval 11 if \em a is less than \em b
749 *
750 * This function is invoked by qsort(3) from within
751 * opal_list_sort(). It is important to understand what
752 * opal_list_sort() does before invoking qsort, so go read that
753 * documentation first.
754 *
755 * The important thing to realize here is that a and b will be \em
756 * double pointers to the items that you need to compare. Here's
757 * a sample compare function to illustrate this point:
758 *
759 * \verb
760 * static int compare(opal_list_item_t **a, opal_list_item_t **b)
761 * {
762 * orte_pls_base_cmp_t *aa = *((orte_pls_base_cmp_t **) a);
763 * orte_pls_base_cmp_t *bb = *((orte_pls_base_cmp_t **) b);
764 *
765 * if (bb->priority > aa->priority) {
766 * return 1;
767 * } else if (bb->priority == aa->priority) {
768 * return 0;
769 * } else {
770 * return -1;
771 * }
772 * }
773 * \endverb
774 */
775 typedef int (*opal_list_item_compare_fn_t)(opal_list_item_t **a,
776 opal_list_item_t **b);
777
778 /**
779 * Sort a list with a provided compare function.
780 *
781 * @param list The list to sort
782 * @param compare Compare function
783 *
784 * Put crassly, this function's complexity is O(N) + O(log(N)).
785 * Its algorithm is:
786 *
787 * - remove every item from the list and put the corresponding
788 * (opal_list_item_t*)'s in an array
789 * - call qsort(3) with that array and your compare function
790 * - re-add every element of the now-sorted array to the list
791 *
792 * The resulting list is now ordered. Note, however, that since
793 * an array of pointers is sorted, the comparison function must do
794 * a double de-reference to get to the actual opal_list_item_t (or
795 * whatever the underlying type is). See the documentation of
796 * opal_list_item_compare_fn_t for an example).
797 */
798 OPAL_DECLSPEC int opal_list_sort(opal_list_t* list, opal_list_item_compare_fn_t compare);
799
800 END_C_DECLS
801
802 #endif /* OPAL_LIST_H */
opal_list_get_first
static opal_list_item_t * opal_list_get_first(opal_list_t *list)
Return the first item on the list (does not remove it).
Definition: opal_list.h:195
opal_list_t::opal_list_length
volatile size_t opal_list_length
Quick reference to the number of items in the list.
Definition: opal_list.h:153
opal_list_item_t::opal_list_next
volatile struct opal_list_item_t * opal_list_next
Pointer to next list item.
Definition: opal_list.h:102
OPAL_THREAD_ADD32
#define OPAL_THREAD_ADD32(x, y)
Use an atomic operation for increment/decrement if opal_using_threads() indicates that threads are in...
Definition: mutex.h:367
opal_list_remove_item
static opal_list_item_t * opal_list_remove_item(opal_list_t *list, opal_list_item_t *item)
Remove an item from a list.
Definition: opal_list.h:348
opal_list_get_last
static opal_list_item_t * opal_list_get_last(opal_list_t *list)
Return the last item on the list (does not remove it).
Definition: opal_list.h:222
opal_list_get_begin
static opal_list_item_t * opal_list_get_begin(opal_list_t *list)
Return the beginning of the list; an invalid list entry suitable for comparison only.
Definition: opal_list.h:252
opal_list_is_empty
static bool opal_list_is_empty(opal_list_t *list)
Check for empty list.
Definition: opal_list.h:174
opal_list_item_t::super
opal_object_t super
Generic parent class for all Open MPI objects.
Definition: opal_list.h:100
opal_list_get_size
static size_t opal_list_get_size(opal_list_t *list)
Return the number of items in a list.
Definition: opal_list.h:299
opal_list_join
OPAL_DECLSPEC void opal_list_join(opal_list_t *thislist, opal_list_item_t *pos, opal_list_t *xlist)
Join a list into another list.
Definition: opal_list.c:191
opal_list_item_t
Definition: opal_list.h:98
opal_list_t::super
opal_object_t super
Generic parent class for all Open MPI objects.
Definition: opal_list.h:149
opal_list_remove_last
static opal_list_item_t * opal_list_remove_last(opal_list_t *list)
Remove the last item from the list and return it.
Definition: opal_list.h:584
opal_list_get_next
#define opal_list_get_next(item)
Get the next item in a list.
Definition: opal_list.h:128
opal_list_item_t::opal_list_prev
volatile struct opal_list_item_t * opal_list_prev
Pointer to previous list item.
Definition: opal_list.h:104
opal_object_t
Base object.
Definition: opal_object.h:182
opal_list_splice
OPAL_DECLSPEC void opal_list_splice(opal_list_t *thislist, opal_list_item_t *pos, opal_list_t *xlist, opal_list_item_t *first, opal_list_item_t *last)
Splice a list into another list.
Definition: opal_list.c:206
opal_list_t
Definition: opal_list.h:147
opal_list_insert
OPAL_DECLSPEC bool opal_list_insert(opal_list_t *list, opal_list_item_t *item, long long idx)
Add an item to the list at a specific index location in the list.
Definition: opal_list.c:112
opal_list_sort
OPAL_DECLSPEC int opal_list_sort(opal_list_t *list, opal_list_item_compare_fn_t compare)
Sort a list with a provided compare function.
Definition: opal_list.c:231
opal_list_remove_first
static opal_list_item_t * opal_list_remove_first(opal_list_t *list)
Remove the first item from the list and return it.
Definition: opal_list.h:522
opal_list_prepend
static void opal_list_prepend(opal_list_t *list, opal_list_item_t *item)
Prepend an item to the beginning of the list.
Definition: opal_list.h:469
opal_list_item_compare_fn_t
int(* opal_list_item_compare_fn_t)(opal_list_item_t **a, opal_list_item_t **b)
Comparison function for opal_list_sort(), below.
Definition: opal_list.h:775
opal_list_t::opal_list_sentinel
opal_list_item_t opal_list_sentinel
Head and tail item of the list.
Definition: opal_list.h:151
atomic.h
Atomic operations.
mutex.h
Mutual exclusion functions.
opal_list_insert_pos
static void opal_list_insert_pos(opal_list_t *list, opal_list_item_t *pos, opal_list_item_t *item)
Add an item to the list before a given element.
Definition: opal_list.h:637
opal_object.h
A simple C-language object-oriented system with single inheritance and ownership-based memory managem...
OBJ_CLASS_DECLARATION
#define OBJ_CLASS_DECLARATION(NAME)
Declaration for class descriptor.
Definition: opal_object.h:236
opal_list_get_end
static opal_list_item_t * opal_list_get_end(opal_list_t *list)
Return the end of the list; an invalid list entry suitable for comparison only.
Definition: opal_list.h:274