include/thread_mpi/list.h

   1 /*
   2 This source code file is part of thread_mpi.
   3 Written by Sander Pronk, Erik Lindahl, and possibly others.
   4
   5 Copyright (c) 2009, Sander Pronk, Erik Lindahl.
   6 All rights reserved.
   7
   8 Redistribution and use in source and binary forms, with or without
   9 modification, are permitted provided that the following conditions are met:
  10 1) Redistributions of source code must retain the above copyright
  11    notice, this list of conditions and the following disclaimer.
  12 2) Redistributions in binary form must reproduce the above copyright
  13    notice, this list of conditions and the following disclaimer in the
  14    documentation and/or other materials provided with the distribution.
  15 3) Neither the name of the copyright holders nor the
  16    names of its contributors may be used to endorse or promote products
  17    derived from this software without specific prior written permission.
  18
  19 THIS SOFTWARE IS PROVIDED BY US ''AS IS'' AND ANY
  20 EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
  21 WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  22 DISCLAIMED. IN NO EVENT SHALL WE BE LIABLE FOR ANY
  23 DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
  24 (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  25 LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
  26 ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  27 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
  28 SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29
  30 If you want to redistribute modifications, please consider that
  31 scientific software is very special. Version control is crucial -
  32 bugs must be traceable. We will be happy to consider code for
  33 inclusion in the official distribution, but derived work should not
  34 be called official thread_mpi. Details are found in the README & COPYING
  35 files.
  36 */
  37
  38 #ifndef _TMPI_LIST_H_
  39 #define _TMPI_LIST_H_
  40
  41 #include "thread_mpi/atomic.h"
  42
  43
  44 /** \file
  45  *
  46  * \brief Lock-free list data structures.
  47  *
  48 */
  49
  50
  51 #ifdef __cplusplus
  52 extern "C"
  53 {
  54 #endif
  55 #if 0
  56 } /* Avoids screwing up auto-indentation */
  57 #endif
  58
  59
  60 /**  Lock-free single-ended stack (FIFO)
  61
  62   Is a list with push, pop and detach operations */
  63 typedef struct
  64 {
  65     tMPI_Atomic_ptr_t head;
  66 } tMPI_Stack;
  67
  68 /**  A single element in stack */
  69 typedef struct tMPI_Stack_element
  70 {
  71     struct tMPI_Stack_element *next; /*< pointer to the next stack element */
  72     void *data;               /*< pointer to data */
  73 } tMPI_Stack_element;
  74
  75
  76 /**  Initialize a stack */
  77 void tMPI_Stack_init(tMPI_Stack *st);
  78
  79 /**  Deallocates a stack */
  80 void tMPI_Stack_destroy(tMPI_Stack *st);
  81
  82 /**  Pushes a stack element onto a stack */
  83 void tMPI_Stack_push(tMPI_Stack *st, tMPI_Stack_element *el);
  84
  85 /**  Pops a stack element from  a stack */
  86 tMPI_Stack_element *tMPI_Stack_pop(tMPI_Stack *st);
  87
  88 /**  Detaches entire stack for use by a single thread */
  89 tMPI_Stack_element *tMPI_Stack_detach(tMPI_Stack *st);
  90
  91
  92
  93
  94 /**  Lock-free double-ended queue (LIFO)
  95
  96   Is a list with enqueue and dequeue operations */
  97 typedef struct
  98 {
  99     tMPI_Atomic_ptr_t head, tail;
 100 } tMPI_Queue;
 101
 102 /**  A single element in a queue */
 103 typedef struct tMPI_Queue_element
 104 {
 105     struct tMPI_Queue_element *next,*prev; /*< pointer to the next, prev queue
 106                                                element */
 107     void *data;                     /*< pointer to data */
 108 } tMPI_Queue_element;
 109
 110 /**  Initialize a queue */
 111 void tMPI_Queue_init(tMPI_Queue *q);
 112
 113 /**  Deallocates a queue */
 114 void tMPI_Queue_destroy(tMPI_Queue *q);
 115
 116 /**  Enqueue an element onto the head of a queue */
 117 void tMPI_Queue_enqueue(tMPI_Queue *q, tMPI_Queue_element *qe);
 118
 119 /**  Dequeue an element from the end a queue */
 120 tMPI_Queue_element *tMPI_Queue_dequeue(tMPI_Queue *q);
 121
 122
 123
 124
 125
 126 /**  Lock-free circular doubly linked list */
 127 typedef struct
 128 {
 129     tMPI_Atomic_ptr_t head;
 130 } tMPI_List;
 131
 132 /**  Lock-free circular doubly linked list */
 133 typedef struct tMPI_List_element
 134 {
 135     struct tMPI_List_element *next, *prev;
 136     void *data;
 137 } tMPI_List_element;
 138
 139 void tMPI_List_init(tMPI_List *l);
 140 void tMPI_List_destroy(tMPI_List *l);
 141
 142 tMPI_List_element* tMPI_List_first(tMPI_List *l);
 143 tMPI_List_element* tMPI_List_next(tMPI_List *l,
 144                                   tMPI_List_element *le);
 145 tMPI_List_element* tMPI_List_prev(tMPI_List *l,
 146                                   tMPI_List_element *le);
 147
 148 void tMPI_List_add(tMPI_List *l, tMPI_List_element *le);
 149 void tMPI_List_insert(tMPI_List *l, tMPI_List_element *after,
 150                       tMPI_List_element *le);
 151 void tMPI_List_remove(tMPI_List *l, tMPI_List_element *le);
 152
 153
 154 #ifdef __cplusplus
 155 } /* closing extern "C" */
 156 #endif
 157
 158 #endif /* _TMPI_H_ */