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

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