pd.if.org Git - liblfds/blob - liblfds/liblfds6.0.0/liblfds600/src/lfds600_queue/lfds600_queue_query.c

   1 #include "lfds600_queue_internal.h"
   2
   3
   4
   5
   6
   7 /****************************************************************************/
   8 #pragma warning( disable : 4100 )
   9
  10 void lfds600_queue_query( struct lfds600_queue_state *qs, enum lfds600_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 LFDS600_QUEUE_QUERY_ELEMENT_COUNT:
  20       assert( query_input == NULL );
  21
  22       lfds600_freelist_query( qs->fs, LFDS600_FREELIST_QUERY_ELEMENT_COUNT, NULL, query_output );
  23     break;
  24
  25     case LFDS600_QUEUE_QUERY_VALIDATE:
  26       // TRD : query_input can be NULL
  27
  28       lfds600_queue_internal_validate( qs, (struct lfds600_validation_info *) query_input, (enum data_structure_validity *) query_output, ((enum 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 lfds600_queue_internal_validate( struct lfds600_queue_state *qs, struct lfds600_validation_info *vi, enum data_structure_validity *lfds600_queue_validity, enum data_structure_validity *lfds600_freelist_validity )
  43 {
  44   struct lfds600_queue_element
  45     *qe,
  46     *qe_slow,
  47     *qe_fast;
  48
  49   lfds600_atom_t
  50     element_count = 0,
  51     total_elements;
  52
  53   struct lfds600_validation_info
  54     lfds600_freelist_vi;
  55
  56   assert( qs != NULL );
  57   // TRD : vi can be NULL
  58   assert( lfds600_queue_validity != NULL );
  59   assert( lfds600_freelist_validity != NULL );
  60
  61   *lfds600_queue_validity = VALIDITY_VALID;
  62
  63   qe_slow = qe_fast = (struct lfds600_queue_element *) qs->dequeue[LFDS600_QUEUE_POINTER];
  64
  65   /* TRD : first, check for a loop
  66            we have two pointers
  67            both of which start at the dequeue end of the lfds600_queue
  68            we enter a loop
  69            and on each iteration
  70            we advance one pointer by one element
  71            and the other by two
  72
  73            we exit the loop when both pointers are NULL
  74            (have reached the end of the lfds600_queue)
  75
  76            or
  77
  78            if we fast pointer 'sees' the slow pointer
  79            which means we have a loop
  80   */
  81
  82   if( qe_slow != NULL )
  83     do
  84     {
  85       qe_slow = qe_slow->next[LFDS600_QUEUE_POINTER];
  86
  87       if( qe_fast != NULL )
  88         qe_fast = qe_fast->next[LFDS600_QUEUE_POINTER];
  89
  90       if( qe_fast != NULL )
  91         qe_fast = qe_fast->next[LFDS600_QUEUE_POINTER];
  92     }
  93     while( qe_slow != NULL and qe_fast != qe_slow );
  94
  95   if( qe_fast != NULL and qe_slow != NULL and qe_fast == qe_slow )
  96     *lfds600_queue_validity = VALIDITY_INVALID_LOOP;
  97
  98   /* TRD : now check for expected number of elements
  99            vi can be NULL, in which case we do not check
 100            we know we don't have a loop from our earlier check
 101   */
 102
 103   if( *lfds600_queue_validity == VALIDITY_VALID and vi != NULL )
 104   {
 105     qe = (struct lfds600_queue_element *) qs->dequeue[LFDS600_QUEUE_POINTER];
 106
 107     while( qe != NULL )
 108     {
 109       element_count++;
 110       qe = (struct lfds600_queue_element *) qe->next[LFDS600_QUEUE_POINTER];
 111     }
 112
 113     /* TRD : remember there is a dummy element in the lfds600_queue */
 114     element_count--;
 115
 116     if( element_count < vi->min_elements )
 117       *lfds600_queue_validity = VALIDITY_INVALID_MISSING_ELEMENTS;
 118
 119     if( element_count > vi->max_elements )
 120       *lfds600_queue_validity = VALIDITY_INVALID_ADDITIONAL_ELEMENTS;
 121   }
 122
 123   /* TRD : now we validate the lfds600_freelist
 124
 125            we may be able to check for the expected number of
 126            elements in the lfds600_freelist
 127
 128            if the caller has given us an expected min and max
 129            number of elements in the lfds600_queue, then the total number
 130            of elements in the lfds600_freelist, minus that min and max,
 131            gives us the expected number of elements in the
 132            lfds600_freelist
 133   */
 134
 135   if( vi != NULL )
 136   {
 137     lfds600_freelist_query( qs->fs, LFDS600_FREELIST_QUERY_ELEMENT_COUNT, NULL, (void *) &total_elements );
 138
 139     /* TRD : remember there is a dummy element in the lfds600_queue */
 140     total_elements--;
 141
 142     lfds600_freelist_vi.min_elements = total_elements - vi->max_elements;
 143     lfds600_freelist_vi.max_elements = total_elements - vi->min_elements;
 144
 145     lfds600_freelist_query( qs->fs, LFDS600_FREELIST_QUERY_VALIDATE, (void *) &lfds600_freelist_vi, (void *) lfds600_freelist_validity );
 146   }
 147
 148   if( vi == NULL )
 149     lfds600_freelist_query( qs->fs, LFDS600_FREELIST_QUERY_VALIDATE, NULL, (void *) lfds600_freelist_validity );
 150
 151   return;
 152 }
 153