6

Possible Duplicate:
Is there a production ready lock-free queue or hash implementation in C++

I'm looking for implementations of lock-free containers:

  • Queue
  • Stack
  • Hash Map
  • etc...

How about blocking containers:

  • Blocking Queue
  • Blocking Stack

Are there any good libraries out there? I would like to refrain from writing these data structures... I would much rather use something that has been tested by the community.

Community
  • 1
  • 1
Kiril
  • 39,672
  • 31
  • 167
  • 226
  • 1
    if you use the word "blocking", it isn't lock-free... – Evan Teran May 15 '10 at 17:51
  • @Evan, I corrected my question, but there should be a way to make a lock-free blocking queue using CAS and something like a C++ equivalent ManualResetEvent... – Kiril May 15 '10 at 18:41
  • @Link: CAS cannot be used to implement blocking. At best, you could use spinlocks (which would be terrible for this type of thing), but you need the assistance of the scheduler (mutex/semaphore/etc) to actually block. – Evan Teran May 15 '10 at 18:46
  • @Evan, right... CAS will not be used to implement blocking, but a C++ equivalent of the ManualResetEvent could be used for blocking, while CAS would be used for insertion or removal of elements. – Kiril May 15 '10 at 19:08

2 Answers2

4

Have a look at the container classes of Intel TBB. The reference says:

The container classes permit multiple threads to simultaneously invoke certain methods on the same container.

Karl von Moor
  • 8,484
  • 4
  • 40
  • 52
3

Herb Sutter did a few articles in his Effective Concurrency series in Dr. Dobbs Journal. The two articles you'll probably want to read right away are:

The rest of the series is definitely worth a read as well.

greyfade
  • 24,948
  • 7
  • 64
  • 80
  • thanks... I'm aware that there are articles describing how to write these containers, but I would prefer to use a tried and tested library rather than write the containers myself. – Kiril May 15 '10 at 19:08
  • @Lirik: The main reason I link to them is because Herb does a *very* deep discussion on how and why it works, and what pitfalls there are in writing it. He also has complete, working examples which I've copied and used verbatim with success. (Although they expect a C++0x-compatible compiler or an equivalent `atomic<>` type.) – greyfade May 16 '10 at 00:42