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