pd.if.org Git - liblfds/blob - liblfds/liblfds7.1.0/liblfds710/src/lfds710_queue_bounded_singleproducer_singleconsumer/lfds710_queue_bounded_singleproducer_singleconsumer_init.c

   1 /***** includes *****/
   2 #include "lfds710_queue_bounded_singleproducer_singleconsumer_internal.h"
   3
   4
   5
   6
   7
   8 /****************************************************************************/
   9 void lfds710_queue_bss_init_valid_on_current_logical_core( struct lfds710_queue_bss_state *qbsss,
  10                                                            struct lfds710_queue_bss_element *element_array,
  11                                                            lfds710_pal_uint_t number_elements,
  12                                                            void *user_state )
  13 {
  14   LFDS710_PAL_ASSERT( qbsss != NULL );
  15   LFDS710_PAL_ASSERT( element_array != NULL );
  16   LFDS710_PAL_ASSERT( number_elements >= 2 );
  17   LFDS710_PAL_ASSERT( ( number_elements & (number_elements-1) ) == 0 ); // TRD : number_elements must be a positive integer power of 2
  18   // TRD : user_state can be NULL
  19
  20   /* TRD : the use of mask and the restriction on a power of two
  21            upon the number of elements bears some remark
  22
  23            in this queue, there are a fixed number of elements
  24            we have a read index and a write index
  25            when we write, and thre is space to write, we increment the write index
  26            (if no space to write, we just return)
  27            when we read, and there are elements to be read, we after reading increment the read index
  28            (if no elements to read, we just return)
  29            the problem is - how do we handle wrap around?
  30            e.g. when I write, but my write index is now equal to the number of elements
  31            the usual solution is to modulus the write index by the nunmber of elements
  32            problem is modulus is slow
  33            there is a better way
  34            first, we restrict the number of elements to be a power of two
  35            so imagine we have a 64-bit system and we set the number of elements to be 2^64
  36            this gives us a bit pattern of 1000 0000 0000 0000 (...etc, lots of zeros)
  37            now (just roll with this for a bit) subtract one from this
  38            this gives us a mask (on a two's compliment machine)
  39            0111 1111 1111 1111 (...etc, lots of ones)
  40            so what we do now, when we increment an index (think of the write index as the example)
  41            we bitwise and it with the mask
  42            now think about thwt happens
  43            all the numbers up to 2^64 will be unchanged - their MSB is never set, and we and with all the other bits
  44            but when we finally hit 2^64 and need to roll over... bingo!
  45            we drop MSB (which we finally have) and have the value 0!
  46            this is exactly what we want
  47            bitwise and is much faster than modulus
  48   */
  49
  50   qbsss->number_elements = number_elements;
  51   qbsss->mask = qbsss->number_elements - 1;
  52   qbsss->read_index = 0;
  53   qbsss->write_index = 0;
  54   qbsss->element_array = element_array;
  55   qbsss->user_state = user_state;
  56
  57   LFDS710_MISC_BARRIER_STORE;
  58
  59   lfds710_misc_force_store();
  60
  61   return;
  62 }
  63