pd.if.org Git - liblfds/blob - liblfds/liblfds6.1.0/liblfds610/src/lfds610_freelist/lfds610_freelist_query.c

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