utils_list.h

Path MPICH-V for MPICH the MPI Implementation

#ifndef LIST_TYPES_H_HAS_BEEN_INCLUDED
#define LIST_TYPES_H_HAS_BEEN_INCLUDED

#include "debug.h"
#include <stdlib.h>
#include "utils_mutex.h"

typedef unsigned int keyid_t;

#if defined(__i386__)
#ifndef __GNUC__
#warning "Non GNUC Compiler, test_and_set has no effect and multithreaded list do not work any more"
static int test_and_set(unsigned int *addr, int val) {
  return val;
}
static void clear(unsigned int *addr) {}
#else /* GNUC */
inline static int test_and_set(volatile unsigned int *addr, int val) {
    int oldval, newval = val;
    /* Note: the "xchg" instruction does not need a "lock" prefix */
    __asm__ __volatile__("xchgl %0, %1"
        : "=r"(oldval), "=m"(*(addr))
        : "r"(newval), "m"(*(addr)));
    return oldval;
}
inline static void clear(volatile unsigned int *addr) {
    int oldval;
    /* Note: the "xchg" instruction does not need a "lock" prefix */
    __asm__ __volatile__("xchgl %0, %1"
        : "=r"(oldval), "=m"(*(addr))
        : "0"(0), "m"(*(addr)));
}
#endif /* GNUC */
#else
#   error need implementation of test_and_set
#endif

#define __PASTE(X,Y)  X##Y
#define PASTE(A,B)  __PASTE(A, B)

typedef struct __SELEMENT {
    unsigned int       iKey;
    struct __SELEMENT* pNext;
    struct __SELEMENT* pPrev;
    void*              data;
} sElement_t;

/* double linked list structures and defines */
typedef struct __dll_t {
    READ_WRITE_LOCK_TYPE lock;
    sElement_t* head;
} dll_t;

/* There are 2 kind of functions. Generic one that take a void* as user argument.
 * Normal user has to use these. But for "advanced" users there is another way. Put
 * a sElement_t structure on your struct head, and use the __versions of these functions.
 */
void* dll_add_head( dll_t* pdll, void* data );
void* dll_add_tail( dll_t* pdll, void* data );
void* dll_remove_head( dll_t* pdll );
void* dll_remove_elem( dll_t* pdll, void* data );
void dll_dump( dll_t* pdll, void (*fct)(void*) );
dll_t* dll_create( dll_t* pdll );
#define dll_is_empty(pdll) (((dll_t*)pdll)->head == NULL)
/* advanced functions */
sElement_t* __dll_add_head( dll_t* pdll, sElement_t* pdllElem );
sElement_t* __dll_add_tail( dll_t* pdll, sElement_t* pdllElem );
sElement_t* __dll_remove_head( dll_t* pdll );
sElement_t* __dll_remove_elem( dll_t* pdll, sElement_t* pdllElem );
void __dll_dump( dll_t* pdll, void (*fct)(sElement_t*) );

/* linked list structures and defines */
typedef struct __ll_t {
    READ_WRITE_LOCK_TYPE lock;
    sElement_t* head;
    sElement_t* tail;
    int size;
} LinkedList_t;

void* ll_add_head( LinkedList_t* pll, void* data );
void* ll_add_tail( LinkedList_t* pll, void* data );

/** add a data in linked list, sorted by function given in argument
 * @param pll : pointer to a linked list
 * @param data : pointer to the data to add
 * @param comparator : function (void*->void*->int)
 * @return : void*
 */
void* ll_add_sorted( LinkedList_t *pll,void *data, int (*comparator)(void *,void *));
void* ll_remove_head( LinkedList_t* pll );
void* ll_remove( LinkedList_t* pll, void* data );
void *ll_remove_by_key( LinkedList_t* pll,  int (*fct)(void*, void *), void *param);
void *ll_find_by_key( LinkedList_t* pll,  int (*fct)(void*, void *), void *param);
void ll_dump( LinkedList_t* pll, void (*fct)(void*) );
LinkedList_t* ll_create( LinkedList_t* pList );
#define ll_is_empty(pll) (((LinkedList_t*)pll)->head == NULL )
/* advanced functions */
sElement_t* __ll_add_head( LinkedList_t* pll, sElement_t* pElem );
sElement_t* __ll_add_tail( LinkedList_t* pll, sElement_t* pElem );
sElement_t* __ll_remove_head( LinkedList_t* pll );


extern LinkedList_t pFreeElements;
#define ADD_TO_FREE_ELEMENTS(PELEM) __ll_add_head(&pFreeElements, PELEM)
#define GET_NEW_ELEMENT(PELEM) \
    { if( ((PELEM) = __ll_remove_head(&pFreeElements)) == NULL ) { \
	  (PELEM) = (sElement_t*)calloc(1, sizeof(sElement_t)); \
      } }

/* hash table structures and defines */
typedef keyid_t (*pf_hash)(keyid_t);
typedef struct __HASH_T {
    size_t iSize;
    pf_hash keyFct;
    sElement_t* ghostElem;
    LinkedList_t column[1];
} hash_t;

hash_t* hash_create( hash_t* phash, pf_hash fct );
void* hash_add( hash_t* phash, keyid_t iKey, void* pData );
void* hash_search( hash_t* phash, keyid_t key );
void* hash_remove( hash_t* phash, keyid_t key );
int hash_dump_key( hash_t* pHash, keyid_t iKey, void (*fct)(sElement_t*) );
void hash_dump( hash_t* phash, void (*fct)(sElement_t*) );
#define hash_is_empty( phash )               (((hash_t*)phash)->nbElems == 0)
sElement_t* __hash_add( LinkedList_t* poll, sElement_t* pElem );
sElement_t* __hash_search( hash_t* phash, keyid_t key );
sElement_t* __hash_get_next( hash_t* phash, keyid_t key, sElement_t* phllElem );
sElement_t* __hash_remove( hash_t* phash, sElement_t* phllElem );

#endif  /* LIST_TYPES_H_HAS_BEEN_INCLUDED */