pd.if.org Git - liblfds/blob - liblfds/liblfds7.1.0/liblfds710/src/lfds710_freelist/lfds710_freelist_query.c

   1 /***** includes *****/
   2 #include "lfds710_freelist_internal.h"
   3
   4 /***** private prototypes *****/
   5 static void lfds710_freelist_internal_freelist_validate( struct lfds710_freelist_state *fs,
   6                                                          struct lfds710_misc_validation_info *vi,
   7                                                          enum lfds710_misc_validity *lfds710_freelist_validity );
   8
   9
  10
  11
  12
  13 /****************************************************************************/
  14 void lfds710_freelist_query( struct lfds710_freelist_state *fs,
  15                              enum lfds710_freelist_query query_type,
  16                              void *query_input,
  17                              void *query_output )
  18 {
  19   struct lfds710_freelist_element
  20     *fe;
  21
  22   LFDS710_PAL_ASSERT( fs != NULL );
  23   // TRD : query_type can be any value in its range
  24
  25   LFDS710_MISC_BARRIER_LOAD;
  26
  27   switch( query_type )
  28   {
  29     case LFDS710_FREELIST_QUERY_SINGLETHREADED_GET_COUNT:
  30     {
  31       lfds710_pal_uint_t
  32         loop,
  33         subloop;
  34
  35       LFDS710_PAL_ASSERT( query_input == NULL );
  36       LFDS710_PAL_ASSERT( query_output != NULL );
  37
  38       *(lfds710_pal_uint_t *) query_output = 0;
  39
  40       // TRD : count the elements in the elimination array
  41       for( loop = 0 ; loop < fs->elimination_array_size_in_elements ; loop++ )
  42         for( subloop = 0 ; subloop < LFDS710_FREELIST_ELIMINATION_ARRAY_ELEMENT_SIZE_IN_FREELIST_ELEMENTS ; subloop++ )
  43           if( fs->elimination_array[loop][subloop] != NULL )
  44             ( *(lfds710_pal_uint_t *) query_output )++;
  45
  46       // TRD : count the elements on the freelist
  47       fe = (struct lfds710_freelist_element *) fs->top[POINTER];
  48
  49       while( fe != NULL )
  50       {
  51         ( *(lfds710_pal_uint_t *) query_output )++;
  52         fe = (struct lfds710_freelist_element *) fe->next;
  53       }
  54     }
  55     break;
  56
  57     case LFDS710_FREELIST_QUERY_SINGLETHREADED_VALIDATE:
  58       // TRD : query_input can be NULL
  59       LFDS710_PAL_ASSERT( query_output != NULL );
  60
  61       lfds710_freelist_internal_freelist_validate( fs, (struct lfds710_misc_validation_info *) query_input, (enum lfds710_misc_validity *) query_output );
  62     break;
  63
  64     case LFDS710_FREELIST_QUERY_GET_ELIMINATION_ARRAY_EXTRA_ELEMENTS_IN_FREELIST_ELEMENTS:
  65     {
  66       LFDS710_PAL_ASSERT( query_input == NULL );
  67       LFDS710_PAL_ASSERT( query_output != NULL );
  68
  69       ( *(lfds710_pal_uint_t *) query_output ) = (fs->elimination_array_size_in_elements-1) * LFDS710_FREELIST_ELIMINATION_ARRAY_ELEMENT_SIZE_IN_FREELIST_ELEMENTS;
  70     }
  71     break;
  72   }
  73
  74   return;
  75 }
  76
  77
  78
  79
  80
  81 /****************************************************************************/
  82 static void lfds710_freelist_internal_freelist_validate( struct lfds710_freelist_state *fs,
  83                                                          struct lfds710_misc_validation_info *vi,
  84                                                          enum lfds710_misc_validity *lfds710_freelist_validity )
  85 {
  86   lfds710_pal_uint_t
  87     number_elements = 0;
  88
  89   struct lfds710_freelist_element
  90     *fe_slow,
  91     *fe_fast;
  92
  93   LFDS710_PAL_ASSERT( fs != NULL );
  94   // TRD : vi can be NULL
  95   LFDS710_PAL_ASSERT( lfds710_freelist_validity != NULL );
  96
  97   *lfds710_freelist_validity = LFDS710_MISC_VALIDITY_VALID;
  98
  99   fe_slow = fe_fast = (struct lfds710_freelist_element *) fs->top[POINTER];
 100
 101   /* TRD : first, check for a loop
 102            we have two pointers
 103            both of which start at the top of the freelist
 104            we enter a loop
 105            and on each iteration
 106            we advance one pointer by one element
 107            and the other by two
 108
 109            we exit the loop when both pointers are NULL
 110            (have reached the end of the freelist)
 111
 112            or
 113
 114            if we fast pointer 'sees' the slow pointer
 115            which means we have a loop
 116   */
 117
 118   if( fe_slow != NULL )
 119     do
 120     {
 121       fe_slow = fe_slow->next;
 122
 123       if( fe_fast != NULL )
 124         fe_fast = fe_fast->next;
 125
 126       if( fe_fast != NULL )
 127         fe_fast = fe_fast->next;
 128     }
 129     while( fe_slow != NULL and fe_fast != fe_slow );
 130
 131   if( fe_fast != NULL and fe_slow != NULL and fe_fast == fe_slow )
 132     *lfds710_freelist_validity = LFDS710_MISC_VALIDITY_INVALID_LOOP;
 133
 134   /* TRD : now check for expected number of elements
 135            vi can be NULL, in which case we do not check
 136            we know we don't have a loop from our earlier check
 137   */
 138
 139   if( *lfds710_freelist_validity == LFDS710_MISC_VALIDITY_VALID and vi != NULL )
 140   {
 141     lfds710_freelist_query( fs, LFDS710_FREELIST_QUERY_SINGLETHREADED_GET_COUNT, NULL, (void *) &number_elements );
 142
 143     if( number_elements < vi->min_elements )
 144       *lfds710_freelist_validity = LFDS710_MISC_VALIDITY_INVALID_MISSING_ELEMENTS;
 145
 146     if( number_elements > vi->max_elements )
 147       *lfds710_freelist_validity = LFDS710_MISC_VALIDITY_INVALID_ADDITIONAL_ELEMENTS;
 148   }
 149
 150   return;
 151 }
 152