ilist.h is not useful as-is

From: Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us>
To: pgsql-hackers(at)postgreSQL(dot)org
Subject: ilist.h is not useful as-is
Date: 2013-07-24 15:26:00
Message-ID: 24647.1374679560@sss.pgh.pa.us
Views: Raw Message | Whole Thread | Download mbox | Resend email
Thread:
Lists: pgsql-hackers

So I went off to implement the SPITupleTable tracking discussed in
<6553(dot)1374424838(at)sss(dot)pgh(dot)pa(dot)us>, and thought it would be cool to
use the slist infrastructure defined in lib/ilist.h rather than
creating a separate List node for each SPITupleTable struct.
However, I soon ran into a problem: there's no real support for
"remove the current element of an slist while we're scanning it",
which is really the only list manipulation I need. The only way
to remove an element is slist_delete(), which will iterate over
the list *again* and thus create an O(N^2) penalty. Or I could
use a dlist, but two pointers per struct seem pretty silly.

So I'm going to end up hand-implementing the same kind of manipulation
we frequently use with traditional Lists, namely keep a second variable
that's the preceding list element (not the next one) so I can unlink and
delete the target element when I find it. ilist.h is not offering me
any useful support at all for this scenario. Seems like we're missing
a bet here.

regards, tom lane

Responses

Browse pgsql-hackers by date

  From Date Subject
Next Message Andres Freund 2013-07-24 15:34:39 Re: ilist.h is not useful as-is
Previous Message Andres Freund 2013-07-24 15:11:34 Re: [bug fix] PITR corrupts the database cluster