Merge branch 'rs/pop-recent-commit-with-prio-queue' into next

The pop_most_recent_commit() function can have quite expensive
worst case performance characteristics, which has been optimized by
using prio-queue data structure.

* rs/pop-recent-commit-with-prio-queue:
  commit: use prio_queue_replace() in pop_most_recent_commit()
  prio-queue: add prio_queue_replace()
  commit: convert pop_most_recent_commit() to prio_queue

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 }));
+}