embedded list v2

On Tue, Jun 26, 2012 at 7:26 PM, Andres Freund <andres@2ndquadrant.com> wrote:

Attached are three patches:
1. embedded list implementation
2. make the list implementation usable without USE_INLINE
3. convert all callers to ilist.h away from dllist.h

This code doesn't follow PostgreSQL coding style guidelines; in a
function definition, the name must start on its own line. Also, stuff
like this is grossly unlike what's done elsewhere; use the same
formatting as e.g. foreach:

+#define ilist_d_reverse_foreach(name, ptr) for(name =
(ptr)->head.prev;        \
+                                               name != &(ptr)->head;    \
+                                               name = name->prev)

And this is definitely NOT going to survive pgindent:

+    for(cur = head->head.prev;
+        cur != &head->head;
+        cur = cur->prev){
+           if(!(cur) ||
+              !(cur->next) ||
+              !(cur->prev) ||
+              !(cur->prev->next == cur) ||
+              !(cur->next->prev == cur))
+           {
+                   elog(ERROR, "double linked list is corrupted");
+           }
+    }

And this is another meme we don't use elsewhere; add an explicit NULL test:

+ while ((cur = last->next))

And then there's stuff like this:

+           if(!cur){
+                   elog(ERROR, "single linked list is corrupted");
+           }

Aside from the formatting issues, I think it would be sensible to
preserve the terminology of talking about the "head" and "tail" of a
list that we use elsewhere, instead of calling them the "front" and
"back" as you've done here. I would suggest that instead of add_after
and add_before you use the names insert_after and insert_before, which
I think is more clear; also instead of remove, I think you should say
delete, for consistency with pg_list.h.

A number of these inlined functions could be rewritten as macros -
e.g. ilist_d_has_next, ilist_d_has_prev, ilist_d_is_empty. Since some
things are written as macros anyway maybe it's good to do all the
one-liners that way, although I guess it doesn't matter that much. I
also agree with your XXX comment that ilist_s_remove should probably
be out of line.

Apart from the above, mostly fairly superficial concerns I think this
makes sense.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

On Thursday, June 28, 2012 06:23:05 PM Robert Haas wrote:

On Tue, Jun 26, 2012 at 7:26 PM, Andres Freund <andres@2ndquadrant.com>

wrote:

Attached are three patches:
1. embedded list implementation
2. make the list implementation usable without USE_INLINE
3. convert all callers to ilist.h away from dllist.h

This code doesn't follow PostgreSQL coding style guidelines; in a
function definition, the name must start on its own line.

Hrmpf. Yes.

Also, stuff like this is grossly unlike what's done elsewhere; use the same
formatting as e.g. foreach:
+#define ilist_d_reverse_foreach(name, ptr) for(name =
(ptr)->head.prev;        \
+                                               name != &(ptr)->head;    \
+                                               name = name->prev)

Its not only unlike the rest its also ugly... Fixed.

And this is definitely NOT going to survive pgindent:

+    for(cur = head->head.prev;
+        cur != &head->head;
+        cur = cur->prev){
+           if(!(cur) ||
+              !(cur->next) ||
+              !(cur->prev) ||
+              !(cur->prev->next == cur) ||
+              !(cur->next->prev == cur))
+           {
+                   elog(ERROR, "double linked list is corrupted");
+           }
+    }

I changed the for() contents to one line. I don't think I can write anything
that won't be changed by pgindent for the if()s contents.

And this is another meme we don't use elsewhere; add an explicit NULL test:

+ while ((cur = last->next))

Fixed.

And then there's stuff like this:

+           if(!cur){
+                   elog(ERROR, "single linked list is corrupted");
+           }

Fixed the places that I found.

Aside from the formatting issues, I think it would be sensible to
preserve the terminology of talking about the "head" and "tail" of a
list that we use elsewhere, instead of calling them the "front" and
"back" as you've done here. I would suggest that instead of add_after
and add_before you use the names insert_after and insert_before, which
I think is more clear; also instead of remove, I think you should say
delete, for consistency with pg_list.h.

