2 #include "lfds710_freelist_internal.h"
8 /****************************************************************************/
9 int lfds710_freelist_pop( struct lfds710_freelist_state *fs,
10 struct lfds710_freelist_element **fe,
11 struct lfds710_prng_st_state *psts )
17 backoff_iteration = LFDS710_BACKOFF_INITIAL_VALUE,
18 elimination_array_index,
22 struct lfds710_freelist_element LFDS710_PAL_ALIGN(LFDS710_PAL_ALIGN_DOUBLE_POINTER)
24 *volatile original_top[PAC_SIZE];
26 LFDS710_PAL_ASSERT( fs != NULL );
27 LFDS710_PAL_ASSERT( fe != NULL );
28 // TRD : psts can be NULL
30 LFDS710_MISC_BARRIER_LOAD;
32 if( fs->elimination_array_size_in_elements > 0 )
36 LFDS710_PRNG_ST_GENERATE( *psts, random_value );
37 elimination_array_index = ( random_value & (fs->elimination_array_size_in_elements-1) );
41 elimination_array_index = (lfds710_pal_uint_t) fe;
42 LFDS710_PRNG_ST_MIXING_FUNCTION( elimination_array_index );
43 elimination_array_index = ( elimination_array_index & (fs->elimination_array_size_in_elements-1) );
46 // TRD : full scan of one cache line, max pointers per cache line
50 for( loop = 0 ; loop < LFDS710_FREELIST_ELIMINATION_ARRAY_ELEMENT_SIZE_IN_FREELIST_ELEMENTS ; loop++ )
51 if( fs->elimination_array[elimination_array_index][loop] != NULL )
53 LFDS710_PAL_ATOMIC_EXCHANGE( &fs->elimination_array[elimination_array_index][loop], *fe, struct lfds710_freelist_element * );
59 original_top[COUNTER] = fs->top[COUNTER];
60 original_top[POINTER] = fs->top[POINTER];
64 if( original_top[POINTER] == NULL )
70 new_top[COUNTER] = original_top[COUNTER] + 1;
71 new_top[POINTER] = original_top[POINTER]->next;
73 LFDS710_PAL_ATOMIC_DWCAS( fs->top, original_top, new_top, LFDS710_MISC_CAS_STRENGTH_WEAK, result );
77 LFDS710_BACKOFF_EXPONENTIAL_BACKOFF( fs->pop_backoff, backoff_iteration );
78 LFDS710_MISC_BARRIER_LOAD;
83 *fe = original_top[POINTER];
85 LFDS710_BACKOFF_AUTOTUNE( fs->pop_backoff, backoff_iteration );