opal_list.h

来自「MPI stands for the Message Passing Inter」· C头文件 代码 · 共 805 行 · 第 1/2 页

#if OMPI_ENABLE_DEBUG
#define opal_list_append(l,i) \
_opal_list_append(l,i,__FILE__,__LINE__)
#else
#define opal_list_append(l,i) \
_opal_list_append(l,i)
#endif  /* OMPI_ENABLE_DEBUG */

static inline void _opal_list_append(opal_list_t *list, opal_list_item_t *item
#if OMPI_ENABLE_DEBUG
                                     , char* FILE_NAME, int LINENO
#endif  /* OMPI_ENABLE_DEBUG */
                                     )
{
    opal_list_item_t* sentinel = &(list->opal_list_sentinel);
#if OMPI_ENABLE_DEBUG
  /* Spot check: ensure that this item is previously on no lists */

  assert(0 == item->opal_list_item_refcount);
  assert( NULL == item->opal_list_item_belong_to );
  item->super.cls_init_file_name = FILE_NAME;
  item->super.cls_init_lineno    = LINENO;
#endif

  /* set new element's previous pointer */
  item->opal_list_prev = sentinel->opal_list_prev;

  /* reset previous pointer on current last element */
  sentinel->opal_list_prev->opal_list_next = item;

  /* reset new element's next pointer */
  item->opal_list_next = sentinel;

  /* reset the list's tail element previous pointer */
  sentinel->opal_list_prev = item;

  /* increment list element counter */
  list->opal_list_length++;

#if OMPI_ENABLE_DEBUG
  /* Spot check: ensure this item is only on the list that we just
     appended it to */

  OPAL_THREAD_ADD32( &(item->opal_list_item_refcount), 1 );
  assert(1 == item->opal_list_item_refcount);
  item->opal_list_item_belong_to = list;
#endif
}


/**
 * Prepend an item to the beginning of the list.
 *
 * @param list The list container
 * @param item The 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.
 */
static inline void opal_list_prepend(opal_list_t *list, 
                                     opal_list_item_t *item) 
{
    opal_list_item_t* sentinel = &(list->opal_list_sentinel);
#if OMPI_ENABLE_DEBUG
  /* Spot check: ensure that this item is previously on no lists */

  assert(0 == item->opal_list_item_refcount);
  assert( NULL == item->opal_list_item_belong_to );
#endif

  /* reset item's next pointer */
  item->opal_list_next = sentinel->opal_list_next;
  
  /* reset item's previous pointer */
  item->opal_list_prev = sentinel;
  
  /* reset previous first element's previous poiner */
  sentinel->opal_list_next->opal_list_prev = item;
  
  /* reset head's next pointer */
  sentinel->opal_list_next = item;
  
  /* increment list element counter */
  list->opal_list_length++;

#if OMPI_ENABLE_DEBUG
  /* Spot check: ensure this item is only on the list that we just
     prepended it to */

  OPAL_THREAD_ADD32( &(item->opal_list_item_refcount), 1 );
  assert(1 == item->opal_list_item_refcount);
  item->opal_list_item_belong_to = list;
#endif
}


/**
 * Remove the first item from the list and return it.
 *
 * @param list The 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.
 */
static inline opal_list_item_t *opal_list_remove_first(opal_list_t *list)
{
  /*  Removes and returns first item on list.
      Caller now owns the item and should release the item
      when caller is done with it.
  */
  volatile opal_list_item_t *item;
  if ( 0 == list->opal_list_length ) {
    return (opal_list_item_t *)NULL;
  }
  
#if OMPI_ENABLE_DEBUG
  /* Spot check: ensure that the first item is only on this list */

  assert(1 == list->opal_list_sentinel.opal_list_next->opal_list_item_refcount);
#endif

  /* reset list length counter */
  list->opal_list_length--;
  
  /* get pointer to first element on the list */
  item = list->opal_list_sentinel.opal_list_next;
  
  /* reset previous pointer of next item on the list */
  item->opal_list_next->opal_list_prev = item->opal_list_prev;
  
  /* reset the head next pointer */
  list->opal_list_sentinel.opal_list_next = item->opal_list_next;
  
#if OMPI_ENABLE_DEBUG
  assert( list == item->opal_list_item_belong_to );
  item->opal_list_item_belong_to = NULL;
  item->opal_list_prev=(opal_list_item_t *)NULL;
  item->opal_list_next=(opal_list_item_t *)NULL;

  /* Spot check: ensure that the item we're returning is now on no
     lists */

  OPAL_THREAD_ADD32( &(item->opal_list_item_refcount), -1 );
  assert(0 == item->opal_list_item_refcount);
#endif

  return (opal_list_item_t *) item;
}


/**
 * Remove the last item from the list and return it.
 *
 * @param list The 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.
 */
