1 #include "lfds610_freelist_internal.h"
7 /****************************************************************************/
8 void lfds610_freelist_query( struct lfds610_freelist_state *fs, enum lfds610_freelist_query_type query_type, void *query_input, void *query_output )
11 // TRD : query type can be any value in its range
12 // TRD : query_input can be NULL in some cases
13 assert( query_output != NULL );
19 case LFDS610_FREELIST_QUERY_ELEMENT_COUNT:
20 assert( query_input == NULL );
22 *(lfds610_atom_t *) query_output = fs->element_count;
25 case LFDS610_FREELIST_QUERY_VALIDATE:
26 // TRD : query_input can be NULL
28 lfds610_freelist_internal_validate( fs, (struct lfds610_validation_info *) query_input, (enum lfds610_data_structure_validity *) query_output );
39 /****************************************************************************/
40 void lfds610_freelist_internal_validate( struct lfds610_freelist_state *fs, struct lfds610_validation_info *vi, enum lfds610_data_structure_validity *lfds610_freelist_validity )
42 struct lfds610_freelist_element
51 // TRD : vi can be NULL
52 assert( lfds610_freelist_validity != NULL );
54 *lfds610_freelist_validity = LFDS610_VALIDITY_VALID;
56 fe_slow = fe_fast = (struct lfds610_freelist_element *) fs->top[LFDS610_FREELIST_POINTER];
58 /* TRD : first, check for a loop
60 both of which start at the top of the lfds610_freelist
63 we advance one pointer by one element
66 we exit the loop when both pointers are NULL
67 (have reached the end of the lfds610_freelist)
71 if we fast pointer 'sees' the slow pointer
72 which means we have a loop
78 fe_slow = fe_slow->next[LFDS610_FREELIST_POINTER];
81 fe_fast = fe_fast->next[LFDS610_FREELIST_POINTER];
84 fe_fast = fe_fast->next[LFDS610_FREELIST_POINTER];
86 while( fe_slow != NULL and fe_fast != fe_slow );
88 if( fe_fast != NULL and fe_slow != NULL and fe_fast == fe_slow )
89 *lfds610_freelist_validity = LFDS610_VALIDITY_INVALID_LOOP;
91 /* TRD : now check for expected number of elements
92 vi can be NULL, in which case we do not check
93 we know we don't have a loop from our earlier check
96 if( *lfds610_freelist_validity == LFDS610_VALIDITY_VALID and vi != NULL )
98 fe = (struct lfds610_freelist_element *) fs->top[LFDS610_FREELIST_POINTER];
103 fe = (struct lfds610_freelist_element *) fe->next[LFDS610_FREELIST_POINTER];
106 if( element_count < vi->min_elements )
107 *lfds610_freelist_validity = LFDS610_VALIDITY_INVALID_MISSING_ELEMENTS;
109 if( element_count > vi->max_elements )
110 *lfds610_freelist_validity = LFDS610_VALIDITY_INVALID_ADDITIONAL_ELEMENTS;