2 #include "lfds710_btree_addonly_unbalanced_internal.h"
4 /***** private prototypes *****/
5 static void lfds710_btree_au_internal_validate( struct lfds710_btree_au_state *abs, struct lfds710_misc_validation_info *vi, enum lfds710_misc_validity *lfds710_btree_au_validity );
11 /****************************************************************************/
12 void lfds710_btree_au_query( struct lfds710_btree_au_state *baus,
13 enum lfds710_btree_au_query query_type,
17 LFDS710_PAL_ASSERT( baus != NULL );
18 // TRD : query_type can be any value in its range
20 LFDS710_MISC_BARRIER_LOAD;
24 case LFDS710_BTREE_AU_QUERY_GET_POTENTIALLY_INACCURATE_COUNT:
26 struct lfds710_btree_au_element
29 LFDS710_PAL_ASSERT( query_input == NULL );
30 LFDS710_PAL_ASSERT( query_output != NULL );
32 *(lfds710_pal_uint_t *) query_output = 0;
34 while( lfds710_btree_au_get_by_absolute_position_and_then_by_relative_position(baus, &baue, LFDS710_BTREE_AU_ABSOLUTE_POSITION_SMALLEST_IN_TREE, LFDS710_BTREE_AU_RELATIVE_POSITION_NEXT_LARGER_ELEMENT_IN_ENTIRE_TREE) )
35 ( *(lfds710_pal_uint_t *) query_output )++;
39 case LFDS710_BTREE_AU_QUERY_SINGLETHREADED_VALIDATE:
40 // TRD : query_input can be NULL
41 LFDS710_PAL_ASSERT( query_output != NULL );
43 lfds710_btree_au_internal_validate( baus, (struct lfds710_misc_validation_info *) query_input, (enum lfds710_misc_validity *) query_output );
54 /****************************************************************************/
55 static void lfds710_btree_au_internal_validate( struct lfds710_btree_au_state *baus,
56 struct lfds710_misc_validation_info *vi,
57 enum lfds710_misc_validity *lfds710_btree_au_validity )
60 number_elements_from_query_tree = 0,
61 number_elements_from_walk = 0;
63 struct lfds710_btree_au_element
67 LFDS710_PAL_ASSERT( baus!= NULL );
68 // TRD : vi can be NULL
69 LFDS710_PAL_ASSERT( lfds710_btree_au_validity != NULL );
71 *lfds710_btree_au_validity = LFDS710_MISC_VALIDITY_VALID;
73 /* TRD : validation is performed by;
75 performing an in-order walk
76 we should see every element is larger than the preceeding element
77 we count elements as we go along (visited elements, that is)
78 and check our tally equals the expected count
81 LFDS710_MISC_BARRIER_LOAD;
83 while( lfds710_btree_au_get_by_absolute_position_and_then_by_relative_position(baus, &baue, LFDS710_BTREE_AU_ABSOLUTE_POSITION_SMALLEST_IN_TREE, LFDS710_BTREE_AU_RELATIVE_POSITION_NEXT_LARGER_ELEMENT_IN_ENTIRE_TREE) )
85 // TRD : baue_prev should always be smaller than or equal to baue
86 if( baue_prev != NULL )
87 if( baus->key_compare_function(baue_prev->key, baue->key) > 0 )
89 *lfds710_btree_au_validity = LFDS710_MISC_VALIDITY_INVALID_ORDER;
94 number_elements_from_walk++;
97 if( *lfds710_btree_au_validity == LFDS710_MISC_VALIDITY_VALID )
99 lfds710_btree_au_query( (struct lfds710_btree_au_state *) baus, LFDS710_BTREE_AU_QUERY_GET_POTENTIALLY_INACCURATE_COUNT, NULL, &number_elements_from_query_tree );
101 if( number_elements_from_walk > number_elements_from_query_tree )
102 *lfds710_btree_au_validity = LFDS710_MISC_VALIDITY_INVALID_ADDITIONAL_ELEMENTS;
104 if( number_elements_from_walk < number_elements_from_query_tree )
105 *lfds710_btree_au_validity = LFDS710_MISC_VALIDITY_INVALID_MISSING_ELEMENTS;
108 /* TRD : now check for expected number of elements
109 vi can be NULL, in which case we do not check
110 we know we don't have a loop from our earlier check
113 if( *lfds710_btree_au_validity == LFDS710_MISC_VALIDITY_VALID and vi != NULL )
115 lfds710_btree_au_query( (struct lfds710_btree_au_state *) baus, LFDS710_BTREE_AU_QUERY_GET_POTENTIALLY_INACCURATE_COUNT, NULL, &number_elements_from_query_tree );
117 if( number_elements_from_query_tree < vi->min_elements )
118 *lfds710_btree_au_validity = LFDS710_MISC_VALIDITY_INVALID_MISSING_ELEMENTS;
120 if( number_elements_from_query_tree > vi->max_elements )
121 *lfds710_btree_au_validity = LFDS710_MISC_VALIDITY_INVALID_ADDITIONAL_ELEMENTS;