Additional macro to iterate over list #1

ndreys · 2011-11-16T11:07:28Z

Neither list_for_each, nor list_for_each_safe allow user to iterate
over a list if the structure of its elements is opaque.
List_for_each_opaque provides said functionality, for opaque
structures pointers to which can be safely cast to struct node_list *. In other words if the corresponding struct node_list field is placed at the top of the structure declaration.

P.S. I tried my best to figure out how the testing infrastructure
works, but I'm afraid I wasn't completely successful. I added my tests
to run.c, but the purpose of run-with-debug.c(looks completely
identical) and the mechanics behind using "Examples" section of
documentation for testing completely evade me. So for now I just
ignored them but if it's necessary I'll add tests there.

Neither list_for_each, nor list_for_each_safe allow user to iterate over a list if the structure of its elements is opaque. List_for_each_opaque provides said functionality, for opaque structures pointers to which can be safely cast to `struct node_list *`. In other words if the corresponding `struct node_list` field is placed at the top of the structure declaration.

rustyrussell · 2011-11-21T03:36:00Z

On Wed, 16 Nov 2011 03:07:29 -0800, ndreys reply@reply.github.com wrote:

Neither list_for_each, nor list_for_each_safe allow user to iterate
over a list if the structure of its elements is opaque.
List_for_each_opaque provides said functionality, for opaque
structures pointers to which can be safely cast to struct node_list *. In other words if the corresponding struct node_list field is placed at the top of the structure declaration.

Interesting. The limitation that the list struct be the first member
makes this dangerous to use, though.

Should we go for a more generic wrapper, like so:

    list_for_each_off(h, i, off)

Where off == 0 is your case. That at least makes the user realize their
implicit assumption, and may allow the others to be implemented in terms
of that macro (using offsetof() and typeof()?)...

P.S. I tried my best to figure out how the testing infrastructure
works, but I'm afraid I wasn't completely successful. I added my tests
to run.c, but the purpose of run-with-debug.c(looks completely
identical) and the mechanics behind using "Examples" section of
documentation for testing completely evade me. So for now I just
ignored them but if it's necessary I'll add tests there.

Your run.c patch was fine. run-with-debug.c defines CCAN_LIST_DEBUG
before including the list module, so it runs with all the debug checks.

I will fix it now to be clearer, ie:

    #define CCAN_LIST_DEBUG 1
    #include <ccan/list/test/run.c>

As to examples, you need to have an Example: header so it can be found
by ccanlint. Then it's kind of tricky, because it tries to compile
each example, where necessary combining it with previous ones. When you
insert a new function like this, it's easy to break the chain and break
following examples...

Thanks!
Rusty.

ndreys · 2011-11-21T05:53:29Z

Rusty Russell
reply@reply.github.com
writes:

On Wed, 16 Nov 2011 03:07:29 -0800, ndreys reply@reply.github.com wrote:

Neither list_for_each, nor list_for_each_safe allow user to iterate
over a list if the structure of its elements is opaque.
List_for_each_opaque provides said functionality, for opaque
structures pointers to which can be safely cast to struct node_list *. In other words if the corresponding struct node_list field is placed at the top of the structure declaration.

Interesting. The limitation that the list struct be the first member
makes this dangerous to use, though.

Should we go for a more generic wrapper, like so:
    list_for_each_off(h, i, off)
Where off == 0 is your case. That at least makes the user realize their
implicit assumption, and may allow the others to be implemented in terms
of that macro (using offsetof() and typeof()?)...

You make a "Damn, why didn't I think of this?" kind of point. I'll
rewrite the code and update the repo.

As to examples, you need to have an Example: header so it can be found
by ccanlint. Then it's kind of tricky, because it tries to compile
each example, where necessary combining it with previous ones. When you
insert a new function like this, it's easy to break the chain and break
following examples...

