| Home | Libraries | People | FAQ | More

## Class template queue

boost::lockfree::queue

## Synopsis

    // In header: <boost/lockfree/queue.hpp>

    template<typename T, typename A0, typename A1, typename A2>
    class queue {
    public:
      // member classes/structs/unions
      template<typename T, typename... Options>
      struct implementation_defined {
        // types
        typedef node_allocator allocator;
        typedef std::size_t    size_type;
      };
      // construct/copy/destruct
      queue(void);
      template<typename U>
        explicit queue(typename node_allocator::template rebind< U >::other const &);
      explicit queue(allocator const &);
      explicit queue(size_type);
      template<typename U>
        queue(size_type,
              typename node_allocator::template rebind< U >::other const &);
      ~queue(void);

      // private member functions
       BOOST_STATIC_ASSERT((boost::has_trivial_destructor< T >::value));
       BOOST_STATIC_ASSERT((boost::has_trivial_assign< T >::value));
      struct BOOST_ALIGNMENT(BOOST_LOCKFREE_CACHELINE_BYTES);
      void initialize(void);
       BOOST_DELETED_FUNCTION(queue(queue const &));
      bool is_lock_free(void) const;
      void reserve(size_type);
      void reserve_unsafe(size_type);
      bool empty(void) const;
      bool push(T const &);
      bool bounded_push(T const &);
      template<bool Bounded> bool do_push(T const &);

      // public member functions
      bool unsynchronized_push(T const &);
      bool pop(T &);
      template<typename U> bool pop(U &);
      bool unsynchronized_pop(T &);
      template<typename U> bool unsynchronized_pop(U &);
      template<typename Functor> bool consume_one(Functor &);
      template<typename Functor> bool consume_one(Functor const &);
      template<typename Functor> size_t consume_all(Functor &);
      template<typename Functor> size_t consume_all(Functor const &);
    };

## Description

The queue class provides a multi-writer/multi-reader queue, pushing and popping is lock-free, construction/destruction has to be synchronized. It uses a freelist for memory management, freed nodes are pushed to the freelist and not returned to the OS before the queue is destroyed.

Policies:

- boost::lockfree::fixed_sized, defaults to `boost::lockfree::fixed_sized<false>`
  Can be used to completely disable dynamic memory allocations during push in order to ensure lockfree behavior.
  If the data structure is configured as fixed-sized, the internal nodes are stored inside an array and they are addressed by array indexing. This limits the possible size of the queue to the number of elements that can be addressed by the index type (usually 2**16-2), but on platforms that lack double-width compare-and-exchange instructions, this is the best way to achieve lock-freedom.

- boost::lockfree::capacity, optional
  If this template argument is passed to the options, the size of the queue is set at compile-time.
  This option implies `fixed_sized<true>`

- boost::lockfree::allocator, defaults to `boost::lockfree::allocator<std::allocator<void>>`
  Specifies the allocator that is used for the internal freelist

Requirements:

- T must have a copy constructor

- T must have a trivial assignment operator

- T must have a trivial destructor

### `queue` public construct/copy/destruct

1.     queue(void);

   Construct queue.

2.     template<typename U>
         explicit queue(typename node_allocator::template rebind< U >::other const & alloc);

3.     explicit queue(allocator const & alloc);

4.     explicit queue(size_type n);

   Construct queue, allocate n nodes for the freelist.

5.     template<typename U>
         queue(size_type n,
               typename node_allocator::template rebind< U >::other const & alloc);

6.     ~queue(void);

   Destroys queue, free all nodes from freelist.

### `queue` private member functions

1.      BOOST_STATIC_ASSERT((boost::has_trivial_destructor< T >::value));

2.      BOOST_STATIC_ASSERT((boost::has_trivial_assign< T >::value));

3.     struct BOOST_ALIGNMENT(BOOST_LOCKFREE_CACHELINE_BYTES);

4.     void initialize(void);

5.      BOOST_DELETED_FUNCTION(queue(queue const &));

6.     bool is_lock_free(void) const;

   | Warning
   It only checks, if the queue head and tail nodes and the freelist can be modified in a lock-free manner. On most platforms, the whole implementation is lock-free, if this is true. Using c++0x-style atomics, there is no possibility to provide a completely accurate implementation, because one would need to test every internal node, which is impossible if further nodes will be allocated from the operating system.

   Returns: | true, if implementation is lock-free.

