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

On Thu, Oct 27, 2022 at 9:05 AM David Rowley <dgrowleyml(at)gmail(dot)com> wrote:
>
> As part of the AIO work [1], there are quite a number of dlist_heads
> which a counter is used to keep track on how many items are in the
> list. We also have a few places in master which do the same thing.
>
> In order to tidy this up and to help ensure that the count variable
> does not get out of sync with the items which are stored in the list,
> how about we introduce "dclist" which maintains the count for us?
>
> I've attached a patch which does this. The majority of the functions
> for the new type are just wrappers around the equivalent dlist
> function.
>
> dclist provides all of the functionality that dlist does except
> there's no dclist_delete() function. dlist_delete() can be done by
> just knowing the element to delete and not the list that the element
> belongs to. With dclist, that's not possible as we must also subtract
> 1 from the count variable and obviously we need the dclist_head for
> that.
>
> [1] https://www.postgresql.org/message-id/flat/20210223100344(dot)llw5an2aklengrmn(at)alap3(dot)anarazel(dot)de

+1. Using dlist_head in dclist_head enables us to reuse dlist_* functions.

Some comments on the patch:
1. I think it's better to just return dlist_is_empty(&head->dlist) &&
(head->count == 0); from dclist_is_empty() and remove the assert for
better readability and safety against count being zero.

2. Missing dlist_is_memberof() in dclist_delete_from()?

3. Just thinking if we need to move dlist_is_memberof() check from
dclist_* functions to dlist_* functions, because they also need such
insurance against callers passing spurious nodes.

4. More opportunities to use dclist_* in below places, no?
dlist_push_tail(&src->mappings, &pmap->node);
src->num_mappings++;

dlist_push_head(&MXactCache, &entry->node);
if (MXactCacheMembers++ >= MAX_CACHE_ENTRIES)

5. dlist_is_memberof() - do we need this at all? We trust the callers
of dlist_* today that the passed in node belongs to the list, no?

6. If we decide to have dlist_is_memberof() and the asserts around it,
can we design it on the similar lines as dlist_check() to avoid many
#ifdef ILIST_DEBUG #endif blocks spreading around the code?

7. Do we need Assert(head->count > 0); in more places like dclist_delete_from()?

8. Don't we need dlist_container(), dlist_head_element(),
dlist_tail_element() for dclist_*? Even though, we might not use them
immediately, just for the sake for completeness of dclist data
structure.

> I'll add this to the November commitfest.

Yes, please.

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