I can attest to that it is Then indeed. My initial comment had an
Example section(and example was slightly different), right before I
tried to run tests and have no regressions. What I couldn't figure out
was what the cclint tool was wrapping the code into. It kept spouting
all kind of errors to my terminal but with that kind of a set up(when a
portion of documentation gets extracted and wrapped in some auxiliary
code, then executed as a test) it is easy to have sort of a butterfly
effect when a slight and seemingly innocuous change in example causes an
avalanche of errors, so I caved in to my laziness and just removed the
title.

Andrey Smirnov

rustyrussell · 2011-11-22T01:00:19Z

On Sun, 20 Nov 2011 21:53:29 -0800, ndreys reply@reply.github.com wrote:

Rusty Russell reply@reply.github.com writes:

On Wed, 16 Nov 2011 03:07:29 -0800, ndreys reply@reply.github.com wrote:
You make a "Damn, why didn't I think of this?" kind of point. I'll
rewrite the code and update the repo.

Thanks!

As to examples, you need to have an Example: header so it can be found
by ccanlint. Then it's kind of tricky, because it tries to compile
each example, where necessary combining it with previous ones. When you
insert a new function like this, it's easy to break the chain and break
following examples...

I can attest to that it is Then indeed. My initial comment had an
Example section(and example was slightly different), right before I
tried to run tests and have no regressions. What I couldn't figure out
was what the cclint tool was wrapping the code into. It kept spouting
all kind of errors to my terminal but with that kind of a set up(when a
portion of documentation gets extracted and wrapped in some auxiliary
code, then executed as a test) it is easy to have sort of a butterfly
effect when a slight and seemingly innocuous change in example causes an
avalanche of errors, so I caved in to my laziness and just removed the
title.

Indeed, it spits out what it tried, but that butterfly effect is nasty
on something with this many members.

I think if you rewrite it it'll make things easier; you should be able
to write the same example loop in terms of list_for_each_off().

Thanks,
Rusty.

This is a second attempt at implementing iteration through list of opaque structures. It is based on suggestion from Rusty Russel: >> Neither list_for_each, nor list_for_each_safe allow user to iterate >> over a list if the structure of its elements is opaque. >> List_for_each_opaque provides said functionality, for opaque >> structures pointers to which can be safely cast to `struct >> node_list *`. In other words if the corresponding `struct >> node_list` field is placed at the top of the structure declaration. > > Interesting. The limitation that the list struct be the first member > makes this dangerous to use, though. > > Should we go for a more generic wrapper, like so: > > > list_for_each_off(h, i, off) > > Where off == 0 is your case. That at least makes the user realize their > implicit assumption, and may allow the others to be implemented in terms > of that macro (using offsetof() and typeof()?)... >

Just adding `-g' to list of CFLAGS doesn't make gcc to generate debug information required for macro expansion during debugging. Replacing it with `-g3 -ggdb' rectifies this.

ndreys · 2011-11-22T10:20:25Z

The last commit is completely unrelated. But it was really annoying not to be able to expand macros in gdb and I didn't want to open a separate pull request for such a small change. Feel free to ask me to discard it.

This is an addendum to previous commit which didn't fix the issue in all the required places.

rustyrussell · 2011-11-23T23:45:17Z

On Tue, 22 Nov 2011 02:20:27 -0800, ndreys reply@reply.github.com wrote:

The last commit is completely unrelated. But it was really annoying not to be able to expand macros in gdb and I didn't want to open a separate pull request for such a small change. Feel free to ask me to discard it.

OK, I'll review the combined list_for_each_off() patch here. Since it's
one of the first patches I've had from you, I'm going to really nitpick
:)

diff --git a/ccan/list/list.h b/ccan/list/list.h
index 18f077a..72894f8 100644
--- a/ccan/list/list.h
+++ b/ccan/list/list.h
@@ -1,6 +1,7 @@
/* Licensed under LGPLv2.1+ - see LICENSE file for details */
#ifndef CCAN_LIST_H
#define CCAN_LIST_H
+#include <stddef.h>
#include <stdbool.h>
#include <assert.h>
#include <ccan/container_of/container_of.h>
@@ -297,6 +298,45 @@ static inline void list_del_from(struct list_head
*h, str> uct list_node *n)
#define list_tail(h, type, member)
(list_empty(h) ? NULL : list_entry((h)->n.prev, type, member))

+#define __ptr_add_off(ptr, off) \

((void *) ((char *) (ptr) + (ptrdiff_t) (off)))
+#define __ptr_sub_off(ptr, off) \

((void *) ((char *) (ptr) - (ptrdiff_t) (off)))

I wouldn't cast to ptrdiff_t here; it allows them to pass anything as
"off".

I also would avoid the __ prefix; I like it, but reserved-word-pedants
don't. And you should stick to the "list_" namespace implied.

Finally, I think it's clearer as list_node_from_off_ and list_node_to_off_:

static inline void *list_node_to_off_(struct list_node *node, size_t off)
{
return (char *)node - off;
}

static inline struct list_node *list_node_from_off_(void *ptr, size_t off)
{
return (char *)ptr + off;
}

+/**

* list_for_each_off - iterate through a list of memory regions.

* @h: the list_head

* @i: the pointer to a memory region wich contains list node data.

* @off: offset(relative to @i) at which list node data resides.

* This is a low-level wrapper to iterate @i over the entire list, used to

* implement all oher, more high-level, for-each constructs. It's a for loop,

* so you can break and continue as normal.

Because these are all macros, we can order them any way we like. Thus I
would put this towards the end of the header file after the "normal"
loops, which will signficantly reduce the description as well.

* Example:

* list_for_each_off(&parent->children, child, sizeof(const char *))

* printf("Name: %s\n", child->name);

*/

Use offsetof() here, instead of sizeof(const char *). More explicit.

+#define list_for_each_off(h, i, off) \
for (i = __ptr_sub_off(list_debug(h)->n.next, off); \
  (struct list_node *) __ptr_add_off(i, off) != &(h)->n;           \
  i = __ptr_sub_off(((struct list_node *)__ptr_add_off(i, off))->next, \
                    off))

This becomes (untested);

#define list_for_each_off(h, i, off)
for (i = list_node_to_off_(list_debug(h)->n.next, (off));
list_node_from_off_(i, (off)) != &(h)->n;
i = list_node_to_off_(list_node_from_off_(i, (off))->next, off))

@@ -310,10 +350,57 @@ static inline void list_del_from(struct
list_head *h, st> ruct list_node *n)
list_for_each(&parent->children, child, list)
  printf("Name: %s\n", child->name);
*/
-#define list_for_each(h, i, member) \
for (i = container_of_var(list_debug(h)->n.next, i, member); \
 &i->member != &(h)->n;                 \
 i = container_of_var(i->member.next, i, member))
+#if HAVE_TYPEOF
+#define list_for_each(h, i, member) \
list_for_each_off(h, i, offsetof(typeof(*i), member))
+#else
+#define list_for_each(h, i, member) \

list_for_each_off(h, i, (char *)&(i)->member - (char *)(i))
+#endif

Implement of container_of_var_off() as a separate patch?

+/**

* list_for_each_off_safe - iterate through a list of memory regions, maybe

* during deletion

Prefer list_for_each_safe_off(), but that's a bit arbitrary.

diff --git a/ccan/list/test/run.c b/ccan/list/test/run.c
index f80e364..55c7e2a 100644
--- a/ccan/list/test/run.c
+++ b/ccan/list/test/run.c
@@ -13,6 +13,12 @@ struct child {
struct list_node list;
};

+typedef struct {
struct list_node list;
   const char  *name;
   unsigned int answer;
+} opaque_t;
+

This isn't really opaque though, is it?

There are two ways to make it really opaque. One is to never define it
at all: malloc memory in char * and treat it as your structure. The
other is to define a helper.c which has the actual definition (all
unrecognized C files get linked into the tests).

The latter gives you a more realistic test.

Thanks,
Rusty.

8000

There is are certain use-cases when it is necessary to know the offset of the member in a structure's memory layout. One such use-case can be seen in `ccan/list/list.h' in macros `list_for_each' and `list_for_each_safe'. This commit implements said functionality with `container_of_var_off' macro.

See #1 (comment) for details.

ndreys · 2011-11-27T17:16:03Z

On Wed, 23 Nov 2011 15:45:19 -0800, Rusty Russell reply@reply.github.com wrote:

OK, I'll review the combined list_for_each_off() patch here. Since it's
one of the first patches I've had from you, I'm going to really nitpick
:)

Oh, please do, it is far more likely that my code will only improve from
a review that it will get worse. I'm all for it.

I also would avoid the __ prefix; I like it, but reserved-word-pedants
don't. And you should stick to the "list_" namespace implied.

Yes I suspected that this might be an issue. I just didn't know to
signify that those macros were internal and not for library users.

Finally, I think it's clearer as list_node_from_off_ and list_node_to_off_:

static inline void *list_node_to_off_(struct list_node *node, size_t off)
{
return (char *)node - off;
}

static inline struct list_node *list_node_from_off_(void *ptr, size_t off)
{
return (char *)ptr + off;
}

Agree that is probably a better idea, but, I am afraid that now I would
receive threads and hate-mail from C90 crowd.:-)

BTW, I didn't put any documentation for those function, seeing how they
are internal and all. Should I've done it?

+/**

* list_for_each_off - iterate through a list of memory regions.

* @h: the list_head

* @i: the pointer to a memory region wich contains list node data.

* @off: offset(relative to @i) at which list node data resides.

* This is a low-level wrapper to iterate @i over the entire list, used to

* implement all oher, more high-level, for-each constructs. It's a for loop,

* so you can break and continue as normal.

Because these are all macros, we can order them any way we like. Thus I
would put this towards the end of the header file after the "normal"
loops, which will signficantly reduce the description as well.

That very well might be true, and I've reordered them, but as I recently
figured out, or so I think I did, the examples from documentation are
taken in order of appearance and concatenated in a test file, that is
then compiled and run. So, I suspect, said reordering, given how it put
new macros after list_for_each_safe' and itslist_del' in the Example,
left me with empty lists to iterate through in my Examples sections. Am
I wrong?

Implement of container_of_var_off() as a separate patch?

Done.

+typedef struct {
struct list_node list;
   const char  *name;
   unsigned int answer;
+} opaque_t;
+
This isn't really opaque though, is it?

There are two ways to make it really opaque. One is to never define it
at all: malloc memory in char * and treat it as your structure. The
other is to define a helper.c which has the actual definition (all
unrecognized C files get linked into the tests).

First way doesn't seem to be any close to real life usage, so I forgo
it, the second one, though, is nice. But that testing system of CCAN's
is quite a puzzle wrapped in enigma and shrouded in mystery, how was I
to know about unknown *.c's? :-) By the way I implemented such a
test-case.

Andrey Smirnov

rustyrussell · 2011-11-28T03:29:15Z

On Sun, 27 Nov 2011 09:16:04 -0800, ndreys reply@reply.github.com wrote:

On Wed, 23 Nov 2011 15:45:19 -0800, Rusty Russell reply@reply.github.com wrote:

OK, I'll review the combined list_for_each_off() patch here. Since it's
one of the first patches I've had from you, I'm going to really nitpick
:)
static inline struct list_node *list_node_from_off_(void *ptr, size_t off)
{
return (char *)ptr + off;
}

Agree that is probably a better idea, but, I am afraid that now I would
receive threads and hate-mail from C90 crowd.:-)

Haven't yet; inline is such a common option. If/when we do, we add
INLINE to compiler.h and define it out.

BTW, I didn't put any documentation for those function, seeing how they
are internal and all. Should I've done it?

No, I reserve the kerneldoc-style comments for public functions.

+/**

* list_for_each_off - iterate through a list of memory regions.

* @h: the list_head

* @i: the pointer to a memory region wich contains list node data.

* @off: offset(relative to @i) at which list node data resides.

* This is a low-level wrapper to iterate @i over the entire list, used to

* implement all oher, more high-level, for-each constructs. It's a for loop,

* so you can break and continue as normal.

Because these are all macros, we can order them any way we like. Thus I
would put this towards the end of the header file after the "normal"
loops, which will signficantly reduce the description as well.

That very well might be true, and I've reordered them, but as I recently
figured out, or so I think I did, the examples from documentation are
taken in order of appearance and concatenated in a test file, that is
then compiled and run. So, I suspect, said reordering, given how it put
new macros after list_for_each_safe' and itslist_del' in the Example,
left me with empty lists to iterate through in my Examples sections. Am
I wrong?

No, you're right. ccanlint tries several things to compile Examples,
including appending to the previous example. But it's much nicer for
humans if the common functions are first, the weird ones later.

First way doesn't seem to be any close to real life usage, so I forgo
it, the second one, though, is nice. But that testing system of CCAN's
is quite a puzzle wrapped in enigma and shrouded in mystery, how was I
to know about unknown *.c's? :-) By the way I implemented such a
test-case.

Good point. Writing a ccanlint man page with all this is on my TODO
list for this week.

Cheers,
Rusty.

ndreys · 2011-12-10T21:18:12Z

Rusty, I hope we aren't deadlocked waiting for each others actions, are we? Because I am waiting for you to comment on my latest code, so that I can fix all the issues and make the whole thing good enough for inclusion.

Andrey Smirnov

rustyrussell · 2011-12-12T03:59:28Z

On Sat, 10 Dec 2011 13:18:13 -0800, ndreys reply@reply.github.com wrote:

Rusty, I hope we aren't deadlocked waiting for each others actions, are we? Because I am waiting for you to comment on my latest code, so that I can fix all the issues and make the whole thing good enough for inclusion.

We did: thanks for breaking it :)

I took your changes and re-factored them into three commits:

The cflags changes.
Introduce container_off_var (I added container_off recently, so this
name makes more sense than container_of_var_off).
Your list.h changes (minus some whitespace changes which crept in).
Some indentation consistency stuff, and I also added some more ()s in
macros, and changed 'q' to 'n' to be consistent. I changed
list_entry_off(), and list_tail_off() to take a type, so we can cast
for them as an extra typecheck. And I added list_head_off, which was
missing. I also added helper.h to remove a warning.

I've uploaded now...

Thanks!
Rusty.

rustyrussell · 2012-02-26T23:56:01Z

Done, thanks!

ndreys added 2 commits November 22, 2011 17:12

Add additional debug flags to CFLAGS

425cad9

Just adding `-g' to list of CFLAGS doesn't make gcc to generate debug information required for macro expansion during debugging. Replacing it with `-g3 -ggdb' rectifies this.

Additional CFLAGS for GDB

30d9a13

This is an addendum to previous commit which didn't fix the issue in all the required places.

ndreys added 2 commits November 28, 2011 00:06

Opaque list iteration functionality (Implementation #3)

a33a446

See #1 (comment) for details.

rustyrussell closed this Feb 26, 2012

smcameron mentioned this pull request May 4, 2016

ccanlint core dumps if _info example contains a comment #39

Closed

nebulaeonline mentioned this pull request Sep 13, 2023

Non-conforming Isaac64 PRNG #110

Closed

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Additional macro to iterate over list #1

Additional macro to iterate over list #1

Additional macro to iterate over list #1

Additional macro to iterate over list #1

Conversation