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

   1 /***** includes *****/
   2 #include "lfds700_queue_internal.h"
   3
   4
   5
   6
   7
   8 /****************************************************************************/
   9 int lfds700_queue_dequeue( 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   enum lfds700_queue_queue_state
  18     state = LFDS700_QUEUE_QUEUE_STATE_UNKNOWN;
  19
  20   int
  21     rv = 1,
  22     finished_flag = LFDS700_MISC_FLAG_LOWERED;
  23
  24   lfds700_pal_uint_t
  25     backoff_iteration = LFDS700_MISC_ABSTRACTION_BACKOFF_INITIAL_VALUE;
  26
  27   struct lfds700_queue_element LFDS700_PAL_ALIGN(LFDS700_PAL_ALIGN_DOUBLE_POINTER)
  28     *dequeue[PAC_SIZE],
  29     *enqueue[PAC_SIZE],
  30     *next[PAC_SIZE];
  31
  32   void
  33     *key = NULL,
  34     *value = NULL;
  35
  36   LFDS700_PAL_ASSERT( qs != NULL );
  37   LFDS700_PAL_ASSERT( qe != NULL );
  38   LFDS700_PAL_ASSERT( ps != NULL );
  39
  40   LFDS700_MISC_BARRIER_LOAD;
  41
  42   do
  43   {
  44     dequeue[COUNTER] = qs->dequeue[COUNTER];
  45     dequeue[POINTER] = qs->dequeue[POINTER];
  46
  47     enqueue[COUNTER] = qs->enqueue[COUNTER];
  48     enqueue[POINTER] = qs->enqueue[POINTER];
  49
  50     next[COUNTER] = qs->dequeue[POINTER]->next[COUNTER];
  51     next[POINTER] = qs->dequeue[POINTER]->next[POINTER];
  52
  53     LFDS700_MISC_BARRIER_LOAD;
  54
  55     if( dequeue[COUNTER] == qs->dequeue[COUNTER] and dequeue[POINTER] == qs->dequeue[POINTER] )
  56     {
  57       if( enqueue[POINTER] == dequeue[POINTER] and next[POINTER] == NULL )
  58         state = LFDS700_QUEUE_QUEUE_STATE_EMPTY;
  59
  60       if( enqueue[POINTER] == dequeue[POINTER] and next[POINTER] != NULL )
  61         state = LFDS700_QUEUE_QUEUE_STATE_ENQUEUE_OUT_OF_PLACE;
  62
  63       if( enqueue[POINTER] != dequeue[POINTER] )
  64         state = LFDS700_QUEUE_QUEUE_STATE_ATTEMPT_DEQUEUE;
  65
  66       switch( state )
  67       {
  68         case LFDS700_QUEUE_QUEUE_STATE_UNKNOWN:
  69           // TRD : eliminates compiler warning
  70         break;
  71
  72         case LFDS700_QUEUE_QUEUE_STATE_EMPTY:
  73           rv = 0;
  74           *qe = NULL;
  75           finished_flag = LFDS700_MISC_FLAG_RAISED;
  76         break;
  77
  78         case LFDS700_QUEUE_QUEUE_STATE_ENQUEUE_OUT_OF_PLACE:
  79           next[COUNTER] = enqueue[COUNTER] + 1;
  80           LFDS700_MISC_BARRIER_STORE;
  81           LFDS700_PAL_ATOMIC_DWCAS( qs->enqueue, enqueue, next, LFDS700_MISC_CAS_STRENGTH_WEAK, unwanted_result );
  82         break;
  83
  84         case LFDS700_QUEUE_QUEUE_STATE_ATTEMPT_DEQUEUE:
  85           key = next[POINTER]->key;
  86           value = next[POINTER]->value;
  87
  88           next[COUNTER] = dequeue[COUNTER] + 1;
  89           LFDS700_MISC_BARRIER_STORE;
  90           LFDS700_PAL_ATOMIC_DWCAS_WITH_BACKOFF( qs->dequeue, dequeue, next, LFDS700_MISC_CAS_STRENGTH_WEAK, result, backoff_iteration, ps );
  91
  92           if( result == 1 )
  93             finished_flag = LFDS700_MISC_FLAG_RAISED;
  94         break;
  95       }
  96     }
  97   }
  98   while( finished_flag == LFDS700_MISC_FLAG_LOWERED );
  99
 100   if( result == 1 )
 101   {
 102     *qe = dequeue[POINTER];
 103     (*qe)->key = key;
 104     (*qe)->value = value;
 105   }
 106
 107   return( rv );
 108 }
 109