pg.ddx.io  pgsql-committers@postgresql.org mailing list archive  
help / color / mirror / Atom feed
From: David Rowley <drowley@postgresql.org>
To: pgsql-committers@lists.postgresql.org
Subject: pgsql: Add doubly linked count list implementation
Date: Wed, 02 Nov 2022 01:07:30 +0000
Message-ID: <E1oq2E6-0002Cq-8b@gemulon.postgresql.org> (raw)

Add doubly linked count list implementation

We have various requirements when using a dlist_head to keep track of the
number of items in the list.  This, traditionally, has been done by
maintaining a counter variable in the calling code.  Here we tidy this up
by adding "dclist", which is very similar to dlist but also keeps track of
the number of items stored in the list.

Callers may use the new dclist_count() function when they need to know how
many items are stored. Obtaining the count is an O(1) operation.

For simplicity reasons, dclist and dlist both use dlist_node as their node
type and dlist_iter/dlist_mutable_iter as their iterator type. dclists
have all of the same functionality as dlists except there is no function
named dclist_delete().  To remove an item from a list dclist_delete_from()
must be used.  This requires knowing which dclist the given item is stored
in.

Additionally, here we also convert some dlists where additional code
exists to keep track of the number of items stored and to make these use
dclists instead.

Author: David Rowley
Reviewed-by: Bharath Rupireddy, Aleksander Alekseev
Discussion: https://postgr.es/m/CAApHDvrtVxr+FXEX0VbViCFKDGxA3tWDgw9oFewNXCJMmwLjLg@mail.gmail.com

Branch
------
master

Details
-------
https://git.postgresql.org/pg/commitdiff/7c335b7a20278079e796d62122ef4b821c7fcdf5

Modified Files
--------------
src/backend/access/heap/rewriteheap.c           |  25 +-
src/backend/access/transam/multixact.c          |  34 +--
src/backend/lib/ilist.c                         |  17 ++
src/backend/replication/logical/reorderbuffer.c |  35 +--
src/backend/replication/logical/snapbuild.c     |   2 +-
src/backend/utils/activity/pgstat_xact.c        |  40 +--
src/backend/utils/adt/ri_triggers.c             |  19 +-
src/include/lib/ilist.h                         | 376 +++++++++++++++++++++++-
src/include/replication/reorderbuffer.h         |   3 +-
src/include/utils/pgstat_internal.h             |   3 +-
src/tools/pgindent/typedefs.list                |   3 +-
11 files changed, 448 insertions(+), 109 deletions(-)



Message-ID: <E1oq2E6-0002Cq-8b@gemulon.postgresql.org>
Permalink:  ../E1oq2E6-0002Cq-8b@gemulon.postgresql.org/
Also on:    postgresql.org/message-id/E1oq2E6-0002Cq-8b@gemulon.postgresql.org

 · 

reply

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Reply to all the recipients from your mail client; the link fills in
  the headers below: reply via email
  Some clients, webmail especially, drop In-Reply-To and References from
  a link, and the reply then starts a new thread: use the mbox below.

  To: pgsql-committers@postgresql.org
  Cc: drowley@postgresql.org
  Subject: Re: pgsql: Add doubly linked count list implementation
  In-Reply-To: <E1oq2E6-0002Cq-8b@gemulon.postgresql.org>
  References: <E1oq2E6-0002Cq-8b@gemulon.postgresql.org>

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox