Re[15]: Generators in C++, (a.k.a. foreach & iteartors)
От: siv Украина  
Дата: 29.05.08 16:37
Оценка:
siv>>Увы, не хватает "динамического goto" какого-нибудь:

CS>В GCC кстати такой goto есть. И там можно все это построить без наворотов со switch.

CS>Там можно взять адрес label и по нему перейти — goto *label.
Вах, не знал! Супер, может быть таки поюзаю тогда в реальном проекте под Вынь\Линукс...
Re[14]: Generators in C++, (a.k.a. foreach & iteartors)
От: anonim_44ax  
Дата: 30.05.08 07:20
Оценка:
Согласен, потому и говорю, что к сожалению сие компиллится под MS VS 7.1.3, хотя и не должно.
Re[23]: Generators in C++, (a.k.a. foreach & iteartors)
От: c-smile Канада http://terrainformatica.com
Дата: 30.05.08 15:38
Оценка: 34 (1)
Здравствуйте, remark, Вы писали:

CS>>В общем случае нужен stack on the heap.


CS>>Для C++ по всей видимости вполне себе будет достаточно объявления _generator как CRTP

CS>>структуры/шаблона плюс поле _generatror<NAME>* _stack.

CS>>Это точно будет работать — т.е. можно и рекурсивные вызовы делать (но только себя самого)


R>А можешь привести полную реализацию с примером использования. А то пока это всё не складывается в единое целое...


Вот generator с поддержкой restart — рекурсивный рестарт себя самого.