7.     void reserve(size_type n);

   Allocate n nodes for freelist

   | Note
   thread-safe, may block if memory allocator blocks

   Requires: | only valid if no capacity<> argument given

8.     void reserve_unsafe(size_type n);

   Allocate n nodes for freelist

   | Note
   not thread-safe, may block if memory allocator blocks

   Requires: | only valid if no capacity<> argument given

9.     bool empty(void) const;

   Check if the queue is empty

   | Note
   The result is only accurate, if no other thread modifies the queue. Therefore it is rarely practical to use this value in program logic.

   Returns: | true, if the queue is empty, false otherwise

10.     bool push(T const & t);

    Pushes object t to the queue.

    | Note
    Thread-safe. If internal memory pool is exhausted and the memory pool is not fixed-sized, a new node will be allocated from the OS. This may not be lock-free.

    Postconditions: | object will be pushed to the queue, if internal node can be allocated
    Returns: | true, if the push operation is successful.

11.     bool bounded_push(T const & t);

    Pushes object t to the queue.

    | Note
    Thread-safe and non-blocking. If internal memory pool is exhausted, operation will fail

    Postconditions: | object will be pushed to the queue, if internal node can be allocated
    Returns: | true, if the push operation is successful.
    Throws: | if memory allocator throws

12.     template<bool Bounded> bool do_push(T const & t);

### `queue` public member functions

1.     bool unsynchronized_push(T const & t);

   Pushes object t to the queue.

   | Note
   Not Thread-safe. If internal memory pool is exhausted and the memory pool is not fixed-sized, a new node will be allocated from the OS. This may not be lock-free.

   Postconditions: | object will be pushed to the queue, if internal node can be allocated
   Returns: | true, if the push operation is successful.
   Throws: | if memory allocator throws

2.     bool pop(T & ret);

   Pops object from queue.

   | Note
   Thread-safe and non-blocking

   Postconditions: | if pop operation is successful, object will be copied to ret.
   Returns: | true, if the pop operation is successful, false if queue was empty.

3.     template<typename U> bool pop(U & ret);

   Pops object from queue.

   | Note
   Thread-safe and non-blocking

   Requires: | type U must be constructible by T and copyable, or T must be convertible to U
   Postconditions: | if pop operation is successful, object will be copied to ret.
   Returns: | true, if the pop operation is successful, false if queue was empty.

4.     bool unsynchronized_pop(T & ret);

   Pops object from queue.

   | Note
   Not thread-safe, but non-blocking

   Postconditions: | if pop operation is successful, object will be copied to ret.
   Returns: | true, if the pop operation is successful, false if queue was empty.

5.     template<typename U> bool unsynchronized_pop(U & ret);

   Pops object from queue.

   | Note
   Not thread-safe, but non-blocking

   Requires: | type U must be constructible by T and copyable, or T must be convertible to U
   Postconditions: | if pop operation is successful, object will be copied to ret.
   Returns: | true, if the pop operation is successful, false if queue was empty.

6.     template<typename Functor> bool consume_one(Functor & f);

   consumes one element via a functor

   pops one element from the queue and applies the functor on this object

   | Note
   Thread-safe and non-blocking, if functor is thread-safe and non-blocking

   Returns: | true, if one element was consumed

7.     template<typename Functor> bool consume_one(Functor const & f);

   consumes one element via a functor

   pops one element from the queue and applies the functor on this object

   | Note
   Thread-safe and non-blocking, if functor is thread-safe and non-blocking

   Returns: | true, if one element was consumed

8.     template<typename Functor> size_t consume_all(Functor & f);

   consumes all elements via a functor

   sequentially pops all elements from the queue and applies the functor on each object

   | Note
   Thread-safe and non-blocking, if functor is thread-safe and non-blocking

   Returns: | number of elements that are consumed

9.     template<typename Functor> size_t consume_all(Functor const & f);

   consumes all elements via a functor

   sequentially pops all elements from the queue and applies the functor on each object

   | Note
   Thread-safe and non-blocking, if functor is thread-safe and non-blocking

   Returns: | number of elements that are consumed