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