Heh. Ive been poisoned from using c++ too much (thats partially stl names).

Changed.

A number of these inlined functions could be rewritten as macros -
e.g. ilist_d_has_next, ilist_d_has_prev, ilist_d_is_empty. Since some
things are written as macros anyway maybe it's good to do all the
one-liners that way, although I guess it doesn't matter that much.

I find inline functions preferrable because of multiple evaluation stuff. The
macros are macros because of the dynamic return type and other similar issues
which cannot be done in plain C.

I also agree with your XXX comment that ilist_s_remove should probably
be out of line.

Done.

Looks good now?

Andres
--
Andres Freund http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

Excerpts from Andres Freund's message of jue jun 28 14:20:59 -0400 2012:

Looks good now?

The one thing I dislike about this code is the names you've chosen. I
mean, ilist_s_stuff and ilist_d_stuff. I mean, why not just Slist_foo
and Dlist_bar, say? As far as I can tell, you've chosen the "i" prefix
because it's "integrated" or "inline", but this seems to me a rather
irrelevant implementation detail that's of little use to the callers.

Also, I don't find so great an idea to have everything in a single file.
Is there anything wrong with separating singly and doubly linked lists
each to its own file? Other than you not liking it, I mean. As a
person who spends some time trying to untangle header dependencies, I
would appreciate keeping stuff as lean as possible. However, since
nobody else seems to have commented on this, maybe it's just me.

--
Álvaro Herrera <alvherre@commandprompt.com>
The PostgreSQL Company - Command Prompt, Inc.
PostgreSQL Replication, Consulting, Custom Development, 24x7 support

On Thu, Jun 28, 2012 at 3:47 PM, Alvaro Herrera
<alvherre@commandprompt.com> wrote:

Excerpts from Andres Freund's message of jue jun 28 14:20:59 -0400 2012:

Looks good now?

The one thing I dislike about this code is the names you've chosen.  I
mean, ilist_s_stuff and ilist_d_stuff.  I mean, why not just Slist_foo
and Dlist_bar, say?  As far as I can tell, you've chosen the "i" prefix
because it's "integrated" or "inline", but this seems to me a rather
irrelevant implementation detail that's of little use to the callers.

Also, I don't find so great an idea to have everything in a single file.
Is there anything wrong with separating singly and doubly linked lists
each to its own file?  Other than you not liking it, I mean.  As a
person who spends some time trying to untangle header dependencies, I
would appreciate keeping stuff as lean as possible.  However, since
nobody else seems to have commented on this, maybe it's just me.

Well, it's not JUST you. I agree entirely with all of your points.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

On Thursday, June 28, 2012 09:47:05 PM Alvaro Herrera wrote:

Excerpts from Andres Freund's message of jue jun 28 14:20:59 -0400 2012:

Looks good now?

The one thing I dislike about this code is the names you've chosen. I
mean, ilist_s_stuff and ilist_d_stuff. I mean, why not just Slist_foo
and Dlist_bar, say? As far as I can tell, you've chosen the "i" prefix
because it's "integrated" or "inline", but this seems to me a rather
irrelevant implementation detail that's of little use to the callers.

Well, its not irrelevant because you actually need to change the contained
structs to use it. I find that a pretty relevant distinction.

Also, I don't find so great an idea to have everything in a single file.
Is there anything wrong with separating singly and doubly linked lists
each to its own file? Other than you not liking it, I mean. As a
person who spends some time trying to untangle header dependencies, I
would appreciate keeping stuff as lean as possible. However, since
nobody else seems to have commented on this, maybe it's just me.

Robert had the same comment, its not just you...

It would mean duplicating the ugliness around the conditional inlining, the
comment explaining how to use the stuff (because its basically used the same
way for single and double linked lists), you would need to #define
ilist_container twice or have a third file....
Just seems to much overhead for ~100 lines (the single linked list
implementation).

