OpenMPI  0.1.1
opal_list.h File Reference

The opal_list_t interface is used to provide a generic doubly-linked list container for Open MPI. More...

#include "opal_config.h"
#include <stdio.h>
#include <stdlib.h>
#include "opal/class/opal_object.h"

Go to the source code of this file.

Data Structures

struct  opal_list_item_t
 
struct  opal_list_t
 

Macros

#define opal_list_get_next(item)   ((item) ? ((opal_list_item_t*) ((opal_list_item_t*)(item))->opal_list_next) : NULL)
 Get the next item in a list. More...
 
#define opal_list_get_prev(item)   ((item) ? ((opal_list_item_t*) ((opal_list_item_t*)(item))->opal_list_prev) : NULL)
 Get the next item in a list. More...
 
#define opal_list_append(l, i)   _opal_list_append(l,i)
 Append an item to the end of the list. More...
 

Typedefs

typedef struct opal_list_item_t opal_list_item_t
 Base type for items that are put in a list (opal_list_t) containers.
 
typedef struct opal_list_t opal_list_t
 List container type.
 
typedef int(* opal_list_item_compare_fn_t )(opal_list_item_t **a, opal_list_item_t **b)
 Comparison function for opal_list_sort(), below. More...
 

Functions

BEGIN_C_DECLS OPAL_DECLSPEC OBJ_CLASS_DECLARATION (opal_list_t)
 
OPAL_DECLSPEC OBJ_CLASS_DECLARATION (opal_list_item_t)
 
static bool opal_list_is_empty (opal_list_t *list)
 Check for empty list. More...
 
static opal_list_item_topal_list_get_first (opal_list_t *list)
 Return the first item on the list (does not remove it). More...
 
static opal_list_item_topal_list_get_last (opal_list_t *list)
 Return the last item on the list (does not remove it). More...
 
static opal_list_item_topal_list_get_begin (opal_list_t *list)
 Return the beginning of the list; an invalid list entry suitable for comparison only. More...
 
static opal_list_item_topal_list_get_end (opal_list_t *list)
 Return the end of the list; an invalid list entry suitable for comparison only. More...
 
static size_t opal_list_get_size (opal_list_t *list)
 Return the number of items in a list. More...
 
static opal_list_item_topal_list_remove_item (opal_list_t *list, opal_list_item_t *item)
 Remove an item from a list. More...
 
static void _opal_list_append (opal_list_t *list, opal_list_item_t *item)
 
static void opal_list_prepend (opal_list_t *list, opal_list_item_t *item)
 Prepend an item to the beginning of the list. More...
 
static opal_list_item_topal_list_remove_first (opal_list_t *list)
 Remove the first item from the list and return it. More...
 
static opal_list_item_topal_list_remove_last (opal_list_t *list)
 Remove the last item from the list and return it. More...
 
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. More...
 
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. More...
 
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. More...
 
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. More...
 
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. More...
 

Detailed Description

The opal_list_t interface is used to provide a generic doubly-linked list container for Open MPI.

It was inspired by (but is slightly different than) the Stantard Template Library (STL) std::list class. One notable difference from std::list is that when an opal_list_t is destroyed, all of the opal_list_item_t objects that it contains are orphaned – they are not destroyed.

The general idea is that opal_list_item_t objects can be put on an opal_list_t. Hence, you create a new type that derives from opal_list_item_t; this new type can then be used with opal_list_t containers.

NOTE: opal_list_item_t instances can only be on one list at a time. Specifically, if you add an opal_list_item_t to one list, and then add it to another list (without first removing it from the first list), you will effectively be hosing the first list. You have been warned.

If OPAL_ENABLE_DEBUG is true, a bunch of checks occur, including some spot checks for a debugging reference count in an attempt to ensure that an opal_list_item_t is only one one list at a time. Given the highly concurrent nature of this class, these spot checks cannot guarantee that an item is only one list at a time. Specifically, since it is a desirable attribute of this class to not use locks for normal operations, it is possible that two threads may [erroneously] modify an opal_list_item_t concurrently.

