diff options
| author | René Scharfe <l.s.r@web.de> | 2025-07-18 11:39:14 +0200 |
|---|---|---|
| committer | Junio C Hamano <gitster@pobox.com> | 2025-07-22 07:28:35 -0700 |
| commit | 3d5091d232ea991a6a991c86e9fb000f5a9009a0 (patch) | |
| tree | cbc48f1816bea87ac7f374d11029cfa1a725a0ff /t/unit-tests/u-prio-queue.c | |
| parent | d6ec08788e667d4f556e9c2d97bbd7adb7e582be (diff) | |
| download | git-3d5091d232ea991a6a991c86e9fb000f5a9009a0.tar.gz | |
prio-queue: add prio_queue_replace()
Add a function to replace the top element of the queue that basically
does the same as prio_queue_get() followed by prio_queue_put(), but
without the work by prio_queue_get() to rebalance the heap. It can be
used to optimize loops that get one element and then immediately add
another one. That's common e.g., with commit history traversal, where
we get out a commit and then put in its parents.
Signed-off-by: René Scharfe <l.s.r@web.de>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
Diffstat (limited to 't/unit-tests/u-prio-queue.c')
| -rw-r--r-- | t/unit-tests/u-prio-queue.c | 23 |
1 files changed, 23 insertions, 0 deletions
diff --git a/t/unit-tests/u-prio-queue.c b/t/unit-tests/u-prio-queue.c index 145e689c9c..63e58114ae 100644 --- a/t/unit-tests/u-prio-queue.c +++ b/t/unit-tests/u-prio-queue.c @@ -13,6 +13,7 @@ static int intcmp(const void *va, const void *vb, void *data UNUSED) #define STACK -3 #define GET -4 #define REVERSE -5 +#define REPLACE -6 static int show(int *v) { @@ -51,6 +52,15 @@ static void test_prio_queue(int *input, size_t input_size, case REVERSE: prio_queue_reverse(&pq); break; + case REPLACE: + peek = prio_queue_peek(&pq); + cl_assert(i + 1 < input_size); + cl_assert(input[i + 1] >= 0); + cl_assert(j < result_size); + cl_assert_equal_i(result[j], show(peek)); + j++; + prio_queue_replace(&pq, &input[++i]); + break; default: prio_queue_put(&pq, &input[i]); break; @@ -81,6 +91,13 @@ void test_prio_queue__empty(void) ((int []){ 1, 2, MISSING, 1, 2, MISSING })); } +void test_prio_queue__replace(void) +{ + TEST_INPUT(((int []){ REPLACE, 6, 2, 4, REPLACE, 5, 7, GET, + REPLACE, 1, DUMP }), + ((int []){ MISSING, 2, 4, 5, 1, 6, 7 })); +} + void test_prio_queue__stack(void) { TEST_INPUT(((int []){ STACK, 8, 1, 5, 4, 6, 2, 3, DUMP }), @@ -92,3 +109,9 @@ void test_prio_queue__reverse_stack(void) TEST_INPUT(((int []){ STACK, 1, 2, 3, 4, 5, 6, REVERSE, DUMP }), ((int []){ 1, 2, 3, 4, 5, 6 })); } + +void test_prio_queue__replace_stack(void) +{ + TEST_INPUT(((int []){ STACK, 8, 1, 5, REPLACE, 4, 6, 2, 3, DUMP }), + ((int []){ 5, 3, 2, 6, 4, 1, 8 })); +} |