9

I have a container (C++) on which I need to operate in two ways, from different threads: 1) Add and remove elements, and 2) iterate through its members. Clearly, remove element while iteration is happening = disaster. The code looks something like this:

class A
{
public:
   ...
   void AddItem(const T& item, int index) { /*Put item into my_stuff at index*/ }
   void RemoveItem(const T& item) { /*Take item out of m_stuff*/ }
   const list<T>& MyStuff() { return my_stuff; } //*Hate* this, but see class C
private:
   Mutex mutex; //Goes in the *Item methods, but is largely worthless in MyStuff()
   list<T> my_stuff; //Just as well a vector or deque
};
extern A a; //defined in the .cpp file

class B
{
   ...
   void SomeFunction() { ... a.RemoveItem(item); }
};

class C
{
   ...
   void IterateOverStuff()
   {
      const list<T>& my_stuff(a.MyStuff());
      for (list<T>::const_iterator it=my_stuff.begin(); it!=my_stuff.end(); ++it)
      {
          ...
      }
   }
};

Again, B::SomeFunction() and C::IterateOverStuff() are getting called asynchronously. What's a data structure I can use to ensure that during the iteration, my_stuff is 'protected' from add or remove operations?

Evan Teran
  • 87,561
  • 32
  • 179
  • 238
Matt Phillips
  • 9,465
  • 8
  • 44
  • 75

3 Answers3

15

sounds like a reader/writer lock is needed. Basically, the idea is that you may have 1 or more readers OR a single writer. Never can you have a read and write lock at the same time.

EDIT: An example of usage which I think fits your design involves making a small change. Add an "iterate" function to the class which owns the list and make it templated so you can pass a function/functor to define what to do for each node. Something like this (quick and dirty pseudo code, but you get the point...):

class A {
public:
    ...
    void AddItem(const T& item, int index) {
        rwlock.lock_write();
        // add the item
        rwlock.unlock_write();
    }

    void RemoveItem(const T& item) {
        rwlock.lock_write();
        // remove the item
        rwlock.unlock_write();
    }

    template <class P>
    void iterate_list(P pred) {
        rwlock.lock_read();
        std::for_each(my_stuff.begin(), my_stuff.end(), pred);
        rwlock.unlock_read();
    }

private:
    rwlock_t rwlock;
    list<T> my_stuff; //Just as well a vector or deque
};


extern A a; //defined in the .cpp file

class B {
    ...
    void SomeFunction() { ... a.RemoveItem(item); }
};

class C {
    ...

    void read_node(const T &element) { ... }

    void IterateOverStuff() {
        a.iterate_list(boost::bind(&C::read_node, this));
   }
};

Another Option would be to make the reader/writer lock publicly accessible and have the caller responsible for correctly using the lock. But that's more error prone.

Evan Teran
  • 87,561
  • 32
  • 179
  • 238
  • 5
    +1. Boost has an implementation of these: http://www.boost.org/doc/libs/1_46_1/doc/html/thread/synchronization.html#thread.synchronization.mutex_types.shared_mutex – Fred Foo Apr 14 '11 at 18:08
  • @Evan, @larsmans I don't quite understand--where would I put it? Just define it globally and put it in C::Iterate... as well as the A methods? How does it 'know' whether read or write is being performed – Matt Phillips Apr 14 '11 at 18:16
  • @Matt: it likely should have the same scope/ownership as the list itself. If the list is global, then the lock should be global. If some object owns the list, then that same object should own the lock. – Evan Teran Apr 14 '11 at 18:20
  • @Evan Your solution in the edit would be great except for cases, like mine unfortunately, where pred would have to be something very complicated (when there's lots of things happening between the brackets in the for loop). Specifically where pred is accessing the private data members of C. For this I'd have to globalize pred and pass it an instance of class C (and probably make it a friend), is that right? So in this case would you recommend your second option? – Matt Phillips Apr 14 '11 at 18:45
  • 1
    @Matt: no, in my example, I've used boost bind to pass a **member function** of C as the Pred. It will be called with the correct `this` and everything. – Evan Teran Apr 14 '11 at 19:33
  • @Evan Ok great that sounds fantastic, I've never used Boost before but maybe now is the time to start. Last question, then: Does linking to Boost have any hidden costs, beyond the obvious extra size of my program? Am I 'getting myself into' anything with Boost I might regret later? – Matt Phillips Apr 15 '11 at 00:03
  • Most of boost is "header only" making it so using one part doesn't mean you have to link to a huge library. – Evan Teran Apr 15 '11 at 02:59
5

IMHO it is a mistake to have a private mutex in a data structure class and then write the class methods so that the whole thing is thread safe no matter what the code that calls the methods does. The complexity that is required to do this completely and perfectly is way over the top.

The simpler way is to have a public ( or global ) mutex which the calling code is responsible for locking when it needs to access the data.

Here is my blog article on this subject.

ravenspoint
  • 19,093
  • 6
  • 57
  • 103
3

When you return the list, return it enclosed in a class that locks/unlocks the mutex in its constructor/destructor. Something along the lines of

class LockedIterable {
public:
  LockedIterable(const list<T> &l, Mutex &mutex) : list_(l), mutex_(mutex)
  {lock(mutex);}
  LockedIterable(const LockedIterable &other) : list_(other.list_), mutex_(other.mutex_) {
    // may be tricky - may be wrap mutex_/list_ in a separate structure and manage it via shared_ptr?
  }
  ~LockedIterable(){unlock(mutex);}
  list<T>::iterator begin(){return list_.begin();}
  list<T>::iterator end(){return list_.end();}
private:
  list<T> &list_;
  Mutex &mutex_;
};

class A {
  ...
  LockedIterable MyStuff() { return LockedIterable(my_stuff, mutex); }  
};

The tricky part is writing copy constructor so that your mutex does not have to be recursive. Or just use auto_ptr.

Oh, and reader/writer lock is indeed a better solution than mutex here.

  • Thanks, I had thought about something along these lines. The only thing is that this requires me to then destroy the LockedIterable after the iteration is complete. If there's a lot more happening in C::IterateOverStuff after the iteration is complete, then simply waiting for it to go out of scope isn't enough... so I guess new/delete is the option here? Lastly isn't the copy structure trivial, since LockedIterable has no data members? – Matt Phillips Apr 14 '11 at 18:30
  • I'd rather use an extra block {LockedIterable l = ...;for(){...}}. This manages the scope for you. As to having no data members - I over-simplified my code - it has data members list_ and mutex_. Copy is non-trivial if you need don't want to keep locking/unlocking the mutex and/or don't want to lock non-recursive mutex twice. –  Apr 15 '11 at 18:05