Re: ilist.h is not useful as-is

On 2013-07-24 11:26:00 -0400, Tom Lane wrote:
> 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.

Hm. Yes. This should be added. I didn't need it so far, but I definitely
can see usecases.

slist_delete_current(slist_mutable_iter *)?

I am willing to cough up a patch if you want.

This will require another member variable in slist_mutable_iter which
obviously will need to be maintained, but that seems fine to me since it
will reduce the cost of actually deleting noticeably.

Greetings,

Andres Freund

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