What I wonder is how hard it would be to remove catcache.h's structs into the
implementation. Thats the reason why the old and new list implementation
currently is included all over the backend...

Greetings,

Andres
--
Andres Freund http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

On Thursday, June 28, 2012 10:03:26 PM Andres Freund wrote:

What I wonder is how hard it would be to remove catcache.h's structs into
the implementation. Thats the reason why the old and new list
implementation currently is included all over the backend...

Moving them into the implementation isn't possible, but catcache.h being
included just about everywhere simply isn't needed.

It being included everywhere was introduced by a series of commits from Bruce:
b85a965f5fc7243d0386085e12f7a6c836503b42
b43ebe5f83b28e06a3fd933b989aeccf0df7844a
e0522505bd13bc5aae993fc50b8f420665d78e96
and others

That looks broken. An implementation file not including its own header... A
minimal patch to fix this particular problem is attached (looks like there are
others in the series).

Andres
--
Andres Freund http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

Excerpts from Andres Freund's message of jue jun 28 16:03:26 -0400 2012:

On Thursday, June 28, 2012 09:47:05 PM Alvaro Herrera wrote:

Excerpts from Andres Freund's message of jue jun 28 14:20:59 -0400 2012:

Looks good now?

The one thing I dislike about this code is the names you've chosen. I
mean, ilist_s_stuff and ilist_d_stuff. I mean, why not just Slist_foo
and Dlist_bar, say? As far as I can tell, you've chosen the "i" prefix
because it's "integrated" or "inline", but this seems to me a rather
irrelevant implementation detail that's of little use to the callers.

Well, its not irrelevant because you actually need to change the contained
structs to use it. I find that a pretty relevant distinction.

Sure, at that point it is relevant. Once you're past that, there's no
point. I mean, you would look up how it's used in the header comment of
the implementation, and then just refer to the API.

Also, I don't find so great an idea to have everything in a single file.
Is there anything wrong with separating singly and doubly linked lists
each to its own file? Other than you not liking it, I mean. As a
person who spends some time trying to untangle header dependencies, I
would appreciate keeping stuff as lean as possible. However, since
nobody else seems to have commented on this, maybe it's just me.

Robert had the same comment, its not just you...

It would mean duplicating the ugliness around the conditional inlining, the
comment explaining how to use the stuff (because its basically used the same
way for single and double linked lists), you would need to #define
ilist_container twice or have a third file....
Just seems to much overhead for ~100 lines (the single linked list
implementation).

Well, then don't duplicate a comment -- create a README.lists and
refer to it in the comments. Not sure about the ilist_container stuff,
but in principle I don't have a problem with having a file with a single
#define that's included by two other headers.

What I wonder is how hard it would be to remove catcache.h's structs into the
implementation. Thats the reason why the old and new list implementation
currently is included all over the backend...

Yeah, catcache.h is a pretty ugly beast. I'm sure there are ways to behead it.

--
Álvaro Herrera <alvherre@commandprompt.com>
The PostgreSQL Company - Command Prompt, Inc.
PostgreSQL Replication, Consulting, Custom Development, 24x7 support

Excerpts from Andres Freund's message of jue jun 28 17:06:49 -0400 2012:

On Thursday, June 28, 2012 10:03:26 PM Andres Freund wrote:

What I wonder is how hard it would be to remove catcache.h's structs into
the implementation. Thats the reason why the old and new list
implementation currently is included all over the backend...

Moving them into the implementation isn't possible, but catcache.h being
included just about everywhere simply isn't needed.

It being included everywhere was introduced by a series of commits from Bruce:
b85a965f5fc7243d0386085e12f7a6c836503b42
b43ebe5f83b28e06a3fd933b989aeccf0df7844a
e0522505bd13bc5aae993fc50b8f420665d78e96
and others

