Movatterモバイル変換

[0]ホーム
URL:

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

 Sign up
Appearance settings

Commit5af0263

Browse files
Make binaryheap available to frontend code.
There are a couple of places in frontend code that could make useof this simple binary heap implementation. This commit makesbinaryheap usable in frontend code, much like commit26aaf97 didfor 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 sincefrontend code does not have access to the Datum definitions. Thisseemed like a better approach than switching all existing uses tovoid * or making the Datum definitions available to frontend code.Reviewed-by: Tom Lane, Alvaro HerreraDiscussion:https://postgr.es/m/3612876.1689443232%40sss.pgh.pa.us
1 parentf73fa5a commit5af0263

File tree

7 files changed

+52
-20
lines changed

7 files changed

+52
-20
lines changed

‎src/backend/lib/Makefile

Lines 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

Lines 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

Lines 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.crenamed to‎src/common/binaryheap.c

Lines 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+
#ifdefFRONTEND
15+
#include"postgres_fe.h"
16+
#else
1417
#include"postgres.h"
18+
#endif
1519

1620
#include<math.h>
1721

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

2027
staticvoidsift_down(binaryheap*heap,intnode_off);
@@ -34,7 +41,7 @@ binaryheap_allocate(int capacity, binaryheap_comparator compare, void *arg)
3441
intsz;
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,Datumd)
116+
binaryheap_add_unordered(binaryheap*heap,bh_node_typed)
110117
{
111118
if (heap->bh_size >=heap->bh_space)
119+
{
120+
#ifdefFRONTEND
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,Datumd)
154+
binaryheap_add(binaryheap*heap,bh_node_typed)
142155
{
143156
if (heap->bh_size >=heap->bh_space)
157+
{
158+
#ifdefFRONTEND
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-
Datumresult;
194+
bh_node_typeresult;
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,Datumd)
226+
binaryheap_replace_first(binaryheap*heap,bh_node_typed)
208227
{
209228
Assert(!binaryheap_empty(heap)&&heap->bh_has_heap_property);
210229

@@ -221,7 +240,7 @@ binaryheap_replace_first(binaryheap *heap, Datum d)
221240
staticvoid
222241
sift_up(binaryheap*heap,intnode_off)
223242
{
224-
Datumnode_val=heap->bh_nodes[node_off];
243+
bh_node_typenode_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
intcmp;
234253
intparent_off;
235-
Datumparent_val;
254+
bh_node_typeparent_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
staticvoid
265284
sift_down(binaryheap*heap,intnode_off)
266285
{
267-
Datumnode_val=heap->bh_nodes[node_off];
286+
bh_node_typenode_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

Lines 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

Lines changed: 19 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -11,11 +11,23 @@
1111
#ifndefBINARYHEAP_H
1212
#defineBINARYHEAP_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+
#ifdefFRONTEND
21+
typedefvoid*bh_node_type;
22+
#else
23+
typedefDatumbh_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-
typedefint (*binaryheap_comparator) (Datuma,Datumb,void*arg);
30+
typedefint (*binaryheap_comparator) (bh_node_typea,bh_node_typeb,void*arg);
1931

2032
/*
2133
* binaryheap
@@ -34,20 +46,20 @@ typedef struct binaryheap
3446
boolbh_has_heap_property;/* debugging cross-check */
3547
binaryheap_comparatorbh_compare;
3648
void*bh_arg;
37-
Datumbh_nodes[FLEXIBLE_ARRAY_MEMBER];
49+
bh_node_typebh_nodes[FLEXIBLE_ARRAY_MEMBER];
3850
}binaryheap;
3951

4052
externbinaryheap*binaryheap_allocate(intcapacity,
4153
binaryheap_comparatorcompare,
4254
void*arg);
4355
externvoidbinaryheap_reset(binaryheap*heap);
4456
externvoidbinaryheap_free(binaryheap*heap);
45-
externvoidbinaryheap_add_unordered(binaryheap*heap,Datumd);
57+
externvoidbinaryheap_add_unordered(binaryheap*heap,bh_node_typed);
4658
externvoidbinaryheap_build(binaryheap*heap);
47-
externvoidbinaryheap_add(binaryheap*heap,Datumd);
48-
externDatumbinaryheap_first(binaryheap*heap);
49-
externDatumbinaryheap_remove_first(binaryheap*heap);
50-
externvoidbinaryheap_replace_first(binaryheap*heap,Datumd);
59+
externvoidbinaryheap_add(binaryheap*heap,bh_node_typed);
60+
externbh_node_typebinaryheap_first(binaryheap*heap);
61+
externbh_node_typebinaryheap_remove_first(binaryheap*heap);
62+
externvoidbinaryheap_replace_first(binaryheap*heap,bh_node_typed);
5163

5264
#definebinaryheap_empty(h)((h)->bh_size == 0)
5365

‎src/tools/pgindent/typedefs.list

Lines 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)
[8]ページ先頭
©2009-2025 Movatter.jp