[boost] bounded_blocking_queue, unbounded_blocking_queue

From: Peter Dimov (pdimov_at_[hidden])
Date: 2005-10-02 06:46:06

Hello,

I've been tasked to implement approximate C++ equivalents of

http://java.sun.com/j2se/1.5.0/docs/api/java/util/concurrent/ArrayBlockingQueue.html
http://java.sun.com/j2se/1.5.0/docs/api/java/util/concurrent/LinkedBlockingQueue.html
http://java.sun.com/j2se/1.5.0/docs/api/java/util/concurrent/ConcurrentHashMap.html

(and I'm generously allowed to use the Boost license.)

What I have so far is (synopsis):

template<class V> class bounded_blocking_queue
{
public:

    // exclusive access

    explicit bounded_blocking_queue( size_t n );
    ~bounded_blocking_queue();

    // queries

    size_t size() const; // aproximate queue size

    // non-blocking

    bool try_push( V const & v );
    bool try_pop( V & v );

    // blocking

    void push( V const & v );
    void pop( V & v );
};

with a "reference" two-lock implementation at

http://www.pdimov.com/cpp/bounded_blocking_queue.cpp

(with at least one race condition and at least two visibility bugs, but 
still...)

and:

template<class V> class unbounded_blocking_queue
{
    explicit unbounded_blocking_queue();
    ~unbounded_blocking_queue();

    // non-blocking

    void push( V const & v );
    bool try_pop( V & v );

    // blocking

    void pop( V & v );
};

with a two-lock implementation at

http://www.pdimov.com/cpp/unbounded_blocking_queue.cpp

I appreciate any comments on the interface, the implementation, or whether 
it'd be a good idea to include these components in Boost.Threads. Thanks in 
advance for any feedback.

Incidentally, I want to join the "catch(...) in thread_proxy is EVIL" camp. 
While developing these queues the catch(...) clause ate all access 
violations, transforming them into different access violations in totally 
unrelated parts of the code, making debugging a pain. I've removed the 
catch(...) in my local copy, and I think that we need to do the same in the 
CVS.

Oh, and comments about the interface of the concurrent hash map are very 
much appreciated; my current line of thinking is that the only operation 
that is allowed to invalidate should be rehash() and it'd be the user's 
responsibility to call it during "quiet" periods when no other thread is 
holding an iterator or is inserting/removing elements. But if you have a 
better idea, please let me know!

--
Peter Dimov
http://www.pdimov.com