That looks broken. An implementation file not including its own header... A
minimal patch to fix this particular problem is attached (looks like there are
others in the series).

Hmm, I think this is against project policy -- we do want each header to
be compilable separately. I would go instead the way of splitting
resowner.h in two or more pieces.

--
Álvaro Herrera <alvherre@commandprompt.com>
The PostgreSQL Company - Command Prompt, Inc.
PostgreSQL Replication, Consulting, Custom Development, 24x7 support

On Thursday, June 28, 2012 11:45:08 PM Alvaro Herrera wrote:

Excerpts from Andres Freund's message of jue jun 28 17:06:49 -0400 2012:

On Thursday, June 28, 2012 10:03:26 PM Andres Freund wrote:

What I wonder is how hard it would be to remove catcache.h's structs
into the implementation. Thats the reason why the old and new list
implementation currently is included all over the backend...

Moving them into the implementation isn't possible, but catcache.h being
included just about everywhere simply isn't needed.

It being included everywhere was introduced by a series of commits from
Bruce: b85a965f5fc7243d0386085e12f7a6c836503b42
b43ebe5f83b28e06a3fd933b989aeccf0df7844a
e0522505bd13bc5aae993fc50b8f420665d78e96
and others

That looks broken. An implementation file not including its own header...
A minimal patch to fix this particular problem is attached (looks like
there are others in the series).

Hmm, I think this is against project policy -- we do want each header to
be compilable separately. I would go instead the way of splitting
resowner.h in two or more pieces.

It was done nearly the same way in catcache.h before Bruce changed things. You
can see still the rememnants of that in syscache.h:
/* list-search interface. Users of this must import catcache.h too */
extern struct catclist *SearchSysCacheList(int cacheId, int nkeys,
Datum key1, Datum key2, Datum key3, Datum key4);

The only difference is that gcc warns if you declare a struct in a parameter -
thats why I forward declared it explicitly...

resowner.h still compiles standalone and is still usable. You can even call
ResourceOwnerRememberCatCacheListRef if you get the list parameter from
somewhere else.

Andres
--
Andres Freund http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

On 28 June 2012 19:20, Andres Freund <andres@2ndquadrant.com> wrote:

<0001-Add-embedded-list-interface.patch>

Looks good now?

I have a few gripes.

+ * there isn't much we can test in a single linked list except that its

There are numerous references to "single linked lists", where, I
believe, "singly linked list" is intended (the same can be said for
"double" and "doubly" respectively).

/* Functions we want to be inlined if possible */
+ #ifndef USE_INLINE
...
+ #endif /* USE_INLINE */

A minor quibble, but that last line probably be:

#endif /* ! defined USE_INLINE */

Another minor quibble. We usually try and keep these in alphabetical order:

*** a/src/backend/lib/Makefile
--- b/src/backend/lib/Makefile
*************** subdir = src/backend/lib
*** 12,17 ****
  top_builddir = ../../..
  include $(top_builddir)/src/Makefile.global

! OBJS = dllist.o stringinfo.o

  include $(top_srcdir)/src/backend/common.mk
--- 12,17 ----
  top_builddir = ../../..
  include $(top_builddir)/src/Makefile.global

! OBJS = dllist.o stringinfo.o ilist.o

include $(top_srcdir)/src/backend/common.mk

New files generally don't require this:

+ * Portions Copyright (c) 1994, Regents of the University of California

This needs to be altered:

+ /*
+  * enable for extra debugging. This is rather expensive so its not enabled by
+  * default even with --enable-cassert
+ */
+ /* #define ILIST_DEBUG */

