Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly
Appearance settings

Commit 5af0263

Browse filesBrowse files
nathan-bossartnathan-bossart
committed
Make binaryheap available to frontend code.
There are a couple of places in frontend code that could make use of this simple binary heap implementation. This commit makes binaryheap usable in frontend code, much like commit 26aaf97 did for StringInfo. Like StringInfo, the header file is left in lib/ to reduce the likelihood of unnecessary breakage. The frontend version of binaryheap exposes a void *-based API since frontend code does not have access to the Datum definitions. This seemed like a better approach than switching all existing uses to void * or making the Datum definitions available to frontend code. Reviewed-by: Tom Lane, Alvaro Herrera Discussion: https://postgr.es/m/3612876.1689443232%40sss.pgh.pa.us
1 parent f73fa5a commit 5af0263
Copy full SHA for 5af0263

File tree

Expand file treeCollapse file tree

7 files changed

+52
-20
lines changed
Filter options
Expand file treeCollapse file tree

7 files changed

+52
-20
lines changed

‎src/backend/lib/Makefile

Copy file name to clipboardExpand all lines: src/backend/lib/Makefile
-1Lines changed: 0 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -13,7 +13,6 @@ top_builddir = ../../..
1313
include $(top_builddir)/src/Makefile.global
1414

1515
OBJS = \
16-
binaryheap.o \
1716
bipartite_match.o \
1817
bloomfilter.o \
1918
dshash.o \

‎src/backend/lib/meson.build

Copy file name to clipboardExpand all lines: src/backend/lib/meson.build
-1Lines changed: 0 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,6 @@
11
# Copyright (c) 2022-2023, PostgreSQL Global Development Group
22

