iterators

Discussion in 'C Programming' started by Philip Herron, Jul 8, 2013.

  1. I've been following http://www.chiark.greenend.org.uk/~sgtatham/coroutines.html

    Trying to understand iterators and came up with this:

    #include <stdio.h>
    #include <stdlib.h>

    enum STATUS {
    YIELD_OK,
    YIELD_EOF,
    };

    enum STATUS yield (void ** context/*, int * retval*/)
    {
    struct ctx {
    int line;
    int i;
    };
    struct ctx * x = (struct ctx *) *context;

    if (!x)
    {
    x = *context = malloc (sizeof (struct ctx));
    x->line = 0;
    }

    if (x)
    switch (x->line) { case 0:;
    for (x->i = 0; x->i < 10; x->i++)
    {
    do {/*
    int it = x->i;
    *retval = it;*/
    x->line = __LINE__; return YIELD_OK; case __LINE__:;
    } while (0);
    }
    }

    free (*context);
    *context = 0;
    //*retval = -1;
    return YIELD_EOF;
    }

    int main (int argc, char ** argv)
    {
    int val = 0;
    int co = 0;
    enum STATUS s;
    for (s = yield ((void **) &co/*, &val*/);
    s != YIELD_EOF;
    s = yield ((void **) &co/*, &val*/))
    printf ("iteration %i\n", val);

    return 0;
    }

    I set val = 0 and don't touch it and the loop prints:

    10-4-5-68:workspace redbrain$ gcc iterator.c -g -O0 -Wall
    10-4-5-68:workspace redbrain$ ./a.out
    iteration 32673
    iteration 32673
    iteration 32673
    iteration 32673
    iteration 32673
    iteration 32673
    iteration 32673
    iteration 32673
    iteration 32673
    iteration 32673

    I think the malloc in the callee is doing something funny but not really sure whats going on i know its a fairly big test case but any pointers would be great.

    Thanks

    --Phil
     
    Philip Herron, Jul 8, 2013
    #1
    1. Advertising

  2. *retval = it is commented out, so you are just printing whatever garbage value
    your variable was initialised to on the stack.
    Switch labels within non-nested curly brackets are in fact legal C, but they
    shouldn't be. It's just a quirk of the language which was probably put in
    to make compilers easier to write. It's completely unacceptable to play
    games like that with flow control.
     
    Malcolm McLean, Jul 8, 2013
    #2
    1. Advertising

  3. Philip Herron

    James Kuyper Guest

    On 07/08/2013 12:56 PM, Malcolm McLean wrote:
    > *retval = it is commented out, so you are just printing whatever garbage value
    > your variable was initialised to on the stack.


    Every use of retval in that code is also commented out, so while that
    program has many problems, this isn't one of them.
     
    James Kuyper, Jul 8, 2013
    #3
  4. Philip Herron

    James Kuyper Guest

    On 07/08/2013 12:40 PM, Philip Herron wrote:
    > I've been following http://www.chiark.greenend.org.uk/~sgtatham/coroutines.html
    >
    > Trying to understand iterators and came up with this:
    >
    > #include <stdio.h>
    > #include <stdlib.h>
    >
    > enum STATUS {
    > YIELD_OK,
    > YIELD_EOF,
    > };
    >
    > enum STATUS yield (void ** context/*, int * retval*/)
    > {
    > struct ctx {
    > int line;
    > int i;
    > };
    > struct ctx * x = (struct ctx *) *context;
    >
    > if (!x)
    > {
    > x = *context = malloc (sizeof (struct ctx));


    In this context, "sizeof *x" is both simpler than sizeof(struct ctx),
    and safer in case you ever decide to change the type of *x.

    malloc() can fail. Your code fails to check for that possibility before
    attempting to dereference x on the next line. If malloc() did fail, then
    the following line has undefined behavior:

    > x->line = 0;


    However, on most modern systems a single allocation of this size is
    extremely unlikely to fail, so while you should fix that defect, it's
    probably not what's actually making your program fail.

    > }
    >
    > if (x)
    > switch (x->line) { case 0:;
    > for (x->i = 0; x->i < 10; x->i++)
    > {
    > do {/*
    > int it = x->i;
    > *retval = it;*/
    > x->line = __LINE__; return YIELD_OK; case __LINE__:;
    > } while (0);
    > }
    > }
    >
    > free (*context);
    > *context = 0;
    > //*retval = -1;
    > return YIELD_EOF;
    > }
    >
    > int main (int argc, char ** argv)
    > {
    > int val = 0;
    > int co = 0;
    > enum STATUS s;
    > for (s = yield ((void **) &co/*, &val*/);


    You've converted &co, which has the type int*, to void**. The result of
    that conversion is undefined unless &co is correctly aligned to be
    converted to a void**.

    yield() converts *context to (struct ctx*). That conversion has
    undefined behavior if &co is not correctly aligned for a struct ctx*.

    yield() attempts to dereference x, on the line which says x->line. That
    line has undefined behavior because x was derived from &co, and co
    doesn't have the type "struct ctx"; co.line doesn't even exist.

    Finally, yield() attempts to free(*context). Since &co is a pointer that
    was not the returned by a previous call to malloc(), calloc(), or
    realloc(), attempting to free() it has undefined behavior.

    You could fix all of the above problems by defining

    struct ctx context * = malloc(sizeof *context);

    Handle the possibility that context == NULL, and if it does not, set
    context->line to 0, and then call yield(&context).
    However, it's simpler to just write

    struct ctx context * = NULL;

    and let yield(&context) itself handle those details.

    > s != YIELD_EOF;
    > s = yield ((void **) &co/*, &val*/))


    The above for() statement is equivalent to the simpler

    while(yield(&co) != YIELD_EOF)

    > printf ("iteration %i\n", val);


    Since you've commented out the code that passes &val to yield(), there's
    not much point in printing out it's value. If it weren't for the
    undefined behavior of the rest of your code, val would be guaranteed to
    have retained it's initial value of 0.

    > return 0;
    > }
     
    James Kuyper, Jul 8, 2013
    #4
  5. Philip Herron

    Eric Sosman Guest

    On 7/8/2013 12:40 PM, Philip Herron wrote:
    > I've been following http://www.chiark.greenend.org.uk/~sgtatham/coroutines.html
    >
    > Trying to understand iterators and came up with this:
    > [...]
    > enum STATUS yield (void ** context/*, int * retval*/)


    Okay, yield() has one parameter: A pointer that points
    to another pointer, whose type is `void*'.

    > [...]
    > x = *context = malloc (sizeof (struct ctx));


    Here, yield() stores the `void*' value it gets from
    malloc(), putting it in the place where its parameter points.

    > [...]
    > int val = 0;
    > int co = 0;
    > enum STATUS s;
    > for (s = yield ((void **) &co/*, &val*/);


    Okay, here you call yield() and supply one argument:
    It's a pointer, and its type has been coerced to `void**'
    as required, but does it point at a `void*'? No, it does
    not: It points at an `int'.

    Internally yield() will try to store an actual `void*'
    value in the destination the argument points to. That target
    is of the wrong type, so the behavior is undefined. In theory
    absolutely anything could happen thereafter; the saying "Demons
    will fly out of your nose" used to be a popular description.

    At a guess, what *may* be happening goes something like:

    - The code inside yield() stores the `void*' value in memory,
    starting at the indicated target, and

    - You're using a system where `void*' is bigger than `int'
    (quite likely a system with 32-bit integers and 64-bit
    pointers), so

    - Only part (probably half) of the `void*' value fits in
    the target `int', and the rest slops over whatever happens
    to be nearby, and

    - The thing immediately after `co' in memory happens to
    be `val', so

    - Part of the `void*' value clobbers `val'.

    > I set val = 0 and don't touch it and the loop prints:
    >[...]


    Sorry; C can't be answerable for what nasal demons print.

    --
    Eric Sosman
    d
     
    Eric Sosman, Jul 8, 2013
    #5
  6. Philip Herron

    Siri Cruise Guest

    In article <>,
    Philip Herron <> wrote:


    > int main (int argc, char ** argv)
    > {
    > int val = 0;
    > int co = 0;


    You're going to end up storing a pointer in an int which isn't guarenteed to
    work. You can test with

    if (sizeof co<sizeof(void*)) puts("int too small");

    Alternatively do

    void *co = 0;
    or
    intptr_t co = 0;
    --
    Mommy is giving the world some kind of bird.
    :-<> Siri Seal of Disavowal #000-001. Disavowed. Denied. Deleted.
    NSA CIA Constitution patriot terrorism freedom Snowden Paid Maternity Leave
     
    Siri Cruise, Jul 8, 2013
    #6
  7. On Monday, 8 July 2013 19:23:17 UTC+1, Siri Cruise wrote:
    > In article <>,
    >
    > Philip Herron <> wrote:
    >
    >
    >
    >
    >
    > > int main (int argc, char ** argv)

    >
    > > {

    >
    > > int val = 0;

    >
    > > int co = 0;

    >
    >
    >
    > You're going to end up storing a pointer in an int which isn't guarenteedto
    >
    > work. You can test with
    >
    >
    >
    > if (sizeof co<sizeof(void*)) puts("int too small");
    >
    >
    >
    > Alternatively do
    >
    >
    >
    > void *co = 0;
    >
    > or
    >
    > intptr_t co = 0;
    >
    > --
    >
    > Mommy is giving the world some kind of bird.
    >
    > :-<> Siri Seal of Disavowal #000-001. Disavowed. Denied. Deleted.
    >
    > NSA CIA Constitution patriot terrorism freedom Snowden Paid Maternity Leave


    Yeah i commented out the retval stuff since it was making it segv for me and i couldnt understand why. Just never seen case statements like this before and i really dont like it but i wanted to understand more thanks for the pointers i think i wont use this again for actual code lol.

    --Phil
     
    Philip Herron, Jul 8, 2013
    #7
  8. On Monday, 8 July 2013 21:08:50 UTC+1, Philip Herron wrote:
    > On Monday, 8 July 2013 19:23:17 UTC+1, Siri Cruise wrote:
    >
    > > In article <>,

    >
    > >

    >
    > > Philip Herron <> wrote:

    >
    > >

    >
    > >

    >
    > >

    >
    > >

    >
    > >

    >
    > > > int main (int argc, char ** argv)

    >
    > >

    >
    > > > {

    >
    > >

    >
    > > > int val = 0;

    >
    > >

    >
    > > > int co = 0;

    >
    > >

    >
    > >

    >
    > >

    >
    > > You're going to end up storing a pointer in an int which isn't guarenteed to

    >
    > >

    >
    > > work. You can test with

    >
    > >

    >
    > >

    >
    > >

    >
    > > if (sizeof co<sizeof(void*)) puts("int too small");

    >
    > >

    >
    > >

    >
    > >

    >
    > > Alternatively do

    >
    > >

    >
    > >

    >
    > >

    >
    > > void *co = 0;

    >
    > >

    >
    > > or

    >
    > >

    >
    > > intptr_t co = 0;

    >
    > >

    >
    > > --

    >
    > >

    >
    > > Mommy is giving the world some kind of bird.

    >
    > >

    >
    > > :-<> Siri Seal of Disavowal #000-001. Disavowed. Denied. Deleted.

    >
    > >

    >
    > > NSA CIA Constitution patriot terrorism freedom Snowden Paid Maternity Leave

    >
    >
    >
    > Yeah i commented out the retval stuff since it was making it segv for me and i couldnt understand why. Just never seen case statements like this before and i really dont like it but i wanted to understand more thanks for the pointers i think i wont use this again for actual code lol.
    >
    >
    >
    > --Phil


    Spent some time there and came up with this:

    #include <stdio.h>
    #include <stdlib.h>
    #include <assert.h>

    enum STATUS {
    YIELD_NEW,
    YIELD_CONT,
    YIELD_OK,
    YIELD_EOF,
    };

    struct iterctx {
    int it;
    enum STATUS is;
    };
    struct myObject {
    int length;
    int * array;
    };

    enum STATUS yield (int * retval, struct myObject * o,
    struct iterctx * itx)
    {
    if (itx->is == YIELD_NEW)
    itx->it = 0;

    while (itx->it < o->length)
    {
    *retval = o->array [itx->it];
    itx->it ++;
    return YIELD_OK;
    }
    return YIELD_EOF;
    }

    int main (int argc, char ** argv)
    {
    struct myObject obj;
    obj.length = 10;
    int array[obj.length];

    int i;
    for (i = 0; i < obj.length; ++i)
    array = i + 1;

    obj.array = array;
    struct iterctx itx;
    itx.is = YIELD_NEW;

    int val = 0;
    while (yield (&val, &obj, &itx) != YIELD_EOF)
    {
    printf ("val = %i!\n", val);
    itx.is = YIELD_CONT;
    }

    return 0;
    }

    Now sure how reentrant this might be or not. i dont feel that condident in it but if its wrong could you point me where i should read up on more to implement some kind of co-routines.

    Thanks again
     
    Philip Herron, Jul 8, 2013
    #8
  9. Philip Herron

    Eric Sosman Guest

    On 7/8/2013 5:00 PM, Philip Herron wrote:
    > On Monday, 8 July 2013 21:08:50 UTC+1, Philip Herron wrote:
    >> On Monday, 8 July 2013 19:23:17 UTC+1, Siri Cruise wrote:
    >>
    >>> In article <>,

    >>
    >>>

    >>
    >>> Philip Herron <> wrote:

    >>
    >>>

    >>
    >>>

    >>
    >>>

    >>
    >>>

    >>
    >>>

    >>
    >>>> int main (int argc, char ** argv)

    >>
    >>>

    >>
    >>>> {

    >>
    >>>

    >>
    >>>> int val = 0;

    >>
    >>>

    >>
    >>>> int co = 0;

    >>
    >>>

    >>
    >>>

    >>
    >>>

    >>
    >>> You're going to end up storing a pointer in an int which isn't guarenteed to

    >>
    >>>

    >>
    >>> work. You can test with

    >>
    >>>

    >>
    >>>

    >>
    >>>

    >>
    >>> if (sizeof co<sizeof(void*)) puts("int too small");

    >>
    >>>

    >>
    >>>

    >>
    >>>

    >>
    >>> Alternatively do

    >>
    >>>

    >>
    >>>

    >>
    >>>

    >>
    >>> void *co = 0;

    >>
    >>>

    >>
    >>> or

    >>
    >>>

    >>
    >>> intptr_t co = 0;

    >>
    >>>

    >>
    >>> --

    >>
    >>>

    >>
    >>> Mommy is giving the world some kind of bird.

    >>
    >>>

    >>
    >>> :-<> Siri Seal of Disavowal #000-001. Disavowed. Denied. Deleted.

    >>
    >>>

    >>
    >>> NSA CIA Constitution patriot terrorism freedom Snowden Paid Maternity Leave

    >>
    >>
    >>
    >> Yeah i commented out the retval stuff since it was making it segv for me and i couldnt understand why. Just never seen case statements like this before and i really dont like it but i wanted to understand more thanks for the pointers i think i wont use this again for actual code lol.
    >>
    >>
    >>
    >> --Phil

    >
    > Spent some time there and came up with this:
    >
    > #include <stdio.h>
    > #include <stdlib.h>
    > #include <assert.h>
    >
    > enum STATUS {
    > YIELD_NEW,
    > YIELD_CONT,
    > YIELD_OK,
    > YIELD_EOF,
    > };
    >
    > struct iterctx {
    > int it;
    > enum STATUS is;
    > };
    > struct myObject {
    > int length;
    > int * array;
    > };
    >
    > enum STATUS yield (int * retval, struct myObject * o,
    > struct iterctx * itx)
    > {
    > if (itx->is == YIELD_NEW)
    > itx->it = 0;
    >
    > while (itx->it < o->length)
    > {
    > *retval = o->array [itx->it];
    > itx->it ++;
    > return YIELD_OK;
    > }
    > return YIELD_EOF;
    > }
    >
    > int main (int argc, char ** argv)
    > {
    > struct myObject obj;
    > obj.length = 10;
    > int array[obj.length];
    >
    > int i;
    > for (i = 0; i < obj.length; ++i)
    > array = i + 1;
    >
    > obj.array = array;
    > struct iterctx itx;
    > itx.is = YIELD_NEW;
    >
    > int val = 0;
    > while (yield (&val, &obj, &itx) != YIELD_EOF)
    > {
    > printf ("val = %i!\n", val);
    > itx.is = YIELD_CONT;
    > }
    >
    > return 0;
    > }
    >
    > Now sure how reentrant this might be or not. i dont feel that condident in it but if its wrong could you point me where i should read up on more to implement some kind of co-routines.


    It seems a somewhat clumsy way to implement an iterator,
    but (on a brief look) it appears it should work. (I don't like
    the way the iteration's state is spread out across two different
    objects, but my likes and dislikes don't have the force of law.)

    However, I guess you're not all that interested in iterators
    as such, but only as an example of how one might use coroutines.
    C doesn't have language support for coroutines: Each call enters
    the called function "at the top," and execution proceeds from
    there. Once a function returns (or longjmp()'s) there's no way
    to re-enter it where you left off.

    You can do a sort of manual simulation of coroutines, by
    maintaining a "Now then, where was I?" datum, which might even
    be as simple as an int ("I last returned after doing Step 7") or
    could be a more elaborate struct ("... and local variables x,y,z
    had the following values:..."). For a non-reentrant version
    the datum could be a static variable; for a version capable of
    reentrancy you'd want a parameter pointing to a state variable
    supplied by the caller.

    I've written C for three and a half decades and haven't found
    much use for coroutines (I think I used them once or twice, and
    wound up scrapping them after rearranging the code). Callback
    functions are less flexible than coroutines, but are a lot easier
    to manage -- think of qsort() or atexit() for examples of standard
    library functions that use callbacks.

    Is there a particular problem you're trying to solve? Or
    are you just exploring?

    --
    Eric Sosman
    d
     
    Eric Sosman, Jul 8, 2013
    #9
  10. On Mon, 8 Jul 2013 14:00:04 -0700 (PDT), Philip Herron
    <> wrote:

    <snip>

    >Spent some time there and came up with this:
    >
    >#include <stdio.h>
    >#include <stdlib.h>
    >#include <assert.h>
    >
    >enum STATUS {
    > YIELD_NEW,
    > YIELD_CONT,
    > YIELD_OK,
    > YIELD_EOF,
    >};
    >
    >struct iterctx {
    > int it;
    > enum STATUS is;
    >};
    >struct myObject {
    > int length;
    > int * array;
    >};
    >
    >enum STATUS yield (int * retval, struct myObject * o,
    > struct iterctx * itx)
    >{
    > if (itx->is == YIELD_NEW)
    > itx->it = 0;
    >
    > while (itx->it < o->length)
    > {
    > *retval = o->array [itx->it];
    > itx->it ++;
    > return YIELD_OK;
    > }


    Can this while loop ever iterate more than once? Is this any
    different that a simple if?

    > return YIELD_EOF;
    >}
    >
    >int main (int argc, char ** argv)
    >{
    > struct myObject obj;
    > obj.length = 10;
    > int array[obj.length];
    >
    > int i;
    > for (i = 0; i < obj.length; ++i)
    > array = i + 1;
    >
    > obj.array = array;
    > struct iterctx itx;
    > itx.is = YIELD_NEW;
    >
    > int val = 0;
    > while (yield (&val, &obj, &itx) != YIELD_EOF)
    > {
    > printf ("val = %i!\n", val);
    > itx.is = YIELD_CONT;
    > }
    >
    > return 0;
    >}
    >
    >Now sure how reentrant this might be or not. i dont feel that condident in it but if its wrong could you point me where i should read up on more to implement some kind of co-routines.
    >
    >Thanks again


    --
    Remove del for email
     
    Barry Schwarz, Jul 8, 2013
    #10
  11. Philip Herron

    Rosario1903 Guest

    On Mon, 8 Jul 2013 09:40:41 -0700 (PDT), Philip Herron wrote:

    >I've been following http://www.chiark.greenend.org.uk/~sgtatham/coroutines.html
    >
    >Trying to understand iterators and came up with this:
    >
    >#include <stdio.h>
    >#include <stdlib.h>
    >
    >enum STATUS {
    > YIELD_OK,
    > YIELD_EOF,
    >};
    >
    >enum STATUS yield (void ** context/*, int * retval*/)
    >{
    > struct ctx {
    > int line;
    > int i;
    > };
    > struct ctx * x = (struct ctx *) *context;


    note: u8== uint8_t
    for follow what i say, goto to begin label and follow goto

    (**)
    here context is a pointer to pointer
    x=*context has to be 32 bit 0 as pointer to struct
    so x==NULL here


    > if (!x)
    > {


    so x it is 0 and follow this path

    > x = *context = malloc (sizeof (struct ctx));


    here malloc return the right not inizializated memory, or 0.
    if return 0 x->line whould seg fault the program

    otherwise
    now varible co contain that value returned from malloc if
    pointers are 32 bit pointers, if they are 64 bit pointers
    &co, (u8*)&co+4 would contain that pointer
    and
    so if (u8*)&co+4 == &val than, val is changed

    > x->line = 0;
    > }
    >
    > if (x)
    > switch (x->line) {



    > case 0:;


    this is the case of the path of run

    > for (x->i = 0; x->i < 10; x->i++)



    > {
    > do {/*
    > int it = x->i;
    > *retval = it;*/
    > x->line = __LINE__; return YIELD_OK; case __LINE__:;


    so you insert
    case __LINE__:;
    inside the for?
    not at same level of the switch
    it would insert x->line=__LINE__ and return yield_ok
    goto (*)

    > } while (0);
    > }
    > }
    >
    > free (*context);
    > *context = 0;
    > //*retval = -1;
    > return YIELD_EOF;
    >}
    >
    >int main (int argc, char ** argv)
    >{
    > int val = 0;
    > int co = 0;
    > enum STATUS s;


    begin:
    *here* &co is an address of a mem that contain 32bit 0
    in the first passage yeald() function has that argument,
    than goto (**)

    > for (s = yield ((void **) &co/*, &val*/);
    > s != YIELD_EOF;
    > s = yield ((void **) &co/*, &val*/))
    > printf ("iteration %i\n", val);


    (*)
    here it print what val contain==0 void*[*?] pointers are
    32 bit

    >
    > return 0;
    >}
    >
    >I set val = 0 and don't touch it and the loop prints:
    >
    >10-4-5-68:workspace redbrain$ gcc iterator.c -g -O0 -Wall
    >10-4-5-68:workspace redbrain$ ./a.out
    >iteration 32673
    >iteration 32673
    >iteration 32673
    >iteration 32673
    >iteration 32673
    >iteration 32673


    if 64 bit and &val=(u8)&co+4 than printf print
    the half value address return from malloc
    so Sosman would be right for me
    and in your pc void* and void** are 64 bit pointers

    >iteration 32673
    >iteration 32673
    >iteration 32673
    >iteration 32673
    >
    >I think the malloc in the callee is doing something funny but not really sure whats going on i know its a fairly big test case but any pointers would be great.
    >
    >Thanks
    >
    >--Phil
     
    Rosario1903, Jul 11, 2013
    #11
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Ken Sprague
    Replies:
    4
    Views:
    692
  2. Russ Perry Jr
    Replies:
    2
    Views:
    4,161
    Russ Perry Jr
    Aug 20, 2004
  3. Paul Chapman

    Idempotent ODBMS iterators

    Paul Chapman, Feb 16, 2005, in forum: Java
    Replies:
    0
    Views:
    433
    Paul Chapman
    Feb 16, 2005
  4. Marcin Kaliciñski

    Iterators and reverse iterators

    Marcin Kaliciñski, May 8, 2005, in forum: C++
    Replies:
    1
    Views:
    493
    Kai-Uwe Bux
    May 8, 2005
  5. , India
    Replies:
    10
    Views:
    1,085
    James Kanze
    Aug 8, 2009
Loading...

Share This Page