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

On Fri, Oct 28, 2022 at 11:01 AM David Rowley <dgrowleyml(at)gmail(dot)com> wrote:
>
> > 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.
>
> I think the affected functions there would be; dlist_move_head(),
> dlist_move_tail(), dlist_has_next(), dlist_has_prev(),
> dlist_next_node() and dlist_prev_node(). I believe if we did that then
> it's effectively an API change. The comments only claim that it's
> undefined if node is not a member of the list. It does not say 'node'
> *must* be part of the list. Now, perhaps doing this would just make
> it more likely that we'd find bugs in our code and extension authors
> would find bugs in their code, but it does move the bar.
> dlist_move_head and dlist_move_tail look like they'd work perfectly
> well to remove an item from 1 list and put it on the head or tail of
> some completely different list. Should we really be changing that in a
> patch that is meant to just add the dclist type?

Hm. Let's not touch that here.

Thanks for the patch. Few more comments on v2:
1. I guess we need to cast the 'node' parameter too, something like
below? I'm reading the comment there talking about compilers
complaning about the unused function arguments.
dlist_member_check(head, node) ((void) (head); (void) (node);)

2.
+ * maximum of UINT32 elements. It is up to the caller to ensure no more than
+ * this many items are added to a dclist.
Can we put max limit, at least in assert, something like below, on
'count' instead of saying above? I'm not sure if there's someone
storing 4 billion items, but it will be a good-to-have safety from the
data structure perspective if others think it's not an overkill.
Assert(head->count > 0 && head->count <= PG_UINT32_MAX);

3. I guess, we can split up the patches for the ease of review, 0001
introducing dclist_* data structure and 0002 using it. It's not
mandatory though. The two patches can go separately if needed.

4.
+/*
+ * As dlist_delete but performs checks in ILIST_DEBUG to ensure that 'node'
+ * belongs to 'head'.
I think 'Same as dlist_delete' instead of just 'As dlist_delete'

5.
+ * Caution: 'node' must be a member of 'head'.
+ * Caller must ensure that 'before' is a member of 'head'.
Can we have the same comments around something like below?
+ * Caller must ensure that 'node' must be a member of 'head'.
+ * Caller must ensure that 'before' is a member of 'head'.
or
+ * Caution: 'node' must be a member of 'head'.
+ * Caution: 'before' must be a member of 'head'.
or
* Caution: unreliable if 'node' is not in the list.
* Caution: unreliable if 'before' is not in the list.

6.
+dclist_has_prev(dclist_head *head, dlist_node *node)
+{
+ dlist_member_check(&head->dlist, node);
+
+ Assert(head->count > 0);

+ Assert(head->count > 0);
+
+ return (dlist_node *) dlist_head_element_off(&head->dlist, 0);

+ Assert(head->count > 0);
+
+ return (dlist_node *) dlist_tail_element_off(&head->dlist, 0);

+ Assert(!dclist_is_empty(head));
+ return (char *) head->dlist.head.next - off;

+ dlist_member_check(&head->dlist, node);
+
+ Assert(head->count > 0);
+
+ return dlist_has_prev(&head->dlist, node);

+ dlist_member_check(&head->dlist, node);
+ Assert(head->count > 0);
+
+ return dlist_has_next(&head->dlist, node);

Remove extra lines in between and have them uniformly across,
something like below?

dlist_member_check();
Assert();

return XXX;

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?

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