Re: [boost] Futures Review - wait_for_any complexity

Subject: Re: [boost] Futures Review - wait_for_any complexity
From: vicente.botet (vicente.botet_at_[hidden])
Date: 2009-01-16 02:40:41

Hi,

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);
                }
            }

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);
            }

We need to pass to the register_external_waiter the specific data, in this case the index

            template<typename F>
            void add(F& f)
            {
                if(f.future)
                {
                    futures.push_back(registered_waiter(f.future,
                    f.future->register_external_waiter(cv_with_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>*, 
                                        unsigned> 
                                    > waiter_list;
            waiter_list::iterator register_external_waiter(
                        condition_variable_any_with_value<unsigned>& cv_with_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_all(it->second);
                }
            }

The interface of the condition_variable_any_with_value is the same as condition_variable_any but

template <typename T>
class condition_variable_any_with_value {
    // add a get function
    T get(); // gets the value stored when notify called
    // change the interface for the notify functions
    bool notify_one(T val);
    bool notify_all(T val);
};

What do you think?