pd.if.org Git - liblfds/blob - liblfds/liblfds6.1.0/liblfds610/src/lfds610_stack/lfds610_stack_query.c

   1 #include "lfds610_stack_internal.h"
   2
   3
   4
   5
   6
   7 /****************************************************************************/
   8 void lfds610_stack_query( struct lfds610_stack_state *ss, enum lfds610_stack_query_type query_type, void *query_input, void *query_output )
   9 {
  10   assert( ss != NULL );
  11   // TRD : query_type can be any value in its range
  12   // TRD : query_iput can be NULL
  13   assert( query_output != NULL );
  14
  15   LFDS610_BARRIER_LOAD;
  16
  17   switch( query_type )
  18   {
  19     case LFDS610_STACK_QUERY_ELEMENT_COUNT:
  20       assert( query_input == NULL );
  21
  22       lfds610_freelist_query( ss->fs, LFDS610_FREELIST_QUERY_ELEMENT_COUNT, NULL, query_output );
  23     break;
  24
  25     case LFDS610_STACK_QUERY_VALIDATE:
  26       // TRD : query_input can be NULL
  27
  28       /* TRD : the validation info passed in is for the stack
  29                it indicates the minimum and maximum number of elements
  30                which should be present
  31
  32                we need to validate the freelist
  33                and validate the stack
  34
  35                we cannot know the min/max for the freelist, given only
  36                the min/max for the stack
  37       */
  38
  39       lfds610_freelist_query( ss->fs, LFDS610_FREELIST_QUERY_VALIDATE, NULL, (enum lfds610_data_structure_validity *) query_output );
  40
  41       if( *(enum lfds610_data_structure_validity *) query_output == LFDS610_VALIDITY_VALID )
  42         lfds610_stack_internal_validate( ss, (struct lfds610_validation_info *) query_input, (enum lfds610_data_structure_validity *) query_output, ((enum lfds610_data_structure_validity *) query_output)+1 );
  43     break;
  44   }
  45
  46   return;
  47 }
  48
  49
  50
  51
  52
  53 /****************************************************************************/
  54 void lfds610_stack_internal_validate( struct lfds610_stack_state *ss, struct lfds610_validation_info *vi, enum lfds610_data_structure_validity *stack_validity, enum lfds610_data_structure_validity *freelist_validity )
  55 {
  56   struct lfds610_stack_element
  57     *se,
  58     *se_slow,
  59     *se_fast;
  60
  61   lfds610_atom_t
  62     element_count = 0,
  63     total_elements;
  64
  65   struct lfds610_validation_info
  66     freelist_vi;
  67
  68   assert( ss != NULL );
  69   // TRD : vi can be NULL
  70   assert( stack_validity != NULL );
  71
  72   *stack_validity = LFDS610_VALIDITY_VALID;
  73
  74   se_slow = se_fast = (struct lfds610_stack_element *) ss->top[LFDS610_STACK_POINTER];
  75
  76   /* TRD : first, check for a loop
  77            we have two pointers
  78            both of which start at the top of the stack
  79            we enter a loop
  80            and on each iteration
  81            we advance one pointer by one element
  82            and the other by two
  83
  84            we exit the loop when both pointers are NULL
  85            (have reached the end of the stack)
  86
  87            or
  88
  89            if we fast pointer 'sees' the slow pointer
  90            which means we have a loop
  91   */
  92
  93   if( se_slow != NULL )
  94     do
  95     {
  96       se_slow = se_slow->next[LFDS610_STACK_POINTER];
  97
  98       if( se_fast != NULL )
  99         se_fast = se_fast->next[LFDS610_STACK_POINTER];
 100
 101       if( se_fast != NULL )
 102         se_fast = se_fast->next[LFDS610_STACK_POINTER];
 103     }
 104     while( se_slow != NULL and se_fast != se_slow );
 105
 106   if( se_fast != NULL and se_slow != NULL and se_fast == se_slow )
 107     *stack_validity = LFDS610_VALIDITY_INVALID_LOOP;
 108
 109   /* TRD : now check for expected number of elements
 110            vi can be NULL, in which case we do not check
 111            we know we don't have a loop from our earlier check
 112   */
 113
 114   if( *stack_validity == LFDS610_VALIDITY_VALID and vi != NULL )
 115   {
 116     se = (struct lfds610_stack_element *) ss->top[LFDS610_STACK_POINTER];
 117
 118     while( se != NULL )
 119     {
 120       element_count++;
 121       se = (struct lfds610_stack_element *) se->next[LFDS610_STACK_POINTER];
 122     }
 123
 124     if( element_count < vi->min_elements )
 125       *stack_validity = LFDS610_VALIDITY_INVALID_MISSING_ELEMENTS;
 126
 127     if( element_count > vi->max_elements )
 128       *stack_validity = LFDS610_VALIDITY_INVALID_ADDITIONAL_ELEMENTS;
 129   }
 130
 131   /* TRD : now we validate the freelist
 132
 133            we may be able to check for the expected number of
 134            elements in the freelist
 135
 136            if the caller has given us an expected min and max
 137            number of elements in the stack, then the total number
 138            of elements in the freelist, minus that min and max,
 139            gives us the expected number of elements in the
 140            freelist
 141   */
 142
 143   if( vi != NULL )
 144   {
 145     lfds610_freelist_query( ss->fs, LFDS610_FREELIST_QUERY_ELEMENT_COUNT, NULL, (void *) &total_elements );
 146
 147     freelist_vi.min_elements = total_elements - vi->max_elements;
 148     freelist_vi.max_elements = total_elements - vi->min_elements;
 149
 150     lfds610_freelist_query( ss->fs, LFDS610_FREELIST_QUERY_VALIDATE, (void *) &freelist_vi, (void *) freelist_validity );
 151   }
 152
 153   if( vi == NULL )
 154     lfds610_freelist_query( ss->fs, LFDS610_FREELIST_QUERY_VALIDATE, NULL, (void *) freelist_validity );
 155
 156   return;
 157 }
 158