pd.if.org Git - liblfds/blob - liblfds/liblfds6.1.1/liblfds611/src/lfds611_stack/lfds611_stack_query.c

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