The only way to guarantee that a debugging reference count is valid for the duration of an operation is to lock the item_t during the operation. But this fundamentally changes the desirable attribute of this class (i.e., no locks). So all we can do is spot-check the reference count in a bunch of places and check that it is still the value that we think it should be. But this doesn't mean that you can run into "unlucky" cases where two threads are concurrently modifying an item_t, but all the spot checks still return the "right" values. All we can do is hope that we have enough spot checks to statistically drive down the possibility of the unlucky cases happening.

Macro Definition Documentation

#define opal_list_append (   l,
 
)    _opal_list_append(l,i)

Append an item to the end of the list.

Parameters
listThe list container
itemThe item to append

This is an O(1) operation to append an item to the end of a list. The opal_list_item_t is not OBJ_RETAIN()'ed; it is assumed that "ownership" of the item is passed from the caller to the list.

This is an inlined function in compilers that support inlining, so it's usually a cheap operation.

Referenced by append_frag_to_list(), mca_allocator_basic_alloc(), mca_allocator_basic_free(), mca_base_param_dump(), mca_btl_base_select(), mca_btl_elan_component_progress(), mca_btl_sctp_add_procs(), mca_btl_tcp_add_procs(), mca_btl_ud_component_init(), mca_btl_udapl_put(), mca_btl_vader_send(), mca_btl_vader_sendi(), mca_coll_base_find_available(), mca_io_base_find_available(), mca_mpool_grdma_deregister(), mca_mpool_grdma_release_memory(), mca_mpool_rdma_deregister(), mca_mpool_rdma_release_memory(), mca_oob_base_init(), mca_oob_tcp_msg_complete(), mca_oob_tcp_peer_send(), mca_oob_tcp_recv_nb(), mca_pml_bfo_error_pending_packets(), mca_rcache_vma_tree_delete(), ompi_op_base_find_available(), ompi_proc_init(), opal_cmd_line_parse(), opal_graph_add_edge(), opal_graph_add_vertex(), opal_hash_table_remove_value_ptr(), opal_hash_table_remove_value_uint32(), opal_hash_table_remove_value_uint64(), opal_hash_table_set_value_ptr(), opal_hash_table_set_value_uint32(), opal_hash_table_set_value_uint64(), opal_list_sort(), orte_odls_base_open(), orte_ras_gridengine_allocate(), and orte_rmaps_base_get_target_nodes().

#define opal_list_get_next (   item)    ((item) ? ((opal_list_item_t*) ((opal_list_item_t*)(item))->opal_list_next) : NULL)

Get the next item in a list.

Parameters
itemA list item.
Returns
The next item in the list

Referenced by mca_allocator_basic_alloc(), mca_allocator_basic_free(), mca_allocator_component_lookup(), mca_base_param_dump(), mca_btl_base_select(), mca_mpool_base_alloc(), mca_oob_base_init(), mca_oob_base_module_init(), mca_oob_tcp_get_addr(), mca_oob_tcp_msg_match_post(), mca_oob_tcp_msg_match_recv(), mca_oob_tcp_recv_cancel(), mca_pml_bfo_is_duplicate_msg(), mca_rcache_vma_tree_delete(), mca_rcache_vma_tree_find(), mca_rcache_vma_tree_find_all(), ompi_proc_all(), ompi_proc_complete_init(), ompi_proc_find(), ompi_proc_refresh(), ompi_proc_world(), opal_cmd_line_get_ninsts(), opal_cmd_line_get_param(), opal_cmd_line_get_usage_msg(), opal_graph_add_edge(), opal_graph_add_vertex(), opal_graph_adjacent(), opal_graph_dijkstra(), opal_graph_duplicate(), opal_graph_find_vertex(), opal_graph_get_adjacent_vertices(), opal_graph_get_graph_vertices(), opal_graph_print(), opal_hash_table_get_next_key_uint32(), opal_hash_table_get_next_key_uint64(), opal_hash_table_get_value_ptr(), opal_hash_table_get_value_uint32(), opal_hash_table_get_value_uint64(), opal_hash_table_remove_value_ptr(), opal_hash_table_remove_value_uint32(), opal_hash_table_remove_value_uint64(), opal_hash_table_set_value_ptr(), opal_hash_table_set_value_uint32(), opal_hash_table_set_value_uint64(), opal_list_get_size(), opal_list_splice(), orte_notifier_base_select(), orte_odls_base_default_signal_local_procs(), orte_ras_gridengine_allocate(), orte_rmaps_base_get_target_nodes(), orte_rml_base_select(), orte_sensor_base_select(), and orte_util_add_hostfile_nodes().

