pd.if.org Git - liblfds/blob - liblfds/liblfds7.1.0/liblfds710/src/lfds710_queue_unbounded_manyproducer_manyconsumer/lfds710_queue_unbounded_manyproducer_manyconsumer_query.c

   1 /***** includes *****/
   2 #include "lfds710_queue_unbounded_manyproducer_manyconsumer_internal.h"
   3
   4 /***** private prototypes *****/
   5 static void lfds710_queue_umm_internal_validate( struct lfds710_queue_umm_state *qumms,
   6                                                  struct lfds710_misc_validation_info *vi,
   7                                                  enum lfds710_misc_validity *lfds710_queue_umm_validity );
   8
   9
  10
  11
  12
  13 /****************************************************************************/
  14 void lfds710_queue_umm_query( struct lfds710_queue_umm_state *qumms,
  15                               enum lfds710_queue_umm_query query_type,
  16                               void *query_input,
  17                               void *query_output )
  18 {
  19   struct lfds710_queue_umm_element
  20     *qumme;
  21
  22   LFDS710_MISC_BARRIER_LOAD;
  23
  24   LFDS710_PAL_ASSERT( qumms != NULL );
  25   // TRD : query_type can be any value in its range
  26
  27   switch( query_type )
  28   {
  29     case LFDS710_QUEUE_UMM_QUERY_SINGLETHREADED_GET_COUNT:
  30       LFDS710_PAL_ASSERT( query_input == NULL );
  31       LFDS710_PAL_ASSERT( query_output != NULL );
  32
  33       *(lfds710_pal_uint_t *) query_output = 0;
  34
  35       qumme = (struct lfds710_queue_umm_element *) qumms->dequeue[POINTER];
  36
  37       while( qumme != NULL )
  38       {
  39         ( *(lfds710_pal_uint_t *) query_output )++;
  40         qumme = (struct lfds710_queue_umm_element *) qumme->next[POINTER];
  41       }
  42
  43       // TRD : remember there is a dummy element in the queue
  44       ( *(lfds710_pal_uint_t *) query_output )--;
  45     break;
  46
  47     case LFDS710_QUEUE_UMM_QUERY_SINGLETHREADED_VALIDATE:
  48       // TRD : query_input can be NULL
  49       LFDS710_PAL_ASSERT( query_output != NULL );
  50
  51       lfds710_queue_umm_internal_validate( qumms, (struct lfds710_misc_validation_info *) query_input, (enum lfds710_misc_validity *) query_output );
  52     break;
  53   }
  54
  55   return;
  56 }
  57
  58
  59
  60
  61
  62 /****************************************************************************/
  63 static void lfds710_queue_umm_internal_validate( struct lfds710_queue_umm_state *qumms,
  64                                                  struct lfds710_misc_validation_info *vi,
  65                                                  enum lfds710_misc_validity *lfds710_queue_umm_validity )
  66 {
  67   lfds710_pal_uint_t
  68     number_elements = 0;
  69
  70   struct lfds710_queue_umm_element
  71     *qumme_fast,
  72     *qumme_slow;
  73
  74   LFDS710_PAL_ASSERT( qumms != NULL );
  75   // TRD : vi can be NULL
  76   LFDS710_PAL_ASSERT( lfds710_queue_umm_validity != NULL );
  77
  78   *lfds710_queue_umm_validity = LFDS710_MISC_VALIDITY_VALID;
  79
  80   qumme_slow = qumme_fast = (struct lfds710_queue_umm_element *) qumms->dequeue[POINTER];
  81
  82   /* TRD : first, check for a loop
  83            we have two pointers
  84            both of which start at the dequeue end of the queue
  85            we enter a loop
  86            and on each iteration
  87            we advance one pointer by one element
  88            and the other by two
  89
  90            we exit the loop when both pointers are NULL
  91            (have reached the end of the queue)
  92
  93            or
  94
  95            if we fast pointer 'sees' the slow pointer
  96            which means we have a loop
  97   */
  98
  99   if( qumme_slow != NULL )
 100     do
 101     {
 102       qumme_slow = qumme_slow->next[POINTER];
 103
 104       if( qumme_fast != NULL )
 105         qumme_fast = qumme_fast->next[POINTER];
 106
 107       if( qumme_fast != NULL )
 108         qumme_fast = qumme_fast->next[POINTER];
 109     }
 110     while( qumme_slow != NULL and qumme_fast != qumme_slow );
 111
 112   if( qumme_fast != NULL and qumme_slow != NULL and qumme_fast == qumme_slow )
 113     *lfds710_queue_umm_validity = LFDS710_MISC_VALIDITY_INVALID_LOOP;
 114
 115   /* TRD : now check for expected number of elements
 116            vi can be NULL, in which case we do not check
 117            we know we don't have a loop from our earlier check
 118   */
 119
 120   if( *lfds710_queue_umm_validity == LFDS710_MISC_VALIDITY_VALID and vi != NULL )
 121   {
 122     lfds710_queue_umm_query( qumms, LFDS710_QUEUE_UMM_QUERY_SINGLETHREADED_GET_COUNT, NULL, (void *) &number_elements );
 123
 124     if( number_elements < vi->min_elements )
 125       *lfds710_queue_umm_validity = LFDS710_MISC_VALIDITY_INVALID_MISSING_ELEMENTS;
 126
 127     if( number_elements > vi->max_elements )
 128       *lfds710_queue_umm_validity = LFDS710_MISC_VALIDITY_INVALID_ADDITIONAL_ELEMENTS;
 129   }
 130
 131   return;
 132 }
 133