/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Copyright by The HDF Group. * * Copyright by the Board of Trustees of the University of Illinois. * * All rights reserved. * * * * This file is part of HDF5. The full HDF5 copyright notice, including * * terms governing use, modification, and redistribution, is contained in * * the COPYING file, which can be found at the root of the source code * * distribution tree, or in https://www.hdfgroup.org/licenses. * * If you do not have access to either file, you may request a copy from * * help@hdfgroup.org. * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ /* Test HDF Heap routines. REMARKS DESIGN BUGS/LIMITATIONS EXPORTED ROUTINES AUTHOR Quincey Koziol MODIFICATION HISTORY 2/18/03 - Started coding */ #include "testhdf5.h" #include "H5HPprivate.h" /* The number of elements in testing arrays */ #define NUM_ELEMS 1000 /* Objects for testing in heaps */ typedef struct test_obj { H5HP_info_t heap_info; /* Information required for heap. _MUST_ be first */ int val; /* Actual information for object */ } test_obj; /* Array of random element values */ static test_obj *rand_num; /* Array of random elements values, sorted in increasing order */ static test_obj *inc_sort_num; /* Array of random elements values, sorted in decreasing order */ static test_obj *dec_sort_num; static int tst_dec_sort(const void *_i1, const void *_i2) { const test_obj *i1 = (const test_obj *)_i1; const test_obj *i2 = (const test_obj *)_i2; if (i1->val < i2->val) return (1); else if (i1->val > i2->val) return (-1); return (0); } static int tst_inc_sort(const void *_i1, const void *_i2) { const test_obj *i1 = (const test_obj *)_i1; const test_obj *i2 = (const test_obj *)_i2; if (i1->val < i2->val) return (-1); else if (i1->val > i2->val) return (1); return (0); } /**************************************************************** ** ** test_heap_init(): Test H5HP (heap) code. ** Initialize data for Heap testing ** ****************************************************************/ static void test_heap_init(void) { time_t curr_time; /* Current time, for seeding random number generator */ size_t u; /* Local index variables */ /* Allocate arrays */ rand_num = (test_obj *)HDmalloc(sizeof(test_obj) * NUM_ELEMS); CHECK_PTR(rand_num, "HDmalloc"); inc_sort_num = (test_obj *)HDmalloc(sizeof(test_obj) * NUM_ELEMS); CHECK_PTR(inc_sort_num, "HDmalloc"); dec_sort_num = (test_obj *)HDmalloc(sizeof(test_obj) * NUM_ELEMS); CHECK_PTR(dec_sort_num, "HDmalloc"); /* Create randomized set of numbers */ curr_time = HDtime(NULL); HDsrandom((unsigned)curr_time); for (u = 0; u < NUM_ELEMS; u++) /* Generate random numbers from -1000 to 1000 */ rand_num[u].val = (int)(HDrandom() % 2001) - 1001; /* Sort random numbers into increasing order */ HDmemcpy(inc_sort_num, rand_num, sizeof(test_obj) * NUM_ELEMS); HDqsort(inc_sort_num, (size_t)NUM_ELEMS, sizeof(test_obj), tst_inc_sort); /* Sort random numbers into decreasing order */ HDmemcpy(dec_sort_num, rand_num, sizeof(test_obj) * NUM_ELEMS); HDqsort(dec_sort_num, (size_t)NUM_ELEMS, sizeof(test_obj), tst_dec_sort); } /* end test_heap_init() */ /**************************************************************** ** ** test_heap_create(): Test basic H5HP (heap) code. ** Tests creating and closing heaps. ** ****************************************************************/ static void test_heap_create(void) { H5HP_t *heap; /* Heap created */ herr_t ret; /* Generic return value */ /* Output message about test being performed */ MESSAGE(6, ("Testing Creating & Closing Heaps\n")); /* Try creating a maximum Heap */ heap = H5HP_create(H5HP_MAX_HEAP); CHECK_PTR(heap, "H5HP_create"); /* Try closing the heap */ ret = H5HP_close(heap); CHECK(ret, FAIL, "H5HP_close"); /* Try creating a minimum Heap */ heap = H5HP_create(H5HP_MIN_HEAP); CHECK_PTR(heap, "H5HP_create"); /* Try closing the heap */ ret = H5HP_close(heap); CHECK(ret, FAIL, "H5HP_close"); } /* end test_heap_create() */ /**************************************************************** ** ** test_heap_insert_min(): Test H5HP (heap) code. ** Tests basic inserting objects into minimum heaps. ** ****************************************************************/ static void test_heap_insert_min(void) { H5HP_t * heap; /* Heap created */ ssize_t num; /* Number of elements in heap */ int val; /* Value of object on heap */ test_obj obj1, obj2, obj3; /* Test objects to insert */ herr_t ret; /* Generic return value */ /* Output message about test being performed */ MESSAGE(7, ("Testing Inserting Into Minimum Heaps\n")); /* Create a Heap */ heap = H5HP_create(H5HP_MIN_HEAP); CHECK_PTR(heap, "H5HP_create"); /* Check that the heap has no elements */ num = H5HP_count(heap); VERIFY(num, 0, "H5HP_count"); /* Insert an object into the heap */ obj1.val = 100; ret = H5HP_insert(heap, 10, &obj1); CHECK(ret, FAIL, "H5HP_insert"); /* Check that the heap has one element */ num = H5HP_count(heap); VERIFY(num, 1, "H5HP_count"); /* Check the minimum value on the heap */ ret = H5HP_top(heap, &val); CHECK(ret, FAIL, "H5HP_top"); VERIFY(val, 10, "H5HP_top"); /* Insert another object into the heap, with value less than top element */ obj2.val = 50; ret = H5HP_insert(heap, 5, &obj2); CHECK(ret, FAIL, "H5HP_insert"); /* Check that the heap has two elements */ num = H5HP_count(heap); VERIFY(num, 2, "H5HP_count"); /* Check the minimum value on the heap */ ret = H5HP_top(heap, &val); CHECK(ret, FAIL, "H5HP_top"); VERIFY(val, 5, "H5HP_top"); /* Insert third object into the heap, with value greater than top element */ obj3.val = 200; ret = H5HP_insert(heap, 20, &obj3); CHECK(ret, FAIL, "H5HP_insert"); /* Check that the heap has three elements */ num = H5HP_count(heap); VERIFY(num, 3, "H5HP_count"); /* Check the minimum value on the heap */ ret = H5HP_top(heap, &val); CHECK(ret, FAIL, "H5HP_top"); VERIFY(val, 5, "H5HP_top"); /* Close the heap */ ret = H5HP_close(heap); CHECK(ret, FAIL, "H5HP_close"); } /* end test_heap_insert_min() */ /**************************************************************** ** ** test_heap_insert(): Test H5HP (heap) code. ** Tests basic inserting objects into maximum heaps. ** ****************************************************************/ static void test_heap_insert_max(void) { H5HP_t * heap; /* Heap created */ ssize_t num; /* Number of elements in heap */ int val; /* Value of object on heap */ test_obj obj1, obj2, obj3; /* Test objects to insert */ herr_t ret; /* Generic return value */ /* Output message about test being performed */ MESSAGE(7, ("Testing Inserting Into Maximum Heaps\n")); /* Create a Heap */ heap = H5HP_create(H5HP_MAX_HEAP); CHECK_PTR(heap, "H5HP_create"); /* Check that the heap has no elements */ num = H5HP_count(heap); VERIFY(num, 0, "H5HP_count"); /* Insert an object into the heap */ obj1.val = 100; ret = H5HP_insert(heap, 10, &obj1); CHECK(ret, FAIL, "H5HP_insert"); /* Check that the heap has one element */ num = H5HP_count(heap); VERIFY(num, 1, "H5HP_count"); /* Check the maximum value on the heap */ ret = H5HP_top(heap, &val); CHECK(ret, FAIL, "H5HP_top"); VERIFY(val, 10, "H5HP_top"); /* Insert another object into the heap, with value less than top element */ obj2.val = 50; ret = H5HP_insert(heap, 5, &obj2); CHECK(ret, FAIL, "H5HP_insert"); /* Check that the heap has two elements */ num = H5HP_count(heap); VERIFY(num, 2, "H5HP_count"); /* Check the maximum value on the heap */ ret = H5HP_top(heap, &val); CHECK(ret, FAIL, "H5HP_top"); VERIFY(val, 10, "H5HP_top"); /* Insert third object into the heap, with value greater than top element */ obj3.val = 200; ret = H5HP_insert(heap, 20, &obj3); CHECK(ret, FAIL, "H5HP_insert"); /* Check that the heap has three elements */ num = H5HP_count(heap); VERIFY(num, 3, "H5HP_count"); /* Check the maximum value on the heap */ ret = H5HP_top(heap, &val); CHECK(ret, FAIL, "H5HP_top"); VERIFY(val, 20, "H5HP_top"); /* Close the heap */ ret = H5HP_close(heap); CHECK(ret, FAIL, "H5HP_close"); } /* end test_heap_insert_max() */ /**************************************************************** ** ** test_heap_insert(): Test H5HP (heap) code. ** Tests basic inserting objects into heaps. ** ****************************************************************/ static void test_heap_insert(void) { /* Output message about test being performed */ MESSAGE(6, ("Testing Inserting Into Heaps\n")); /* Test insertions into minimum & maximum heaps */ test_heap_insert_max(); test_heap_insert_min(); } /* end test_heap_insert() */ /**************************************************************** ** ** test_heap_insert_many_core (): Tests H5HP (heap) code. ** "Core" routine called by test_heap_insert_many() routine. ** ****************************************************************/ static void test_heap_insert_many_core(H5HP_type_t heap_type, test_obj *arr, size_t nelem, int top_val) { H5HP_t *heap; /* Heap created */ ssize_t num; /* Number of elements in heap */ int val; /* Value of object on heap */ size_t u; /* Local index variable */ herr_t ret; /* Generic return value */ /* Create a Heap */ heap = H5HP_create(heap_type); CHECK_PTR(heap, "H5HP_create"); /* Check that the heap has no elements */ num = H5HP_count(heap); VERIFY(num, 0, "H5HP_count"); /* Insert the array elements into the heap */ for (u = 0; u < nelem; u++) { ret = H5HP_insert(heap, arr[u].val, &arr[u]); CHECK(ret, FAIL, "H5HP_insert"); } /* end for */ /* Check that the heap has correct number of elements */ num = H5HP_count(heap); CHECK(num, FAIL, "H5HP_count"); VERIFY((size_t)num, nelem, "H5HP_count"); /* Check the maximum value on the heap */ ret = H5HP_top(heap, &val); CHECK(ret, FAIL, "H5HP_top"); VERIFY(val, top_val, "H5HP_top"); /* Close the heap */ ret = H5HP_close(heap); CHECK(ret, FAIL, "H5HP_close"); } /* end test_heap_insert_many_core() */ /**************************************************************** ** ** test_heap_insert_many (): Test H5HP (heap) code. ** Tests inserting many objects into heaps. ** ****************************************************************/ static void test_heap_insert_many(void) { /* Output message about test being performed */ MESSAGE(6, ("Testing Inserting Many Objects Into Heaps\n")); /* Test creating a heap from random elements */ test_heap_insert_many_core(H5HP_MAX_HEAP, rand_num, (size_t)NUM_ELEMS, dec_sort_num[0].val); /* Test creating a heap from elements in increasing order */ test_heap_insert_many_core(H5HP_MAX_HEAP, inc_sort_num, (size_t)NUM_ELEMS, dec_sort_num[0].val); /* Test creating a heap from elements in decreasing order */ test_heap_insert_many_core(H5HP_MAX_HEAP, dec_sort_num, (size_t)NUM_ELEMS, dec_sort_num[0].val); /* Test creating a heap from random elements */ test_heap_insert_many_core(H5HP_MIN_HEAP, rand_num, (size_t)NUM_ELEMS, inc_sort_num[0].val); /* Test creating a heap from elements in increasing order */ test_heap_insert_many_core(H5HP_MIN_HEAP, inc_sort_num, (size_t)NUM_ELEMS, inc_sort_num[0].val); /* Test creating a heap from elements in decreasing order */ test_heap_insert_many_core(H5HP_MIN_HEAP, dec_sort_num, (size_t)NUM_ELEMS, inc_sort_num[0].val); } /* end test_heap_insert_many() */ /**************************************************************** ** ** test_heap_remove_min(): Test H5HP (heap) code. ** Tests basic removal of objects from minimum heaps. ** ****************************************************************/ static void test_heap_remove_min(void) { H5HP_t * heap; /* Heap created */ ssize_t num; /* Number of elements in heap */ int val; /* Value of object on heap */ void * ptr; /* Pointer for object on heap */ test_obj obj1, obj2, obj3; /* Test objects to insert */ herr_t ret; /* Generic return value */ /* Output message about test being performed */ MESSAGE(7, ("Testing Removing From Minimum Heaps\n")); /* Create a Heap */ heap = H5HP_create(H5HP_MIN_HEAP); CHECK_PTR(heap, "H5HP_create"); /* Check that the heap has no elements */ num = H5HP_count(heap); VERIFY(num, 0, "H5HP_count"); /* Try removing an object from an empty heap */ ret = H5HP_remove(heap, &val, &ptr); VERIFY(ret, FAIL, "H5HP_remove"); /* Insert an object into the heap */ obj1.val = 100; ret = H5HP_insert(heap, 10, &obj1); CHECK(ret, FAIL, "H5HP_insert"); /* Insert another object into the heap, with value less than top element */ obj2.val = 50; ret = H5HP_insert(heap, 5, &obj2); CHECK(ret, FAIL, "H5HP_insert"); /* Insert third object into the heap, with value greater than top element */ obj3.val = 200; ret = H5HP_insert(heap, 20, &obj3); CHECK(ret, FAIL, "H5HP_insert"); /* Remove first maximum value from heap */ ret = H5HP_remove(heap, &val, &ptr); CHECK(ret, FAIL, "H5HP_remove"); VERIFY(val, 5, "H5HP_remove"); CHECK_PTR_EQ(ptr, &obj2, "H5HP_remove"); /* Remove second maximum value from heap */ ret = H5HP_remove(heap, &val, &ptr); CHECK(ret, FAIL, "H5HP_remove"); VERIFY(val, 10, "H5HP_remove"); CHECK_PTR_EQ(ptr, &obj1, "H5HP_remove"); /* Remove third maximum value from heap */ ret = H5HP_remove(heap, &val, &ptr); CHECK(ret, FAIL, "H5HP_remove"); VERIFY(val, 20, "H5HP_remove"); CHECK_PTR_EQ(ptr, &obj3, "H5HP_remove"); /* Try removing an object from an empty heap */ ret = H5HP_remove(heap, &val, &ptr); VERIFY(ret, FAIL, "H5HP_remove"); /* Close the heap */ ret = H5HP_close(heap); CHECK(ret, FAIL, "H5HP_close"); } /* end test_heap_remove_min() */ /**************************************************************** ** ** test_heap_remove_max(): Test H5HP (heap) code. ** Tests basic removal of objects from maximum heaps. ** ****************************************************************/ static void test_heap_remove_max(void) { H5HP_t * heap; /* Heap created */ ssize_t num; /* Number of elements in heap */ int val; /* Value of object on heap */ void * ptr; /* Pointer for object on heap */ test_obj obj1, obj2, obj3; /* Test objects to insert */ herr_t ret; /* Generic return value */ /* Output message about test being performed */ MESSAGE(7, ("Testing Removing From Maximum Heaps\n")); /* Create a Heap */ heap = H5HP_create(H5HP_MAX_HEAP); CHECK_PTR(heap, "H5HP_create"); /* Check that the heap has no elements */ num = H5HP_count(heap); VERIFY(num, 0, "H5HP_count"); /* Try removing an object from an empty heap */ ret = H5HP_remove(heap, &val, &ptr); VERIFY(ret, FAIL, "H5HP_remove"); /* Insert an object into the heap */ obj1.val = 100; ret = H5HP_insert(heap, 10, &obj1); CHECK(ret, FAIL, "H5HP_insert"); /* Insert another object into the heap, with value less than top element */ obj2.val = 50; ret = H5HP_insert(heap, 5, &obj2); CHECK(ret, FAIL, "H5HP_insert"); /* Insert third object into the heap, with value greater than top element */ obj3.val = 200; ret = H5HP_insert(heap, 20, &obj3); CHECK(ret, FAIL, "H5HP_insert"); /* Remove first maximum value from heap */ ret = H5HP_remove(heap, &val, &ptr); CHECK(ret, FAIL, "H5HP_remove"); VERIFY(val, 20, "H5HP_remove"); CHECK_PTR_EQ(ptr, &obj3, "H5HP_remove"); /* Remove second maximum value from heap */ ret = H5HP_remove(heap, &val, &ptr); CHECK(ret, FAIL, "H5HP_remove"); VERIFY(val, 10, "H5HP_remove"); CHECK_PTR_EQ(ptr, &obj1, "H5HP_remove"); /* Remove third maximum value from heap */ ret = H5HP_remove(heap, &val, &ptr); CHECK(ret, FAIL, "H5HP_remove"); VERIFY(val, 5, "H5HP_remove"); CHECK_PTR_EQ(ptr, &obj2, "H5HP_remove"); /* Try removing an object from an empty heap */ ret = H5HP_remove(heap, &val, &ptr); VERIFY(ret, FAIL, "H5HP_remove"); /* Close the heap */ ret = H5HP_close(heap); CHECK(ret, FAIL, "H5HP_close"); } /* end test_heap_remove_max() */ /**************************************************************** ** ** test_heap_remove(): Test H5HP (heap) code. ** Tests basic removal of objects from minimum & maximum heaps. ** ****************************************************************/ static void test_heap_remove(void) { /* Output message about test being performed */ MESSAGE(6, ("Testing Removing From Heaps\n")); /* Test removals from minimum & maximum heaps */ test_heap_remove_max(); test_heap_remove_min(); } /* end test_heap_remove() */ /**************************************************************** ** ** test_heap_remove_many_core (): Tests H5HP (heap) code. ** "Core" routine called by test_heap_remove_many() routine. ** ****************************************************************/ static void test_heap_remove_many_core(H5HP_type_t heap_type, test_obj *arr, size_t nelem) { H5HP_t * heap; /* Heap created */ ssize_t num; /* Number of elements in heap */ int last_val; /* Last value from the heap */ int val; /* Value of object on heap */ test_obj *ptr; /* Pointer for object on heap */ size_t u; /* Local index variable */ herr_t ret; /* Generic return value */ /* Create a Heap */ heap = H5HP_create(heap_type); CHECK_PTR(heap, "H5HP_create"); /* Check that the heap has no elements */ num = H5HP_count(heap); VERIFY(num, 0, "H5HP_count"); /* Insert the array elements into the heap */ for (u = 0; u < nelem; u++) { ret = H5HP_insert(heap, arr[u].val, &arr[u]); CHECK(ret, FAIL, "H5HP_insert"); } /* end for */ /* Check that the heap has correct number of elements */ num = H5HP_count(heap); CHECK(num, FAIL, "H5HP_count"); VERIFY((size_t)num, nelem, "H5HP_count"); /* Set an appropriate starting value for the "last" value from heap */ if (heap_type == H5HP_MAX_HEAP) last_val = INT_MAX; else last_val = INT_MIN; /* Remove the objects from the heap */ for (u = 0; u < nelem; u++) { ret = H5HP_remove(heap, &val, (void **)&ptr); CHECK(ret, FAIL, "H5HP_remove"); VERIFY(val, ptr->val, "H5HP_remove"); /* Check that the value is correct, based on the heap type */ if (heap_type == H5HP_MAX_HEAP) { if (val > last_val) TestErrPrintf("Error on line %d: incorrect value from heap=%d, last_val=%d\n", __LINE__, val, last_val); } /* end if */ else { if (val < last_val) TestErrPrintf("Error on line %d: incorrect value from heap=%d, last_val=%d\n", __LINE__, val, last_val); } /* end else */ /* Update last value */ last_val = val; } /* end for */ /* Check that the heap has no elements */ num = H5HP_count(heap); VERIFY(num, 0, "H5HP_count"); /* Insert & remove again, to check that completely empty heaps can be added again */ /* Set an appropriate starting value for the "last" value from heap */ if (heap_type == H5HP_MAX_HEAP) last_val = INT_MAX; else last_val = INT_MIN; /* Insert the array elements into the heap */ for (u = 0; u < nelem; u++) { ret = H5HP_insert(heap, arr[u].val, &arr[u]); CHECK(ret, FAIL, "H5HP_insert"); } /* end for */ /* Check that the heap has correct number of elements */ num = H5HP_count(heap); CHECK(num, FAIL, "H5HP_count"); VERIFY((size_t)num, nelem, "H5HP_count"); /* Remove the objects from the heap */ for (u = 0; u < nelem; u++) { ret = H5HP_remove(heap, &val, (void **)&ptr); CHECK(ret, FAIL, "H5HP_remove"); VERIFY(val, ptr->val, "H5HP_remove"); /* Check that the value is correct, based on the heap type */ if (heap_type == H5HP_MAX_HEAP) { if (val > last_val) TestErrPrintf("Error on line %d: incorrect value from heap=%d, last_val=%d\n", __LINE__, val, last_val); } /* end if */ else { if (val < last_val) TestErrPrintf("Error on line %d: incorrect value from heap=%d, last_val=%d\n", __LINE__, val, last_val); } /* end else */ /* Update last value */ last_val = val; } /* end for */ /* Check that the heap has no elements */ num = H5HP_count(heap); VERIFY(num, 0, "H5HP_count"); /* Close the heap */ ret = H5HP_close(heap); CHECK(ret, FAIL, "H5HP_close"); } /* end test_heap_remove_many_core() */ /**************************************************************** ** ** test_heap_remove_many (): Test H5HP (heap) code. ** Tests removing many objects into heaps. ** ****************************************************************/ static void test_heap_remove_many(void) { /* Output message about test being performed */ MESSAGE(6, ("Testing Removing Many Objects From Heaps\n")); /* Test removing objects from maximum heap with random elements */ test_heap_remove_many_core(H5HP_MAX_HEAP, rand_num, (size_t)NUM_ELEMS); /* Test removing objects from maximum heap with elements already sorted in increasing order */ test_heap_remove_many_core(H5HP_MAX_HEAP, inc_sort_num, (size_t)NUM_ELEMS); /* Test removing objects from maximum heap with elements already sorted in decreasing order */ test_heap_remove_many_core(H5HP_MAX_HEAP, dec_sort_num, (size_t)NUM_ELEMS); /* Test removing objects from minimum heap with random elements */ test_heap_remove_many_core(H5HP_MIN_HEAP, rand_num, (size_t)NUM_ELEMS); /* Test removing objects from minimum heap with elements already sorted in increasing order */ test_heap_remove_many_core(H5HP_MIN_HEAP, inc_sort_num, (size_t)NUM_ELEMS); /* Test removing objects from minimum heap with elements already sorted in decreasing order */ test_heap_remove_many_core(H5HP_MIN_HEAP, dec_sort_num, (size_t)NUM_ELEMS); } /* end test_heap_remove_many() */ /**************************************************************** ** ** test_heap_change_min (): Test H5HP (heap) code. ** Tests changing the priority of an object in a minimum heap ** ****************************************************************/ static void test_heap_change_min(void) { H5HP_t * heap; /* Heap created */ ssize_t num; /* Number of elements in heap */ int val; /* Value of object on heap */ test_obj obj1, obj2, obj3; /* Test objects to insert */ herr_t ret; /* Generic return value */ /* Output message about test being performed */ MESSAGE(7, ("Testing Changing Priority of Objects in Minimum Heaps\n")); /* Create a Heap */ heap = H5HP_create(H5HP_MIN_HEAP); CHECK_PTR(heap, "H5HP_create"); /* Check that the heap has no elements */ num = H5HP_count(heap); VERIFY(num, 0, "H5HP_count"); /* Insert an object into the heap */ obj1.val = 100; ret = H5HP_insert(heap, 10, &obj1); CHECK(ret, FAIL, "H5HP_insert"); /* Insert another object into the heap, with value less than top element */ obj2.val = 50; ret = H5HP_insert(heap, 5, &obj2); CHECK(ret, FAIL, "H5HP_insert"); /* Insert third object into the heap, with value greater than top element */ obj3.val = 200; ret = H5HP_insert(heap, 20, &obj3); CHECK(ret, FAIL, "H5HP_insert"); /* Change priority of first object on heap in way which shouldn't affect heap order */ ret = H5HP_change(heap, 11, &obj1); CHECK(ret, FAIL, "H5HP_change"); /* Check the minimum value on the heap */ ret = H5HP_top(heap, &val); CHECK(ret, FAIL, "H5HP_top"); VERIFY(val, 5, "H5HP_top"); /* Change priority of first object on heap to be the top object on the heap */ ret = H5HP_change(heap, 3, &obj1); CHECK(ret, FAIL, "H5HP_change"); /* Check the maximum value on the heap */ ret = H5HP_top(heap, &val); CHECK(ret, FAIL, "H5HP_top"); VERIFY(val, 3, "H5HP_top"); /* Change priority of first object on heap to not be the top object on the heap */ ret = H5HP_change(heap, 10, &obj1); CHECK(ret, FAIL, "H5HP_change"); /* Check the maximum value on the heap */ ret = H5HP_top(heap, &val); CHECK(ret, FAIL, "H5HP_top"); VERIFY(val, 5, "H5HP_top"); /* Close the heap */ ret = H5HP_close(heap); CHECK(ret, FAIL, "H5HP_close"); } /* end test_heap_change_min() */ /**************************************************************** ** ** test_heap_change_max (): Test H5HP (heap) code. ** Tests changing the priority of an object in a maximumheap ** ****************************************************************/ static void test_heap_change_max(void) { H5HP_t * heap; /* Heap created */ ssize_t num; /* Number of elements in heap */ int val; /* Value of object on heap */ test_obj obj1, obj2, obj3; /* Test objects to insert */ herr_t ret; /* Generic return value */ /* Output message about test being performed */ MESSAGE(7, ("Testing Changing Priority of Objects in Maximum Heaps\n")); /* Create a Heap */ heap = H5HP_create(H5HP_MAX_HEAP); CHECK_PTR(heap, "H5HP_create"); /* Check that the heap has no elements */ num = H5HP_count(heap); VERIFY(num, 0, "H5HP_count"); /* Insert an object into the heap */ obj1.val = 100; ret = H5HP_insert(heap, 10, &obj1); CHECK(ret, FAIL, "H5HP_insert"); /* Insert another object into the heap, with value less than top element */ obj2.val = 50; ret = H5HP_insert(heap, 5, &obj2); CHECK(ret, FAIL, "H5HP_insert"); /* Insert third object into the heap, with value greater than top element */ obj3.val = 200; ret = H5HP_insert(heap, 20, &obj3); CHECK(ret, FAIL, "H5HP_insert"); /* Change priority of first object on heap in way which shouldn't affect heap order */ ret = H5HP_change(heap, 11, &obj1); CHECK(ret, FAIL, "H5HP_change"); /* Check the maximum value on the heap */ ret = H5HP_top(heap, &val); CHECK(ret, FAIL, "H5HP_top"); VERIFY(val, 20, "H5HP_top"); /* Change priority of first object on heap to be the top object on the heap */ ret = H5HP_change(heap, 21, &obj1); CHECK(ret, FAIL, "H5HP_change"); /* Check the maximum value on the heap */ ret = H5HP_top(heap, &val); CHECK(ret, FAIL, "H5HP_top"); VERIFY(val, 21, "H5HP_top"); /* Change priority of first object on heap to not be the top object on the heap */ ret = H5HP_change(heap, 10, &obj1); CHECK(ret, FAIL, "H5HP_change"); /* Check the maximum value on the heap */ ret = H5HP_top(heap, &val); CHECK(ret, FAIL, "H5HP_top"); VERIFY(val, 20, "H5HP_top"); /* Close the heap */ ret = H5HP_close(heap); CHECK(ret, FAIL, "H5HP_close"); } /* end test_heap_change() */ /**************************************************************** ** ** test_heap_change (): Test H5HP (heap) code. ** Tests changing the priority of an object in maximum & minimum heaps ** ****************************************************************/ static void test_heap_change(void) { /* Output message about test being performed */ MESSAGE(6, ("Testing Changing Priority of Objects in Heaps\n")); /* Test removals from minimum & maximum heaps */ test_heap_change_max(); test_heap_change_min(); } /* end test_heap_change() */ /**************************************************************** ** ** test_heap_incdec_min (): Test H5HP (heap) code. ** Tests incrementing & decrementing priority of objects on ** a minimum heap. ** ****************************************************************/ static void test_heap_incdec_min(void) { H5HP_t * heap; /* Heap created */ ssize_t num; /* Number of elements in heap */ int val; /* Value of object on heap */ test_obj obj1, obj2, obj3; /* Test objects to insert */ herr_t ret; /* Generic return value */ /* Output message about test being performed */ MESSAGE(7, ("Testing Incrementing & Decrementing Priority of Objects in Minimum Heaps\n")); /* Create a Heap */ heap = H5HP_create(H5HP_MIN_HEAP); CHECK_PTR(heap, "H5HP_create"); /* Check that the heap has no elements */ num = H5HP_count(heap); VERIFY(num, 0, "H5HP_count"); /* Insert an object into the heap */ obj1.val = 100; ret = H5HP_insert(heap, 6, &obj1); CHECK(ret, FAIL, "H5HP_insert"); /* Insert another object into the heap, with value less than top element */ obj2.val = 50; ret = H5HP_insert(heap, 5, &obj2); CHECK(ret, FAIL, "H5HP_insert"); /* Insert third object into the heap, with value greater than top element */ obj3.val = 200; ret = H5HP_insert(heap, 20, &obj3); CHECK(ret, FAIL, "H5HP_insert"); /* Decrement object one's priority by two to put it on top of the heap */ ret = H5HP_decr(heap, 2, &obj1); CHECK(ret, FAIL, "H5HP_change"); /* Check the minimum value on the heap */ ret = H5HP_top(heap, &val); CHECK(ret, FAIL, "H5HP_top"); VERIFY(val, 4, "H5HP_top"); /* Decrement object two's priority by two to put it back on top of the heap */ ret = H5HP_decr(heap, 2, &obj2); CHECK(ret, FAIL, "H5HP_change"); /* Check the minimum value on the heap */ ret = H5HP_top(heap, &val); CHECK(ret, FAIL, "H5HP_top"); VERIFY(val, 3, "H5HP_top"); /* Increment object two's priority by two to return object one to the top */ ret = H5HP_incr(heap, 2, &obj2); CHECK(ret, FAIL, "H5HP_change"); /* Check the minimum value on the heap */ ret = H5HP_top(heap, &val); CHECK(ret, FAIL, "H5HP_top"); VERIFY(val, 4, "H5HP_top"); /* Close the heap */ ret = H5HP_close(heap); CHECK(ret, FAIL, "H5HP_close"); } /* end test_heap_incdec_min() */ /**************************************************************** ** ** test_heap_incdec_max (): Test H5HP (heap) code. ** Tests incrementing & decrementing priority of objects on ** a maximum heap. ** ****************************************************************/ static void test_heap_incdec_max(void) { H5HP_t * heap; /* Heap created */ ssize_t num; /* Number of elements in heap */ int val; /* Value of object on heap */ test_obj obj1, obj2, obj3; /* Test objects to insert */ herr_t ret; /* Generic return value */ /* Output message about test being performed */ MESSAGE(7, ("Testing Incrementing & Decrementing Priority of Objects in Maximum Heaps\n")); /* Create a Heap */ heap = H5HP_create(H5HP_MAX_HEAP); CHECK_PTR(heap, "H5HP_create"); /* Check that the heap has no elements */ num = H5HP_count(heap); VERIFY(num, 0, "H5HP_count"); /* Insert an object into the heap */ obj1.val = 100; ret = H5HP_insert(heap, 19, &obj1); CHECK(ret, FAIL, "H5HP_insert"); /* Insert another object into the heap, with value less than top element */ obj2.val = 50; ret = H5HP_insert(heap, 5, &obj2); CHECK(ret, FAIL, "H5HP_insert"); /* Insert third object into the heap, with value greater than top element */ obj3.val = 200; ret = H5HP_insert(heap, 20, &obj3); CHECK(ret, FAIL, "H5HP_insert"); /* Increment object one's priority by two to put it on top of the heap */ ret = H5HP_incr(heap, 2, &obj1); CHECK(ret, FAIL, "H5HP_change"); /* Check the maximum value on the heap */ ret = H5HP_top(heap, &val); CHECK(ret, FAIL, "H5HP_top"); VERIFY(val, 21, "H5HP_top"); /* Increment object three's priority by two to put it back on top of the heap */ ret = H5HP_incr(heap, 2, &obj3); CHECK(ret, FAIL, "H5HP_change"); /* Check the maximum value on the heap */ ret = H5HP_top(heap, &val); CHECK(ret, FAIL, "H5HP_top"); VERIFY(val, 22, "H5HP_top"); /* Decrement object three's priority by two to return object one to the top */ ret = H5HP_decr(heap, 2, &obj3); CHECK(ret, FAIL, "H5HP_change"); /* Check the maximum value on the heap */ ret = H5HP_top(heap, &val); CHECK(ret, FAIL, "H5HP_top"); VERIFY(val, 21, "H5HP_top"); /* Close the heap */ ret = H5HP_close(heap); CHECK(ret, FAIL, "H5HP_close"); } /* end test_heap_incdec_max() */ /**************************************************************** ** ** test_heap_incdec (): Test H5HP (heap) code. ** Tests incrementing & decrementing priority of objects on ** maximum & minimum heaps. ** ****************************************************************/ static void test_heap_incdec(void) { /* Output message about test being performed */ MESSAGE(6, ("Testing Incrementing & Decrementing Priority of Objects in Heaps\n")); /* Test increments & decrements in minimum & maximum heaps */ test_heap_incdec_max(); test_heap_incdec_min(); } /* end test_heap_incdec() */ /**************************************************************** ** ** test_heap_term(): Test H5HP (heap) code. ** Release data for Heap testing ** ****************************************************************/ static void test_heap_term(void) { /* Release arrays */ if (rand_num) HDfree(rand_num); if (inc_sort_num) HDfree(inc_sort_num); if (dec_sort_num) HDfree(dec_sort_num); } /* end test_heap_term() */ /**************************************************************** ** ** test_heap(): Main H5HP testing routine. ** ****************************************************************/ void test_heap(void) { /* Output message about test being performed */ MESSAGE(5, ("Testing Heaps\n")); /* Initialize Heap testing data */ test_heap_init(); /* Actual Heap tests */ test_heap_create(); /* Test Heap creation */ test_heap_insert(); /* Test basic Heap insertion */ test_heap_insert_many(); /* Test Heap insertion of many items */ test_heap_remove(); /* Test basic Heap removal */ test_heap_remove_many(); /* Test Heap removal of many items */ test_heap_change(); /* Test changing priority of objects on Heap */ test_heap_incdec(); /* Test incrementing & decrementing priority of objects on Heap */ /* Release Heap testing data */ test_heap_term(); } /* end test_heap() */