4
\$\begingroup\$

C++11's range-based loops allow convenient and easy iteration over containers, but what about more complicated iterations such as tree traversal? Usually this involves a lot of boilerplate code and potential errors since we need to write complicated iterator classes as well as some wrapper class proving begin() and end() methods. I simplify process this by implementing a generator class using threads and exceptions that mimics Python's yield syntax.

Very simple example:

Generator<int> range(int max){
  return Generator<int>([=](Yield<int> &yield){
    for(int i = 0;i<max;++i) yield(i);
  });
}

int main(){
  for(int i:range(10)) std::cout << i << std::endl;
}

Is the following implementation correct and safe? Are there better ways to do this (besides switching to more suitable concepts such as visitors)? Any comments are welcome.

#include <thread>
#include <future>
#include <memory>
#include <exception>
#include <iterator>

template <class T> class Generator;

template <class T> class Yield{

  enum State{ WAITING,READY,TERMINATED,FINISHED } state = WAITING;

  friend Generator<T>;
  std::promise<T> promise;
  std::mutex mutex;
  std::condition_variable ready_wait;

  struct FinishedException:public std::exception{ };
  struct TerminatedException:public std::exception{ };

  void terminate(){
    std::lock_guard<std::mutex> guard(mutex);
    if(state != FINISHED){
      state = TERMINATED;
      ready_wait.notify_one();
    }
  }

  void finish(){
    std::unique_lock<std::mutex> lock(mutex);
    while(state == WAITING) ready_wait.wait(lock);
    if(state == TERMINATED) return;
    state = FINISHED;
    throw FinishedException();
  }

  template <class E> void set_exception(E e){
    std::unique_lock<std::mutex> lock(mutex);
    while(state == WAITING) ready_wait.wait(lock);
    if(state == TERMINATED) return;
    promise.set_exception(e);
  }

  std::future<T> get_future(){
    std::lock_guard<std::mutex> guard(mutex);
    promise = std::promise<T>();
    ready_wait.notify_one();
    state = READY;
    return promise.get_future();
  }

  Yield(){ }

  public:
  void operator()(const T &value){
    std::unique_lock<std::mutex> lock(mutex);
    while(state == WAITING) ready_wait.wait(lock);
    if(state == TERMINATED) throw TerminatedException();
    promise.set_value(value);
    state = WAITING;
  }

};

template <class T> class Generator{
  std::function<void(Yield<T> &)> generator_function;

  public:
  Generator(const std::function<void(Yield<T> &)> &gf):generator_function(gf){ }

  class const_iterator:public std::iterator<std::input_iterator_tag,T>{
    friend Generator;

    struct Data{
      Yield<T> yield;
      T current_value;
      std::thread thread;
      ~Data(){ yield.terminate(); thread.join(); }
    };

    std::unique_ptr<Data> data;

    public:
    const T &operator*(){ return data->current_value; }
    const T *operator->(){ return &data->current_value; }

    void operator++(){
      try{
        data->current_value = data->yield.get_future().get();
      }
      catch(typename Yield<T>::FinishedException){
        data.reset();
      }
    }

    bool operator!=(const const_iterator &other){ return data != other.data; }
  };

  const_iterator begin()const{
    const_iterator it;
    it.data.reset(new typename const_iterator::Data);
    auto data = it.data.get();

    data->thread = std::thread([this,data](){
      try{
        generator_function(data->yield);
        data->yield.finish();
      }
      catch(typename Yield<T>::TerminatedException){

      }
      catch(...){
        data->yield.set_exception(std::current_exception());
      }
    });

    ++it;

    return it;
  }

  const_iterator end()const{
    return const_iterator();
  }

};

The full source and more examples are located here.

Edit 1: fixed a bug where yield.set_exception() could cause a promise_already_satisfied exception

\$\endgroup\$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.