1 #include "lfds610_queue_internal.h"
7 /****************************************************************************/
8 #pragma warning( disable : 4100 )
10 void lfds610_queue_query( struct lfds610_queue_state *qs, enum lfds610_queue_query_type query_type, void *query_input, void *query_output )
13 // TRD : query_type can be any value in its range
14 // TRD : query_input can be NULL
15 assert( query_output != NULL );
19 case LFDS610_QUEUE_QUERY_ELEMENT_COUNT:
20 assert( query_input == NULL );
22 lfds610_freelist_query( qs->fs, LFDS610_FREELIST_QUERY_ELEMENT_COUNT, NULL, query_output );
25 case LFDS610_QUEUE_QUERY_VALIDATE:
26 // TRD : query_input can be NULL
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 );
35 #pragma warning( default : 4100 )
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 )
44 struct lfds610_queue_element
53 struct lfds610_validation_info
57 // TRD : vi can be NULL
58 assert( lfds610_queue_validity != NULL );
59 assert( lfds610_freelist_validity != NULL );
61 *lfds610_queue_validity = LFDS610_VALIDITY_VALID;
65 qe_slow = qe_fast = (struct lfds610_queue_element *) qs->dequeue[LFDS610_QUEUE_POINTER];
67 /* TRD : first, check for a loop
69 both of which start at the dequeue end of the lfds610_queue
72 we advance one pointer by one element
75 we exit the loop when both pointers are NULL
76 (have reached the end of the lfds610_queue)
80 if we fast pointer 'sees' the slow pointer
81 which means we have a loop
87 qe_slow = qe_slow->next[LFDS610_QUEUE_POINTER];
90 qe_fast = qe_fast->next[LFDS610_QUEUE_POINTER];
93 qe_fast = qe_fast->next[LFDS610_QUEUE_POINTER];
95 while( qe_slow != NULL and qe_fast != qe_slow );
97 if( qe_fast != NULL and qe_slow != NULL and qe_fast == qe_slow )
98 *lfds610_queue_validity = LFDS610_VALIDITY_INVALID_LOOP;
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
105 if( *lfds610_queue_validity == LFDS610_VALIDITY_VALID and vi != NULL )
107 qe = (struct lfds610_queue_element *) qs->dequeue[LFDS610_QUEUE_POINTER];
112 qe = (struct lfds610_queue_element *) qe->next[LFDS610_QUEUE_POINTER];
115 /* TRD : remember there is a dummy element in the lfds610_queue */
118 if( element_count < vi->min_elements )
119 *lfds610_queue_validity = LFDS610_VALIDITY_INVALID_MISSING_ELEMENTS;
121 if( element_count > vi->max_elements )
122 *lfds610_queue_validity = LFDS610_VALIDITY_INVALID_ADDITIONAL_ELEMENTS;
125 /* TRD : now we validate the lfds610_freelist
127 we may be able to check for the expected number of
128 elements in the lfds610_freelist
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
139 lfds610_freelist_query( qs->fs, LFDS610_FREELIST_QUERY_ELEMENT_COUNT, NULL, (void *) &total_elements );
141 /* TRD : remember there is a dummy element in the lfds610_queue */
144 lfds610_freelist_vi.min_elements = total_elements - vi->max_elements;
145 lfds610_freelist_vi.max_elements = total_elements - vi->min_elements;
147 lfds610_freelist_query( qs->fs, LFDS610_FREELIST_QUERY_VALIDATE, (void *) &lfds610_freelist_vi, (void *) lfds610_freelist_validity );
151 lfds610_freelist_query( qs->fs, LFDS610_FREELIST_QUERY_VALIDATE, NULL, (void *) lfds610_freelist_validity );