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 bcb14f4

Browse filesBrowse files
Make binaryheap enlargeable.
The node array space of the binaryheap is doubled when there is no available space. Reviewed-by: Vignesh C, Peter Smith, Hayato Kuroda, Ajin Cherian, Tomas Vondra, Shubham Khanna Discussion: https://postgr.es/m/CAD21AoDffo37RC-eUuyHJKVEr017V2YYDLyn1xF_00ofptWbkg%40mail.gmail.com
1 parent 2c91e13 commit bcb14f4
Copy full SHA for bcb14f4

File tree

Expand file treeCollapse file tree

2 files changed

+28
-25
lines changed
Filter options
Expand file treeCollapse file tree

2 files changed

+28
-25
lines changed

‎src/common/binaryheap.c

Copy file name to clipboardExpand all lines: src/common/binaryheap.c
+26-23Lines 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 heap that has the capacity to
34-
* store the given number of nodes, with the heap property defined by
35-
* the given comparator function, which will be invoked with the additional
36-
* argument specified by 'arg'.
33+
* Returns a pointer to a newly-allocated heap with the given initial number
34+
* of nodes, and with 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(int capacity, binaryheap_comparator compare, void *arg)
39+
binaryheap_allocate(int num_nodes, binaryheap_comparator compare, void *arg)
4040
{
41-
int sz;
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
return heap;
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+
static void
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_type d)
117128
{
129+
/* make sure enough space for a new node */
118130
if (heap->bh_size >= heap->bh_space)
119-
{
120-
#ifdef FRONTEND
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_type d)
155162
{
163+
/* make sure enough space for a new node */
156164
if (heap->bh_size >= heap->bh_space)
157-
{
158-
#ifdef FRONTEND
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

Copy file name to clipboardExpand all lines: src/include/lib/binaryheap.h
+2-2Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -46,10 +46,10 @@ typedef struct binaryheap
4646
bool bh_has_heap_property; /* debugging cross-check */
4747
binaryheap_comparator bh_compare;
4848
void *bh_arg;
49-
bh_node_type bh_nodes[FLEXIBLE_ARRAY_MEMBER];
49+
bh_node_type *bh_nodes;
5050
} binaryheap;
5151

52-
extern binaryheap *binaryheap_allocate(int capacity,
52+
extern binaryheap *binaryheap_allocate(int num_nodes,
5353
binaryheap_comparator compare,
5454
void *arg);
5555
extern void binaryheap_reset(binaryheap *heap);

0 commit comments

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