Re: Adding doubly linked list type which stores the number of items in the list

On Mon, Oct 31, 2022 at 8:26 AM David Rowley <dgrowleyml(at)gmail(dot)com> wrote:
>
> I looked at dlist_check() and I didn't quite manage to figure out why
> the cast is needed. As far as I can see, there are no calls where we
> only pass dlist_head solely for the dlist_check(). For
> dlist_member_check(), dlist_delete_from() does not use the 'head'
> parameter for anything apart from dlist_member_check(), so I believe
> the cast is required for 'head'. I think I'd rather only add the cast
> for 'node' unless we really require it. Cargo-culting it in there just
> because that's what the other macros do does not seem like a good idea
> to me.

Hm, you're right, dlist_member_check() needs it. Also, slist_check()
needs it for slist_has_next(). dlist_check() doesn't need it, however,
keeping it intact doesn't harm, I guess.

> My original thoughts were that it seems unlikely we'd ever give an
> assert build a workload that would ever have 2^32 dlist_nodes in
> dclist. Having said that, perhaps it would do no harm to add some
> overflow checks to 'count'. I've gone and added some
> Assert(head->count > 0) after we do count++.

So, when an overflow occurs, the head->count wraps around after
PG_UINT32_MAX, meaning, becomes 0 and we will catch it in an assert
build. This looks reasonable to me. However, the responsibility lies
with the developers to deal with such overflows.

> > 8. Wondering if we need dlist_delete_from() at all. Can't we just add
> > dlist_member_check() dclist_delete_from() and call dlist_delete()
> > directly?
>
> Certainly, but I made it that way on purpose. I wanted dclist to have
> a superset of the functions that dlist has. I just see no reason why
> dlist shouldn't have dlist_delete_from() when dclist has it.

Okay.

> I've attached the v3 version of the patch which includes some
> additional polishing work.

Thanks. The v3 patch looks good to me.

BTW, do we need sclist_* as well? AFAICS, no such use-case exists
needing slist and element count, maybe we don't need.

I'm wondering if adding count to dlist_head and maintaining it as part
of the existing dlist_* data structure and functions is any better
than introducing dclist_*? In that case, we need only one function,
dlist_count, no? Or do we choose to go dclist_* because we want to
avoid the extra cost of maintaining count within dlist_*? If yes, is
maintaining count in dlist_* really costly?

--
Bharath Rupireddy
PostgreSQL Contributors Team
RDS Open Source Databases
Amazon Web Services: https://aws.amazon.com