template<typename T>
  struct _generator
  {
    T* _stack;
    int _line;
    _generator():_stack(0), _line(-1) {}
    void _push() { T* n = new T; *n = *static_cast<T*>(this); _stack = n; }
    bool _pop() { if(!_stack) return false; T* t = _stack; *static_cast<T*>(this) = *_stack; t->_stack = 0; delete t; return true; }
    ~_generator() { while(_pop()); }
  };

  #define $generator(NAME) struct NAME : public _generator<NAME>

  #define $emit(T) bool operator()(T& _rv) { \
                      if(_line < 0) _line=0; \
                      $START: switch(_line) { case 0:;

  #define $stop  } _line = 0; if(_pop()) goto $START; return false; }

  #define $restart(WITH) { _push(); _stack->_line = __LINE__; _line=0; WITH; goto $START; case __LINE__:; }

  #define $yield(V)     \
          do {\
              _line=__LINE__;\
              _rv = (V); return true; case __LINE__:;\
          } while (0)


Используется так (обход дерева):

struct node
{
   int   value;
   node* next;
   node* kid;
   node(int v):value(v), next(0), kid(0) {}
   node* foster( node* child ) { child->next = kid; kid = child; return child; }
};

$generator(scan)
{
  node* n;
  scan( node* root = 0 ): n(root) {}

  $emit(int)
    for(;n; n = n->next)
    {
      $yield(n->value);
      if( n->kid )
        $restart( n = n->kid );
    }
  $stop
};

int main(int argc, char* argv[])
{
  node * root = new node(0);
  root->foster(new node(1));
  root->foster(new node(2));
  root->foster(new node(3));
  root->foster(new node(4));
  node * child5 = root->foster(new node(5));
  root->foster(new node(6));
  root->foster(new node(7));
  root->foster(new node(8));
  root->foster(new node(9));

  child5->foster(new node(50));
  child5->foster(new node(51));
  child5->foster(new node(52));
  child5->foster(new node(53));

  scan g(root);
  for(int n; g(n);)
      printf("n = %d\n",n);
    return 0;
}


Усовершенствования возможны.
Re[24]: Generators in C++, (a.k.a. foreach & iteartors)
От: remark Россия http://www.1024cores.net/
Дата: 30.05.08 15:48
Оценка:
Здравствуйте, c-smile, Вы писали:

CS>
CS>$generator(scan)
CS>{
CS>  node* n;
CS>  scan( node* root = 0 ): n(root) {}
CS>  $emit(int)
CS>    for(;n; n = n->next)
CS>    {
CS>      $yield(n->value);
CS>      if( n->kid )
CS>        $restart( n = n->kid );
CS>    }
CS>  $stop
CS>};
CS>



Выглядит интересно... Надо помедитировать...



1024cores &mdash; all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
Re[15]: Generators in C++, (a.k.a. foreach & iteartors)
От: siv Украина  
Дата: 30.05.08 20:02
Оценка: 36 (1)
siv>>Увы, не хватает "динамического goto" какого-нибудь:
CS>В GCC кстати такой goto есть. И там можно все это построить без наворотов со switch.
CS>Там можно взять адрес label и по нему перейти — goto *label.
Да, с ним всё просто и красиво. Вот, чуточку доработал один из твоих вариантов на предмет VC/G++ и поддержки switch/case :

#ifndef __generator_h_
#define __generator_h_

#include <boost/preprocessor/cat.hpp>

struct _generator
{
    void * _addr;
    _generator():_addr(0) {}
};

//------------------------------------------------------------------------------
#define $generator(NAME) class NAME : protected _generator

//.......
/// \note NB: Remember! The values of local varaibles are not preserved between
///       generator() invocation. Use them with precaution or use class members.
#define $emit(T)    bool operator()(T& _rv)              \
                    {                                    \
                      GOTO_GENERATOR_LABEL               \
                      {
//.......
#define $yield(V)       do {                             \
                          _rv = (V);                     \
                          SAVE_ADDR;                     \
                          return true;                   \
                      GENERATOR_LABEL:;                  \
                        } while (0);
//.......
#define $stop         }                                  \
                     _addr = 0;                          \
                     return false;                       \
                   }

//------------------------------------------------------------------------------
/// auxiliary macroses
#define GENERATOR_LABEL BOOST_PP_CAT(generator_label_,__LINE__)

#if defined(_MSC_VER)
# define  GOTO_GENERATOR_LABEL                           \
    if ( _addr )                                         \
    {                                                    \
      void * addr = _addr;                               \
      __asm                                              \
      {                                                  \
        __asm jmp addr                                   \
      }                                                  \
    }

# define SAVE_ADDR \
    {                                                    \
      void * pAddr = &_addr;                             \
      __asm                                              \
      {                                                  \
        __asm mov ebx, dword ptr [pAddr]                 \
        __asm mov eax, OFFSET GENERATOR_LABEL            \
        __asm mov dword ptr [ebx], eax                   \
      }                                                  \
    }

#elif defined(__GNUC__)
# define  GOTO_GENERATOR_LABEL                           \
    if ( _addr )                                         \
    {                                                    \
      void * addr = _addr;                               \
      goto *addr;                                        \
    }

# define SAVE_ADDR                                       \
    {                                                    \
      void * addr = &&GENERATOR_LABEL;                   \
      _addr = addr;                                      \
    }
#else
# error You have to check a support of "goto *label" on your platform or implement it yourself.
#endif

#endif // __generator_h_

//=============================================================================
#include <stdio.h>

$generator(desc)
{
  int m_i;

public:
  desc( int start=-1 ) : m_i(start) {}

  $emit(int) 
  {
    for(; m_i >= 0; --m_i)
    {
      switch ( m_i )
      {
        case 9 : case 7 :
          $yield( m_i + 100 );
        break;

        case 5:
          $yield( m_i + 100000 );
        break;
      
        default:
          $yield( m_i );
      }
      $yield( m_i );
    }
  }
  $stop  
};


int main(int argc, char* argv[])
{
  desc gen( 11 );
  int i;
  while(gen(i))
  {    
    printf("got number %d\n", i);
  }
}
Re[10]: Generators in C++, (a.k.a. foreach & iteartors)
От: remark Россия http://www.1024cores.net/
Дата: 01.06.08 17:24
Оценка:
Здравствуйте, remark, Вы писали:

R>Там что-то типа такого, что пользовательский код анализируется специальным компилятором на потребление стека.

R>На стандартные библиотечные функции они рассчитывают, что будут специальные аннотации по поводу максимального потребления стека.
R>А для известного кода используются специальные большие стеки, которые динамически подцепляются и отцепляются.

------/\/\
---для неизвестного


1024cores &mdash; all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
Re: Generators in C++, (a.k.a. foreach & iteartors)
От: c-smile Канада http://terrainformatica.com
Дата: 21.09.08 23:21
Оценка:
Здравствуйте, c-smile, Вы писали:

Добавил статью на codeproject:

http://www.codeproject.com/KB/cpp/cpp_generators.aspx
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.