I'm not sure that this extra error-detection warrants its own macro.
syncrep.c similarly has its own rather expensive error-detection, with
entire function bodies only compiled when USE_ASSERT_CHECKING is
defined. Any of the other dedicated "debugging macros", like
LOCK_DEBUG or WAL_DEBUG seem to exist to dump LOG messages when
binaries were built with the macros defined (this can happen via
pg_config_manual.h. I note that what you have here lacks a
corresponding entry). I think that it would be more idiomatic to just
use USE_ASSERT_CHECKING, and rewrite the debugging functions such that
they are used directly within an Assert, in the style of syncrep.c .
Now, I know Tom wasn't too enthusiastic about having this sort of
thing within --enable-cassert builds, but I'm inclined to think that
there is little point in having this additional error checking if
they're not at least available when that configuration is used. Maybe
we should consider taking the sophisticated asserts out of
--enable-cassert builds, or removing them entirely, if and when they
prove to be annoying?

There is slight misalignment within the comments at the top of ilist.h.

Within ilist.c, the following block exists:

+ #ifndef USE_INLINE
+ #define ILIST_USE_DECLARATION
+ #endif
+
+ #include "lib/ilist.h"
+
+ #ifndef USE_INLINE
+ #undef ILIST_USE_DECLARATION
+ #endif

I see little reason for the latter "#undef" block within ilist.c. It
isn't that exactly the same code already exists at the end of ilist.h
(though there is that too) - it's mostly that it's unnecessary,
because there is no need or logical reason to #undef within ilist.c.

+ /*
+  * The following function declarations are only used if inlining is supported
+  * or when included from a file that explicitly declares USE_DECLARATION
+  */
+ #ifdef ILIST_USE_DECLARATION

Shouldn't that be "The following function definitions..." and
ILIST_USE_DEFINITIONS?

I think the fact that it's possible in principle for
ILIST_USE_DECLARATION to not be exactly equivalent to ! USE_INLINE is
strictly speaking dangerous, since USE_INLINE needs to be baked into
the ABI targeted by third-party module developers. What if a module
was built that called a function that didn't have an entry in the
procedure linkage table, due to ad-hoc usage of ILIST_USE_DECLARATION?
That'd result in a libdl error, if you're lucky. Now, that probably
sounds stupid - I'm pretty sure that you didn't intend that
ILIST_USE_DECLARATION be set by just any old client of this
infrastructure. Rather, you intended that ILIST_USE_DECLARATION be set
either when ilist.h was included while USE_INLINE, so that macro
expansion would make those functions inline, or within ilist.c, when
!USE_INLINE, so that the functions would not be inlined. This should
be much more explicit though. You simply describe the mechanism rather
than the intent at present.

I rather suspect that INLINE_IF_POSSIBLE should be a general purpose
utility, perhaps defined next to NON_EXEC_STATIC within c.h, with a
brief explanation there (rather than in any new header that needs to
do this). I think you'd be able to reasonably split singly and doubly
linked lists into their own headers without much repetition between
the two then. You could formalise the idea that where USE_INLINE,
another macro, defined alongside INLINE_IF_POSSIBLE (functionally
equivalent to ILIST_USE_DECLARATION in the extant code - say,
USE_INLINING_DEFINITIONS) is going to be generally defined everywhere
USE_INLINE is defined. You're then going to have to deal with the hack
whereby USE_INLINING_DEFINITIONS is set just "to suck the definitions
out of the header" to make !USE_INLINE work within .c files only (or
pretty close). That's kins of logical though - !USE_INLINE is hardly
ever used, so it deserves to get the slightly grottier code. The only
direct macro usage that your header files now need is "#ifdef
USE_INLINING_DEFINITIONS" (plus INLINE_IF_POSSIBLE rather than plain
"static inline", of course), as well as having extern declarations for
the !USE_INLINE case. The idea is that each header file has slightly
fewer eyebrow-raising macro hacks, and there is at least no obvious
redundancy between the two. In particular, this only has to happen
once, within c.h:

#ifdef USE_INLINE
#define INLINE_IF_POSSIBLE static inline
#define USE_INLINING_DEFINITIONS // actually spelt
"ILIST_USE_DECLARATION" in patch
#else
#define INLINE_IF_POSSIBLE
#endif

