public inbox for [email protected]help / color / mirror / Atom feed
[PATCH v5 2/3] expand binaryheap api 9+ messages / 3 participants [nested] [flat]
* [PATCH v5 2/3] expand binaryheap api @ 2023-07-20 16:52 Nathan Bossart <[email protected]> 0 siblings, 0 replies; 9+ messages in thread From: Nathan Bossart @ 2023-07-20 16:52 UTC (permalink / raw) --- src/common/binaryheap.c | 29 +++++++++++++++++++++++++++++ src/include/lib/binaryheap.h | 3 +++ 2 files changed, 32 insertions(+) diff --git a/src/common/binaryheap.c b/src/common/binaryheap.c index a6be4b42ae..d24a61fd2b 100644 --- a/src/common/binaryheap.c +++ b/src/common/binaryheap.c @@ -211,6 +211,35 @@ binaryheap_remove_first(binaryheap *heap) return result; } +/* + * binaryheap_remove_node + * + * Removes the nth node from the heap. The caller must ensure that there are + * at least (n - 1) nodes in the heap. O(log n) worst case. + */ +void +binaryheap_remove_node(binaryheap *heap, int n) +{ + int cmp; + + Assert(!binaryheap_empty(heap) && heap->bh_has_heap_property); + Assert(n >= 0 && n < heap->bh_size); + + /* compare last node to the one that is being removed */ + cmp = heap->bh_compare(heap->bh_nodes[--heap->bh_size], + heap->bh_nodes[n], + heap->bh_arg); + + /* remove the last node, placing it in the vacated entry */ + heap->bh_nodes[n] = heap->bh_nodes[heap->bh_size]; + + /* sift as needed to preserve the heap property */ + if (cmp > 0) + sift_up(heap, n); + else if (cmp < 0) + sift_down(heap, n); +} + /* * binaryheap_replace_first * diff --git a/src/include/lib/binaryheap.h b/src/include/lib/binaryheap.h index ae0af68f0d..84c08d7ebb 100644 --- a/src/include/lib/binaryheap.h +++ b/src/include/lib/binaryheap.h @@ -56,8 +56,11 @@ extern void binaryheap_build(binaryheap *heap); extern void binaryheap_add(binaryheap *heap, bh_elem_type d); extern bh_elem_type binaryheap_first(binaryheap *heap); extern bh_elem_type binaryheap_remove_first(binaryheap *heap); +extern void binaryheap_remove_node(binaryheap *heap, int n); extern void binaryheap_replace_first(binaryheap *heap, bh_elem_type d); #define binaryheap_empty(h) ((h)->bh_size == 0) +#define binaryheap_size(h) ((h)->bh_size) +#define binaryheap_get_node(h, n) ((h)->bh_nodes[n]) #endif /* BINARYHEAP_H */ -- 2.25.1 --3MwIy2ne0vdjdPXF Content-Type: text/x-diff; charset=us-ascii Content-Disposition: attachment; filename="v5-0003-use-priority-queue-for-pg_restore-ready_list.patch" ^ permalink raw reply [nested|flat] 9+ messages in thread
* [PATCH v3 3/4] expand binaryheap api @ 2023-07-20 16:52 Nathan Bossart <[email protected]> 0 siblings, 0 replies; 9+ messages in thread From: Nathan Bossart @ 2023-07-20 16:52 UTC (permalink / raw) --- src/common/binaryheap.c | 29 +++++++++++++++++++++++++++++ src/include/lib/binaryheap.h | 3 +++ 2 files changed, 32 insertions(+) diff --git a/src/common/binaryheap.c b/src/common/binaryheap.c index f21838b946..fdd8c0024a 100644 --- a/src/common/binaryheap.c +++ b/src/common/binaryheap.c @@ -211,6 +211,35 @@ binaryheap_remove_first(binaryheap *heap) return result; } +/* + * binaryheap_remove_node + * + * Removes the nth node from the heap. The caller must ensure that there are + * at least (n - 1) nodes in the heap. O(log n) worst case. + */ +void +binaryheap_remove_node(binaryheap *heap, int n) +{ + int cmp; + + Assert(!binaryheap_empty(heap) && heap->bh_has_heap_property); + Assert(n >= 0 && n < heap->bh_size); + + /* compare last node to the one that is being removed */ + cmp = heap->bh_compare(heap->bh_nodes[--heap->bh_size], + heap->bh_nodes[n], + heap->bh_arg); + + /* remove the last node, placing it in the vacated entry */ + heap->bh_nodes[n] = heap->bh_nodes[heap->bh_size]; + + /* sift as needed to preserve the heap property */ + if (cmp > 0) + sift_up(heap, n); + else if (cmp < 0) + sift_down(heap, n); +} + /* * binaryheap_replace_first * diff --git a/src/include/lib/binaryheap.h b/src/include/lib/binaryheap.h index 52f7b06b25..20a7f71244 100644 --- a/src/include/lib/binaryheap.h +++ b/src/include/lib/binaryheap.h @@ -47,8 +47,11 @@ extern void binaryheap_build(binaryheap *heap); extern void binaryheap_add(binaryheap *heap, Datum d); extern Datum binaryheap_first(binaryheap *heap); extern Datum binaryheap_remove_first(binaryheap *heap); +extern void binaryheap_remove_node(binaryheap *heap, int n); extern void binaryheap_replace_first(binaryheap *heap, Datum d); #define binaryheap_empty(h) ((h)->bh_size == 0) +#define binaryheap_size(h) ((h)->bh_size) +#define binaryheap_get_node(h, n) ((h)->bh_nodes[n]) #endif /* BINARYHEAP_H */ -- 2.25.1 --sdtB3X0nJg68CQEu Content-Type: text/x-diff; charset=us-ascii Content-Disposition: attachment; filename="v3-0004-use-priority-queue-for-pg_restore-ready_list.patch" ^ permalink raw reply [nested|flat] 9+ messages in thread
* [PATCH v4 3/4] expand binaryheap api @ 2023-07-20 16:52 Nathan Bossart <[email protected]> 0 siblings, 0 replies; 9+ messages in thread From: Nathan Bossart @ 2023-07-20 16:52 UTC (permalink / raw) --- src/common/binaryheap.c | 29 +++++++++++++++++++++++++++++ src/include/lib/binaryheap.h | 3 +++ 2 files changed, 32 insertions(+) diff --git a/src/common/binaryheap.c b/src/common/binaryheap.c index 400a730c85..aaf529d6a9 100644 --- a/src/common/binaryheap.c +++ b/src/common/binaryheap.c @@ -211,6 +211,35 @@ binaryheap_remove_first(binaryheap *heap) return result; } +/* + * binaryheap_remove_node + * + * Removes the nth node from the heap. The caller must ensure that there are + * at least (n - 1) nodes in the heap. O(log n) worst case. + */ +void +binaryheap_remove_node(binaryheap *heap, int n) +{ + int cmp; + + Assert(!binaryheap_empty(heap) && heap->bh_has_heap_property); + Assert(n >= 0 && n < heap->bh_size); + + /* compare last node to the one that is being removed */ + cmp = heap->bh_compare(heap->bh_nodes[--heap->bh_size], + heap->bh_nodes[n], + heap->bh_arg); + + /* remove the last node, placing it in the vacated entry */ + heap->bh_nodes[n] = heap->bh_nodes[heap->bh_size]; + + /* sift as needed to preserve the heap property */ + if (cmp > 0) + sift_up(heap, n); + else if (cmp < 0) + sift_down(heap, n); +} + /* * binaryheap_replace_first * diff --git a/src/include/lib/binaryheap.h b/src/include/lib/binaryheap.h index 71a25db0f4..06fe2ff213 100644 --- a/src/include/lib/binaryheap.h +++ b/src/include/lib/binaryheap.h @@ -47,8 +47,11 @@ extern void binaryheap_build(binaryheap *heap); extern void binaryheap_add(binaryheap *heap, void *d); extern void *binaryheap_first(binaryheap *heap); extern void *binaryheap_remove_first(binaryheap *heap); +extern void binaryheap_remove_node(binaryheap *heap, int n); extern void binaryheap_replace_first(binaryheap *heap, void *d); #define binaryheap_empty(h) ((h)->bh_size == 0) +#define binaryheap_size(h) ((h)->bh_size) +#define binaryheap_get_node(h, n) ((h)->bh_nodes[n]) #endif /* BINARYHEAP_H */ -- 2.25.1 --qMm9M+Fa2AknHoGS Content-Type: text/x-diff; charset=us-ascii Content-Disposition: attachment; filename="v4-0004-use-priority-queue-for-pg_restore-ready_list.patch" ^ permalink raw reply [nested|flat] 9+ messages in thread
* [PATCH v2 3/4] expand binaryheap api @ 2023-07-20 16:52 Nathan Bossart <[email protected]> 0 siblings, 0 replies; 9+ messages in thread From: Nathan Bossart @ 2023-07-20 16:52 UTC (permalink / raw) --- src/common/binaryheap.c | 28 ++++++++++++++++++++++++++++ src/include/lib/binaryheap.h | 3 +++ 2 files changed, 31 insertions(+) diff --git a/src/common/binaryheap.c b/src/common/binaryheap.c index 7a590eec4a..526e56bbd0 100644 --- a/src/common/binaryheap.c +++ b/src/common/binaryheap.c @@ -211,6 +211,34 @@ binaryheap_remove_first(binaryheap *heap) return result; } +/* + * binaryheap_remove_node + * + * Removes the given node from the heap. O(log n) worst case. + */ +void +binaryheap_remove_node(binaryheap *heap, int n) +{ + int cmp; + + Assert(!binaryheap_empty(heap) && heap->bh_has_heap_property); + Assert(n >= 0 && n < heap->bh_size); + + /* compare last node to the one that is being removed */ + cmp = heap->bh_compare(heap->bh_nodes[--heap->bh_size], + heap->bh_nodes[n], + heap->bh_arg); + + /* remove the last node, placing it in the vacated entry */ + heap->bh_nodes[n] = heap->bh_nodes[heap->bh_size]; + + /* sift as needed to preserve the heap property */ + if (cmp > 0) + sift_up(heap, n); + else if (cmp < 0) + sift_down(heap, n); +} + /* * binaryheap_replace_first * diff --git a/src/include/lib/binaryheap.h b/src/include/lib/binaryheap.h index 06e3878cf7..9f09aff29f 100644 --- a/src/include/lib/binaryheap.h +++ b/src/include/lib/binaryheap.h @@ -76,8 +76,11 @@ extern void binaryheap_build(binaryheap *heap); extern void binaryheap_add(binaryheap *heap, Datum d); extern Datum binaryheap_first(binaryheap *heap); extern Datum binaryheap_remove_first(binaryheap *heap); +extern void binaryheap_remove_node(binaryheap *heap, int n); extern void binaryheap_replace_first(binaryheap *heap, Datum d); #define binaryheap_empty(h) ((h)->bh_size == 0) +#define binaryheap_size(h) ((h)->bh_size) +#define binaryheap_get_node(h, n) ((h)->bh_nodes[n]) #endif /* BINARYHEAP_H */ -- 2.25.1 --qDbXVdCdHGoSgWSk Content-Type: text/x-diff; charset=us-ascii Content-Disposition: attachment; filename="v2-0004-use-priority-queue-for-pg_restore-ready_list.patch" ^ permalink raw reply [nested|flat] 9+ messages in thread
* [PATCH v3 3/4] expand binaryheap api @ 2023-07-20 16:52 Nathan Bossart <[email protected]> 0 siblings, 0 replies; 9+ messages in thread From: Nathan Bossart @ 2023-07-20 16:52 UTC (permalink / raw) --- src/common/binaryheap.c | 29 +++++++++++++++++++++++++++++ src/include/lib/binaryheap.h | 3 +++ 2 files changed, 32 insertions(+) diff --git a/src/common/binaryheap.c b/src/common/binaryheap.c index f21838b946..fdd8c0024a 100644 --- a/src/common/binaryheap.c +++ b/src/common/binaryheap.c @@ -211,6 +211,35 @@ binaryheap_remove_first(binaryheap *heap) return result; } +/* + * binaryheap_remove_node + * + * Removes the nth node from the heap. The caller must ensure that there are + * at least (n - 1) nodes in the heap. O(log n) worst case. + */ +void +binaryheap_remove_node(binaryheap *heap, int n) +{ + int cmp; + + Assert(!binaryheap_empty(heap) && heap->bh_has_heap_property); + Assert(n >= 0 && n < heap->bh_size); + + /* compare last node to the one that is being removed */ + cmp = heap->bh_compare(heap->bh_nodes[--heap->bh_size], + heap->bh_nodes[n], + heap->bh_arg); + + /* remove the last node, placing it in the vacated entry */ + heap->bh_nodes[n] = heap->bh_nodes[heap->bh_size]; + + /* sift as needed to preserve the heap property */ + if (cmp > 0) + sift_up(heap, n); + else if (cmp < 0) + sift_down(heap, n); +} + /* * binaryheap_replace_first * diff --git a/src/include/lib/binaryheap.h b/src/include/lib/binaryheap.h index 52f7b06b25..20a7f71244 100644 --- a/src/include/lib/binaryheap.h +++ b/src/include/lib/binaryheap.h @@ -47,8 +47,11 @@ extern void binaryheap_build(binaryheap *heap); extern void binaryheap_add(binaryheap *heap, Datum d); extern Datum binaryheap_first(binaryheap *heap); extern Datum binaryheap_remove_first(binaryheap *heap); +extern void binaryheap_remove_node(binaryheap *heap, int n); extern void binaryheap_replace_first(binaryheap *heap, Datum d); #define binaryheap_empty(h) ((h)->bh_size == 0) +#define binaryheap_size(h) ((h)->bh_size) +#define binaryheap_get_node(h, n) ((h)->bh_nodes[n]) #endif /* BINARYHEAP_H */ -- 2.25.1 --sdtB3X0nJg68CQEu Content-Type: text/x-diff; charset=us-ascii Content-Disposition: attachment; filename="v3-0004-use-priority-queue-for-pg_restore-ready_list.patch" ^ permalink raw reply [nested|flat] 9+ messages in thread
* [PATCH v5 2/3] expand binaryheap api @ 2023-07-20 16:52 Nathan Bossart <[email protected]> 0 siblings, 0 replies; 9+ messages in thread From: Nathan Bossart @ 2023-07-20 16:52 UTC (permalink / raw) --- src/common/binaryheap.c | 29 +++++++++++++++++++++++++++++ src/include/lib/binaryheap.h | 3 +++ 2 files changed, 32 insertions(+) diff --git a/src/common/binaryheap.c b/src/common/binaryheap.c index a6be4b42ae..d24a61fd2b 100644 --- a/src/common/binaryheap.c +++ b/src/common/binaryheap.c @@ -211,6 +211,35 @@ binaryheap_remove_first(binaryheap *heap) return result; } +/* + * binaryheap_remove_node + * + * Removes the nth node from the heap. The caller must ensure that there are + * at least (n - 1) nodes in the heap. O(log n) worst case. + */ +void +binaryheap_remove_node(binaryheap *heap, int n) +{ + int cmp; + + Assert(!binaryheap_empty(heap) && heap->bh_has_heap_property); + Assert(n >= 0 && n < heap->bh_size); + + /* compare last node to the one that is being removed */ + cmp = heap->bh_compare(heap->bh_nodes[--heap->bh_size], + heap->bh_nodes[n], + heap->bh_arg); + + /* remove the last node, placing it in the vacated entry */ + heap->bh_nodes[n] = heap->bh_nodes[heap->bh_size]; + + /* sift as needed to preserve the heap property */ + if (cmp > 0) + sift_up(heap, n); + else if (cmp < 0) + sift_down(heap, n); +} + /* * binaryheap_replace_first * diff --git a/src/include/lib/binaryheap.h b/src/include/lib/binaryheap.h index ae0af68f0d..84c08d7ebb 100644 --- a/src/include/lib/binaryheap.h +++ b/src/include/lib/binaryheap.h @@ -56,8 +56,11 @@ extern void binaryheap_build(binaryheap *heap); extern void binaryheap_add(binaryheap *heap, bh_elem_type d); extern bh_elem_type binaryheap_first(binaryheap *heap); extern bh_elem_type binaryheap_remove_first(binaryheap *heap); +extern void binaryheap_remove_node(binaryheap *heap, int n); extern void binaryheap_replace_first(binaryheap *heap, bh_elem_type d); #define binaryheap_empty(h) ((h)->bh_size == 0) +#define binaryheap_size(h) ((h)->bh_size) +#define binaryheap_get_node(h, n) ((h)->bh_nodes[n]) #endif /* BINARYHEAP_H */ -- 2.25.1 --3MwIy2ne0vdjdPXF Content-Type: text/x-diff; charset=us-ascii Content-Disposition: attachment; filename="v5-0003-use-priority-queue-for-pg_restore-ready_list.patch" ^ permalink raw reply [nested|flat] 9+ messages in thread
* [PATCH v2 3/4] expand binaryheap api @ 2023-07-20 16:52 Nathan Bossart <[email protected]> 0 siblings, 0 replies; 9+ messages in thread From: Nathan Bossart @ 2023-07-20 16:52 UTC (permalink / raw) --- src/common/binaryheap.c | 28 ++++++++++++++++++++++++++++ src/include/lib/binaryheap.h | 3 +++ 2 files changed, 31 insertions(+) diff --git a/src/common/binaryheap.c b/src/common/binaryheap.c index 7a590eec4a..526e56bbd0 100644 --- a/src/common/binaryheap.c +++ b/src/common/binaryheap.c @@ -211,6 +211,34 @@ binaryheap_remove_first(binaryheap *heap) return result; } +/* + * binaryheap_remove_node + * + * Removes the given node from the heap. O(log n) worst case. + */ +void +binaryheap_remove_node(binaryheap *heap, int n) +{ + int cmp; + + Assert(!binaryheap_empty(heap) && heap->bh_has_heap_property); + Assert(n >= 0 && n < heap->bh_size); + + /* compare last node to the one that is being removed */ + cmp = heap->bh_compare(heap->bh_nodes[--heap->bh_size], + heap->bh_nodes[n], + heap->bh_arg); + + /* remove the last node, placing it in the vacated entry */ + heap->bh_nodes[n] = heap->bh_nodes[heap->bh_size]; + + /* sift as needed to preserve the heap property */ + if (cmp > 0) + sift_up(heap, n); + else if (cmp < 0) + sift_down(heap, n); +} + /* * binaryheap_replace_first * diff --git a/src/include/lib/binaryheap.h b/src/include/lib/binaryheap.h index 06e3878cf7..9f09aff29f 100644 --- a/src/include/lib/binaryheap.h +++ b/src/include/lib/binaryheap.h @@ -76,8 +76,11 @@ extern void binaryheap_build(binaryheap *heap); extern void binaryheap_add(binaryheap *heap, Datum d); extern Datum binaryheap_first(binaryheap *heap); extern Datum binaryheap_remove_first(binaryheap *heap); +extern void binaryheap_remove_node(binaryheap *heap, int n); extern void binaryheap_replace_first(binaryheap *heap, Datum d); #define binaryheap_empty(h) ((h)->bh_size == 0) +#define binaryheap_size(h) ((h)->bh_size) +#define binaryheap_get_node(h, n) ((h)->bh_nodes[n]) #endif /* BINARYHEAP_H */ -- 2.25.1 --qDbXVdCdHGoSgWSk Content-Type: text/x-diff; charset=us-ascii Content-Disposition: attachment; filename="v2-0004-use-priority-queue-for-pg_restore-ready_list.patch" ^ permalink raw reply [nested|flat] 9+ messages in thread
* Re: pg_logical_emit_message() misses a XLogFlush() @ 2023-10-17 06:27 Amit Kapila <[email protected]> 0 siblings, 1 reply; 9+ messages in thread From: Amit Kapila @ 2023-10-17 06:27 UTC (permalink / raw) To: Michael Paquier <[email protected]>; +Cc: bt23nguyent <[email protected]>; Fujii Masao <[email protected]>; Andres Freund <[email protected]>; Tomas Vondra <[email protected]>; Postgres hackers <[email protected]> On Mon, Oct 16, 2023 at 12:47 PM Michael Paquier <[email protected]> wrote: > > On Fri, Oct 13, 2023 at 03:20:30PM +0530, Amit Kapila wrote: > > I would prefer to associate the new parameter 'flush' with > > non-transactional messages as per the proposed patch. > > Check. > > > Is there a reason to make the functions strict now when they were not earlier? > > These two are already STRICT on HEAD: > =# select proname, provolatile, proisstrict from pg_proc > where proname ~ 'message'; > proname | provolatile | proisstrict > -------------------------+-------------+------------- > pg_logical_emit_message | v | t > pg_logical_emit_message | v | t > (2 rows) > oh, I misunderstood the default. > > An updated version is attached. How does it look? > LGTM. -- With Regards, Amit Kapila. ^ permalink raw reply [nested|flat] 9+ messages in thread
* Re: pg_logical_emit_message() misses a XLogFlush() @ 2023-10-18 03:50 Michael Paquier <[email protected]> parent: Amit Kapila <[email protected]> 0 siblings, 0 replies; 9+ messages in thread From: Michael Paquier @ 2023-10-18 03:50 UTC (permalink / raw) To: Amit Kapila <[email protected]>; +Cc: bt23nguyent <[email protected]>; Fujii Masao <[email protected]>; Andres Freund <[email protected]>; Tomas Vondra <[email protected]>; Postgres hackers <[email protected]> On Tue, Oct 17, 2023 at 11:57:33AM +0530, Amit Kapila wrote: > LGTM. Thanks, I've applied that, then. -- Michael Attachments: [application/pgp-signature] signature.asc (833B, ../../[email protected]/2-signature.asc) download ^ permalink raw reply [nested|flat] 9+ messages in thread
end of thread, other threads:[~2023-10-18 03:50 UTC | newest] Thread overview: 9+ messages (download: mbox mbox.gz follow: Atom feed) -- links below jump to the message on this page -- 2023-07-20 16:52 [PATCH v5 2/3] expand binaryheap api Nathan Bossart <[email protected]> 2023-07-20 16:52 [PATCH v3 3/4] expand binaryheap api Nathan Bossart <[email protected]> 2023-07-20 16:52 [PATCH v2 3/4] expand binaryheap api Nathan Bossart <[email protected]> 2023-07-20 16:52 [PATCH v4 3/4] expand binaryheap api Nathan Bossart <[email protected]> 2023-07-20 16:52 [PATCH v5 2/3] expand binaryheap api Nathan Bossart <[email protected]> 2023-07-20 16:52 [PATCH v3 3/4] expand binaryheap api Nathan Bossart <[email protected]> 2023-07-20 16:52 [PATCH v2 3/4] expand binaryheap api Nathan Bossart <[email protected]> 2023-10-17 06:27 Re: pg_logical_emit_message() misses a XLogFlush() Amit Kapila <[email protected]> 2023-10-18 03:50 ` Re: pg_logical_emit_message() misses a XLogFlush() Michael Paquier <[email protected]>
This inbox is served by agora; see mirroring instructions for how to clone and mirror all data and code used for this inbox