pd.if.org Git - liblfds/blob - liblfds/liblfds6.1.1/liblfds611/src/lfds611_queue/lfds611_queue_query.c

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