pd.if.org Git - liblfds/blob - liblfds/liblfds6.0.0/liblfds600/src/lfds600_freelist/lfds600_freelist_query.c

   1 #include "lfds600_freelist_internal.h"
   2
   3
   4
   5
   6
   7 /****************************************************************************/
   8 void lfds600_freelist_query( struct lfds600_freelist_state *fs, enum lfds600_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   switch( query_type )
  16   {
  17     case LFDS600_FREELIST_QUERY_ELEMENT_COUNT:
  18       assert( query_input == NULL );
  19
  20       *(lfds600_atom_t *) query_output = fs->element_count;
  21     break;
  22
  23     case LFDS600_FREELIST_QUERY_VALIDATE:
  24       // TRD : query_input can be NULL
  25
  26       lfds600_freelist_internal_validate( fs, (struct lfds600_validation_info *) query_input, (enum data_structure_validity *) query_output );
  27     break;
  28   }
  29
  30   return;
  31 }
  32
  33
  34
  35
  36
  37 /****************************************************************************/
  38 void lfds600_freelist_internal_validate( struct lfds600_freelist_state *fs, struct lfds600_validation_info *vi, enum data_structure_validity *lfds600_freelist_validity )
  39 {
  40   struct lfds600_freelist_element
  41     *fe,
  42     *fe_slow,
  43     *fe_fast;
  44
  45   lfds600_atom_t
  46     element_count = 0;
  47
  48   assert( fs != NULL );
  49   // TRD : vi can be NULL
  50   assert( lfds600_freelist_validity != NULL );
  51
  52   *lfds600_freelist_validity = VALIDITY_VALID;
  53
  54   fe_slow = fe_fast = (struct lfds600_freelist_element *) fs->top[LFDS600_FREELIST_POINTER];
  55
  56   /* TRD : first, check for a loop
  57            we have two pointers
  58            both of which start at the top of the lfds600_freelist
  59            we enter a loop
  60            and on each iteration
  61            we advance one pointer by one element
  62            and the other by two
  63
  64            we exit the loop when both pointers are NULL
  65            (have reached the end of the lfds600_freelist)
  66
  67            or
  68
  69            if we fast pointer 'sees' the slow pointer
  70            which means we have a loop
  71   */
  72
  73   if( fe_slow != NULL )
  74     do
  75     {
  76       fe_slow = fe_slow->next[LFDS600_FREELIST_POINTER];
  77
  78       if( fe_fast != NULL )
  79         fe_fast = fe_fast->next[LFDS600_FREELIST_POINTER];
  80
  81       if( fe_fast != NULL )
  82         fe_fast = fe_fast->next[LFDS600_FREELIST_POINTER];
  83     }
  84     while( fe_slow != NULL and fe_fast != fe_slow );
  85
  86   if( fe_fast != NULL and fe_slow != NULL and fe_fast == fe_slow )
  87     *lfds600_freelist_validity = VALIDITY_INVALID_LOOP;
  88
  89   /* TRD : now check for expected number of elements
  90            vi can be NULL, in which case we do not check
  91            we know we don't have a loop from our earlier check
  92   */
  93
  94   if( *lfds600_freelist_validity == VALIDITY_VALID and vi != NULL )
  95   {
  96     fe = (struct lfds600_freelist_element *) fs->top[LFDS600_FREELIST_POINTER];
  97
  98     while( fe != NULL )
  99     {
 100       element_count++;
 101       fe = (struct lfds600_freelist_element *) fe->next[LFDS600_FREELIST_POINTER];
 102     }
 103
 104     if( element_count < vi->min_elements )
 105       *lfds600_freelist_validity = VALIDITY_INVALID_MISSING_ELEMENTS;
 106
 107     if( element_count > vi->max_elements )
 108       *lfds600_freelist_validity = VALIDITY_INVALID_ADDITIONAL_ELEMENTS;
 109   }
 110
 111   return;
 112 }
 113