"vicente.botet" <vicente.botet@wanadoo.fr> writes:
there was a long discusion about the complexity of wait_for_any some mounts ago. If I understood well the probleme was in the future_waiter::wait
unsigned wait() { all_futures_lock lk(futures); for(;;) { for(unsigned i=0;i<futures.size();++i) // O(N) { if(futures[i].future->done) { return futures[i].index; } } cv.wait(lk); } }
Yes.
What we need is a synchonization structure that returns a user specific data (in this case the index). So we can replace by
unsigned wait() { all_futures_lock lk(futures); return cv_with_value.wait(lk); }
I'm not sure. I think we're better off with a simple mutex/value/cond-var triplet in the waiter. We then don't need the "all_futures_lock". unsigned wait() { boost::unique_lock<boost::mutex> lk(mut); while(ready_future_index<0) { cv.wait(lk); } return ready_future_index; }
We need to pass to the register_external_waiter the specific data, in this case the index
and the mutex => better off as a struct of some kind. struct ready_future_value { boost::mutex mut; int ready_future_index; boost::condition_variable cv; void notify_ready(unsigned index) { boost::lock_guard<boost::mutex> lk(mut); if(ready_future_index<0) { ready_future_index=index; cv.notify_all(); } } } ready_value;
template<typename F> void add(F& f) { if(f.future) { futures.push_back(registered_waiter(f.future, // f.future->register_external_waiter(cv,future_count,mut),future_count));
f.future->register_external_waiter(&ready_value,future_count),future_count));
} ++future_count; }
So the list of waiters is now
// typedef std::list<std::pair<condition_variable_any_with_value<unsigned>*,
typedef std::list<std::pair<ready_future_value*,
unsigned> > waiter_list; waiter_list::iterator register_external_waiter( // condition_variable_any_with_value<unsigned>& cv_with_value,
ready_future_value& ready_value,
unsigned indx) { boost::unique_lock<boost::mutex> lock(mutex); do_callback(lock); return external_waiters.insert(external_waiters.end(),std::make_pair(&cv, indx)); }
The notification to the waiters will no use the new notify_all interface passing as parameter the index of the future relative to the condition_variable.
void mark_finished_internal() { done=true; waiters.notify_all(); for(waiter_list::const_iterator it=external_waiters.begin(), end=external_waiters.end();it!=end;++it) {
(it->first)->notify_ready(it->second);
} }
It turns out that my ready_future_value struct isn't too far from your cv_with_value, so I like the idea, but not the name. (I don't like ready_future_value either for that matter). Anthony -- Anthony Williams | Just Software Solutions Ltd Custom Software Development | http://www.justsoftwaresolutions.co.uk Registered in England, Company Number 5478976. Registered Office: 15 Carrallack Mews, St Just, Cornwall, TR19 7UL