svn commit: r1508496 - in /subversion/branches/fsx: build.conf subversion/tests/libsvn_subr/priority-queue-test.c

[st...@apache.org]

Author: stefan2
Date: Tue Jul 30 15:44:18 2013
New Revision: 1508496

URL: http://svn.apache.org/r1508496
Log:
On the fsx branch:  Add a test for our priority queues API.

* build.conf
  (priority-queue-test): new target
  (__ALL_TESTS__): register the new target

* subversion/tests/libsvn_subr/priority-queue-test.c
  (): new file

Added:
    subversion/branches/fsx/subversion/tests/libsvn_subr/priority-queue-test.c
Modified:
    subversion/branches/fsx/build.conf

Modified: subversion/branches/fsx/build.conf
URL: http://svn.apache.org/viewvc/subversion/branches/fsx/build.conf?rev=1508496&r1=1508495&r2=1508496&view=diff
==============================================================================
--- subversion/branches/fsx/build.conf (original)
+++ subversion/branches/fsx/build.conf Tue Jul 30 15:44:18 2013
@@ -962,6 +962,14 @@ sources = prefix-string-test.c
 install = test
 libs = libsvn_test libsvn_subr apriconv apr
 
+[priority-queue-test]
+description = Test path library
+type = exe
+path = subversion/tests/libsvn_subr
+sources = priority-queue-test.c
+install = test
+libs = libsvn_test libsvn_subr apriconv apr
+
 [revision-test]
 description = Test revision library
 type = exe
@@ -1340,8 +1348,8 @@ libs = __ALL__
        string-table-test
        skel-test strings-reps-test changes-test locks-test repos-test
        checksum-test compat-test config-test hashdump-test mergeinfo-test
-       opt-test path-test prefix-string-teststream-test string-test
-       time-test utf-test
+       opt-test path-test prefix-string-test priority-queue-test stream-test
+       string-test time-test utf-test
        error-test error-code-test cache-test spillbuf-test crypto-test
        named_atomic-test named_atomic-proc-test revision-test
        subst_translate-test io-test

Added: subversion/branches/fsx/subversion/tests/libsvn_subr/priority-queue-test.c
URL: http://svn.apache.org/viewvc/subversion/branches/fsx/subversion/tests/libsvn_subr/priority-queue-test.c?rev=1508496&view=auto
==============================================================================
--- subversion/branches/fsx/subversion/tests/libsvn_subr/priority-queue-test.c (added)
+++ subversion/branches/fsx/subversion/tests/libsvn_subr/priority-queue-test.c Tue Jul 30 15:44:18 2013
@@ -0,0 +1,235 @@
+/*
+ * 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 "svn_sorts.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 */
+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: */
+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 */
+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
+  };