pd.if.org Git - liblfds/blob - liblfds/liblfds7.1.0/liblfds710/src/lfds710_stack/lfds710_stack_query.c

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