pd.if.org Git - liblfds/blob - liblfds/liblfds7.1.0/liblfds710/src/lfds710_list_addonly_singlylinked_ordered/lfds710_list_addonly_singlylinked_ordered_query.c

   1 /***** includes *****/
   2 #include "lfds710_list_addonly_singlylinked_ordered_internal.h"
   3
   4 /***** private prototypes *****/
   5 static void lfds710_list_aso_internal_validate( struct lfds710_list_aso_state *lasos,
   6                                                 struct lfds710_misc_validation_info *vi,
   7                                                 enum lfds710_misc_validity *lfds710_list_aso_validity );
   8
   9
  10
  11
  12
  13 /****************************************************************************/
  14 void lfds710_list_aso_query( struct lfds710_list_aso_state *lasos,
  15                              enum lfds710_list_aso_query query_type,
  16                              void *query_input,
  17                              void *query_output )
  18 {
  19   LFDS710_PAL_ASSERT( lasos != NULL );
  20   // TRD : query_type can be any value in its range
  21
  22   LFDS710_MISC_BARRIER_LOAD;
  23
  24   switch( query_type )
  25   {
  26     case LFDS710_LIST_ASO_QUERY_GET_POTENTIALLY_INACCURATE_COUNT:
  27     {
  28       struct lfds710_list_aso_element
  29         *lasoe = NULL;
  30
  31       LFDS710_PAL_ASSERT( query_input == NULL );
  32       LFDS710_PAL_ASSERT( query_output != NULL );
  33
  34       *(lfds710_pal_uint_t *) query_output = 0;
  35
  36       while( LFDS710_LIST_ASO_GET_START_AND_THEN_NEXT(*lasos, lasoe) )
  37         ( *(lfds710_pal_uint_t *) query_output )++;
  38     }
  39     break;
  40
  41     case LFDS710_LIST_ASO_QUERY_SINGLETHREADED_VALIDATE:
  42       // TRD : query_input can be NULL
  43       LFDS710_PAL_ASSERT( query_output != NULL );
  44
  45       lfds710_list_aso_internal_validate( lasos, (struct lfds710_misc_validation_info *) query_input, (enum lfds710_misc_validity *) query_output );
  46     break;
  47   }
  48
  49   return;
  50 }
  51
  52
  53
  54
  55
  56
  57 /****************************************************************************/
  58 static void lfds710_list_aso_internal_validate( struct lfds710_list_aso_state *lasos,
  59                                                 struct lfds710_misc_validation_info *vi,
  60                                                 enum lfds710_misc_validity *lfds710_list_aso_validity )
  61 {
  62   lfds710_pal_uint_t
  63     number_elements = 0;
  64
  65   struct lfds710_list_aso_element
  66     *lasoe_fast,
  67     *lasoe_slow;
  68
  69   LFDS710_PAL_ASSERT( lasos!= NULL );
  70   // TRD : vi can be NULL
  71   LFDS710_PAL_ASSERT( lfds710_list_aso_validity != NULL );
  72
  73   *lfds710_list_aso_validity = LFDS710_MISC_VALIDITY_VALID;
  74
  75   lasoe_slow = lasoe_fast = lasos->start->next;
  76
  77   /* TRD : first, check for a loop
  78            we have two pointers
  79            both of which start at the start of the list
  80            we enter a loop
  81            and on each iteration
  82            we advance one pointer by one element
  83            and the other by two
  84
  85            we exit the loop when both pointers are NULL
  86            (have reached the end of the queue)
  87
  88            or
  89
  90            if we fast pointer 'sees' the slow pointer
  91            which means we have a loop
  92   */
  93
  94   if( lasoe_slow != NULL )
  95     do
  96     {
  97       lasoe_slow = lasoe_slow->next;
  98
  99       if( lasoe_fast != NULL )
 100         lasoe_fast = lasoe_fast->next;
 101
 102       if( lasoe_fast != NULL )
 103         lasoe_fast = lasoe_fast->next;
 104     }
 105     while( lasoe_slow != NULL and lasoe_fast != lasoe_slow );
 106
 107   if( lasoe_fast != NULL and lasoe_slow != NULL and lasoe_fast == lasoe_slow )
 108     *lfds710_list_aso_validity = LFDS710_MISC_VALIDITY_INVALID_LOOP;
 109
 110   /* TRD : now check for expected number of elements
 111            vi can be NULL, in which case we do not check
 112            we know we don't have a loop from our earlier check
 113   */
 114
 115   if( *lfds710_list_aso_validity == LFDS710_MISC_VALIDITY_VALID and vi != NULL )
 116   {
 117     lfds710_list_aso_query( lasos, LFDS710_LIST_ASO_QUERY_GET_POTENTIALLY_INACCURATE_COUNT, NULL, &number_elements );
 118
 119     if( number_elements < vi->min_elements )
 120       *lfds710_list_aso_validity = LFDS710_MISC_VALIDITY_INVALID_MISSING_ELEMENTS;
 121
 122     if( number_elements > vi->max_elements )
 123       *lfds710_list_aso_validity = LFDS710_MISC_VALIDITY_INVALID_ADDITIONAL_ELEMENTS;
 124   }
 125
 126   return;
 127 }
 128