pd.if.org Git - liblfds/blob - liblfds/liblfds7.0.0/liblfds700/src/lfds700_queue/lfds700_queue_enqueue.c

   1 /***** includes *****/
   2 #include "lfds700_queue_internal.h"
   3
   4
   5
   6
   7
   8 /****************************************************************************/
   9 void lfds700_queue_enqueue( struct lfds700_queue_state *qs,
  10                             struct lfds700_queue_element *qe,
  11                             struct lfds700_misc_prng_state *ps )
  12 {
  13   char unsigned
  14     result = 0,
  15     unwanted_result;
  16
  17   lfds700_pal_uint_t
  18     backoff_iteration = LFDS700_MISC_ABSTRACTION_BACKOFF_INITIAL_VALUE;
  19
  20   struct lfds700_queue_element LFDS700_PAL_ALIGN(LFDS700_PAL_ALIGN_DOUBLE_POINTER)
  21     *volatile enqueue[PAC_SIZE],
  22     *new_enqueue[PAC_SIZE],
  23     *volatile next[PAC_SIZE];
  24
  25   LFDS700_PAL_ASSERT( qs != NULL );
  26   LFDS700_PAL_ASSERT( qe != NULL );
  27   LFDS700_PAL_ASSERT( (lfds700_pal_uint_t) qe->next % LFDS700_PAL_ATOMIC_ISOLATION_IN_BYTES == 0 );
  28   LFDS700_PAL_ASSERT( (lfds700_pal_uint_t) &qe->key % LFDS700_PAL_ATOMIC_ISOLATION_IN_BYTES == 0 );
  29   LFDS700_PAL_ASSERT( ps != NULL );
  30
  31   qe->next[COUNTER] = (struct lfds700_queue_element *) LFDS700_MISC_PRNG_GENERATE( ps );
  32   qe->next[POINTER] = NULL;
  33
  34   new_enqueue[POINTER] = qe;
  35
  36   LFDS700_MISC_BARRIER_LOAD;
  37
  38   do
  39   {
  40     enqueue[COUNTER] = qs->enqueue[COUNTER];
  41     enqueue[POINTER] = qs->enqueue[POINTER];
  42
  43     next[COUNTER] = qs->enqueue[POINTER]->next[COUNTER];
  44     next[POINTER] = qs->enqueue[POINTER]->next[POINTER];
  45
  46     LFDS700_MISC_BARRIER_LOAD;
  47
  48     if( qs->enqueue[COUNTER] == enqueue[COUNTER] and qs->enqueue[POINTER] == enqueue[POINTER] )
  49     {
  50       if( next[POINTER] == NULL )
  51       {
  52         new_enqueue[COUNTER] = next[COUNTER] + 1;
  53         LFDS700_MISC_BARRIER_STORE;
  54         LFDS700_PAL_ATOMIC_DWCAS_WITH_BACKOFF( enqueue[POINTER]->next, next, new_enqueue, LFDS700_MISC_CAS_STRENGTH_WEAK, result, backoff_iteration, ps );
  55       }
  56       else
  57       {
  58         next[COUNTER] = enqueue[COUNTER] + 1;
  59         LFDS700_MISC_BARRIER_STORE;
  60         // TRD : strictly, this is a weak CAS, but we do an extra iteration of the main loop on a fake failure, so we set it to be strong
  61         LFDS700_PAL_ATOMIC_DWCAS( qs->enqueue, enqueue, next, LFDS700_MISC_CAS_STRENGTH_STRONG, unwanted_result );
  62       }
  63     }
  64   }
  65   while( result != 1 );
  66
  67   new_enqueue[COUNTER] = enqueue[COUNTER] + 1;
  68   LFDS700_MISC_BARRIER_STORE;
  69   // TRD : move enqueue along; only a weak CAS as the dequeue will solve this if its out of place
  70   LFDS700_PAL_ATOMIC_DWCAS( qs->enqueue, enqueue, new_enqueue, LFDS700_MISC_CAS_STRENGTH_WEAK, unwanted_result );
  71
  72   return;
  73 }
  74