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

Commitbcb14f4

Browse files
Make binaryheap enlargeable.
The node array space of the binaryheap is doubled when there is noavailable space.Reviewed-by: Vignesh C, Peter Smith, Hayato Kuroda, Ajin Cherian,Tomas Vondra, Shubham KhannaDiscussion:https://postgr.es/m/CAD21AoDffo37RC-eUuyHJKVEr017V2YYDLyn1xF_00ofptWbkg%40mail.gmail.com
1 parent2c91e13 commitbcb14f4

File tree

2 files changed

+28
-25
lines changed

2 files changed

+28
-25
lines changed

‎src/common/binaryheap.c

Lines changed: 26 additions & 23 deletions
Original file line numberDiff line numberDiff line change
@@ -30,25 +30,24 @@ static void sift_up(binaryheap *heap, int node_off);
3030
/*
3131
* binaryheap_allocate
3232
*
33-
* Returns a pointer to a newly-allocated heapthat hasthecapacity to
34-
*store the given numberof nodes, with the heap property defined by
35-
*the given comparatorfunction, which will be invoked with the additional
36-
*argument specified by'arg'.
33+
* Returns a pointer to a newly-allocated heapwiththegiven initial number
34+
* of nodes,andwith the heap property defined by the given comparator
35+
* function, which will be invoked with the additional argument specified by
36+
* 'arg'.
3737
*/
3838
binaryheap*
39-
binaryheap_allocate(intcapacity,binaryheap_comparatorcompare,void*arg)
39+
binaryheap_allocate(intnum_nodes,binaryheap_comparatorcompare,void*arg)
4040
{
41-
intsz;
4241
binaryheap*heap;
4342

44-
sz= offsetof(binaryheap,bh_nodes)+sizeof(bh_node_type)*capacity;
45-
heap= (binaryheap*)palloc(sz);
46-
heap->bh_space=capacity;
43+
heap= (binaryheap*)palloc(sizeof(binaryheap));
44+
heap->bh_space=num_nodes;
4745
heap->bh_compare=compare;
4846
heap->bh_arg=arg;
4947

5048
heap->bh_size=0;
5149
heap->bh_has_heap_property= true;
50+
heap->bh_nodes= (bh_node_type*)palloc(sizeof(bh_node_type)*num_nodes);
5251

5352
returnheap;
5453
}
@@ -74,6 +73,7 @@ binaryheap_reset(binaryheap *heap)
7473
void
7574
binaryheap_free(binaryheap*heap)
7675
{
76+
pfree(heap->bh_nodes);
7777
pfree(heap);
7878
}
7979

@@ -104,6 +104,17 @@ parent_offset(int i)
104104
return (i-1) /2;
105105
}
106106

107+
/*
108+
* Double the space allocated for nodes.
109+
*/
110+
staticvoid
111+
enlarge_node_array(binaryheap*heap)
112+
{
113+
heap->bh_space *=2;
114+
heap->bh_nodes=repalloc(heap->bh_nodes,
115+
sizeof(bh_node_type)*heap->bh_space);
116+
}
117+
107118
/*
108119
* binaryheap_add_unordered
109120
*
@@ -115,14 +126,10 @@ parent_offset(int i)
115126
void
116127
binaryheap_add_unordered(binaryheap*heap,bh_node_typed)
117128
{
129+
/* make sure enough space for a new node */
118130
if (heap->bh_size >=heap->bh_space)
119-
{
120-
#ifdefFRONTEND
121-
pg_fatal("out of binary heap slots");
122-
#else
123-
elog(ERROR,"out of binary heap slots");
124-
#endif
125-
}
131+
enlarge_node_array(heap);
132+
126133
heap->bh_has_heap_property= false;
127134
heap->bh_nodes[heap->bh_size]=d;
128135
heap->bh_size++;
@@ -153,14 +160,10 @@ binaryheap_build(binaryheap *heap)
153160
void
154161
binaryheap_add(binaryheap*heap,bh_node_typed)
155162
{
163+
/* make sure enough space for a new node */
156164
if (heap->bh_size >=heap->bh_space)
157-
{
158-
#ifdefFRONTEND
159-
pg_fatal("out of binary heap slots");
160-
#else
161-
elog(ERROR,"out of binary heap slots");
162-
#endif
163-
}
165+
enlarge_node_array(heap);
166+
164167
heap->bh_nodes[heap->bh_size]=d;
165168
heap->bh_size++;
166169
sift_up(heap,heap->bh_size-1);

‎src/include/lib/binaryheap.h

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -46,10 +46,10 @@ typedef struct binaryheap
4646
boolbh_has_heap_property;/* debugging cross-check */
4747
binaryheap_comparatorbh_compare;
4848
void*bh_arg;
49-
bh_node_typebh_nodes[FLEXIBLE_ARRAY_MEMBER];
49+
bh_node_type*bh_nodes;
5050
}binaryheap;
5151

52-
externbinaryheap*binaryheap_allocate(intcapacity,
52+
externbinaryheap*binaryheap_allocate(intnum_nodes,
5353
binaryheap_comparatorcompare,
5454
void*arg);
5555
externvoidbinaryheap_reset(binaryheap*heap);

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp