iterators

[Philip Herron]

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

 

[Malcolm McLean]

*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.

 

[James Kuyper]

*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]

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.

 

[Eric Sosman]

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.

 

[Siri Cruise]

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;

 

[Philip Herron]

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]

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

 

[Eric Sosman]

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?

 

[Barry Schwarz]

On Mon, 8 Jul 2013 14:00:04 -0700 (PDT), Philip Herron

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

 

[Rosario1903]

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