static inline opal_list_item_t *opal_list_remove_last(opal_list_t *list)
{
  /*  Removes, releases and returns last item on list.
      Caller now owns the item and should release the item
      when caller is done with it.
  */
  volatile opal_list_item_t  *item;
  if ( 0 == list->opal_list_length ) {
      return (opal_list_item_t *)NULL;
  }
  
#if OMPI_ENABLE_DEBUG
  /* Spot check: ensure that the first item is only on this list */

  assert(1 == list->opal_list_sentinel.opal_list_prev->opal_list_item_refcount);
#endif

  /* reset list length counter */
  list->opal_list_length--;
  
  /* get item */
  item = list->opal_list_sentinel.opal_list_prev;
  
  /* reset previous pointer on next to last pointer */
  item->opal_list_prev->opal_list_next = item->opal_list_next;
  
  /* reset tail's previous pointer */
  list->opal_list_sentinel.opal_list_prev = item->opal_list_prev;
  
#if OMPI_ENABLE_DEBUG
  assert( list == item->opal_list_item_belong_to );
  item->opal_list_next = item->opal_list_prev = (opal_list_item_t *)NULL;

  /* Spot check: ensure that the item we're returning is now on no
     lists */

  OPAL_THREAD_ADD32( &(item->opal_list_item_refcount), -1 );
  assert(0 == item->opal_list_item_refcount);
  item->opal_list_item_belong_to = NULL;
#endif

  return (opal_list_item_t *) item;
}

  /**
   * Add an item to the list before a given element
   *
   * @param list The list container
   * @param pos List element to insert \c item before
   * @param item The item to insert
   *
   * Inserts \c item before \c pos.  This is an O(1) operation.
   */
static inline void opal_list_insert_pos(opal_list_t *list, opal_list_item_t *pos,
                                        opal_list_item_t *item)
{
#if OMPI_ENABLE_DEBUG
    /* Spot check: ensure that the item we're insertting is currently
       not on any list */

    assert(0 == item->opal_list_item_refcount);
    assert( NULL == item->opal_list_item_belong_to );
#endif

    /* point item at the existing elements */
    item->opal_list_next = pos;
    item->opal_list_prev = pos->opal_list_prev;

    /* splice into the list */
    pos->opal_list_prev->opal_list_next = item;
    pos->opal_list_prev = item;

    /* reset list length counter */
    list->opal_list_length++;

#if OMPI_ENABLE_DEBUG
    /* Spot check: double check that this item is only on the list
       that we just added it to */

    OPAL_THREAD_ADD32( &(item->opal_list_item_refcount), 1 );
    assert(1 == item->opal_list_item_refcount);
    item->opal_list_item_belong_to = list;
#endif
}

  /**
   * Add an item to the list at a specific index location in the list.
   *
   * @param list The list container
   * @param item The item to insert
   * @param index Location 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.
   */
  OPAL_DECLSPEC bool opal_list_insert(opal_list_t *list, opal_list_item_t *item, 
                                      long long idx);


    /**
     * Join a list into another list
     *
     * @param thislist List container for list being operated on
     * @param pos List item in \c thislist marking the position before
     *              which items are inserted
     * @param xlist List container for list being spliced from
     *
     * Join a list into another list.  All of the elements of \c xlist
     * are inserted before \c pos and removed from \c xlist.  
     *
     * This operation is an O(1) operation.  Both \c thislist and \c
     * xlist must be valid list containsers.  \c xlist will be empty
     * but valid after the call.  All pointers to \c opal_list_item_t
     * containers remain valid, including those that point to elements
     * in \c xlist.
     */
    OPAL_DECLSPEC void opal_list_join(opal_list_t *thislist, opal_list_item_t *pos, 
                                      opal_list_t *xlist);


    /**
     * Splice a list into another list
     *
     * @param thislist List container for list being operated on
     * @param pos List item in \c thislist marking the position before
     *             which items are inserted
     * @param xlist List container for list being spliced from
     * @param first List item in \c xlist marking the start of elements 
     *             to be copied into \c thislist
     * @param last List item in \c xlist marking the end of elements
     * to be copied into \c thislist
     *
     * Splice a subset of a list into another list.  The \c [first,
     * last) elements of \c xlist are moved into \c thislist,
     * inserting them before \c pos.  \c pos must be a valid iterator
     * in \c thislist and \c [first, last) must be a valid range in \c
     * xlist.  \c postition must not be in the range \c [first, last).
     * It is, however, valid for \c xlist and \c thislist to be the
     * same list.
     *
     * This is an O(N) operation because the length of both lists must
     * be recomputed.
     */
    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);

    /**
     * Comparison function for opal_list_sort(), below.
     *
     * @param a Pointer to a pointer to an opal_list_item_t.
     * Explanation below.
     * @param b Pointer to a pointer to an opal_list_item_t.
     * Explanation below.
     * @retval 1 if \em a is greater than \em b
     * @retval 0 if \em a is equal to \em b
     * @retval 11 if \em a is less than \em 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 \em
     * double pointers to the items that you need to compare.  Here's
     * a sample compare function to illustrate this point:
     *
     * \verb
     * 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;
     *     }
     * }
     * \endverb
     */
    typedef int (*opal_list_item_compare_fn_t)(opal_list_item_t **a,
                                               opal_list_item_t **b);

    /**
     * Sort a list with a provided compare function.
     *
     * @param list The list to sort
     * @param compare Compare 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).
     */
    OPAL_DECLSPEC int opal_list_sort(opal_list_t* list, opal_list_item_compare_fn_t compare);

#if defined(c_plusplus) || defined(__cplusplus)
}
#endif



#endif /* OPAL_LIST_H */