pd.if.org Git - liblfds/blob - liblfds/liblfds6.0.1/liblfds601/src/lfds601_queue/lfds601_queue_query.c

   1 #include "lfds601_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 lfds601_queue_query( struct lfds601_queue_state *qs, enum lfds601_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 LFDS601_QUEUE_QUERY_ELEMENT_COUNT:\r
  20       assert( query_input == NULL );\r
  21 \r
  22       lfds601_freelist_query( qs->fs, LFDS601_FREELIST_QUERY_ELEMENT_COUNT, NULL, query_output );\r
  23     break;\r
  24 \r
  25     case LFDS601_QUEUE_QUERY_VALIDATE:\r
  26       // TRD : query_input can be NULL\r
  27 \r
  28       lfds601_queue_internal_validate( qs, (struct lfds601_validation_info *) query_input, (enum lfds601_data_structure_validity *) query_output, ((enum lfds601_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 lfds601_queue_internal_validate( struct lfds601_queue_state *qs, struct lfds601_validation_info *vi, enum lfds601_data_structure_validity *lfds601_queue_validity, enum lfds601_data_structure_validity *lfds601_freelist_validity )\r
  43 {\r
  44   struct lfds601_queue_element\r
  45     *qe,\r
  46     *qe_slow,\r
  47     *qe_fast;\r
  48 \r
  49   lfds601_atom_t\r
  50     element_count = 0,\r
  51     total_elements;\r
  52 \r
  53   struct lfds601_validation_info\r
  54     lfds601_freelist_vi;\r
  55 \r
  56   assert( qs != NULL );\r
  57   // TRD : vi can be NULL\r
  58   assert( lfds601_queue_validity != NULL );\r
  59   assert( lfds601_freelist_validity != NULL );\r
  60 \r
  61   *lfds601_queue_validity = LFDS601_VALIDITY_VALID;\r
  62 \r
  63   qe_slow = qe_fast = (struct lfds601_queue_element *) qs->dequeue[LFDS601_QUEUE_POINTER];\r
  64 \r
  65   /* TRD : first, check for a loop\r
  66            we have two pointers\r
  67            both of which start at the dequeue end of the lfds601_queue\r
  68            we enter a loop\r
  69            and on each iteration\r
  70            we advance one pointer by one element\r
  71            and the other by two\r
  72 \r
  73            we exit the loop when both pointers are NULL\r
  74            (have reached the end of the lfds601_queue)\r
  75 \r
  76            or\r
  77 \r
  78            if we fast pointer 'sees' the slow pointer\r
  79            which means we have a loop\r
  80   */\r
  81 \r
  82   if( qe_slow != NULL )\r
  83     do\r
  84     {\r
  85       qe_slow = qe_slow->next[LFDS601_QUEUE_POINTER];\r
  86 \r
  87       if( qe_fast != NULL )\r
  88         qe_fast = qe_fast->next[LFDS601_QUEUE_POINTER];\r
  89 \r
  90       if( qe_fast != NULL )\r
  91         qe_fast = qe_fast->next[LFDS601_QUEUE_POINTER];\r
  92     }\r
  93     while( qe_slow != NULL and qe_fast != qe_slow );\r
  94 \r
  95   if( qe_fast != NULL and qe_slow != NULL and qe_fast == qe_slow )\r
  96     *lfds601_queue_validity = LFDS601_VALIDITY_INVALID_LOOP;\r
  97 \r
  98   /* TRD : now check for expected number of elements\r
  99            vi can be NULL, in which case we do not check\r
 100            we know we don't have a loop from our earlier check\r
 101   */\r
 102 \r
 103   if( *lfds601_queue_validity == LFDS601_VALIDITY_VALID and vi != NULL )\r
 104   {\r
 105     qe = (struct lfds601_queue_element *) qs->dequeue[LFDS601_QUEUE_POINTER];\r
 106 \r
 107     while( qe != NULL )\r
 108     {\r
 109       element_count++;\r
 110       qe = (struct lfds601_queue_element *) qe->next[LFDS601_QUEUE_POINTER];\r
 111     }\r
 112 \r
 113     /* TRD : remember there is a dummy element in the lfds601_queue */\r
 114     element_count--;\r
 115 \r
 116     if( element_count < vi->min_elements )\r
 117       *lfds601_queue_validity = LFDS601_VALIDITY_INVALID_MISSING_ELEMENTS;\r
 118 \r
 119     if( element_count > vi->max_elements )\r
 120       *lfds601_queue_validity = LFDS601_VALIDITY_INVALID_ADDITIONAL_ELEMENTS;\r
 121   }\r
 122 \r
 123   /* TRD : now we validate the lfds601_freelist\r
 124 \r
 125            we may be able to check for the expected number of\r
 126            elements in the lfds601_freelist\r
 127 \r
 128            if the caller has given us an expected min and max\r
 129            number of elements in the lfds601_queue, then the total number\r
 130            of elements in the lfds601_freelist, minus that min and max,\r
 131            gives us the expected number of elements in the\r
 132            lfds601_freelist\r
 133   */\r
 134 \r
 135   if( vi != NULL )\r
 136   {\r
 137     lfds601_freelist_query( qs->fs, LFDS601_FREELIST_QUERY_ELEMENT_COUNT, NULL, (void *) &total_elements );\r
 138 \r
 139     /* TRD : remember there is a dummy element in the lfds601_queue */\r
 140     total_elements--;\r
 141 \r
 142     lfds601_freelist_vi.min_elements = total_elements - vi->max_elements;\r
 143     lfds601_freelist_vi.max_elements = total_elements - vi->min_elements;\r
 144 \r
 145     lfds601_freelist_query( qs->fs, LFDS601_FREELIST_QUERY_VALIDATE, (void *) &lfds601_freelist_vi, (void *) lfds601_freelist_validity );\r
 146   }\r
 147 \r
 148   if( vi == NULL )\r
 149     lfds601_freelist_query( qs->fs, LFDS601_FREELIST_QUERY_VALIDATE, NULL, (void *) lfds601_freelist_validity );\r
 150 \r
 151   return;\r
 152 }\r
 153 \r