Hi Shihao,
Thanks for your review.
> 1. With ST_COMPARE_RUNTIME_POINTER the typedef
> uses const ST_ELEMENT_TYPE *, which for Item * becomes const Item **,
> so a comparator taking Item *const * warns. ST_ELEMENT_TYPE const *
> fixes it.
>
> 2. tbm_comparator() lost its const. It can take
> PagetableEntry *const *.
This makes it a const pointer to a pointer to a PagetableEntry. So the
PagetableEntry can still be modified through the pointer. The main use
of consting the pointer arguments is guaranteeing the compiler that the
function doesn't modify them. FWICS, this is not the case with what you
propose.
We would need const PagetableEntry *const *lpage but with that
compilation fails because sort_template.h wants to pass PagetableEntry
** which cannot be converted implicitly.
What I ended up doing is dereferencing the double pointer here:
#define ST_COMPARE(a, b) tbm_comparator(*(a), *(b))
Now we can use tbm_comparator(const PagetableEntry *lpage, ...). This
way we can also call tbm_comparator() from tbm_comparator_shared() which
is neat.
> 3. The common/int.h include in tidbitmap.c is now unused.
Done.
> 4. tbm_shared_comparator() is missing inline in its definition.
Done.
Attached is patch set v3.
--
David Geier
From 2cc3a738100342b05280d3b44aaaf2e4aca6fbb0 Mon Sep 17 00:00:00 2001
From: David Geier <[email protected]>
Date: Tue, 13 Oct 2026 13:36:22 +0200
Subject: [PATCH v3 2/2] TIDBitmap uses sort_template.h for pagetable sorting
Generate specialized sort functions for the pagetable instead of
going through generic qsort()/qsort_arg() comparator calls. The
inlined comparator avoids function call overhead per comparison.
The shared-iteration index arrays need the pagetable base address
to resolve indexes to entries, so that variant uses
ST_COMPARE_ARG_TYPE to pass it through.
---
src/backend/nodes/tidbitmap.c | 66 ++++++++++++++++++++---------------
1 file changed, 37 insertions(+), 29 deletions(-)
diff --git a/src/backend/nodes/tidbitmap.c b/src/backend/nodes/tidbitmap.c
index f1f925cb13b..0753942f464 100644
--- a/src/backend/nodes/tidbitmap.c
+++ b/src/backend/nodes/tidbitmap.c
@@ -42,7 +42,6 @@
#include "access/htup_details.h"
#include "common/hashfn.h"
-#include "common/int.h"
#include "nodes/bitmapset.h"
#include "nodes/tidbitmap.h"
#include "storage/lwlock.h"
@@ -225,9 +224,10 @@ static PagetableEntry *tbm_get_pageentry(TIDBitmap *tbm, BlockNumber pageno);
static bool tbm_page_is_lossy(const TIDBitmap *tbm, BlockNumber pageno);
static void tbm_mark_page_lossy(TIDBitmap *tbm, BlockNumber pageno);
static void tbm_lossify(TIDBitmap *tbm);
-static int tbm_comparator(const void *left, const void *right);
-static int tbm_shared_comparator(const void *left, const void *right,
- void *arg);
+static inline int tbm_comparator(const PagetableEntry *lpage,
+ const PagetableEntry *rpage);
+static inline int tbm_shared_comparator(const int *lindex, const int *rindex,
+ const PagetableEntry *base);
/* define hashtable mapping block numbers to PagetableEntry's */
#define SH_USE_NONDEFAULT_ALLOCATOR
@@ -242,6 +242,25 @@ static int tbm_shared_comparator(const void *left, const void *right,
#define SH_DECLARE
#include "lib/simplehash.h"
+#define ST_SORT qsort_pagetable
+#define ST_ELEMENT_TYPE PagetableEntry *
+#define ST_COMPARE(a, b) tbm_comparator(*(a), *(b))
+#define ST_SCOPE static
+#define ST_DEFINE
+#include "lib/sort_template.h"
+
+/*
+ * The shared-iteration arrays contain indexes into the pagetable entry
+ * array rather than pointers, so their comparator needs the base address
+ * of the entry array passed through as an argument.
+ */
+#define ST_SORT qsort_pagetable_index
+#define ST_ELEMENT_TYPE int
+#define ST_COMPARE(a, b, arg) tbm_shared_comparator(a, b, arg)
+#define ST_COMPARE_ARG_TYPE PagetableEntry
+#define ST_SCOPE static
+#define ST_DEFINE
+#include "lib/sort_template.h"
/*
* tbm_create - create an initially-empty bitmap
@@ -727,11 +746,9 @@ tbm_begin_private_iterate(TIDBitmap *tbm)
Assert(npages == tbm->npages);
Assert(nchunks == tbm->nchunks);
if (npages > 1)
- qsort(tbm->spages, npages, sizeof(PagetableEntry *),
- tbm_comparator);
+ qsort_pagetable(tbm->spages, npages);
if (nchunks > 1)
- qsort(tbm->schunks, nchunks, sizeof(PagetableEntry *),
- tbm_comparator);
+ qsort_pagetable(tbm->schunks, nchunks);
}
tbm->iterating = TBM_ITERATING_PRIVATE;
@@ -840,11 +857,9 @@ tbm_prepare_shared_iterate(TIDBitmap *tbm)
if (ptbase != NULL)
pg_atomic_init_u32(&ptbase->refcount, 0);
if (npages > 1)
- qsort_arg(ptpages->index, npages, sizeof(int),
- tbm_shared_comparator, ptbase->ptentry);
+ qsort_pagetable_index(ptpages->index, npages, ptbase->ptentry);
if (nchunks > 1)
- qsort_arg(ptchunks->index, nchunks, sizeof(int),
- tbm_shared_comparator, ptbase->ptentry);
+ qsort_pagetable_index(ptchunks->index, nchunks, ptbase->ptentry);
}
/*
@@ -1421,13 +1436,14 @@ tbm_lossify(TIDBitmap *tbm)
/*
* qsort comparator to handle PagetableEntry pointers.
*/
-static int
-tbm_comparator(const void *left, const void *right)
+static inline int
+tbm_comparator(const PagetableEntry *lpage, const PagetableEntry *rpage)
{
- BlockNumber l = (*((PagetableEntry *const *) left))->blockno;
- BlockNumber r = (*((PagetableEntry *const *) right))->blockno;
-
- return pg_cmp_u32(l, r);
+ if (lpage->blockno < rpage->blockno)
+ return -1;
+ else if (lpage->blockno > rpage->blockno)
+ return 1;
+ return 0;
}
/*
@@ -1435,18 +1451,10 @@ tbm_comparator(const void *left, const void *right)
* it needs to get actual PagetableEntry using the index before comparing the
* blockno.
*/
-static int
-tbm_shared_comparator(const void *left, const void *right, void *arg)
+static inline int
+tbm_shared_comparator(const int *lindex, const int *rindex, const PagetableEntry *base)
{
- PagetableEntry *base = (PagetableEntry *) arg;
- PagetableEntry *lpage = &base[*(const int *) left];
- PagetableEntry *rpage = &base[*(const int *) right];
-
- if (lpage->blockno < rpage->blockno)
- return -1;
- else if (lpage->blockno > rpage->blockno)
- return 1;
- return 0;
+ return tbm_comparator(&base[*lindex], &base[*rindex]);
}
/*
--
2.53.0
From 763cffbad4f90cb75b703b7483772f2e475d2842 Mon Sep 17 00:00:00 2001
From: David Geier <[email protected]>
Date: Wed, 14 Oct 2026 14:17:42 +0200
Subject: [PATCH v3 1/2] sort_template.h supports pointer element types
Changed the ST_POINTER_TYPE variable declarations in ST_SORT()
to work with ST_ELEMENT_TYPEs which are pointers.
---
src/include/lib/sort_template.h | 16 ++++++++--------
1 file changed, 8 insertions(+), 8 deletions(-)
diff --git a/src/include/lib/sort_template.h b/src/include/lib/sort_template.h
index 22b2092d03b..eae2d80270f 100644
--- a/src/include/lib/sort_template.h
+++ b/src/include/lib/sort_template.h
@@ -294,14 +294,14 @@ ST_SORT(ST_ELEMENT_TYPE * data, size_t n
ST_SORT_PROTO_COMPARE
ST_SORT_PROTO_ARG)
{
- ST_POINTER_TYPE *a = (ST_POINTER_TYPE *) data,
- *pa,
- *pb,
- *pc,
- *pd,
- *pl,
- *pm,
- *pn;
+ ST_POINTER_TYPE *a = (ST_POINTER_TYPE *) data;
+ ST_POINTER_TYPE *pa;
+ ST_POINTER_TYPE *pb;
+ ST_POINTER_TYPE *pc;
+ ST_POINTER_TYPE *pd;
+ ST_POINTER_TYPE *pl;
+ ST_POINTER_TYPE *pm;
+ ST_POINTER_TYPE *pn;
size_t d1,
d2;
int r,
--
2.53.0
