pd.if.org Git - liblfds/blob - liblfds/liblfds6.1.1/liblfds611/src/lfds611_queue/lfds611_queue_queue.c

   1 #include "lfds611_queue_internal.h"\r
   2 \r
   3 \r
   4 \r
   5 \r
   6 \r
   7 /****************************************************************************/\r
   8 int lfds611_queue_enqueue( struct lfds611_queue_state *qs, void *user_data )\r
   9 {\r
  10   LFDS611_ALIGN(LFDS611_ALIGN_DOUBLE_POINTER) struct lfds611_queue_element\r
  11     *qe[LFDS611_QUEUE_PAC_SIZE];\r
  12 \r
  13   assert( qs != NULL );\r
  14   // TRD : user_data can be NULL\r
  15 \r
  16   lfds611_queue_internal_new_element_from_freelist( qs, qe, user_data );\r
  17 \r
  18   if( qe[LFDS611_QUEUE_POINTER] == NULL )\r
  19     return( 0 );\r
  20 \r
  21   lfds611_queue_internal_queue( qs, qe );\r
  22 \r
  23   return( 1 );\r
  24 }\r
  25 \r
  26 \r
  27 \r
  28 \r
  29 \r
  30 /****************************************************************************/\r
  31 int lfds611_queue_guaranteed_enqueue( struct lfds611_queue_state *qs, void *user_data )\r
  32 {\r
  33   LFDS611_ALIGN(LFDS611_ALIGN_DOUBLE_POINTER) struct lfds611_queue_element\r
  34     *qe[LFDS611_QUEUE_PAC_SIZE];\r
  35 \r
  36   assert( qs != NULL );\r
  37   // TRD : user_data can be NULL\r
  38 \r
  39   lfds611_queue_internal_guaranteed_new_element_from_freelist( qs, qe, user_data );\r
  40 \r
  41   if( qe[LFDS611_QUEUE_POINTER] == NULL )\r
  42     return( 0 );\r
  43 \r
  44   lfds611_queue_internal_queue( qs, qe );\r
  45 \r
  46   return( 1 );\r
  47 }\r
  48 \r
  49 \r
  50 \r
  51 \r
  52 \r
  53 /****************************************************************************/\r
  54 void lfds611_queue_internal_queue( struct lfds611_queue_state *qs, struct lfds611_queue_element *qe[LFDS611_QUEUE_PAC_SIZE] )\r
  55 {\r
  56   LFDS611_ALIGN(LFDS611_ALIGN_DOUBLE_POINTER) struct lfds611_queue_element\r
  57     *enqueue[LFDS611_QUEUE_PAC_SIZE],\r
  58     *next[LFDS611_QUEUE_PAC_SIZE];\r
  59 \r
  60   unsigned char\r
  61     cas_result = 0;\r
  62 \r
  63   assert( qs != NULL );\r
  64   assert( qe != NULL );\r
  65 \r
  66   // TRD : the DCAS operation issues a read and write barrier, so we don't need a read barrier in the do() loop\r
  67 \r
  68   LFDS611_BARRIER_LOAD;\r
  69 \r
  70   do\r
  71   {\r
  72     enqueue[LFDS611_QUEUE_POINTER] = qs->enqueue[LFDS611_QUEUE_POINTER];\r
  73     enqueue[LFDS611_QUEUE_COUNTER] = qs->enqueue[LFDS611_QUEUE_COUNTER];\r
  74 \r
  75     next[LFDS611_QUEUE_POINTER] = enqueue[LFDS611_QUEUE_POINTER]->next[LFDS611_QUEUE_POINTER];\r
  76     next[LFDS611_QUEUE_COUNTER] = enqueue[LFDS611_QUEUE_POINTER]->next[LFDS611_QUEUE_COUNTER];\r
  77 \r
  78     /* TRD : this if() ensures that the next we read, just above,\r
  79              really is from qs->enqueue (which we copied into enqueue)\r
  80     */\r
  81 \r
  82     LFDS611_BARRIER_LOAD;\r
  83 \r
  84     if( qs->enqueue[LFDS611_QUEUE_POINTER] == enqueue[LFDS611_QUEUE_POINTER] and qs->enqueue[LFDS611_QUEUE_COUNTER] == enqueue[LFDS611_QUEUE_COUNTER] )\r
  85     {\r
  86       if( next[LFDS611_QUEUE_POINTER] == NULL )\r
  87       {\r
  88         qe[LFDS611_QUEUE_COUNTER] = next[LFDS611_QUEUE_COUNTER] + 1;\r
  89         cas_result = lfds611_abstraction_dcas( (volatile lfds611_atom_t *) enqueue[LFDS611_QUEUE_POINTER]->next, (lfds611_atom_t *) qe, (lfds611_atom_t *) next );\r
  90       }\r
  91       else\r
  92       {\r
  93         next[LFDS611_QUEUE_COUNTER] = enqueue[LFDS611_QUEUE_COUNTER] + 1;\r
  94         lfds611_abstraction_dcas( (volatile lfds611_atom_t *) qs->enqueue, (lfds611_atom_t *) next, (lfds611_atom_t *) enqueue );\r
  95       }\r
  96     }\r
  97   }\r
  98   while( cas_result == 0 );\r
  99 \r
 100   qe[LFDS611_QUEUE_COUNTER] = enqueue[LFDS611_QUEUE_COUNTER] + 1;\r
 101   lfds611_abstraction_dcas( (volatile lfds611_atom_t *) qs->enqueue, (lfds611_atom_t *) qe, (lfds611_atom_t *) enqueue );\r
 102 \r
 103   return;\r
 104 }\r
 105 \r
 106 \r
 107 \r
 108 \r
 109 \r
 110 /****************************************************************************/\r
 111 int lfds611_queue_dequeue( struct lfds611_queue_state *qs, void **user_data )\r
 112 {\r
 113   LFDS611_ALIGN(LFDS611_ALIGN_DOUBLE_POINTER) struct lfds611_queue_element\r
 114     *enqueue[LFDS611_QUEUE_PAC_SIZE],\r
 115     *dequeue[LFDS611_QUEUE_PAC_SIZE],\r
 116     *next[LFDS611_QUEUE_PAC_SIZE];\r
 117 \r
 118   unsigned char\r
 119     cas_result = 0;\r
 120 \r
 121   int\r
 122     rv = 1,\r
 123     state = LFDS611_QUEUE_STATE_UNKNOWN,\r
 124     finished_flag = LOWERED;\r
 125 \r
 126   assert( qs != NULL );\r
 127   assert( user_data != NULL );\r
 128 \r
 129   // TRD : the DCAS operation issues a read and write barrier, so we don't need a read barrier in the do() loop\r
 130 \r
 131   LFDS611_BARRIER_LOAD;\r
 132 \r
 133   do\r
 134   {\r
 135     dequeue[LFDS611_QUEUE_POINTER] = qs->dequeue[LFDS611_QUEUE_POINTER];\r
 136     dequeue[LFDS611_QUEUE_COUNTER] = qs->dequeue[LFDS611_QUEUE_COUNTER];\r
 137 \r
 138     enqueue[LFDS611_QUEUE_POINTER] = qs->enqueue[LFDS611_QUEUE_POINTER];\r
 139     enqueue[LFDS611_QUEUE_COUNTER] = qs->enqueue[LFDS611_QUEUE_COUNTER];\r
 140 \r
 141     next[LFDS611_QUEUE_POINTER] = dequeue[LFDS611_QUEUE_POINTER]->next[LFDS611_QUEUE_POINTER];\r
 142     next[LFDS611_QUEUE_COUNTER] = dequeue[LFDS611_QUEUE_POINTER]->next[LFDS611_QUEUE_COUNTER];\r
 143 \r
 144     /* TRD : confirm that dequeue didn't move between reading it\r
 145              and reading its next pointer\r
 146     */\r
 147 \r
 148     LFDS611_BARRIER_LOAD;\r
 149 \r
 150     if( dequeue[LFDS611_QUEUE_POINTER] == qs->dequeue[LFDS611_QUEUE_POINTER] and dequeue[LFDS611_QUEUE_COUNTER] == qs->dequeue[LFDS611_QUEUE_COUNTER] )\r
 151     {\r
 152       if( enqueue[LFDS611_QUEUE_POINTER] == dequeue[LFDS611_QUEUE_POINTER] and next[LFDS611_QUEUE_POINTER] == NULL )\r
 153         state = LFDS611_QUEUE_STATE_EMPTY;\r
 154 \r
 155       if( enqueue[LFDS611_QUEUE_POINTER] == dequeue[LFDS611_QUEUE_POINTER] and next[LFDS611_QUEUE_POINTER] != NULL )\r
 156         state = LFDS611_QUEUE_STATE_ENQUEUE_OUT_OF_PLACE;\r
 157 \r
 158       if( enqueue[LFDS611_QUEUE_POINTER] != dequeue[LFDS611_QUEUE_POINTER] )\r
 159         state = LFDS611_QUEUE_STATE_ATTEMPT_DELFDS611_QUEUE;\r
 160 \r
 161       switch( state )\r
 162       {\r
 163         case LFDS611_QUEUE_STATE_EMPTY:\r
 164           *user_data = NULL;\r
 165           rv = 0;\r
 166           finished_flag = RAISED;\r
 167         break;\r
 168 \r
 169         case LFDS611_QUEUE_STATE_ENQUEUE_OUT_OF_PLACE:\r
 170           next[LFDS611_QUEUE_COUNTER] = enqueue[LFDS611_QUEUE_COUNTER] + 1;\r
 171           lfds611_abstraction_dcas( (volatile lfds611_atom_t *) qs->enqueue, (lfds611_atom_t *) next, (lfds611_atom_t *) enqueue );\r
 172         break;\r
 173 \r
 174         case LFDS611_QUEUE_STATE_ATTEMPT_DELFDS611_QUEUE:\r
 175           *user_data = next[LFDS611_QUEUE_POINTER]->user_data;\r
 176 \r
 177           next[LFDS611_QUEUE_COUNTER] = dequeue[LFDS611_QUEUE_COUNTER] + 1;\r
 178           cas_result = lfds611_abstraction_dcas( (volatile lfds611_atom_t *) qs->dequeue, (lfds611_atom_t *) next, (lfds611_atom_t *) dequeue );\r
 179 \r
 180           if( cas_result == 1 )\r
 181             finished_flag = RAISED;\r
 182         break;\r
 183       }\r
 184     }\r
 185   }\r
 186   while( finished_flag == LOWERED );\r
 187 \r
 188   if( cas_result == 1 )\r
 189     lfds611_freelist_push( qs->fs, dequeue[LFDS611_QUEUE_POINTER]->fe );\r
 190 \r
 191   return( rv );\r
 192 }\r
 193 \r