#define opal_list_get_prev (   item)    ((item) ? ((opal_list_item_t*) ((opal_list_item_t*)(item))->opal_list_prev) : NULL)

Get the next item in a list.

Parameters
itemA list item.
Returns
The next item in the list

Referenced by mca_oob_tcp_peer_lookup(), mca_rcache_vma_tree_delete(), and orte_rmaps_base_get_target_nodes().

Typedef Documentation

typedef int(* opal_list_item_compare_fn_t)(opal_list_item_t **a, opal_list_item_t **b)

Comparison function for opal_list_sort(), below.

Parameters
aPointer to a pointer to an opal_list_item_t. Explanation below.
bPointer to a pointer to an opal_list_item_t. Explanation below.
Return values
1if a is greater than b
0if a is equal to b
11if a is less than b

This function is invoked by qsort(3) from within opal_list_sort(). It is important to understand what opal_list_sort() does before invoking qsort, so go read that documentation first.

The important thing to realize here is that a and b will be double pointers to the items that you need to compare. Here's a sample compare function to illustrate this point:

static int compare(opal_list_item_t **a, opal_list_item_t **b) { orte_pls_base_cmp_t *aa = *((orte_pls_base_cmp_t **) a); orte_pls_base_cmp_t *bb = *((orte_pls_base_cmp_t **) b);

if (bb->priority > aa->priority) { return 1; } else if (bb->priority == aa->priority) { return 0; } else { return -1; } }

Function Documentation

static opal_list_item_t* opal_list_get_begin ( opal_list_t list)
inlinestatic

Return the beginning of the list; an invalid list entry suitable for comparison only.

Parameters
listThe list container
Returns
A pointer to the beginning of the list.

This is an O(1) operation to return the beginning of the list. Similar to the STL, this is a special invalid list item – it should not be used for storage. It is only suitable for comparison to other items in the list to see if they are valid or not; it's ususally used when iterating through the items in a list.

This is an inlined function in compilers that support inlining, so it's usually a cheap operation.

References opal_list_t::opal_list_sentinel.

Referenced by mca_oob_tcp_peer_lookup(), mca_pml_bfo_send_request_restart(), mca_rcache_vma_tree_delete(), and orte_rmaps_base_get_target_nodes().

static opal_list_item_t* opal_list_get_end ( opal_list_t list)
inlinestatic

Return the end of the list; an invalid list entry suitable for comparison only.

Parameters
listThe list container
Returns
A pointer to the end of the list.

This is an O(1) operation to return the end of the list. Similar to the STL, this is a special invalid list item – it should not be used for storage. It is only suitable for comparison to other items in the list to see if they are valid or not; it's ususally used when iterating through the items in a list.

This is an inlined function in compilers that support inlining, so it's usually a cheap operation.

References opal_list_t::opal_list_sentinel.

