pd.if.org Git - liblfds/blob - liblfds/liblfds6.0.1/liblfds601/src/lfds601_queue/lfds601_queue_queue.c

   1 #include "lfds601_queue_internal.h"\r
   2 \r
   3 \r
   4 \r
   5 \r
   6 \r
   7 /****************************************************************************/\r
   8 int lfds601_queue_enqueue( struct lfds601_queue_state *qs, void *user_data )\r
   9 {\r
  10   LFDS601_ALIGN(LFDS601_ALIGN_DOUBLE_POINTER) struct lfds601_queue_element\r
  11     *qe[LFDS601_QUEUE_PAC_SIZE];\r
  12 \r
  13   assert( qs != NULL );\r
  14   // TRD : user_data can be NULL\r
  15 \r
  16   lfds601_queue_internal_new_element_from_freelist( qs, qe, user_data );\r
  17 \r
  18   if( qe[LFDS601_QUEUE_POINTER] == NULL )\r
  19     return( 0 );\r
  20 \r
  21   lfds601_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 lfds601_queue_guaranteed_enqueue( struct lfds601_queue_state *qs, void *user_data )\r
  32 {\r
  33   LFDS601_ALIGN(LFDS601_ALIGN_DOUBLE_POINTER) struct lfds601_queue_element\r
  34     *qe[LFDS601_QUEUE_PAC_SIZE];\r
  35 \r
  36   assert( qs != NULL );\r
  37   // TRD : user_data can be NULL\r
  38 \r
  39   lfds601_queue_internal_guaranteed_new_element_from_freelist( qs, qe, user_data );\r
  40 \r
  41   if( qe[LFDS601_QUEUE_POINTER] == NULL )\r
  42     return( 0 );\r
  43 \r
  44   lfds601_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 lfds601_queue_internal_queue( struct lfds601_queue_state *qs, struct lfds601_queue_element *qe[LFDS601_QUEUE_PAC_SIZE] )\r
  55 {\r
  56   LFDS601_ALIGN(LFDS601_ALIGN_DOUBLE_POINTER) struct lfds601_queue_element\r
  57     *enqueue[LFDS601_QUEUE_PAC_SIZE],\r
  58     *next[LFDS601_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   do\r
  67   {\r
  68     enqueue[LFDS601_QUEUE_POINTER] = qs->enqueue[LFDS601_QUEUE_POINTER];\r
  69     enqueue[LFDS601_QUEUE_COUNTER] = qs->enqueue[LFDS601_QUEUE_COUNTER];\r
  70 \r
  71     next[LFDS601_QUEUE_POINTER] = enqueue[LFDS601_QUEUE_POINTER]->next[LFDS601_QUEUE_POINTER];\r
  72     next[LFDS601_QUEUE_COUNTER] = enqueue[LFDS601_QUEUE_POINTER]->next[LFDS601_QUEUE_COUNTER];\r
  73 \r
  74     /* TRD : this if() ensures that the next we read, just above,\r
  75              really is from qs->enqueue (which we copied into enqueue)\r
  76     */\r
  77 \r
  78     if( qs->enqueue[LFDS601_QUEUE_POINTER] == enqueue[LFDS601_QUEUE_POINTER] and qs->enqueue[LFDS601_QUEUE_COUNTER] == enqueue[LFDS601_QUEUE_COUNTER] )\r
  79     {\r
  80       if( next[LFDS601_QUEUE_POINTER] == NULL )\r
  81       {\r
  82         qe[LFDS601_QUEUE_COUNTER] = next[LFDS601_QUEUE_COUNTER] + 1;\r
  83         cas_result = lfds601_abstraction_dcas( (volatile lfds601_atom_t *) enqueue[LFDS601_QUEUE_POINTER]->next, (lfds601_atom_t *) qe, (lfds601_atom_t *) next );\r
  84       }\r
  85       else\r
  86       {\r
  87         next[LFDS601_QUEUE_COUNTER] = enqueue[LFDS601_QUEUE_COUNTER] + 1;\r
  88         lfds601_abstraction_dcas( (volatile lfds601_atom_t *) qs->enqueue, (lfds601_atom_t *) next, (lfds601_atom_t *) enqueue );\r
  89       }\r
  90     }\r
  91   }\r
  92   while( cas_result == 0 );\r
  93 \r
  94   qe[LFDS601_QUEUE_COUNTER] = enqueue[LFDS601_QUEUE_COUNTER] + 1;\r
  95   lfds601_abstraction_dcas( (volatile lfds601_atom_t *) qs->enqueue, (lfds601_atom_t *) qe, (lfds601_atom_t *) enqueue );\r
  96 \r
  97   return;\r
  98 }\r
  99 \r
 100 \r
 101 \r
 102 \r
 103 \r
 104 /****************************************************************************/\r
 105 int lfds601_queue_dequeue( struct lfds601_queue_state *qs, void **user_data )\r
 106 {\r
 107   LFDS601_ALIGN(LFDS601_ALIGN_DOUBLE_POINTER) struct lfds601_queue_element\r
 108     *enqueue[LFDS601_QUEUE_PAC_SIZE],\r
 109     *dequeue[LFDS601_QUEUE_PAC_SIZE],\r
 110     *next[LFDS601_QUEUE_PAC_SIZE];\r
 111 \r
 112   unsigned char\r
 113     cas_result = 0;\r
 114 \r
 115   int\r
 116     rv = 1,\r
 117     state = LFDS601_QUEUE_STATE_UNKNOWN,\r
 118     finished_flag = LOWERED;\r
 119 \r
 120   assert( qs != NULL );\r
 121   assert( user_data != NULL );\r
 122 \r
 123   do\r
 124   {\r
 125     dequeue[LFDS601_QUEUE_POINTER] = qs->dequeue[LFDS601_QUEUE_POINTER];\r
 126     dequeue[LFDS601_QUEUE_COUNTER] = qs->dequeue[LFDS601_QUEUE_COUNTER];\r
 127 \r
 128     enqueue[LFDS601_QUEUE_POINTER] = qs->enqueue[LFDS601_QUEUE_POINTER];\r
 129     enqueue[LFDS601_QUEUE_COUNTER] = qs->enqueue[LFDS601_QUEUE_COUNTER];\r
 130 \r
 131     next[LFDS601_QUEUE_POINTER] = dequeue[LFDS601_QUEUE_POINTER]->next[LFDS601_QUEUE_POINTER];\r
 132     next[LFDS601_QUEUE_COUNTER] = dequeue[LFDS601_QUEUE_POINTER]->next[LFDS601_QUEUE_COUNTER];\r
 133 \r
 134     /* TRD : confirm that dequeue didn't move between reading it\r
 135              and reading its next pointer\r
 136     */\r
 137 \r
 138     if( dequeue[LFDS601_QUEUE_POINTER] == qs->dequeue[LFDS601_QUEUE_POINTER] and dequeue[LFDS601_QUEUE_COUNTER] == qs->dequeue[LFDS601_QUEUE_COUNTER] )\r
 139     {\r
 140       if( enqueue[LFDS601_QUEUE_POINTER] == dequeue[LFDS601_QUEUE_POINTER] and next[LFDS601_QUEUE_POINTER] == NULL )\r
 141         state = LFDS601_QUEUE_STATE_EMPTY;\r
 142 \r
 143       if( enqueue[LFDS601_QUEUE_POINTER] == dequeue[LFDS601_QUEUE_POINTER] and next[LFDS601_QUEUE_POINTER] != NULL )\r
 144         state = LFDS601_QUEUE_STATE_ENQUEUE_OUT_OF_PLACE;\r
 145 \r
 146       if( enqueue[LFDS601_QUEUE_POINTER] != dequeue[LFDS601_QUEUE_POINTER] )\r
 147         state = LFDS601_QUEUE_STATE_ATTEMPT_DELFDS601_QUEUE;\r
 148 \r
 149       switch( state )\r
 150       {\r
 151         case LFDS601_QUEUE_STATE_EMPTY:\r
 152           *user_data = NULL;\r
 153           rv = 0;\r
 154           finished_flag = RAISED;\r
 155         break;\r
 156 \r
 157         case LFDS601_QUEUE_STATE_ENQUEUE_OUT_OF_PLACE:\r
 158           next[LFDS601_QUEUE_COUNTER] = enqueue[LFDS601_QUEUE_COUNTER] + 1;\r
 159           lfds601_abstraction_dcas( (volatile lfds601_atom_t *) qs->enqueue, (lfds601_atom_t *) next, (lfds601_atom_t *) enqueue );\r
 160         break;\r
 161 \r
 162         case LFDS601_QUEUE_STATE_ATTEMPT_DELFDS601_QUEUE:\r
 163           *user_data = next[LFDS601_QUEUE_POINTER]->user_data;\r
 164 \r
 165           next[LFDS601_QUEUE_COUNTER] = dequeue[LFDS601_QUEUE_COUNTER] + 1;\r
 166           cas_result = lfds601_abstraction_dcas( (volatile lfds601_atom_t *) qs->dequeue, (lfds601_atom_t *) next, (lfds601_atom_t *) dequeue );\r
 167 \r
 168           if( cas_result == 1 )\r
 169             finished_flag = RAISED;\r
 170         break;\r
 171       }\r
 172     }\r
 173   }\r
 174   while( finished_flag == LOWERED );\r
 175 \r
 176   if( cas_result == 1 )\r
 177     lfds601_freelist_push( qs->fs, dequeue[LFDS601_QUEUE_POINTER]->fe );\r
 178 \r
 179   return( rv );\r
 180 }\r
 181 \r