2 #include "lfds710_stack_internal.h"
4 /***** private prototypes *****/
5 static void lfds710_stack_internal_stack_validate( struct lfds710_stack_state *ss,
6 struct lfds710_misc_validation_info *vi,
7 enum lfds710_misc_validity *lfds710_stack_validity );
13 /****************************************************************************/
14 void lfds710_stack_query( struct lfds710_stack_state *ss,
15 enum lfds710_stack_query query_type,
19 struct lfds710_stack_element
22 LFDS710_MISC_BARRIER_LOAD;
24 LFDS710_PAL_ASSERT( ss != NULL );
25 // TRD : query_type can be any value in its range
29 case LFDS710_STACK_QUERY_SINGLETHREADED_GET_COUNT:
30 LFDS710_PAL_ASSERT( query_input == NULL );
31 LFDS710_PAL_ASSERT( query_output != NULL );
33 *(lfds710_pal_uint_t *) query_output = 0;
35 se = (struct lfds710_stack_element *) ss->top[POINTER];
39 ( *(lfds710_pal_uint_t *) query_output )++;
40 se = (struct lfds710_stack_element *) se->next;
44 case LFDS710_STACK_QUERY_SINGLETHREADED_VALIDATE:
45 // TRD : query_input can be NULL
46 LFDS710_PAL_ASSERT( query_output != NULL );
48 lfds710_stack_internal_stack_validate( ss, (struct lfds710_misc_validation_info *) query_input, (enum lfds710_misc_validity *) query_output );
59 /****************************************************************************/
60 static void lfds710_stack_internal_stack_validate( struct lfds710_stack_state *ss,
61 struct lfds710_misc_validation_info *vi,
62 enum lfds710_misc_validity *lfds710_stack_validity )
67 struct lfds710_stack_element
71 LFDS710_PAL_ASSERT( ss != NULL );
72 // TRD : vi can be NULL
73 LFDS710_PAL_ASSERT( lfds710_stack_validity != NULL );
75 *lfds710_stack_validity = LFDS710_MISC_VALIDITY_VALID;
77 se_slow = se_fast = (struct lfds710_stack_element *) ss->top[POINTER];
79 /* TRD : first, check for a loop
81 both of which start at the top of the stack
84 we advance one pointer by one element
87 we exit the loop when both pointers are NULL
88 (have reached the end of the stack)
92 if we fast pointer 'sees' the slow pointer
93 which means we have a loop
99 se_slow = se_slow->next;
101 if( se_fast != NULL )
102 se_fast = se_fast->next;
104 if( se_fast != NULL )
105 se_fast = se_fast->next;
107 while( se_slow != NULL and se_fast != se_slow );
109 if( se_fast != NULL and se_slow != NULL and se_fast == se_slow )
110 *lfds710_stack_validity = LFDS710_MISC_VALIDITY_INVALID_LOOP;
112 /* TRD : now check for expected number of elements
113 vi can be NULL, in which case we do not check
114 we know we don't have a loop from our earlier check
117 if( *lfds710_stack_validity == LFDS710_MISC_VALIDITY_VALID and vi != NULL )
119 lfds710_stack_query( ss, LFDS710_STACK_QUERY_SINGLETHREADED_GET_COUNT, NULL, (void *) &number_elements );
121 if( number_elements < vi->min_elements )
122 *lfds710_stack_validity = LFDS710_MISC_VALIDITY_INVALID_MISSING_ELEMENTS;
124 if( number_elements > vi->max_elements )
125 *lfds710_stack_validity = LFDS710_MISC_VALIDITY_INVALID_ADDITIONAL_ELEMENTS;