pd.if.org Git - liblfds/blob - liblfds/liblfds6.1.0/liblfds610/src/lfds610_queue/lfds610_queue_query.c

   1 #include "lfds610_queue_internal.h"
   2
   3
   4
   5
   6
   7 /****************************************************************************/
   8 #pragma warning( disable : 4100 )
   9
  10 void lfds610_queue_query( struct lfds610_queue_state *qs, enum lfds610_queue_query_type query_type, void *query_input, void *query_output )
  11 {
  12   assert( qs != NULL );
  13   // TRD : query_type can be any value in its range
  14   // TRD : query_input can be NULL
  15   assert( query_output != NULL );
  16
  17   switch( query_type )
  18   {
  19     case LFDS610_QUEUE_QUERY_ELEMENT_COUNT:
  20       assert( query_input == NULL );
  21
  22       lfds610_freelist_query( qs->fs, LFDS610_FREELIST_QUERY_ELEMENT_COUNT, NULL, query_output );
  23     break;
  24
  25     case LFDS610_QUEUE_QUERY_VALIDATE:
  26       // TRD : query_input can be NULL
  27
  28       lfds610_queue_internal_validate( qs, (struct lfds610_validation_info *) query_input, (enum lfds610_data_structure_validity *) query_output, ((enum lfds610_data_structure_validity *) query_output)+1 );
  29     break;
  30   }
  31
  32   return;
  33 }
  34
  35 #pragma warning( default : 4100 )
  36
  37
  38
  39
  40
  41 /****************************************************************************/
  42 void lfds610_queue_internal_validate( struct lfds610_queue_state *qs, struct lfds610_validation_info *vi, enum lfds610_data_structure_validity *lfds610_queue_validity, enum lfds610_data_structure_validity *lfds610_freelist_validity )
  43 {
  44   struct lfds610_queue_element
  45     *qe,
  46     *qe_slow,
  47     *qe_fast;
  48
  49   lfds610_atom_t
  50     element_count = 0,
  51     total_elements;
  52
  53   struct lfds610_validation_info
  54     lfds610_freelist_vi;
  55
  56   assert( qs != NULL );
  57   // TRD : vi can be NULL
  58   assert( lfds610_queue_validity != NULL );
  59   assert( lfds610_freelist_validity != NULL );
  60
  61   *lfds610_queue_validity = LFDS610_VALIDITY_VALID;
  62
  63   LFDS610_BARRIER_LOAD;
  64
  65   qe_slow = qe_fast = (struct lfds610_queue_element *) qs->dequeue[LFDS610_QUEUE_POINTER];
  66
  67   /* TRD : first, check for a loop
  68            we have two pointers
  69            both of which start at the dequeue end of the lfds610_queue
  70            we enter a loop
  71            and on each iteration
  72            we advance one pointer by one element
  73            and the other by two
  74
  75            we exit the loop when both pointers are NULL
  76            (have reached the end of the lfds610_queue)
  77
  78            or
  79
  80            if we fast pointer 'sees' the slow pointer
  81            which means we have a loop
  82   */
  83
  84   if( qe_slow != NULL )
  85     do
  86     {
  87       qe_slow = qe_slow->next[LFDS610_QUEUE_POINTER];
  88
  89       if( qe_fast != NULL )
  90         qe_fast = qe_fast->next[LFDS610_QUEUE_POINTER];
  91
  92       if( qe_fast != NULL )
  93         qe_fast = qe_fast->next[LFDS610_QUEUE_POINTER];
  94     }
  95     while( qe_slow != NULL and qe_fast != qe_slow );
  96
  97   if( qe_fast != NULL and qe_slow != NULL and qe_fast == qe_slow )
  98     *lfds610_queue_validity = LFDS610_VALIDITY_INVALID_LOOP;
  99
 100   /* TRD : now check for expected number of elements
 101            vi can be NULL, in which case we do not check
 102            we know we don't have a loop from our earlier check
 103   */
 104
 105   if( *lfds610_queue_validity == LFDS610_VALIDITY_VALID and vi != NULL )
 106   {
 107     qe = (struct lfds610_queue_element *) qs->dequeue[LFDS610_QUEUE_POINTER];
 108
 109     while( qe != NULL )
 110     {
 111       element_count++;
 112       qe = (struct lfds610_queue_element *) qe->next[LFDS610_QUEUE_POINTER];
 113     }
 114
 115     /* TRD : remember there is a dummy element in the lfds610_queue */
 116     element_count--;
 117
 118     if( element_count < vi->min_elements )
 119       *lfds610_queue_validity = LFDS610_VALIDITY_INVALID_MISSING_ELEMENTS;
 120
 121     if( element_count > vi->max_elements )
 122       *lfds610_queue_validity = LFDS610_VALIDITY_INVALID_ADDITIONAL_ELEMENTS;
 123   }
 124
 125   /* TRD : now we validate the lfds610_freelist
 126
 127            we may be able to check for the expected number of
 128            elements in the lfds610_freelist
 129
 130            if the caller has given us an expected min and max
 131            number of elements in the lfds610_queue, then the total number
 132            of elements in the lfds610_freelist, minus that min and max,
 133            gives us the expected number of elements in the
 134            lfds610_freelist
 135   */
 136
 137   if( vi != NULL )
 138   {
 139     lfds610_freelist_query( qs->fs, LFDS610_FREELIST_QUERY_ELEMENT_COUNT, NULL, (void *) &total_elements );
 140
 141     /* TRD : remember there is a dummy element in the lfds610_queue */
 142     total_elements--;
 143
 144     lfds610_freelist_vi.min_elements = total_elements - vi->max_elements;
 145     lfds610_freelist_vi.max_elements = total_elements - vi->min_elements;
 146
 147     lfds610_freelist_query( qs->fs, LFDS610_FREELIST_QUERY_VALIDATE, (void *) &lfds610_freelist_vi, (void *) lfds610_freelist_validity );
 148   }
 149
 150   if( vi == NULL )
 151     lfds610_freelist_query( qs->fs, LFDS610_FREELIST_QUERY_VALIDATE, NULL, (void *) lfds610_freelist_validity );
 152
 153   return;
 154 }
 155