1 files changed, 240 insertions, 0 deletions
diff --git a/subversion/tests/libsvn_subr/priority-queue-test.c b/subversion/tests/libsvn_subr/priority-queue-test.c
new file mode 100644
index 0000000..bd2d991
--- /dev/null
+++ b/subversion/tests/libsvn_subr/priority-queue-test.c
@@ -0,0 +1,240 @@
+/*
+ * priority-queue-test.c:  a collection of svn_priority_queue__* tests
+ *
+ * ====================================================================
+ *    Licensed to the Apache Software Foundation (ASF) under one
+ *    or more contributor license agreements.  See the NOTICE file
+ *    distributed with this work for additional information
+ *    regarding copyright ownership.  The ASF licenses this file
+ *    to you under the Apache License, Version 2.0 (the
+ *    "License"); you may not use this file except in compliance
+ *    with the License.  You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ *    Unless required by applicable law or agreed to in writing,
+ *    software distributed under the License is distributed on an
+ *    "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ *    KIND, either express or implied.  See the License for the
+ *    specific language governing permissions and limitations
+ *    under the License.
+ * ====================================================================
+ */
+
+/* ====================================================================
+   To add tests, look toward the bottom of this file.
+
+*/
+
+
+
+#include <stdio.h>
+#include <string.h>
+#include <apr_pools.h>
+
+#include "../svn_test.h"
+
+#include "svn_error.h"
+#include "private/svn_sorts_private.h"
+
+/* priority queue test:
+ * items in the queue are simple integers, in ascending order */
+
+/* number of items to put into the queue */
+enum {NUMBER_COUNT = 11};
+
+/* the actual values in the order we add them to the queue */
+static const int numbers[NUMBER_COUNT]
+  = { 8395, 0, -1, 3885, 1,  -435, 99993, 10, 0, 1,  8395 };
+
+/* test_update will modify in-queue data and expects the queue to return
+   the values in the following order: */
+static const int expected_modified[NUMBER_COUNT]
+  = { -431, 0, 1, 3,  5, 10, 16, 3889, 8395, 8403,  99997 };
+
+/* standard compare function for integers */
+static int
+compare_func(const void *lhs, const void *rhs)
+{
+  return *(const int *)lhs - *(const int *)rhs;
+}
+
+/* Check that QUEUE is empty and the usual operations still work */
+static svn_error_t *
+verify_empty_queue(svn_priority_queue__t *queue)
+{
+  /* it's an empty queue */
+  SVN_TEST_ASSERT(svn_priority_queue__size(queue) == 0);
+  SVN_TEST_ASSERT(svn_priority_queue__peek(queue) == NULL);
+
+  /* these should be no-ops */
+  svn_priority_queue__update(queue);
+  svn_priority_queue__pop(queue);
+
+  return SVN_NO_ERROR;
+}
+
+/* check that the tip of QUEUE equals EXPECTED and remove the first element */
+static svn_error_t *
+extract_expected(svn_priority_queue__t *queue, int expected)
+{
+  int value = *(int *)svn_priority_queue__peek(queue);
+  SVN_TEST_ASSERT(value == expected);
+  svn_priority_queue__pop(queue);
+
+  return SVN_NO_ERROR;
+}
+
+/* Verify that QUEUE returns all elements in the proper order.
+   Also check that data can be added & removed without disturbing the order.
+ */
+static svn_error_t *
+verify_queue_order(svn_priority_queue__t *queue)
+{
+  int sorted[NUMBER_COUNT];
+  int i;
+
+  /* reference order */
+  memcpy(sorted, numbers, sizeof(numbers));
+  qsort(sorted, NUMBER_COUNT, sizeof(sorted[0]), compare_func);
+
+  /* verify that the queue returns the data in the same order */
+  for (i = 0; i < NUMBER_COUNT; ++i)
+    {
+      int item = *(int *)svn_priority_queue__peek(queue);
+      int to_insert;
+
+      /* is this the value we expected? */
+      SVN_TEST_ASSERT(item == sorted[i]);
+
+      /* add two items at the tip of the queue */
+      to_insert = item - 1;
+      svn_priority_queue__push(queue, &to_insert);
+      svn_priority_queue__push(queue, &item);
+
+      /* check queue length */
+      SVN_TEST_ASSERT(svn_priority_queue__size(queue) == NUMBER_COUNT-i+2);
+
+      /* now, lets extract all 3 of them */
+      SVN_ERR(extract_expected(queue, item-1));
+      SVN_ERR(extract_expected(queue, item));
+      SVN_ERR(extract_expected(queue, item));
+
+      /* check queue length */
+      SVN_TEST_ASSERT(svn_priority_queue__size(queue) == NUMBER_COUNT-i-1);
+    }
+
+  /* the queue should now be empty */
+  verify_empty_queue(queue);
+
+  return SVN_NO_ERROR;
+}
+
+/* return a queue allocated in POOL containing all items of NUMBERS */
+static svn_priority_queue__t *
+create_standard_queue(apr_pool_t *pool)
+{
+  apr_array_header_t *elements
+    = apr_array_make(pool, 11, sizeof(numbers[0]));
+
+  /* build queue */
+  int i;
+  for (i = 0; i < NUMBER_COUNT; ++i)
+    APR_ARRAY_PUSH(elements, int) = numbers[i];
+
+  return svn_priority_queue__create(elements, compare_func);
+}
+
+
+static svn_error_t *
+test_empty_queue(apr_pool_t *pool)
+{
+  apr_array_header_t *elements
+    = apr_array_make(pool, 0, sizeof(int));
+  svn_priority_queue__t *queue
+    = svn_priority_queue__create(elements, compare_func);
+
+  verify_empty_queue(queue);
+
+  return SVN_NO_ERROR;
+}
+
+static svn_error_t *
+test_sort_queue(apr_pool_t *pool)
+{
+  svn_priority_queue__t *queue = create_standard_queue(pool);
+
+  /* data should come out of the queue in sorted order */
+  SVN_ERR(verify_queue_order(queue));
+
+  return SVN_NO_ERROR;
+}
+
+static svn_error_t *
+test_push(apr_pool_t *pool)
+{
+  apr_array_header_t *elements
+    = apr_array_make(pool, 3, sizeof(int));
+  svn_priority_queue__t *queue
+    = svn_priority_queue__create(elements, compare_func);
+
+  /* build queue */
+  int i;
+  for (i = 0; i < NUMBER_COUNT; ++i)
+    svn_priority_queue__push(queue, &numbers[i]);
+
+  /* data should come out of the queue in sorted order */
+  SVN_ERR(verify_queue_order(queue));
+
+  return SVN_NO_ERROR;
+}
+
+static svn_error_t *
+test_update(apr_pool_t *pool)
+{
+  svn_priority_queue__t *queue = create_standard_queue(pool);
+
+  /* modify all items in the queue */
+  int i;
+  for (i = 0; i < NUMBER_COUNT; ++i)
+    {
+      int *tip = svn_priority_queue__peek(queue);
+      *tip += 4;
+      svn_priority_queue__update(queue);
+
+      /* extract and verify tip */
+      SVN_TEST_ASSERT(*(int *)svn_priority_queue__peek(queue)
+                      == expected_modified[i]);
+      svn_priority_queue__pop(queue);
+
+      /* this should be a no-op now */
+      svn_priority_queue__update(queue);
+
+      SVN_TEST_ASSERT(svn_priority_queue__size(queue) == NUMBER_COUNT-i-1);
+    }
+
+  /* the queue should now be empty */
+  verify_empty_queue(queue);
+
+  return SVN_NO_ERROR;
+}
+
+/* An array of all test functions */
+
+static int max_threads = 1;
+
+static struct svn_test_descriptor_t test_funcs[] =
+  {
+    SVN_TEST_NULL,
+    SVN_TEST_PASS2(test_empty_queue,
+                   "test empty queue"),
+    SVN_TEST_PASS2(test_sort_queue,
+                   "data returned by a priority queue shall be ordered"),
+    SVN_TEST_PASS2(test_push,
+                   "priority queues can be built up incrementally"),
+    SVN_TEST_PASS2(test_update,
+                   "updating the head of the queue"),
+    SVN_TEST_NULL
+  };
+
+SVN_TEST_MAIN