pd.if.org Git - liblfds/blob - liblfds/liblfds6.0.0/liblfds600/src/lfds600_queue/lfds600_queue_queue.c

   1 #include "lfds600_queue_internal.h"
   2
   3
   4
   5
   6
   7 /****************************************************************************/
   8 int lfds600_queue_enqueue( struct lfds600_queue_state *qs, void *user_data )
   9 {
  10   LFDS600_ALIGN(LFDS600_ALIGN_DOUBLE_POINTER) struct lfds600_queue_element
  11     *qe[LFDS600_QUEUE_PAC_SIZE];
  12
  13   assert( qs != NULL );
  14   // TRD : user_data can be NULL
  15
  16   lfds600_queue_internal_new_element_from_freelist( qs, qe, user_data );
  17
  18   if( qe[LFDS600_QUEUE_POINTER] == NULL )
  19     return( 0 );
  20
  21   lfds600_queue_internal_queue( qs, qe );
  22
  23   return( 1 );
  24 }
  25
  26
  27
  28
  29
  30 /****************************************************************************/
  31 int lfds600_queue_guaranteed_enqueue( struct lfds600_queue_state *qs, void *user_data )
  32 {
  33   LFDS600_ALIGN(LFDS600_ALIGN_DOUBLE_POINTER) struct lfds600_queue_element
  34     *qe[LFDS600_QUEUE_PAC_SIZE];
  35
  36   assert( qs != NULL );
  37   // TRD : user_data can be NULL
  38
  39   lfds600_queue_internal_guaranteed_new_element_from_freelist( qs, qe, user_data );
  40
  41   if( qe[LFDS600_QUEUE_POINTER] == NULL )
  42     return( 0 );
  43
  44   lfds600_queue_internal_queue( qs, qe );
  45
  46   return( 1 );
  47 }
  48
  49
  50
  51
  52
  53 /****************************************************************************/
  54 void lfds600_queue_internal_queue( struct lfds600_queue_state *qs, struct lfds600_queue_element *qe[LFDS600_QUEUE_PAC_SIZE] )
  55 {
  56   LFDS600_ALIGN(LFDS600_ALIGN_DOUBLE_POINTER) struct lfds600_queue_element
  57     *enqueue[LFDS600_QUEUE_PAC_SIZE],
  58     *next[LFDS600_QUEUE_PAC_SIZE];
  59
  60   unsigned char
  61     cas_result = 0;
  62
  63   assert( qs != NULL );
  64   assert( qe != NULL );
  65
  66   do
  67   {
  68     enqueue[LFDS600_QUEUE_POINTER] = qs->enqueue[LFDS600_QUEUE_POINTER];
  69     enqueue[LFDS600_QUEUE_COUNTER] = qs->enqueue[LFDS600_QUEUE_COUNTER];
  70
  71     next[LFDS600_QUEUE_POINTER] = enqueue[LFDS600_QUEUE_POINTER]->next[LFDS600_QUEUE_POINTER];
  72     next[LFDS600_QUEUE_COUNTER] = enqueue[LFDS600_QUEUE_POINTER]->next[LFDS600_QUEUE_COUNTER];
  73
  74     /* TRD : this if() ensures that the next we read, just above,
  75              really is from qs->enqueue (which we copied into enqueue)
  76     */
  77
  78     if( qs->enqueue[LFDS600_QUEUE_POINTER] == enqueue[LFDS600_QUEUE_POINTER] and qs->enqueue[LFDS600_QUEUE_COUNTER] == enqueue[LFDS600_QUEUE_COUNTER] )
  79     {
  80       if( next[LFDS600_QUEUE_POINTER] == NULL )
  81       {
  82         qe[LFDS600_QUEUE_COUNTER] = next[LFDS600_QUEUE_COUNTER] + 1;
  83         cas_result = lfds600_abstraction_dcas( (volatile lfds600_atom_t *) enqueue[LFDS600_QUEUE_POINTER]->next, (lfds600_atom_t *) qe, (lfds600_atom_t *) next );
  84       }
  85       else
  86       {
  87         next[LFDS600_QUEUE_COUNTER] = enqueue[LFDS600_QUEUE_COUNTER] + 1;
  88         lfds600_abstraction_dcas( (volatile lfds600_atom_t *) qs->enqueue, (lfds600_atom_t *) next, (lfds600_atom_t *) enqueue );
  89       }
  90     }
  91   }
  92   while( cas_result == 0 );
  93
  94   qe[LFDS600_QUEUE_COUNTER] = enqueue[LFDS600_QUEUE_COUNTER] + 1;
  95   lfds600_abstraction_dcas( (volatile lfds600_atom_t *) qs->enqueue, (lfds600_atom_t *) qe, (lfds600_atom_t *) enqueue );
  96
  97   return;
  98 }
  99
 100
 101
 102
 103
 104 /****************************************************************************/
 105 int lfds600_queue_dequeue( struct lfds600_queue_state *qs, void **user_data )
 106 {
 107   LFDS600_ALIGN(LFDS600_ALIGN_DOUBLE_POINTER) struct lfds600_queue_element
 108     *enqueue[LFDS600_QUEUE_PAC_SIZE],
 109     *dequeue[LFDS600_QUEUE_PAC_SIZE],
 110     *next[LFDS600_QUEUE_PAC_SIZE];
 111
 112   unsigned char
 113     cas_result = 0;
 114
 115   int
 116     rv = 1,
 117     state = LFDS600_QUEUE_STATE_UNKNOWN,
 118     finished_flag = LOWERED;
 119
 120   assert( qs != NULL );
 121   assert( user_data != NULL );
 122
 123   do
 124   {
 125     dequeue[LFDS600_QUEUE_POINTER] = qs->dequeue[LFDS600_QUEUE_POINTER];
 126     dequeue[LFDS600_QUEUE_COUNTER] = qs->dequeue[LFDS600_QUEUE_COUNTER];
 127
 128     enqueue[LFDS600_QUEUE_POINTER] = qs->enqueue[LFDS600_QUEUE_POINTER];
 129     enqueue[LFDS600_QUEUE_COUNTER] = qs->enqueue[LFDS600_QUEUE_COUNTER];
 130
 131     next[LFDS600_QUEUE_POINTER] = dequeue[LFDS600_QUEUE_POINTER]->next[LFDS600_QUEUE_POINTER];
 132     next[LFDS600_QUEUE_COUNTER] = dequeue[LFDS600_QUEUE_POINTER]->next[LFDS600_QUEUE_COUNTER];
 133
 134     /* TRD : confirm that dequeue didn't move between reading it
 135              and reading its next pointer
 136     */
 137
 138     if( dequeue[LFDS600_QUEUE_POINTER] == qs->dequeue[LFDS600_QUEUE_POINTER] and dequeue[LFDS600_QUEUE_COUNTER] == qs->dequeue[LFDS600_QUEUE_COUNTER] )
 139     {
 140       if( enqueue[LFDS600_QUEUE_POINTER] == dequeue[LFDS600_QUEUE_POINTER] and next[LFDS600_QUEUE_POINTER] == NULL )
 141         state = LFDS600_QUEUE_STATE_EMPTY;
 142
 143       if( enqueue[LFDS600_QUEUE_POINTER] == dequeue[LFDS600_QUEUE_POINTER] and next[LFDS600_QUEUE_POINTER] != NULL )
 144         state = LFDS600_QUEUE_STATE_ENQUEUE_OUT_OF_PLACE;
 145
 146       if( enqueue[LFDS600_QUEUE_POINTER] != dequeue[LFDS600_QUEUE_POINTER] )
 147         state = LFDS600_QUEUE_STATE_ATTEMPT_DELFDS600_QUEUE;
 148
 149       switch( state )
 150       {
 151         case LFDS600_QUEUE_STATE_EMPTY:
 152           *user_data = NULL;
 153           rv = 0;
 154           finished_flag = RAISED;
 155         break;
 156
 157         case LFDS600_QUEUE_STATE_ENQUEUE_OUT_OF_PLACE:
 158           next[LFDS600_QUEUE_COUNTER] = enqueue[LFDS600_QUEUE_COUNTER] + 1;
 159           lfds600_abstraction_dcas( (volatile lfds600_atom_t *) qs->enqueue, (lfds600_atom_t *) next, (lfds600_atom_t *) enqueue );
 160         break;
 161
 162         case LFDS600_QUEUE_STATE_ATTEMPT_DELFDS600_QUEUE:
 163           *user_data = next[LFDS600_QUEUE_POINTER]->user_data;
 164
 165           next[LFDS600_QUEUE_COUNTER] = dequeue[LFDS600_QUEUE_COUNTER] + 1;
 166           cas_result = lfds600_abstraction_dcas( (volatile lfds600_atom_t *) qs->dequeue, (lfds600_atom_t *) next, (lfds600_atom_t *) dequeue );
 167
 168           if( cas_result == 1 )
 169             finished_flag = RAISED;
 170         break;
 171       }
 172     }
 173   }
 174   while( finished_flag == LOWERED );
 175
 176   if( cas_result == 1 )
 177     lfds600_freelist_push( qs->fs, dequeue[LFDS600_QUEUE_POINTER]->fe );
 178
 179   return( rv );
 180 }
 181