Referenced by mca_allocator_basic_alloc(), mca_allocator_basic_free(), mca_allocator_component_lookup(), mca_base_param_dump(), mca_btl_base_select(), mca_mpool_base_alloc(), mca_oob_base_init(), mca_oob_base_module_init(), mca_oob_tcp_fini(), mca_oob_tcp_get_addr(), mca_oob_tcp_msg_match_post(), mca_oob_tcp_msg_match_recv(), mca_oob_tcp_recv_cancel(), mca_pml_bfo_is_duplicate_msg(), mca_rcache_vma_tree_delete(), mca_rcache_vma_tree_find(), mca_rcache_vma_tree_find_all(), ompi_proc_all(), ompi_proc_complete_init(), ompi_proc_finalize(), ompi_proc_find(), ompi_proc_refresh(), ompi_proc_world(), opal_cmd_line_get_ninsts(), opal_cmd_line_get_param(), opal_cmd_line_get_usage_msg(), opal_graph_add_edge(), opal_graph_add_vertex(), opal_graph_adjacent(), opal_graph_dijkstra(), opal_graph_duplicate(), opal_graph_find_vertex(), opal_graph_get_adjacent_vertices(), opal_graph_get_graph_vertices(), opal_graph_print(), opal_hash_table_get_next_key_uint32(), opal_hash_table_get_next_key_uint64(), opal_hash_table_get_value_ptr(), opal_hash_table_get_value_uint32(), opal_hash_table_get_value_uint64(), opal_hash_table_remove_value_ptr(), opal_hash_table_remove_value_uint32(), opal_hash_table_remove_value_uint64(), opal_hash_table_set_value_ptr(), opal_hash_table_set_value_uint32(), opal_hash_table_set_value_uint64(), opal_list_get_size(), opal_list_join(), opal_list_remove_item(), orte_notifier_base_select(), orte_odls_base_default_signal_local_procs(), orte_ras_gridengine_allocate(), orte_rmaps_base_get_target_nodes(), orte_rml_base_select(), orte_sensor_base_select(), and orte_util_add_hostfile_nodes().

static opal_list_item_t* opal_list_get_first ( opal_list_t list)
inlinestatic

Return the first item on the list (does not remove it).

Parameters
listThe list container
Returns
A pointer to the first item on the list

This is an O(1) operation to return the first item on the list. It should be compared against the returned value from opal_list_get_end() to ensure that the list is not empty.

This is an inlined function in compilers that support inlining, so it's usually a cheap operation.

References opal_list_item_t::opal_list_next, and opal_list_t::opal_list_sentinel.

Referenced by mca_allocator_basic_alloc(), mca_allocator_basic_free(), mca_allocator_component_lookup(), mca_base_param_dump(), mca_btl_base_select(), mca_btl_elan_component_progress(), mca_mpool_base_alloc(), mca_oob_base_init(), mca_oob_base_module_init(), mca_oob_tcp_fini(), mca_oob_tcp_get_addr(), mca_oob_tcp_msg_match_post(), mca_oob_tcp_msg_match_recv(), mca_oob_tcp_recv_cancel(), mca_pml_bfo_is_duplicate_msg(), mca_rcache_vma_tree_find(), mca_rcache_vma_tree_find_all(), ompi_proc_all(), ompi_proc_complete_init(), ompi_proc_finalize(), ompi_proc_find(), ompi_proc_refresh(), ompi_proc_world(), opal_cmd_line_get_ninsts(), opal_cmd_line_get_param(), opal_cmd_line_get_usage_msg(), opal_graph_add_edge(), opal_graph_add_vertex(), opal_graph_adjacent(), opal_graph_dijkstra(), opal_graph_duplicate(), opal_graph_find_vertex(), opal_graph_get_adjacent_vertices(), opal_graph_get_graph_vertices(), opal_graph_print(), opal_hash_table_get_first_key_uint32(), opal_hash_table_get_first_key_uint64(), opal_hash_table_get_next_key_uint32(), opal_hash_table_get_next_key_uint64(), opal_hash_table_get_value_ptr(), opal_hash_table_get_value_uint32(), opal_hash_table_get_value_uint64(), opal_hash_table_remove_value_ptr(), opal_hash_table_remove_value_uint32(), opal_hash_table_remove_value_uint64(), opal_hash_table_set_value_ptr(), opal_hash_table_set_value_uint32(), opal_hash_table_set_value_uint64(), opal_list_get_size(), opal_list_join(), opal_list_remove_item(), orte_notifier_base_select(), orte_odls_base_default_signal_local_procs(), orte_ras_gridengine_allocate(), orte_rmaps_base_get_target_nodes(), orte_rml_base_select(), orte_sensor_base_select(), and orte_util_add_hostfile_nodes().

