function lfds711_freelist_pop

Jump to navigation Jump to search

Source Files

    │   └───liblfds711
    │           lfds711_freelist.h

Opaque Structures

struct lfds711_freelist_element;
struct lfds711_freelist_state;
struct lfds711_prng_st_state;


int lfds711_freelist_pop( struct lfds711_freelist_state *fs,
                          struct lfds711_freelist_element **fe,
                          struct lfds711_prng_st_state *psts );


struct lfds711_freelist_state *fs

A pointer to an initialized struct lfds711_freelist_state.

struct lfds711_freelist_element **fe

A pointer to a user-allocated struct lfds711_freelist_element *, which is set to point to the freelist element popped from the freelist.

struct lfds711_prng_st_state *psts

A pointer to a user-allocated struct lfds711_prng_st_state. This argument is used by the elimination array to randomly select an element in the array. This argument can be NULL, in which case elimination array performance is degraded. If when initialized the freelist was given no elimination array, this argument is ignored as the elimination layer is not in use.

Return Value

Returns 1 on a successful pop. Returns 0 if popping failed.

If the elimination layer is not in use, popping only fails if the freelist is empty. If the elimination array is in use, where the popping thread scans only one element in the array (each element consists of one cache line, so it's normally eight pointers worth of possible elements, not just one!), it is possible for the attempt to pop from the elimination array to fail even though there are elements in the elimination array, because the one element which was scanned was empty. Upon failing to obtain an element from the elimination array, the popping thread will try to pop normally from the freelist. It may be then the freelist itself is actually empty, and so the attempt to pop will fail even though there are in fact elements available in the elimination array. The solution to this is to provide additional elements at initialization time, equal to the size of the elimination array. The size of the array is available from a call to lfds711_freelist_query.


This function pops a freelist element, with its key and value, from the freelist. The key and value are read from the freelist element by the macros LFDS711_FREELIST_GET_KEY_FROM_ELEMENT and LFDS711_FREELIST_GET_VALUE_FROM_ELEMENT respectively, and can only be correctly read when a freelist element is outside of a freelist; the macros can be issued at any time, of course, but if the element has not been popped by the thread calling the macro, then there is no guarantee the key and value read will be that which was written into the element. You were warned.

See Also