/* * 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 #include #include #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