pd.if.org Git - liblfds/blob - liblfds/liblfds7.0.0/liblfds700/src/lfds700_list_addonly_singlylinked_unordered/lfds700_list_addonly_singlylinked_unordered_query.c

   1 /***** includes *****/
   2 #include "lfds700_list_addonly_singlylinked_unordered_internal.h"
   3
   4 /***** private prototypes *****/
   5 static void lfds700_list_asu_internal_validate( struct lfds700_list_asu_state *lasus, struct lfds700_misc_validation_info *vi, enum lfds700_misc_validity *lfds700_list_asu_validity );
   6
   7
   8
   9
  10
  11 /****************************************************************************/
  12 void lfds700_list_asu_query( struct lfds700_list_asu_state *lasus, enum lfds700_list_asu_query query_type, void *query_input, void *query_output )
  13 {
  14   LFDS700_PAL_ASSERT( lasus != 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_LIST_ASU_QUERY_GET_POTENTIALLY_INACCURATE_COUNT:
  22     {
  23       struct lfds700_list_asu_element
  24         *lasue = 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_LIST_ASU_GET_START_AND_THEN_NEXT(*lasus, lasue) )
  32         ( *(lfds700_pal_uint_t *) query_output )++;
  33     }
  34     break;
  35
  36     case LFDS700_LIST_ASU_QUERY_SINGLETHREADED_VALIDATE:
  37       // TRD : query_input can be NULL
  38       LFDS700_PAL_ASSERT( query_output != NULL );
  39
  40       lfds700_list_asu_internal_validate( lasus, (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 /****************************************************************************/
  53 static void lfds700_list_asu_internal_validate( struct lfds700_list_asu_state *lasus, struct lfds700_misc_validation_info *vi, enum lfds700_misc_validity *lfds700_list_asu_validity )
  54 {
  55   lfds700_pal_uint_t
  56     number_elements = 0;
  57
  58   struct lfds700_list_asu_element
  59     *lasue_fast,
  60     *lasue_slow;
  61
  62   LFDS700_PAL_ASSERT( lasus!= NULL );
  63   // TRD : vi can be NULL
  64   LFDS700_PAL_ASSERT( lfds700_list_asu_validity != NULL );
  65
  66   *lfds700_list_asu_validity = LFDS700_MISC_VALIDITY_VALID;
  67
  68   lasue_slow = lasue_fast = lasus->start->next;
  69
  70   /* TRD : first, check for a loop
  71            we have two pointers
  72            both of which start at the start of the list
  73            we enter a loop
  74            and on each iteration
  75            we advance one pointer by one element
  76            and the other by two
  77
  78            we exit the loop when both pointers are NULL
  79            (have reached the end of the queue)
  80
  81            or
  82
  83            if we fast pointer 'sees' the slow pointer
  84            which means we have a loop
  85   */
  86
  87   if( lasue_slow != NULL )
  88     do
  89     {
  90       lasue_slow = lasue_slow->next;
  91
  92       if( lasue_fast != NULL )
  93         lasue_fast = lasue_fast->next;
  94
  95       if( lasue_fast != NULL )
  96         lasue_fast = lasue_fast->next;
  97     }
  98     while( lasue_slow != NULL and lasue_fast != lasue_slow );
  99
 100   if( lasue_fast != NULL and lasue_slow != NULL and lasue_fast == lasue_slow )
 101     *lfds700_list_asu_validity = LFDS700_MISC_VALIDITY_INVALID_LOOP;
 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_list_asu_validity == LFDS700_MISC_VALIDITY_VALID and vi != NULL )
 109   {
 110     lfds700_list_asu_query( lasus, LFDS700_LIST_ASU_QUERY_GET_POTENTIALLY_INACCURATE_COUNT, NULL, &number_elements );
 111
 112     if( number_elements < vi->min_elements )
 113       *lfds700_list_asu_validity = LFDS700_MISC_VALIDITY_INVALID_MISSING_ELEMENTS;
 114
 115     if( number_elements > vi->max_elements )
 116       *lfds700_list_asu_validity = LFDS700_MISC_VALIDITY_INVALID_ADDITIONAL_ELEMENTS;
 117   }
 118
 119   return;
 120 }
 121