pd.if.org Git - liblfds/blob - liblfds/liblfds7.1.0/liblfds710/src/lfds710_btree_addonly_unbalanced/lfds710_btree_addonly_unbalanced_query.c

   1 /***** includes *****/
   2 #include "lfds710_btree_addonly_unbalanced_internal.h"
   3
   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 );
   6
   7
   8
   9
  10
  11 /****************************************************************************/
  12 void lfds710_btree_au_query( struct lfds710_btree_au_state *baus,
  13                              enum lfds710_btree_au_query query_type,
  14                              void *query_input,
  15                              void *query_output )
  16 {
  17   LFDS710_PAL_ASSERT( baus != NULL );
  18   // TRD : query_type can be any value in its range
  19
  20   LFDS710_MISC_BARRIER_LOAD;
  21
  22   switch( query_type )
  23   {
  24     case LFDS710_BTREE_AU_QUERY_GET_POTENTIALLY_INACCURATE_COUNT:
  25     {
  26       struct lfds710_btree_au_element
  27         *baue = NULL;
  28
  29       LFDS710_PAL_ASSERT( query_input == NULL );
  30       LFDS710_PAL_ASSERT( query_output != NULL );
  31
  32       *(lfds710_pal_uint_t *) query_output = 0;
  33
  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 )++;
  36     }
  37     break;
  38
  39     case LFDS710_BTREE_AU_QUERY_SINGLETHREADED_VALIDATE:
  40       // TRD : query_input can be NULL
  41       LFDS710_PAL_ASSERT( query_output != NULL );
  42
  43       lfds710_btree_au_internal_validate( baus, (struct lfds710_misc_validation_info *) query_input, (enum lfds710_misc_validity *) query_output );
  44     break;
  45   }
  46
  47   return;
  48 }
  49
  50
  51
  52
  53
  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 )
  58 {
  59   lfds710_pal_uint_t
  60     number_elements_from_query_tree = 0,
  61     number_elements_from_walk = 0;
  62
  63   struct lfds710_btree_au_element
  64     *baue = NULL,
  65     *baue_prev = NULL;
  66
  67   LFDS710_PAL_ASSERT( baus!= NULL );
  68   // TRD : vi can be NULL
  69   LFDS710_PAL_ASSERT( lfds710_btree_au_validity != NULL );
  70
  71   *lfds710_btree_au_validity = LFDS710_MISC_VALIDITY_VALID;
  72
  73   /* TRD : validation is performed by;
  74
  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
  79   */
  80
  81   LFDS710_MISC_BARRIER_LOAD;
  82
  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) )
  84   {
  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 )
  88       {
  89         *lfds710_btree_au_validity = LFDS710_MISC_VALIDITY_INVALID_ORDER;
  90         return;
  91       }
  92
  93     baue_prev = baue;
  94     number_elements_from_walk++;
  95   }
  96
  97   if( *lfds710_btree_au_validity == LFDS710_MISC_VALIDITY_VALID )
  98   {
  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 );
 100
 101     if( number_elements_from_walk > number_elements_from_query_tree )
 102       *lfds710_btree_au_validity = LFDS710_MISC_VALIDITY_INVALID_ADDITIONAL_ELEMENTS;
 103
 104     if( number_elements_from_walk < number_elements_from_query_tree )
 105       *lfds710_btree_au_validity = LFDS710_MISC_VALIDITY_INVALID_MISSING_ELEMENTS;
 106   }
 107
 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
 111   */
 112
 113   if( *lfds710_btree_au_validity == LFDS710_MISC_VALIDITY_VALID and vi != NULL )
 114   {
 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 );
 116
 117     if( number_elements_from_query_tree < vi->min_elements )
 118       *lfds710_btree_au_validity = LFDS710_MISC_VALIDITY_INVALID_MISSING_ELEMENTS;
 119
 120     if( number_elements_from_query_tree > vi->max_elements )
 121       *lfds710_btree_au_validity = LFDS710_MISC_VALIDITY_INVALID_ADDITIONAL_ELEMENTS;
 122   }
 123
 124   return;
 125 }
 126