33
backend_sources += files(
4-
'binaryheap.c',
54
'bipartite_match.c',
65
'bloomfilter.c',
76
'dshash.c',

‎src/common/Makefile

Copy file name to clipboardExpand all lines: src/common/Makefile
+1Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -48,6 +48,7 @@ LIBS += $(PTHREAD_LIBS)
4848
OBJS_COMMON = \
4949
archive.o \
5050
base64.o \
51+
binaryheap.o \
5152
checksum_helper.o \
5253
compression.o \
5354
config_info.o \

‎src/backend/lib/binaryheap.c renamed to ‎src/common/binaryheap.c

Copy file name to clipboardExpand all lines: src/common/binaryheap.c
+30-11Lines changed: 30 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -6,15 +6,22 @@
66
* Portions Copyright (c) 2012-2023, PostgreSQL Global Development Group
77
*
88
* IDENTIFICATION
9-
* src/backend/lib/binaryheap.c
9+
* src/common/binaryheap.c
1010
*
1111
*-------------------------------------------------------------------------
1212
*/
1313

14+
#ifdef FRONTEND
15+
#include "postgres_fe.h"
16+
#else
1417
#include "postgres.h"
18+
#endif
1519

1620
#include <math.h>
1721

22+
#ifdef FRONTEND
23+
#include "common/logging.h"
24+
#endif
1825
#include "lib/binaryheap.h"
1926

2027
static void sift_down(binaryheap *heap, int node_off);
@@ -34,7 +41,7 @@ binaryheap_allocate(int capacity, binaryheap_comparator compare, void *arg)
3441
int sz;
3542
binaryheap *heap;
3643

37-
sz = offsetof(binaryheap, bh_nodes) + sizeof(Datum) * capacity;
44+
sz = offsetof(binaryheap, bh_nodes) + sizeof(bh_node_type) * capacity;
3845
heap = (binaryheap *) palloc(sz);
3946
heap->bh_space = capacity;
4047
heap->bh_compare = compare;
@@ -106,10 +113,16 @@ parent_offset(int i)
106113
* afterwards.
107114
*/
108115
void
109-
binaryheap_add_unordered(binaryheap *heap, Datum d)
116+
binaryheap_add_unordered(binaryheap *heap, bh_node_type d)
110117
{
111118
if (heap->bh_size >= heap->bh_space)
119+
{
120+
#ifdef FRONTEND
121+
pg_fatal("out of binary heap slots");
122+
#else
112123
elog(ERROR, "out of binary heap slots");
124+
#endif
125+
}
113126
heap->bh_has_heap_property = false;
114127
heap->bh_nodes[heap->bh_size] = d;
115128
heap->bh_size++;
@@ -138,10 +151,16 @@ binaryheap_build(binaryheap *heap)
138151
* the heap property.
139152
*/
140153
void
141-
binaryheap_add(binaryheap *heap, Datum d)
154+
binaryheap_add(binaryheap *heap, bh_node_type d)
142155
{
143156
if (heap->bh_size >= heap->bh_space)
157+
{
158+
#ifdef FRONTEND
159+
pg_fatal("out of binary heap slots");
160+
#else
144161
elog(ERROR, "out of binary heap slots");
162+
#endif
163+
}
145164
heap->bh_nodes[heap->bh_size] = d;
146165
heap->bh_size++;
147166
sift_up(heap, heap->bh_size - 1);
@@ -154,7 +173,7 @@ binaryheap_add(binaryheap *heap, Datum d)
154173
* without modifying the heap. The caller must ensure that this
155174
* routine is not used on an empty heap. Always O(1).
156175
*/
157-
Datum
176+
bh_node_type
158177
binaryheap_first(binaryheap *heap)
159178
{
160179
Assert(!binaryheap_empty(heap) && heap->bh_has_heap_property);
@@ -169,10 +188,10 @@ binaryheap_first(binaryheap *heap)
169188
* that this routine is not used on an empty heap. O(log n) worst
170189
* case.
171190
*/
172-
Datum
191+
bh_node_type
173192
binaryheap_remove_first(binaryheap *heap)
174193
{
175-
Datum result;
194+
bh_node_type result;
176195

177196
Assert(!binaryheap_empty(heap) && heap->bh_has_heap_property);
178197

@@ -204,7 +223,7 @@ binaryheap_remove_first(binaryheap *heap)
204223
* sifting the new node down.
205224
*/
206225
void
207-
binaryheap_replace_first(binaryheap *heap, Datum d)
226+
binaryheap_replace_first(binaryheap *heap, bh_node_type d)
208227
{
209228
Assert(!binaryheap_empty(heap) && heap->bh_has_heap_property);
210229

@@ -221,7 +240,7 @@ binaryheap_replace_first(binaryheap *heap, Datum d)
221240
static void
222241
sift_up(binaryheap *heap, int node_off)
223242
{
224-
Datum node_val = heap->bh_nodes[node_off];
243+
bh_node_type node_val = heap->bh_nodes[node_off];
225244

226245
/*
227246
* Within the loop, the node_off'th array entry is a "hole" that
@@ -232,7 +251,7 @@ sift_up(binaryheap *heap, int node_off)
232251
{
233252
int cmp;
234253
int parent_off;
235-
Datum parent_val;
254+
bh_node_type parent_val;
236255

237256
/*
238257
* If this node is smaller than its parent, the heap condition is
@@ -264,7 +283,7 @@ sift_up(binaryheap *heap, int node_off)
264283
static void
265284
sift_down(binaryheap *heap, int node_off)
266285
{
267-
Datum node_val = heap->bh_nodes[node_off];
286+
bh_node_type node_val = heap->bh_nodes[node_off];
268287

269288
/*
270289
* Within the loop, the node_off'th array entry is a "hole" that

‎src/common/meson.build

Copy file name to clipboardExpand all lines: src/common/meson.build
+1Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -3,6 +3,7 @@
33
common_sources = files(
44
'archive.c',
55
'base64.c',
6+
'binaryheap.c',
67
'checksum_helper.c',
78
'compression.c',
89
'controldata_utils.c',

‎src/include/lib/binaryheap.h

Copy file name to clipboardExpand all lines: src/include/lib/binaryheap.h
+19-7Lines changed: 19 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -11,11 +11,23 @@
1111
#ifndef BINARYHEAP_H
1212
#define BINARYHEAP_H
1313

14+
/*
15+
* We provide a Datum-based API for backend code and a void *-based API for
16+
* frontend code (since the Datum definitions are not available to frontend
17+
* code). You should typically avoid using bh_node_type directly and instead
18+
* use Datum or void * as appropriate.
19+
*/
20+
#ifdef FRONTEND
21+
typedef void *bh_node_type;
22+
#else
23+
typedef Datum bh_node_type;
24+
#endif
25+
1426
/*
1527
* For a max-heap, the comparator must return <0 iff a < b, 0 iff a == b,
1628
* and >0 iff a > b. For a min-heap, the conditions are reversed.
1729
*/
18-
typedef int (*binaryheap_comparator) (Datum a, Datum b, void *arg);
30+
typedef int (*binaryheap_comparator) (bh_node_type a, bh_node_type b, void *arg);
1931

2032
/*
2133
* binaryheap
@@ -34,20 +46,20 @@ typedef struct binaryheap
3446
bool bh_has_heap_property; /* debugging cross-check */
3547
binaryheap_comparator bh_compare;
3648
void *bh_arg;
37-
Datum bh_nodes[FLEXIBLE_ARRAY_MEMBER];
49+
bh_node_type bh_nodes[FLEXIBLE_ARRAY_MEMBER];
3850
} binaryheap;
3951

4052
extern binaryheap *binaryheap_allocate(int capacity,
4153
binaryheap_comparator compare,
4254
void *arg);
4355
extern void binaryheap_reset(binaryheap *heap);
4456
extern void binaryheap_free(binaryheap *heap);
45-
extern void binaryheap_add_unordered(binaryheap *heap, Datum d);
57+
extern void binaryheap_add_unordered(binaryheap *heap, bh_node_type d);
4658
extern void binaryheap_build(binaryheap *heap);
47-
extern void binaryheap_add(binaryheap *heap, Datum d);
48-
extern Datum binaryheap_first(binaryheap *heap);
49-
extern Datum binaryheap_remove_first(binaryheap *heap);
50-
extern void binaryheap_replace_first(binaryheap *heap, Datum d);
59+
extern void binaryheap_add(binaryheap *heap, bh_node_type d);
60+
extern bh_node_type binaryheap_first(binaryheap *heap);
61+
extern bh_node_type binaryheap_remove_first(binaryheap *heap);
62+
extern void binaryheap_replace_first(binaryheap *heap, bh_node_type d);
5163

5264
#define binaryheap_empty(h) ((h)->bh_size == 0)
5365

‎src/tools/pgindent/typedefs.list

Copy file name to clipboardExpand all lines: src/tools/pgindent/typedefs.list
+1Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -3198,6 +3198,7 @@ bbstreamer_tar_archiver
31983198
bbstreamer_tar_parser
31993199
bbstreamer_zstd_frame
32003200
bgworker_main_type
3201+
bh_node_type
32013202
binaryheap
32023203
binaryheap_comparator
32033204
bitmapword

0 commit comments

Comments
0 (0)
Morty Proxy This is a proxified and sanitized view of the page, visit original site.