OpenMPI  0.1.1
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  */
91 
92 
93 /**
94  * \internal
95  *
96  * Struct of an opal_list_item_t
97  */
99 {
101  /**< Generic parent class for all Open MPI objects */
103  /**< Pointer to next list item */
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  */
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  */
148 {
150  /**< Generic parent class for all Open MPI objects */
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  */
196 {
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  */
223 {
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  */
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  */
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  */
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 */
374 
375  /* reset previous pointer of next element */
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  */
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 */
547 
548  /* reset the head next pointer */
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  */
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 */
609 
610  /* reset tail's previous pointer */
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  */
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 */
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
volatile size_t opal_list_length
Quick reference to the number of items in the list.
Definition: opal_list.h:153
volatile struct opal_list_item_t * opal_list_next
Pointer to next list item.
Definition: opal_list.h:102
#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
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
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
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
static bool opal_list_is_empty(opal_list_t *list)
Check for empty list.
Definition: opal_list.h:174
opal_object_t super
Generic parent class for all Open MPI objects.
Definition: opal_list.h:100
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_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
Definition: opal_list.h:98
opal_object_t super
Generic parent class for all Open MPI objects.
Definition: opal_list.h:149
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
#define opal_list_get_next(item)
Get the next item in a list.
Definition: opal_list.h:128
volatile struct opal_list_item_t * opal_list_prev
Pointer to previous list item.
Definition: opal_list.h:104
Base object.
Definition: opal_object.h:182
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
Definition: opal_list.h:147
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_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
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
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
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_item_t opal_list_sentinel
Head and tail item of the list.
Definition: opal_list.h:151
Atomic operations.
Mutual exclusion functions.
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
A simple C-language object-oriented system with single inheritance and ownership-based memory managem...
#define OBJ_CLASS_DECLARATION(NAME)
Declaration for class descriptor.
Definition: opal_object.h:236
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