2 #include "lfds710_list_addonly_singlylinked_unordered_internal.h"
4 /***** private prototypes *****/
5 static void lfds710_list_asu_internal_validate( struct lfds710_list_asu_state *lasus,
6 struct lfds710_misc_validation_info *vi,
7 enum lfds710_misc_validity *lfds710_list_asu_validity );
13 /****************************************************************************/
14 void lfds710_list_asu_query( struct lfds710_list_asu_state *lasus,
15 enum lfds710_list_asu_query query_type,
19 LFDS710_PAL_ASSERT( lasus != NULL );
20 // TRD : query_type can be any value in its range
22 LFDS710_MISC_BARRIER_LOAD;
26 case LFDS710_LIST_ASU_QUERY_GET_POTENTIALLY_INACCURATE_COUNT:
28 struct lfds710_list_asu_element
31 LFDS710_PAL_ASSERT( query_input == NULL );
32 LFDS710_PAL_ASSERT( query_output != NULL );
34 *(lfds710_pal_uint_t *) query_output = 0;
36 while( LFDS710_LIST_ASU_GET_START_AND_THEN_NEXT(*lasus, lasue) )
37 ( *(lfds710_pal_uint_t *) query_output )++;
41 case LFDS710_LIST_ASU_QUERY_SINGLETHREADED_VALIDATE:
42 // TRD : query_input can be NULL
43 LFDS710_PAL_ASSERT( query_output != NULL );
45 lfds710_list_asu_internal_validate( lasus, (struct lfds710_misc_validation_info *) query_input, (enum lfds710_misc_validity *) query_output );
57 /****************************************************************************/
58 static void lfds710_list_asu_internal_validate( struct lfds710_list_asu_state *lasus,
59 struct lfds710_misc_validation_info *vi,
60 enum lfds710_misc_validity *lfds710_list_asu_validity )
65 struct lfds710_list_asu_element
69 LFDS710_PAL_ASSERT( lasus!= NULL );
70 // TRD : vi can be NULL
71 LFDS710_PAL_ASSERT( lfds710_list_asu_validity != NULL );
73 *lfds710_list_asu_validity = LFDS710_MISC_VALIDITY_VALID;
75 lasue_slow = lasue_fast = lasus->start->next;
77 /* TRD : first, check for a loop
79 both of which start at the start of the list
82 we advance one pointer by one element
85 we exit the loop when both pointers are NULL
86 (have reached the end of the queue)
90 if we fast pointer 'sees' the slow pointer
91 which means we have a loop
94 if( lasue_slow != NULL )
97 lasue_slow = lasue_slow->next;
99 if( lasue_fast != NULL )
100 lasue_fast = lasue_fast->next;
102 if( lasue_fast != NULL )
103 lasue_fast = lasue_fast->next;
105 while( lasue_slow != NULL and lasue_fast != lasue_slow );
107 if( lasue_fast != NULL and lasue_slow != NULL and lasue_fast == lasue_slow )
108 *lfds710_list_asu_validity = LFDS710_MISC_VALIDITY_INVALID_LOOP;
110 /* TRD : now check for expected number of elements
111 vi can be NULL, in which case we do not check
112 we know we don't have a loop from our earlier check
115 if( *lfds710_list_asu_validity == LFDS710_MISC_VALIDITY_VALID and vi != NULL )
117 lfds710_list_asu_query( lasus, LFDS710_LIST_ASU_QUERY_GET_POTENTIALLY_INACCURATE_COUNT, NULL, &number_elements );
119 if( number_elements < vi->min_elements )
120 *lfds710_list_asu_validity = LFDS710_MISC_VALIDITY_INVALID_MISSING_ELEMENTS;
122 if( number_elements > vi->max_elements )
123 *lfds710_list_asu_validity = LFDS710_MISC_VALIDITY_INVALID_ADDITIONAL_ELEMENTS;