What's more, under this scheme, the following code does not need to
(and shouldn't) appear at the end of headers like ilist.h:

+ /*
+  * if we defined ILIST_USE_DECLARATION undef it again, its not interesting
+  * outside this file
+  */
+ #ifdef USE_INLINE
+ #undef USE_INLINING_DEFINITIONS // actually spelt
"ILIST_USE_DECLARATION" in patch
+ #endif

because only when considering the !USE_INLINE case do we have to
consider that we might need to manually set USE_INLINING_DEFINITIONS
to "suck in" definitions within C files (as I've said, unsetting it
very probably doesn't matter within a C file, so no need to do it
there either).

If that isn't quite clear, the simple version is:

We assume the USE_INLINE case until we learn otherwise, rather than
assuming neither USE_INLINE nor !USE_INLINE. It's cleaner to treat
!USE_INLINE as a sort of edge case with special handling, rather than
having ilist.h and friends worry about cleaning up after themselves
all the time, and worrying about initialising things for themselves
alone according to the present build configuration.

In any case, if we're going to manage the !USE_INLINE case like this
at all, we should probably formalise it along some lines.

I still don't think this is going to fly:

+ #ifdef __GNUC__
+ #define unused_attr __attribute__((unused))
+ #else
+ #define unused_attr
+ #endif

There is no reasonable way to prevent MSVC from giving a warning as a
result of this. The rationale for doing things this way is:

+ /*
+  * gcc warns about unused parameters if -Wunused-parameter is specified (part
+  * of -Wextra ). In the cases below its perfectly fine not to use those
+  * parameters because they are just passed to make the interface
consistent and
+  * to allow debugging in case of ILIST_DEBUG.
+  *
+  */

Seems to me that you'd be able to do a better job with a thin macro
shim on the existing (usually) inline functions. That'd also take care
of your concerns about multiple evaluation.

The comments could probably use some wordsmithing in various places.
That's no big deal though.

I agree with Alvaro on the naming of these functions. I'd prefer it if
they didn't have the "i" prefix too, though that's hardly very
important.

That's all I have for now. I'll take a look at the other patch
(0002-Remove-usage-of-lib-dllist.h-and-replace-it-by-the-n.patch)
soon.

--
Peter Geoghegan http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training and Services

On 5 July 2012 02:49, Peter Geoghegan <peter@2ndquadrant.com> wrote:

On 28 June 2012 19:20, Andres Freund <andres@2ndquadrant.com> wrote:

<0001-Add-embedded-list-interface.patch>

Looks good now?

I have a few gripes.

We are passed the nominal deadline. Had you planned on getting back to
me this commitfest? If not, I'll shelve my review of
"0002-Remove-usage-of-lib-dllist.h-and-replace-it-by-the-n.patch"
until commitfest 2012-09, and mark this "returned with feedback".

--
Peter Geoghegan http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training and Services

On Monday, July 23, 2012 12:55:01 PM Peter Geoghegan wrote:

On 5 July 2012 02:49, Peter Geoghegan <peter@2ndquadrant.com> wrote:

On 28 June 2012 19:20, Andres Freund <andres@2ndquadrant.com> wrote:

<0001-Add-embedded-list-interface.patch>

Looks good now?

I have a few gripes.

We are passed the nominal deadline. Had you planned on getting back to
me this commitfest? If not, I'll shelve my review of
"0002-Remove-usage-of-lib-dllist.h-and-replace-it-by-the-n.patch"
until commitfest 2012-09, and mark this "returned with feedback".

I was actually waiting for the second review ;). Sorry for the
misunderstanding.

There is no rule that review cannot happen outside the commitfest, so I would
appreciate if we could push this further...

Andres
--
Andres Freund http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

Excerpts from Andres Freund's message of jue jun 28 17:06:49 -0400 2012:

On Thursday, June 28, 2012 10:03:26 PM Andres Freund wrote:

