pd.if.org Git - liblfds/blob - liblfds/liblfds7.0.0/liblfds700/src/lfds700_btree_addonly_unbalanced/lfds700_btree_addonly_unbalanced_query.c

   1 /***** includes *****/
   2 #include "lfds700_btree_addonly_unbalanced_internal.h"
   3
   4 /***** private prototypes *****/
   5 static void lfds700_btree_au_internal_validate( struct lfds700_btree_au_state *abs, struct lfds700_misc_validation_info *vi, enum lfds700_misc_validity *lfds700_btree_au_validity );
   6
   7
   8
   9
  10
  11 /****************************************************************************/
  12 void lfds700_btree_au_query( struct lfds700_btree_au_state *baus, enum lfds700_btree_au_query query_type, void *query_input, void *query_output )
  13 {
  14   LFDS700_PAL_ASSERT( baus != NULL );
  15   // TRD : query_type can be any value in its range
  16
  17   LFDS700_MISC_BARRIER_LOAD;
  18
  19   switch( query_type )
  20   {
  21     case LFDS700_BTREE_AU_QUERY_GET_POTENTIALLY_INACCURATE_COUNT:
  22     {
  23       struct lfds700_btree_au_element
  24         *baue = NULL;
  25
  26       LFDS700_PAL_ASSERT( query_input == NULL );
  27       LFDS700_PAL_ASSERT( query_output != NULL );
  28
  29       *(lfds700_pal_uint_t *) query_output = 0;
  30
  31       while( lfds700_btree_au_get_by_absolute_position_and_then_by_relative_position(baus, &baue, LFDS700_BTREE_AU_ABSOLUTE_POSITION_SMALLEST_IN_TREE, LFDS700_BTREE_AU_RELATIVE_POSITION_NEXT_LARGER_ELEMENT_IN_ENTIRE_TREE) )
  32         ( *(lfds700_pal_uint_t *) query_output )++;
  33     }
  34     break;
  35
  36     case LFDS700_BTREE_AU_QUERY_SINGLETHREADED_VALIDATE:
  37       // TRD : query_input can be NULL
  38       LFDS700_PAL_ASSERT( query_output != NULL );
  39
  40       lfds700_btree_au_internal_validate( baus, (struct lfds700_misc_validation_info *) query_input, (enum lfds700_misc_validity *) query_output );
  41     break;
  42   }
  43
  44   return;
  45 }
  46
  47
  48
  49
  50
  51 /****************************************************************************/
  52 static void lfds700_btree_au_internal_validate( struct lfds700_btree_au_state *baus, struct lfds700_misc_validation_info *vi, enum lfds700_misc_validity *lfds700_btree_au_validity )
  53 {
  54   lfds700_pal_uint_t
  55     number_elements_from_query_tree = 0,
  56     number_elements_from_walk = 0;
  57
  58   struct lfds700_btree_au_element
  59     *baue = NULL,
  60     *baue_prev = NULL;
  61
  62   LFDS700_PAL_ASSERT( baus!= NULL );
  63   // TRD : vi can be NULL
  64   LFDS700_PAL_ASSERT( lfds700_btree_au_validity != NULL );
  65
  66   *lfds700_btree_au_validity = LFDS700_MISC_VALIDITY_VALID;
  67
  68   /* TRD : validation is performed by;
  69
  70            performing an in-order walk
  71            we should see every element is larger than the preceeding element
  72            we count elements as we go along (visited elements, that is)
  73            and check our tally equals the expected count
  74   */
  75
  76   LFDS700_MISC_BARRIER_LOAD;
  77
  78   while( lfds700_btree_au_get_by_absolute_position_and_then_by_relative_position(baus, &baue, LFDS700_BTREE_AU_ABSOLUTE_POSITION_SMALLEST_IN_TREE, LFDS700_BTREE_AU_RELATIVE_POSITION_NEXT_LARGER_ELEMENT_IN_ENTIRE_TREE) )
  79   {
  80     // TRD : baue_prev should always be smaller than or equal to baue
  81     if( baue_prev != NULL )
  82       if( baus->key_compare_function(baue_prev->key, baue->key) > 0 )
  83       {
  84         *lfds700_btree_au_validity = LFDS700_MISC_VALIDITY_INVALID_ORDER;
  85         return;
  86       }
  87
  88     baue_prev = baue;
  89     number_elements_from_walk++;
  90   }
  91
  92   if( *lfds700_btree_au_validity == LFDS700_MISC_VALIDITY_VALID )
  93   {
  94     lfds700_btree_au_query( (struct lfds700_btree_au_state *) baus, LFDS700_BTREE_AU_QUERY_GET_POTENTIALLY_INACCURATE_COUNT, NULL, &number_elements_from_query_tree );
  95
  96     if( number_elements_from_walk > number_elements_from_query_tree )
  97       *lfds700_btree_au_validity = LFDS700_MISC_VALIDITY_INVALID_ADDITIONAL_ELEMENTS;
  98
  99     if( number_elements_from_walk < number_elements_from_query_tree )
 100       *lfds700_btree_au_validity = LFDS700_MISC_VALIDITY_INVALID_MISSING_ELEMENTS;
 101   }
 102
 103   /* TRD : now check for expected number of elements
 104            vi can be NULL, in which case we do not check
 105            we know we don't have a loop from our earlier check
 106   */
 107
 108   if( *lfds700_btree_au_validity == LFDS700_MISC_VALIDITY_VALID and vi != NULL )
 109   {
 110     lfds700_btree_au_query( (struct lfds700_btree_au_state *) baus, LFDS700_BTREE_AU_QUERY_GET_POTENTIALLY_INACCURATE_COUNT, NULL, &number_elements_from_query_tree );
 111
 112     if( number_elements_from_query_tree < vi->min_elements )
 113       *lfds700_btree_au_validity = LFDS700_MISC_VALIDITY_INVALID_MISSING_ELEMENTS;
 114
 115     if( number_elements_from_query_tree > vi->max_elements )
 116       *lfds700_btree_au_validity = LFDS700_MISC_VALIDITY_INVALID_ADDITIONAL_ELEMENTS;
 117   }
 118
 119   return;
 120 }
 121