opal_list.h

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

/*
 * Copyright (c) 2004-2005 The Trustees of Indiana University and Indiana
 *                         University Research and Technology
 *                         Corporation.  All rights reserved.
 * Copyright (c) 2004-2006 The University of Tennessee and The University
 *                         of Tennessee Research Foundation.  All rights
 *                         reserved.
 * Copyright (c) 2004-2005 High Performance Computing Center Stuttgart, 
 *                         University of Stuttgart.  All rights reserved.
 * Copyright (c) 2004-2005 The Regents of the University of California.
 *                         All rights reserved.
 * $COPYRIGHT$
 * 
 * Additional copyrights may follow
 * 
 * $HEADER$
 */
/**
 * @file 
 *
 * 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 \em 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 \em 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 OMPI_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.
 */

#ifndef OPAL_LIST_H
#define OPAL_LIST_H

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

#if OMPI_ENABLE_DEBUG
/* Need atomics for debugging (reference counting) */
#include "opal/sys/atomic.h"
#include "opal/threads/mutex.h"
#endif

#if defined(c_plusplus) || defined(__cplusplus)
extern "C" {
#endif
/**
 * \internal
 *
 * The class for the list container.
 */
OPAL_DECLSPEC OBJ_CLASS_DECLARATION(opal_list_t);
/**
 * \internal
 *
 * Base class for items that are put in list (opal_list_t) containers.
 */
OPAL_DECLSPEC OBJ_CLASS_DECLARATION(opal_list_item_t);


/**
 * \internal
 * 
 * Struct of an opal_list_item_t
 */
struct opal_list_item_t
{
    opal_object_t super;
    /**< Generic parent class for all Open MPI objects */
    volatile struct opal_list_item_t *opal_list_next;
    /**< Pointer to next list item */
    volatile struct opal_list_item_t *opal_list_prev;
    /**< Pointer to previous list item */

#if OMPI_ENABLE_DEBUG
    /** Atomic reference count for debugging */
    volatile int32_t opal_list_item_refcount;
    /** The list this item belong to */
    volatile struct opal_list_t* opal_list_item_belong_to;
#endif
};
/**
 * Base type for items that are put in a list (opal_list_t) containers.
 */
typedef struct opal_list_item_t opal_list_item_t;


/**
 * Get the next item in a list.
 *
 * @param item A list item.
 *
 * @returns The next item in the list
 */
#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.
 *
 * @param item A list item.
 *
 * @returns The next item in the list
 */
#define opal_list_get_prev(item) \
    ((item) ? ((opal_list_item_t*) ((opal_list_item_t*)(item))->opal_list_prev) : NULL)


/**
 * \internal
 *
 * Struct of an opal_list_t
 */
struct opal_list_t
{
    opal_object_t       super;
    /**< Generic parent class for all Open MPI objects */
    opal_list_item_t    opal_list_sentinel;
    /**< Head and tail item of the list */
    volatile size_t     opal_list_length;
    /**< Quick reference to the number of items in the list */
};
/**
 * List container type.
 */
typedef struct opal_list_t opal_list_t;


/**
 * Check for empty list
 *
 * @param list The 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.
 */
static inline bool opal_list_is_empty(opal_list_t* list)
{
    return (list->opal_list_sentinel.opal_list_next == 
        &(list->opal_list_sentinel) ? true : false);
}


/**
 * Return the first item on the list (does not remove it).
 *
 * @param list The 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.
 */
static inline opal_list_item_t* opal_list_get_first(opal_list_t* list)
{
    opal_list_item_t* item = (opal_list_item_t*)list->opal_list_sentinel.opal_list_next;
#if OMPI_ENABLE_DEBUG
    /* Spot check: ensure that the first item is only on one list */

    assert(1 == item->opal_list_item_refcount);
    assert( list == item->opal_list_item_belong_to );
#endif

    return item;
}

/**
 * Return the last item on the list (does not remove it).
 *
 * @param list The 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.
 */
static inline opal_list_item_t* opal_list_get_last(opal_list_t* list)
{
    opal_list_item_t* item = (opal_list_item_t *)list->opal_list_sentinel.opal_list_prev;
#if OMPI_ENABLE_DEBUG
    /* Spot check: ensure that the last item is only on one list */

    assert( 1 == item->opal_list_item_refcount );
    assert( list == item->opal_list_item_belong_to );
#endif

    return item;
}

/**
 * Return the beginning of the list; an invalid list entry suitable
 * for comparison only.
 *
 * @param list The 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 \em 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.
 */
static inline opal_list_item_t* opal_list_get_begin(opal_list_t* list)
{
    return &(list->opal_list_sentinel);
}

/**
 * Return the end of the list; an invalid list entry suitable for
 * comparison only.
 *
 * @param list The 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 \em 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.
 */
static inline opal_list_item_t* opal_list_get_end(opal_list_t* list)
{
    return &(list->opal_list_sentinel);
}


/**
 * Return the number of items in a list
 *
 * @param list The 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 \c opal_list_splice or \c opal_list_join may
 * result in this function recomputing the list size, which would be
 * an O(N) operation.  If \c opal_list_splice or \c opal_list_join is
 * never called on the specified list, this function will always be
 * O(1).
 */
static inline size_t opal_list_get_size(opal_list_t* list)
{
#if OMPI_ENABLE_DEBUG && 0
    /* not sure if we really want this running in devel, as it does
     * slow things down.  Wanted for development of splice / join to
     * make sure length was reset properly 
     */
    size_t check_len = 0;
    opal_list_item_t *item;

    for (item = opal_list_get_first(list) ;
         item != opal_list_get_end(list) ;
         item = opal_list_get_next(item)) {
        check_len++;
    }

    if (check_len != list->opal_list_length) {
        fprintf(stderr," Error :: opal_list_get_size - opal_list_length does not match actual list length\n");
        fflush(stderr);
        abort();
    }
#endif

    return list->opal_list_length;
}


/**
 * Remove an item from a list.
 *
 * @param list The list container
 * @param item The 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.
 */
static inline opal_list_item_t *opal_list_remove_item
  (opal_list_t *list, opal_list_item_t *item)
{
#if OMPI_ENABLE_DEBUG
    opal_list_item_t *item_ptr;
    bool found = false;

    /* check to see that the item is in the list */
    for (item_ptr = opal_list_get_first(list);
            item_ptr != opal_list_get_end(list);
            item_ptr = (opal_list_item_t *)(item_ptr->opal_list_next)) {
        if (item_ptr == (opal_list_item_t *) item) {
            found = true;
            break;
        }
    }
    if (!found) {
        fprintf(stderr," Warning :: opal_list_remove_item - the item %p is not on the list %p \n",(void*) item, (void*) list);
        fflush(stderr);
        return (opal_list_item_t *)NULL;
    }

    assert( list == item->opal_list_item_belong_to );
#endif

    /* reset next pointer of previous element */
    item->opal_list_prev->opal_list_next=item->opal_list_next;

    /* reset previous pointer of next element */
    item->opal_list_next->opal_list_prev=item->opal_list_prev;

    list->opal_list_length--;

#if OMPI_ENABLE_DEBUG
    /* Spot check: ensure that this item is still only on one list */

    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->opal_list_prev;
}


/**
 * Append an item to the end of the list.
 *
 * @param list The list container
 * @param item The 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.
 */