What I wonder is how hard it would be to remove catcache.h's structs into
the implementation. Thats the reason why the old and new list
implementation currently is included all over the backend...

Moving them into the implementation isn't possible, but catcache.h being
included just about everywhere simply isn't needed.

FWIW this got fixed during some header changes I made a couple of weeks
ago. If you have similar fixes to propose, let me know.

--
Álvaro Herrera http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

Here's a prettified version of this stuff. I found one bug in the macro
ilist_s_head: the test was reversed. Also, curiously, the macro had the
same name as the struct, so I renamed the macro. I take it you haven't
used this macro, so maybe it shouldn't be there at all? Or maybe I
completely misread what the macro is supposed to do.

I also renamed all the structs and functions by changing ilist_s_foo to
Slist_foo. Similarly for ilist_d_foo. This is all mechanical so any
subsequent patch should be trivial to refresh for this change.

I think README.ilist (which is what you had in the comment at the top of
ilist.h) should be heavily expanded. I don't find it at all clear.

There were other cosmetic changes, but the implementation is pretty much
the same you submitted.

I didn't look at the other patch you posted, replacing dllist.c usage;
will do that next to verify that the list implementation works.

--
Álvaro Herrera http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

On Thu, Sep 6, 2012 at 12:09 PM, Alvaro Herrera
<alvherre@2ndquadrant.com> wrote:

Here's a prettified version of this stuff. I found one bug in the macro
ilist_s_head: the test was reversed. Also, curiously, the macro had the
same name as the struct, so I renamed the macro. I take it you haven't
used this macro, so maybe it shouldn't be there at all? Or maybe I
completely misread what the macro is supposed to do.

I also renamed all the structs and functions by changing ilist_s_foo to
Slist_foo. Similarly for ilist_d_foo. This is all mechanical so any
subsequent patch should be trivial to refresh for this change.

I think this is a good direction, but why not just slist_foo and
dlist_foo? I don't see much value in capitalizing the first letter.
It's not like it's the beginning of a word or anything. Plus, that
way the new stuff will be more obviously different from Dllist, which
it will (I think) replace.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

Hi Alvaro,

Thanks for the review!

On Thursday, September 06, 2012 06:09:35 PM Alvaro Herrera wrote:

Here's a prettified version of this stuff. I found one bug in the macro
ilist_s_head: the test was reversed.

Oh, good catch. I had only used the _unchecked version because my code checked
that there are elements just some lines before that...

Also, curiously, the macro had the same name as the struct, so I renamed the
macro. I take it you haven't used this macro, so maybe it shouldn't be

there at all? Or maybe I completely misread what the macro is supposed to do.
According to my patches here that got introduced by me whe renaming
_front/back to _head/tail according to Roberts wishes. Sorry for that.

I also renamed all the structs and functions by changing ilist_s_foo to
Slist_foo. Similarly for ilist_d_foo. This is all mechanical so any
subsequent patch should be trivial to refresh for this change.

Ok. I concur with robert that a lower case first letter might be better
readable but again, I don't really care that much.

I think README.ilist (which is what you had in the comment at the top of
ilist.h) should be heavily expanded. I don't find it at all clear.