static opal_list_item_t* opal_list_get_last ( opal_list_t list)
inlinestatic

Return the last item on the list (does not remove it).

Parameters
listThe list container
Returns
A pointer to the last item on the list

This is an O(1) operation to return the last item on the list. It should be compared against the returned value from opal_list_get_begin() to ensure that the list is not empty.

This is an inlined function in compilers that support inlining, so it's usually a cheap operation.

References opal_list_item_t::opal_list_prev, and opal_list_t::opal_list_sentinel.

Referenced by mca_oob_tcp_peer_lookup(), mca_pml_bfo_send_request_restart(), and orte_rmaps_base_get_target_nodes().

static size_t opal_list_get_size ( opal_list_t list)
inlinestatic

Return the number of items in a list.

Parameters
listThe list container
Returns
The size of the list (size_t)

This is an O(1) lookup to return the size of the list.

This is an inlined function in compilers that support inlining, so it's usually a cheap operation.

Warning
The size of the list is cached as part of the list. In the future, calling opal_list_splice or opal_list_join may result in this function recomputing the list size, which would be an O(N) operation. If opal_list_splice or opal_list_join is never called on the specified list, this function will always be O(1).

References opal_list_get_end(), opal_list_get_first(), opal_list_get_next, and opal_list_t::opal_list_length.

Referenced by error_out_all_pending_frags(), mca_base_param_dump(), mca_btl_base_select(), mca_btl_gm_send(), mca_btl_sm_component_progress(), mca_btl_smcuda_component_progress(), mca_mpool_base_alloc(), mca_oob_tcp_get_addr(), mca_oob_tcp_msg_complete(), mca_oob_tcp_peer_lookup(), mca_oob_tcp_peer_resolved(), mca_pml_bfo_error_pending_packets(), mca_pml_bfo_is_duplicate_msg(), mca_pml_bfo_recv_frag_callback_match(), mca_pml_bfo_recv_frag_match(), mca_pml_csum_recv_frag_callback_match(), mca_pml_csum_recv_frag_match(), mca_pml_ob1_recv_frag_callback_match(), mca_pml_ob1_recv_frag_match(), mca_rcache_vma_tree_find_all(), ompi_proc_all(), opal_cmd_line_get_usage_msg(), opal_graph_get_adjacent_vertices(), opal_hash_table_get_first_key_uint32(), opal_hash_table_get_first_key_uint64(), opal_hash_table_get_next_key_uint32(), opal_hash_table_get_next_key_uint64(), opal_hash_table_remove_all(), opal_list_join(), orte_odls_base_open(), orte_ras_base_node_insert(), orte_rmaps_base_filter_nodes(), and orte_rmaps_base_get_target_nodes().

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.

Parameters
listThe list container
itemThe item to insert
indexLocation to add the item
Returns
true if insertion succeeded; otherwise false

This is potentially an O(N) operation to traverse down to the correct location in the list and add an item.

Example: if idx = 2 and list = item1->item2->item3->item4, then after insert, list = item1->item2->item->item3->item4.

If index is greater than the length of the list, no action is performed and false is returned.

References opal_atomic_add, opal_list_t::opal_list_length, opal_list_item_t::opal_list_next, opal_list_prepend(), opal_list_item_t::opal_list_prev, and opal_list_t::opal_list_sentinel.

static void opal_list_insert_pos ( opal_list_t list,
opal_list_item_t pos,
opal_list_item_t item 
)
inlinestatic

Add an item to the list before a given element.

Parameters
listThe list container
posList element to insert item before
itemThe item to insert

Inserts item before pos. This is an O(1) operation.

References opal_list_t::opal_list_length, opal_list_item_t::opal_list_next, opal_list_item_t::opal_list_prev, and OPAL_THREAD_ADD32.

Referenced by mca_allocator_basic_free(), and orte_rmaps_base_get_target_nodes().

static bool opal_list_is_empty ( opal_list_t list)
inlinestatic

Check for empty list.

Parameters
listThe list container
Returns
true if list's size is 0, false otherwise

This is an O(1) operation.

