pd.if.org Git - liblfds/blob - liblfds/liblfds7.0.0/liblfds700/src/lfds700_freelist/lfds700_freelist_query.c

   1 /***** includes *****/
   2 #include "lfds700_freelist_internal.h"
   3
   4 /***** private prototypes *****/
   5 static void lfds700_freelist_internal_freelist_validate( struct lfds700_freelist_state *fs, struct lfds700_misc_validation_info *vi, enum lfds700_misc_validity *lfds700_freelist_validity );
   6
   7
   8
   9
  10
  11 /****************************************************************************/
  12 void lfds700_freelist_query( struct lfds700_freelist_state *fs, enum lfds700_freelist_query query_type, void *query_input, void *query_output )
  13 {
  14   struct lfds700_freelist_element
  15     *fe;
  16
  17   LFDS700_PAL_ASSERT( fs != NULL );
  18   // TRD : query_type can be any value in its range
  19
  20   LFDS700_MISC_BARRIER_LOAD;
  21
  22   switch( query_type )
  23   {
  24     case LFDS700_FREELIST_QUERY_SINGLETHREADED_GET_COUNT:
  25       LFDS700_PAL_ASSERT( query_input == NULL );
  26       LFDS700_PAL_ASSERT( query_output != NULL );
  27
  28       *(lfds700_pal_uint_t *) query_output = 0;
  29
  30       fe = (struct lfds700_freelist_element *) fs->top[POINTER];
  31
  32       while( fe != NULL )
  33       {
  34         ( *(lfds700_pal_uint_t *) query_output )++;
  35         fe = (struct lfds700_freelist_element *) fe->next;
  36       }
  37     break;
  38
  39     case LFDS700_FREELIST_QUERY_SINGLETHREADED_VALIDATE:
  40       // TRD : query_input can be NULL
  41       LFDS700_PAL_ASSERT( query_output != NULL );
  42
  43       lfds700_freelist_internal_freelist_validate( fs, (struct lfds700_misc_validation_info *) query_input, (enum lfds700_misc_validity *) query_output );
  44     break;
  45   }
  46
  47   return;
  48 }
  49
  50
  51
  52
  53
  54 /****************************************************************************/
  55 static void lfds700_freelist_internal_freelist_validate( struct lfds700_freelist_state *fs, struct lfds700_misc_validation_info *vi, enum lfds700_misc_validity *lfds700_freelist_validity )
  56 {
  57   lfds700_pal_uint_t
  58     number_elements = 0;
  59
  60   struct lfds700_freelist_element
  61     *fe_slow,
  62     *fe_fast;
  63
  64   LFDS700_PAL_ASSERT( fs != NULL );
  65   // TRD : vi can be NULL
  66   LFDS700_PAL_ASSERT( lfds700_freelist_validity != NULL );
  67
  68   *lfds700_freelist_validity = LFDS700_MISC_VALIDITY_VALID;
  69
  70   fe_slow = fe_fast = (struct lfds700_freelist_element *) fs->top[POINTER];
  71
  72   /* TRD : first, check for a loop
  73            we have two pointers
  74            both of which start at the top of the freelist
  75            we enter a loop
  76            and on each iteration
  77            we advance one pointer by one element
  78            and the other by two
  79
  80            we exit the loop when both pointers are NULL
  81            (have reached the end of the freelist)
  82
  83            or
  84
  85            if we fast pointer 'sees' the slow pointer
  86            which means we have a loop
  87   */
  88
  89   if( fe_slow != NULL )
  90     do
  91     {
  92       fe_slow = fe_slow->next;
  93
  94       if( fe_fast != NULL )
  95         fe_fast = fe_fast->next;
  96
  97       if( fe_fast != NULL )
  98         fe_fast = fe_fast->next;
  99     }
 100     while( fe_slow != NULL and fe_fast != fe_slow );
 101
 102   if( fe_fast != NULL and fe_slow != NULL and fe_fast == fe_slow )
 103     *lfds700_freelist_validity = LFDS700_MISC_VALIDITY_INVALID_LOOP;
 104
 105   /* TRD : now check for expected number of elements
 106            vi can be NULL, in which case we do not check
 107            we know we don't have a loop from our earlier check
 108   */
 109
 110   if( *lfds700_freelist_validity == LFDS700_MISC_VALIDITY_VALID and vi != NULL )
 111   {
 112     lfds700_freelist_query( fs, LFDS700_FREELIST_QUERY_SINGLETHREADED_GET_COUNT, NULL, (void *) &number_elements );
 113
 114     if( number_elements < vi->min_elements )
 115       *lfds700_freelist_validity = LFDS700_MISC_VALIDITY_INVALID_MISSING_ELEMENTS;
 116
 117     if( number_elements > vi->max_elements )
 118       *lfds700_freelist_validity = LFDS700_MISC_VALIDITY_INVALID_ADDITIONAL_ELEMENTS;
 119   }
 120
 121   return;
 122 }
 123