Hm. I agree :(. Let me have a go when you have a state you find acceptable
otherwise...

There were other cosmetic changes, but the implementation is pretty much
the same you submitted.

Good.

I didn't look at the other patch you posted, replacing dllist.c usage;
will do that next to verify that the list implementation works.

Thanks!

Greetings,

Andres
--
Andres Freund http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

Here's an updated version of both patches, as well as a third patch that
converts the cc_node list link in catcache.c into an slist.

There are very few changes here; in ilist.h a singleton slist was being
considered empty. Andres reported this to me privately. One other
change is that in catcache.c we no longer compute a new HASH_INDEX on a
CatCTup in order to remove it from its list; instead we store a pointer
to the list in the element itself. We weren't able to measure any
difference between these two approaches to the problem, so we chose the
approach that hasn't been previously vetoed -- see
http://archives.postgresql.org/message-id/2852.1174575239%40sss.pgh.pa.us

I also addressed the unused_attr thingy by taking it out and having the
non-debug version emit a cast to void of the argument.

I think I would get this committed during CF2, and then have a look at
changing some uses of SHM_QUEUE with ilists too.

--
Álvaro Herrera http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

Excerpts from Alvaro Herrera's message of vie sep 14 14:22:18 -0300 2012:

Here's an updated version of both patches, as well as a third patch that
converts the cc_node list link in catcache.c into an slist.

One thing I would like more input in, is whether people think it's
worthwhile to split dlists and slists into separate files. Thus far
this has been mentioned by three people independently.

Another question is whether ilist_container() should actually be a more
general macro "containerof" defined in c.h. (ISTM it would be necessary
to have this macro if we want to split into two files; that way we don't
need to have two macros dlist_container and slist_container with
identical definition, or alternatively a third file that defines just
ilist_container)

Third question is about the INLINE_IF_POSSIBLE business as commented by
Peter. It seems to me that the simple technique used here to avoid
having two copies of the source could be used by memcxt.c, list.c,
sortsupport.c as well (maybe clean up fastgetattr too).

--
Álvaro Herrera http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

Alvaro Herrera <alvherre@2ndquadrant.com> writes:

Here's an updated version of both patches, as well as a third patch that
converts the cc_node list link in catcache.c into an slist.

There's a lot of stuff here that seems rather unfortunate and/or sloppy.

Does it even compile? The 0002 patch refers to a typedef ilist_d_head
that I don't see defined anywhere. (It would be good to shorten that
name by a couple of characters anyway, for tab-stop alignment reasons.)

The documentation (such as it is) claims that the lists are circularly
linked, which doesn't seem to be the case from the code; slist_foreach
for instance certainly won't work if that's true. (As far as the
docs go, I'd get rid of the README file and put the how-to-use-it
comments into the header file, where they have some chance of being
(a) seen and (b) maintained. But first they need to be rewritten.)

The distinction between head and node structs seems rather useless,
and it's certainly notationally tedious. Do we need it?

I find the need for this change quite unfortunate:

@@ -256,7 +258,7 @@ typedef struct
static AutoVacuumShmemStruct *AutoVacuumShmem;

 /* the database list in the launcher, and the context that contains it */
-static Dllist *DatabaseList = NULL;
+static ilist_d_head DatabaseList;
 static MemoryContext DatabaseListCxt = NULL;

/* Pointer to my own WorkerInfo, valid on each worker */
@@ -403,6 +405,9 @@ AutoVacLauncherMain(int argc, char *argv[])
/* Identify myself via ps */
init_ps_display("autovacuum launcher process", "", "", "");

+	/* initialize to be empty */
+	ilist_d_init(&DatabaseList);
+
 	ereport(LOG,
 			(errmsg("autovacuum launcher started")));

Instead let's provide a macro for an empty list value, so that you can
do something like

static ilist_d_head DatabaseList = EMPTY_DLIST;

and not require a new assumption that there will be a convenient place
to initialize static list variables. In general I think it'd be a lot
better if the lists were defined such that all-zeroes is a valid empty
list header, anyway.

The apparently random decisions to make some things inline functions
and other things macros (even though they evaluate their args multiple
times) will come back to bite us. I am much more interested in
unsurprising behavior of these constructs than I am in squeezing out
an instruction or two, so I'm very much against the unsafe macros.

I think we could do without such useless distinctions as slist_get_head
vs slist_get_head_unchecked, too. We've already got Assert and
ILIST_DEBUG, we do not need even more layers of check-or-not
distinctions.

Meanwhile, obvious checks that *should* be made, like slist_pop_head
asserting that there be something to pop, don't seem to be made.

Not a full review, just some things that struck me in a quick scan...

regards, tom lane