This is an inlined function in compilers that support inlining, so it's usually a cheap operation.

References opal_list_item_t::opal_list_next, and opal_list_t::opal_list_sentinel.

Referenced by mca_base_param_dump(), mca_btl_elan_component_progress(), mca_btl_ud_component_progress(), mca_mpool_grdma_register(), mca_mpool_rdma_finalize(), mca_mpool_rdma_register(), mca_rcache_vma_tree_delete(), opal_graph_remove_vertex(), and orte_ras_gridengine_allocate().

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.

Parameters
thislistList container for list being operated on
posList item in thislist marking the position before which items are inserted
xlistList container for list being spliced from

Join a list into another list. All of the elements of xlist are inserted before pos and removed from xlist.

This operation is an O(1) operation. Both thislist and xlist must be valid list containsers. xlist will be empty but valid after the call. All pointers to opal_list_item_t containers remain valid, including those that point to elements in xlist.

References opal_list_get_end(), opal_list_get_first(), opal_list_get_size(), and opal_list_t::opal_list_length.

static void opal_list_prepend ( opal_list_t list,
opal_list_item_t item 
)
inlinestatic

Prepend an item to the beginning of the list.

Parameters
listThe list container
itemThe item to prepend

This is an O(1) operation to prepend an item to the beginning of a list. The opal_list_item_t is not OBJ_RETAIN()'ed; it is assumed that "ownership" of the item is passed from the caller to the list.

This is an inlined function in compilers that support inlining, so it's usually a cheap operation.

References opal_list_t::opal_list_length, opal_list_item_t::opal_list_next, opal_list_item_t::opal_list_prev, opal_list_t::opal_list_sentinel, and OPAL_THREAD_ADD32.

Referenced by mca_mpool_rgpusm_deregister(), mca_oob_tcp_peer_lookup(), opal_list_insert(), and orte_rmaps_base_get_target_nodes().

static opal_list_item_t* opal_list_remove_first ( opal_list_t list)
inlinestatic

Remove the first item from the list and return it.

Parameters
listThe list container
Returns
The first item on the list. If the list is empty, NULL will be returned

This is an O(1) operation to return the first item on the list. If the list is not empty, a pointer to the first item in the list will be returned. Ownership of the item is transferred from the list to the caller; no calls to OBJ_RETAIN() or OBJ_RELEASE() are invoked.

This is an inlined function in compilers that support inlining, so it's usually a cheap operation.

References opal_list_t::opal_list_length, opal_list_item_t::opal_list_next, opal_list_item_t::opal_list_prev, opal_list_t::opal_list_sentinel, and OPAL_THREAD_ADD32.

Referenced by error_out_all_pending_frags(), mca_base_param_dump_release(), mca_base_param_finalize(), mca_btl_elan_component_progress(), mca_btl_gm_send(), mca_btl_openib_handle_endpoint_error(), mca_btl_sctp_finalize(), mca_btl_tcp_finalize(), mca_btl_ud_component_init(), mca_btl_ud_component_progress(), mca_coll_base_comm_select(), mca_coll_base_find_available(), mca_io_base_delete(), mca_io_base_file_select(), mca_io_base_find_available(), mca_oob_tcp_fini(), mca_oob_tcp_msg_complete(), mca_oob_tcp_set_addr(), mca_pml_bfo_error_pending_packets(), ompi_mpi_finalize(), ompi_op_base_find_available(), ompi_op_base_op_select(), opal_graph_remove_vertex(), opal_hash_table_remove_all(), opal_hash_table_set_value_ptr(), opal_hash_table_set_value_uint32(), opal_hash_table_set_value_uint64(), opal_list_sort(), orte_ess_base_close(), orte_ras_base_node_insert(), orte_rmaps_base_close(), and orte_util_add_hostfile_nodes().

static opal_list_item_t* opal_list_remove_item ( opal_list_t list,
opal_list_item_t item 
)
inlinestatic

Remove an item from a list.

Parameters
listThe list container
itemThe item to remove
Returns
A pointer to the item on the list previous to the one that was removed.

