pd.if.org Git - liblfds/blob - liblfds/liblfds6.1.1/liblfds611/src/lfds611_freelist/lfds611_freelist_query.c

   1 #include "lfds611_freelist_internal.h"\r
   2 \r
   3 \r
   4 \r
   5 \r
   6 \r
   7 /****************************************************************************/\r
   8 void lfds611_freelist_query( struct lfds611_freelist_state *fs, enum lfds611_freelist_query_type query_type, void *query_input, void *query_output )\r
   9 {\r
  10   assert( fs != NULL );\r
  11   // TRD : query type can be any value in its range\r
  12   // TRD : query_input can be NULL in some cases\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_FREELIST_QUERY_ELEMENT_COUNT:\r
  20       assert( query_input == NULL );\r
  21 \r
  22       *(lfds611_atom_t *) query_output = fs->element_count;\r
  23     break;\r
  24 \r
  25     case LFDS611_FREELIST_QUERY_VALIDATE:\r
  26       // TRD : query_input can be NULL\r
  27 \r
  28       lfds611_freelist_internal_validate( fs, (struct lfds611_validation_info *) query_input, (enum lfds611_data_structure_validity *) query_output );\r
  29     break;\r
  30   }\r
  31 \r
  32   return;\r
  33 }\r
  34 \r
  35 \r
  36 \r
  37 \r
  38 \r
  39 /****************************************************************************/\r
  40 void lfds611_freelist_internal_validate( struct lfds611_freelist_state *fs, struct lfds611_validation_info *vi, enum lfds611_data_structure_validity *lfds611_freelist_validity )\r
  41 {\r
  42   struct lfds611_freelist_element\r
  43     *fe,\r
  44     *fe_slow,\r
  45     *fe_fast;\r
  46 \r
  47   lfds611_atom_t\r
  48     element_count = 0;\r
  49 \r
  50   assert( fs != NULL );\r
  51   // TRD : vi can be NULL\r
  52   assert( lfds611_freelist_validity != NULL );\r
  53 \r
  54   *lfds611_freelist_validity = LFDS611_VALIDITY_VALID;\r
  55 \r
  56   fe_slow = fe_fast = (struct lfds611_freelist_element *) fs->top[LFDS611_FREELIST_POINTER];\r
  57 \r
  58   /* TRD : first, check for a loop\r
  59            we have two pointers\r
  60            both of which start at the top of the lfds611_freelist\r
  61            we enter a loop\r
  62            and on each iteration\r
  63            we advance one pointer by one element\r
  64            and the other by two\r
  65 \r
  66            we exit the loop when both pointers are NULL\r
  67            (have reached the end of the lfds611_freelist)\r
  68 \r
  69            or\r
  70 \r
  71            if we fast pointer 'sees' the slow pointer\r
  72            which means we have a loop\r
  73   */\r
  74 \r
  75   if( fe_slow != NULL )\r
  76     do\r
  77     {\r
  78       fe_slow = fe_slow->next[LFDS611_FREELIST_POINTER];\r
  79 \r
  80       if( fe_fast != NULL )\r
  81         fe_fast = fe_fast->next[LFDS611_FREELIST_POINTER];\r
  82 \r
  83       if( fe_fast != NULL )\r
  84         fe_fast = fe_fast->next[LFDS611_FREELIST_POINTER];\r
  85     }\r
  86     while( fe_slow != NULL and fe_fast != fe_slow );\r
  87 \r
  88   if( fe_fast != NULL and fe_slow != NULL and fe_fast == fe_slow )\r
  89     *lfds611_freelist_validity = LFDS611_VALIDITY_INVALID_LOOP;\r
  90 \r
  91   /* TRD : now check for expected number of elements\r
  92            vi can be NULL, in which case we do not check\r
  93            we know we don't have a loop from our earlier check\r
  94   */\r
  95 \r
  96   if( *lfds611_freelist_validity == LFDS611_VALIDITY_VALID and vi != NULL )\r
  97   {\r
  98     fe = (struct lfds611_freelist_element *) fs->top[LFDS611_FREELIST_POINTER];\r
  99 \r
 100     while( fe != NULL )\r
 101     {\r
 102       element_count++;\r
 103       fe = (struct lfds611_freelist_element *) fe->next[LFDS611_FREELIST_POINTER];\r
 104     }\r
 105 \r
 106     if( element_count < vi->min_elements )\r
 107       *lfds611_freelist_validity = LFDS611_VALIDITY_INVALID_MISSING_ELEMENTS;\r
 108 \r
 109     if( element_count > vi->max_elements )\r
 110       *lfds611_freelist_validity = LFDS611_VALIDITY_INVALID_ADDITIONAL_ELEMENTS;\r
 111   }\r
 112 \r
 113   return;\r
 114 }\r
 115 \r