2 #include "lfds710_freelist_internal.h"
4 /***** private prototypes *****/
5 static void lfds710_freelist_internal_freelist_validate( struct lfds710_freelist_state *fs,
6 struct lfds710_misc_validation_info *vi,
7 enum lfds710_misc_validity *lfds710_freelist_validity );
13 /****************************************************************************/
14 void lfds710_freelist_query( struct lfds710_freelist_state *fs,
15 enum lfds710_freelist_query query_type,
19 struct lfds710_freelist_element
22 LFDS710_PAL_ASSERT( fs != NULL );
23 // TRD : query_type can be any value in its range
25 LFDS710_MISC_BARRIER_LOAD;
29 case LFDS710_FREELIST_QUERY_SINGLETHREADED_GET_COUNT:
35 LFDS710_PAL_ASSERT( query_input == NULL );
36 LFDS710_PAL_ASSERT( query_output != NULL );
38 *(lfds710_pal_uint_t *) query_output = 0;
40 // TRD : count the elements in the elimination array
41 for( loop = 0 ; loop < fs->elimination_array_size_in_elements ; loop++ )
42 for( subloop = 0 ; subloop < LFDS710_FREELIST_ELIMINATION_ARRAY_ELEMENT_SIZE_IN_FREELIST_ELEMENTS ; subloop++ )
43 if( fs->elimination_array[loop][subloop] != NULL )
44 ( *(lfds710_pal_uint_t *) query_output )++;
46 // TRD : count the elements on the freelist
47 fe = (struct lfds710_freelist_element *) fs->top[POINTER];
51 ( *(lfds710_pal_uint_t *) query_output )++;
52 fe = (struct lfds710_freelist_element *) fe->next;
57 case LFDS710_FREELIST_QUERY_SINGLETHREADED_VALIDATE:
58 // TRD : query_input can be NULL
59 LFDS710_PAL_ASSERT( query_output != NULL );
61 lfds710_freelist_internal_freelist_validate( fs, (struct lfds710_misc_validation_info *) query_input, (enum lfds710_misc_validity *) query_output );
64 case LFDS710_FREELIST_QUERY_GET_ELIMINATION_ARRAY_EXTRA_ELEMENTS_IN_FREELIST_ELEMENTS:
66 LFDS710_PAL_ASSERT( query_input == NULL );
67 LFDS710_PAL_ASSERT( query_output != NULL );
69 ( *(lfds710_pal_uint_t *) query_output ) = (fs->elimination_array_size_in_elements-1) * LFDS710_FREELIST_ELIMINATION_ARRAY_ELEMENT_SIZE_IN_FREELIST_ELEMENTS;
81 /****************************************************************************/
82 static void lfds710_freelist_internal_freelist_validate( struct lfds710_freelist_state *fs,
83 struct lfds710_misc_validation_info *vi,
84 enum lfds710_misc_validity *lfds710_freelist_validity )
89 struct lfds710_freelist_element
93 LFDS710_PAL_ASSERT( fs != NULL );
94 // TRD : vi can be NULL
95 LFDS710_PAL_ASSERT( lfds710_freelist_validity != NULL );
97 *lfds710_freelist_validity = LFDS710_MISC_VALIDITY_VALID;
99 fe_slow = fe_fast = (struct lfds710_freelist_element *) fs->top[POINTER];
101 /* TRD : first, check for a loop
103 both of which start at the top of the freelist
105 and on each iteration
106 we advance one pointer by one element
109 we exit the loop when both pointers are NULL
110 (have reached the end of the freelist)
114 if we fast pointer 'sees' the slow pointer
115 which means we have a loop
118 if( fe_slow != NULL )
121 fe_slow = fe_slow->next;
123 if( fe_fast != NULL )
124 fe_fast = fe_fast->next;
126 if( fe_fast != NULL )
127 fe_fast = fe_fast->next;
129 while( fe_slow != NULL and fe_fast != fe_slow );
131 if( fe_fast != NULL and fe_slow != NULL and fe_fast == fe_slow )
132 *lfds710_freelist_validity = LFDS710_MISC_VALIDITY_INVALID_LOOP;
134 /* TRD : now check for expected number of elements
135 vi can be NULL, in which case we do not check
136 we know we don't have a loop from our earlier check
139 if( *lfds710_freelist_validity == LFDS710_MISC_VALIDITY_VALID and vi != NULL )
141 lfds710_freelist_query( fs, LFDS710_FREELIST_QUERY_SINGLETHREADED_GET_COUNT, NULL, (void *) &number_elements );
143 if( number_elements < vi->min_elements )
144 *lfds710_freelist_validity = LFDS710_MISC_VALIDITY_INVALID_MISSING_ELEMENTS;
146 if( number_elements > vi->max_elements )
147 *lfds710_freelist_validity = LFDS710_MISC_VALIDITY_INVALID_ADDITIONAL_ELEMENTS;