This is an O(1) operation to remove an item from the list. The forward / reverse pointers in the list are updated and the item is removed. The list item that is returned is now "owned" by the caller – they are responsible for OBJ_RELEASE()'ing it.

If debugging is enabled (specifically, if –enable-debug was used to configure Open MPI), this is an O(N) operation because it checks to see if the item is actually in the list first.

This is an inlined function in compilers that support inlining, so it's usually a cheap operation.

References opal_list_get_end(), opal_list_get_first(), opal_list_t::opal_list_length, opal_list_item_t::opal_list_next, opal_list_item_t::opal_list_prev, and OPAL_THREAD_ADD32.

Referenced by mca_allocator_basic_alloc(), mca_btl_base_select(), mca_btl_sctp_del_procs(), mca_btl_tcp_del_procs(), mca_mpool_grdma_finalize(), mca_mpool_grdma_find(), mca_mpool_grdma_register(), mca_mpool_grdma_release_memory(), mca_mpool_rdma_finalize(), mca_mpool_rdma_find(), mca_mpool_rdma_register(), mca_mpool_rdma_release_memory(), mca_mpool_rgpusm_finalize(), mca_mpool_rgpusm_find(), mca_mpool_rgpusm_register(), mca_oob_tcp_msg_complete(), mca_oob_tcp_msg_match_post(), mca_oob_tcp_peer_lookup(), mca_oob_tcp_recv_cancel(), mca_pml_bfo_recv_req_start(), mca_pml_bfo_send_request_restart(), mca_pml_csum_recv_req_start(), mca_pml_ob1_recv_req_start(), mca_rcache_vma_tree_delete(), opal_graph_remove_edge(), opal_graph_remove_vertex(), opal_hash_table_remove_value_ptr(), opal_hash_table_remove_value_uint32(), opal_hash_table_remove_value_uint64(), orte_rmaps_base_get_target_nodes(), orte_rml_base_select(), and orte_util_add_hostfile_nodes().

static opal_list_item_t* opal_list_remove_last ( opal_list_t list)
inlinestatic

Remove the last item from the list and return it.

Parameters
listThe list container
Returns
The last item on the list. If the list is empty, NULL will be returned

This is an O(1) operation to return the last item on the list. If the list is not empty, a pointer to the last item in the list will be returned. Ownership of the item is transferred from the list to the caller; no calls to OBJ_RETAIN() or OBJ_RELEASE() are invoked.

This is an inlined function in compilers that support inlining, so it's usually a cheap operation.

References opal_list_t::opal_list_length, opal_list_item_t::opal_list_next, opal_list_item_t::opal_list_prev, opal_list_t::opal_list_sentinel, and OPAL_THREAD_ADD32.

Referenced by mca_io_base_delete(), and mca_io_base_file_select().

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.

Parameters
listThe list to sort
compareCompare function

Put crassly, this function's complexity is O(N) + O(log(N)). Its algorithm is:

  • remove every item from the list and put the corresponding (opal_list_item_t*)'s in an array
  • call qsort(3) with that array and your compare function
  • re-add every element of the now-sorted array to the list

The resulting list is now ordered. Note, however, that since an array of pointers is sorted, the comparison function must do a double de-reference to get to the actual opal_list_item_t (or whatever the underlying type is). See the documentation of opal_list_item_compare_fn_t for an example).

References opal_list_append, opal_list_t::opal_list_length, and opal_list_remove_first().

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.

Parameters
thislistList container for list being operated on
posList item in thislist marking the position before which items are inserted
xlistList container for list being spliced from
firstList item in xlist marking the start of elements to be copied into thislist
lastList item in xlist marking the end of elements to be copied into thislist

Splice a subset of a list into another list. The [first, last) elements of xlist are moved into thislist, inserting them before pos. pos must be a valid iterator in thislist and [first, last) must be a valid range in xlist. postition must not be in the range [first, last). It is, however, valid for xlist and thislist to be the same list.

This is an O(N) operation because the length of both lists must be recomputed.

References opal_list_get_next, and opal_list_t::opal_list_length.