1 #include "lfds601_queue_internal.h"
\r
7 /****************************************************************************/
\r
8 #pragma warning( disable : 4100 )
\r
10 void lfds601_queue_query( struct lfds601_queue_state *qs, enum lfds601_queue_query_type query_type, void *query_input, void *query_output )
\r
12 assert( qs != NULL );
\r
13 // TRD : query_type can be any value in its range
\r
14 // TRD : query_input can be NULL
\r
15 assert( query_output != NULL );
\r
17 switch( query_type )
\r
19 case LFDS601_QUEUE_QUERY_ELEMENT_COUNT:
\r
20 assert( query_input == NULL );
\r
22 lfds601_freelist_query( qs->fs, LFDS601_FREELIST_QUERY_ELEMENT_COUNT, NULL, query_output );
\r
25 case LFDS601_QUEUE_QUERY_VALIDATE:
\r
26 // TRD : query_input can be NULL
\r
28 lfds601_queue_internal_validate( qs, (struct lfds601_validation_info *) query_input, (enum lfds601_data_structure_validity *) query_output, ((enum lfds601_data_structure_validity *) query_output)+1 );
\r
35 #pragma warning( default : 4100 )
\r
41 /****************************************************************************/
\r
42 void lfds601_queue_internal_validate( struct lfds601_queue_state *qs, struct lfds601_validation_info *vi, enum lfds601_data_structure_validity *lfds601_queue_validity, enum lfds601_data_structure_validity *lfds601_freelist_validity )
\r
44 struct lfds601_queue_element
\r
53 struct lfds601_validation_info
\r
54 lfds601_freelist_vi;
\r
56 assert( qs != NULL );
\r
57 // TRD : vi can be NULL
\r
58 assert( lfds601_queue_validity != NULL );
\r
59 assert( lfds601_freelist_validity != NULL );
\r
61 *lfds601_queue_validity = LFDS601_VALIDITY_VALID;
\r
63 qe_slow = qe_fast = (struct lfds601_queue_element *) qs->dequeue[LFDS601_QUEUE_POINTER];
\r
65 /* TRD : first, check for a loop
\r
66 we have two pointers
\r
67 both of which start at the dequeue end of the lfds601_queue
\r
69 and on each iteration
\r
70 we advance one pointer by one element
\r
71 and the other by two
\r
73 we exit the loop when both pointers are NULL
\r
74 (have reached the end of the lfds601_queue)
\r
78 if we fast pointer 'sees' the slow pointer
\r
79 which means we have a loop
\r
82 if( qe_slow != NULL )
\r
85 qe_slow = qe_slow->next[LFDS601_QUEUE_POINTER];
\r
87 if( qe_fast != NULL )
\r
88 qe_fast = qe_fast->next[LFDS601_QUEUE_POINTER];
\r
90 if( qe_fast != NULL )
\r
91 qe_fast = qe_fast->next[LFDS601_QUEUE_POINTER];
\r
93 while( qe_slow != NULL and qe_fast != qe_slow );
\r
95 if( qe_fast != NULL and qe_slow != NULL and qe_fast == qe_slow )
\r
96 *lfds601_queue_validity = LFDS601_VALIDITY_INVALID_LOOP;
\r
98 /* TRD : now check for expected number of elements
\r
99 vi can be NULL, in which case we do not check
\r
100 we know we don't have a loop from our earlier check
\r
103 if( *lfds601_queue_validity == LFDS601_VALIDITY_VALID and vi != NULL )
\r
105 qe = (struct lfds601_queue_element *) qs->dequeue[LFDS601_QUEUE_POINTER];
\r
107 while( qe != NULL )
\r
110 qe = (struct lfds601_queue_element *) qe->next[LFDS601_QUEUE_POINTER];
\r
113 /* TRD : remember there is a dummy element in the lfds601_queue */
\r
116 if( element_count < vi->min_elements )
\r
117 *lfds601_queue_validity = LFDS601_VALIDITY_INVALID_MISSING_ELEMENTS;
\r
119 if( element_count > vi->max_elements )
\r
120 *lfds601_queue_validity = LFDS601_VALIDITY_INVALID_ADDITIONAL_ELEMENTS;
\r
123 /* TRD : now we validate the lfds601_freelist
\r
125 we may be able to check for the expected number of
\r
126 elements in the lfds601_freelist
\r
128 if the caller has given us an expected min and max
\r
129 number of elements in the lfds601_queue, then the total number
\r
130 of elements in the lfds601_freelist, minus that min and max,
\r
131 gives us the expected number of elements in the
\r
137 lfds601_freelist_query( qs->fs, LFDS601_FREELIST_QUERY_ELEMENT_COUNT, NULL, (void *) &total_elements );
\r
139 /* TRD : remember there is a dummy element in the lfds601_queue */
\r
142 lfds601_freelist_vi.min_elements = total_elements - vi->max_elements;
\r
143 lfds601_freelist_vi.max_elements = total_elements - vi->min_elements;
\r
145 lfds601_freelist_query( qs->fs, LFDS601_FREELIST_QUERY_VALIDATE, (void *) &lfds601_freelist_vi, (void *) lfds601_freelist_validity );
\r
149 lfds601_freelist_query( qs->fs, LFDS601_FREELIST_QUERY_VALIDATE, NULL, (void *) lfds601_freelist_validity );
\r