1 #include "lfds610_stack_internal.h"
7 /****************************************************************************/
8 void lfds610_stack_query( struct lfds610_stack_state *ss, enum lfds610_stack_query_type query_type, void *query_input, void *query_output )
11 // TRD : query_type can be any value in its range
12 // TRD : query_iput can be NULL
13 assert( query_output != NULL );
19 case LFDS610_STACK_QUERY_ELEMENT_COUNT:
20 assert( query_input == NULL );
22 lfds610_freelist_query( ss->fs, LFDS610_FREELIST_QUERY_ELEMENT_COUNT, NULL, query_output );
25 case LFDS610_STACK_QUERY_VALIDATE:
26 // TRD : query_input can be NULL
28 /* TRD : the validation info passed in is for the stack
29 it indicates the minimum and maximum number of elements
30 which should be present
32 we need to validate the freelist
33 and validate the stack
35 we cannot know the min/max for the freelist, given only
36 the min/max for the stack
39 lfds610_freelist_query( ss->fs, LFDS610_FREELIST_QUERY_VALIDATE, NULL, (enum lfds610_data_structure_validity *) query_output );
41 if( *(enum lfds610_data_structure_validity *) query_output == LFDS610_VALIDITY_VALID )
42 lfds610_stack_internal_validate( ss, (struct lfds610_validation_info *) query_input, (enum lfds610_data_structure_validity *) query_output, ((enum lfds610_data_structure_validity *) query_output)+1 );
53 /****************************************************************************/
54 void lfds610_stack_internal_validate( struct lfds610_stack_state *ss, struct lfds610_validation_info *vi, enum lfds610_data_structure_validity *stack_validity, enum lfds610_data_structure_validity *freelist_validity )
56 struct lfds610_stack_element
65 struct lfds610_validation_info
69 // TRD : vi can be NULL
70 assert( stack_validity != NULL );
72 *stack_validity = LFDS610_VALIDITY_VALID;
74 se_slow = se_fast = (struct lfds610_stack_element *) ss->top[LFDS610_STACK_POINTER];
76 /* TRD : first, check for a loop
78 both of which start at the top of the stack
81 we advance one pointer by one element
84 we exit the loop when both pointers are NULL
85 (have reached the end of the stack)
89 if we fast pointer 'sees' the slow pointer
90 which means we have a loop
96 se_slow = se_slow->next[LFDS610_STACK_POINTER];
99 se_fast = se_fast->next[LFDS610_STACK_POINTER];
101 if( se_fast != NULL )
102 se_fast = se_fast->next[LFDS610_STACK_POINTER];
104 while( se_slow != NULL and se_fast != se_slow );
106 if( se_fast != NULL and se_slow != NULL and se_fast == se_slow )
107 *stack_validity = LFDS610_VALIDITY_INVALID_LOOP;
109 /* TRD : now check for expected number of elements
110 vi can be NULL, in which case we do not check
111 we know we don't have a loop from our earlier check
114 if( *stack_validity == LFDS610_VALIDITY_VALID and vi != NULL )
116 se = (struct lfds610_stack_element *) ss->top[LFDS610_STACK_POINTER];
121 se = (struct lfds610_stack_element *) se->next[LFDS610_STACK_POINTER];
124 if( element_count < vi->min_elements )
125 *stack_validity = LFDS610_VALIDITY_INVALID_MISSING_ELEMENTS;
127 if( element_count > vi->max_elements )
128 *stack_validity = LFDS610_VALIDITY_INVALID_ADDITIONAL_ELEMENTS;
131 /* TRD : now we validate the freelist
133 we may be able to check for the expected number of
134 elements in the freelist
136 if the caller has given us an expected min and max
137 number of elements in the stack, then the total number
138 of elements in the freelist, minus that min and max,
139 gives us the expected number of elements in the
145 lfds610_freelist_query( ss->fs, LFDS610_FREELIST_QUERY_ELEMENT_COUNT, NULL, (void *) &total_elements );
147 freelist_vi.min_elements = total_elements - vi->max_elements;
148 freelist_vi.max_elements = total_elements - vi->min_elements;
150 lfds610_freelist_query( ss->fs, LFDS610_FREELIST_QUERY_VALIDATE, (void *) &freelist_vi, (void *) freelist_validity );
154 lfds610_freelist_query( ss->fs, LFDS610_FREELIST_QUERY_VALIDATE, NULL, (void *) freelist_validity );