diff options
| -rw-r--r-- | src/CMakeLists.txt | 11 | ||||
| -rw-r--r-- | src/H5HP.c | 904 | ||||
| -rw-r--r-- | src/H5HPprivate.h | 68 | ||||
| -rw-r--r-- | src/Makefile.am | 1 | ||||
| -rw-r--r-- | test/CMakeLists.txt | 1 | ||||
| -rw-r--r-- | test/CMakeTests.cmake | 8 | ||||
| -rw-r--r-- | test/Makefile.am | 2 | ||||
| -rw-r--r-- | test/testhdf5.c | 1 | ||||
| -rw-r--r-- | test/testhdf5.h | 1 | ||||
| -rw-r--r-- | test/theap.c | 1081 |
10 files changed, 2 insertions, 2076 deletions
diff --git a/src/CMakeLists.txt b/src/CMakeLists.txt index 9208532..b95409f 100644 --- a/src/CMakeLists.txt +++ b/src/CMakeLists.txt @@ -377,14 +377,6 @@ set (H5HL_HDRS IDE_GENERATED_PROPERTIES ("H5HL" "${H5HL_HDRS}" "${H5HL_SOURCES}" ) -set (H5HP_SOURCES - ${HDF5_SRC_DIR}/H5HP.c -) -set (H5HP_HDRS -) -IDE_GENERATED_PROPERTIES ("H5HP" "${H5HP_HDRS}" "${H5HP_SOURCES}" ) - - set (H5I_SOURCES ${HDF5_SRC_DIR}/H5I.c ${HDF5_SRC_DIR}/H5Idbg.c @@ -776,7 +768,6 @@ set (common_SRCS ${H5HF_SOURCES} ${H5HG_SOURCES} ${H5HL_SOURCES} - ${H5HP_SOURCES} ${H5I_SOURCES} ${H5L_SOURCES} ${H5M_SOURCES} @@ -904,8 +895,6 @@ set (H5_PRIVATE_HEADERS ${HDF5_SRC_DIR}/H5HLpkg.h ${HDF5_SRC_DIR}/H5HLprivate.h - ${HDF5_SRC_DIR}/H5HPprivate.h - ${HDF5_SRC_DIR}/H5Ipkg.h ${HDF5_SRC_DIR}/H5Iprivate.h diff --git a/src/H5HP.c b/src/H5HP.c deleted file mode 100644 index d164223..0000000 --- a/src/H5HP.c +++ /dev/null @@ -1,904 +0,0 @@ -/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * - * 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. * - * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ - -/* - * Purpose: Provides a heap abstract data type. - * - * (See chapter 11 - "Priority Queues" of _Algorithms_, by - * Sedgewick for additional information) - * - */ - -/* Private headers needed */ -#include "H5private.h" /* Generic Functions */ -#include "H5Eprivate.h" /* Error handling */ -#include "H5HPprivate.h" /* Heap routines */ -#include "H5FLprivate.h" /* Memory management functions */ - -/* Local Macros */ -#define H5HP_START_SIZE 16 /* Initial number of entries for heaps */ - -/* Private typedefs & structs */ - -/* Data structure for entries in the internal heap array */ -typedef struct { - int val; /* Value to be used for heap condition */ - H5HP_info_t *obj; /* Pointer to object stored in heap */ -} H5HP_ent_t; - -/* Main heap data structure */ -struct H5HP_t { - H5HP_type_t type; /* Type of heap (minimum or maximum value at "top") */ - size_t nobjs; /* Number of active objects in heap array */ - size_t nalloc; /* Number of allocated locations in heap array */ - H5HP_ent_t *heap; /* Pointer to array containing heap entries */ -}; - -/* Static functions */ -static herr_t H5HP__swim_max(H5HP_t *heap, size_t loc); -static herr_t H5HP__swim_min(H5HP_t *heap, size_t loc); -static herr_t H5HP__sink_max(H5HP_t *heap, size_t loc); -static herr_t H5HP__sink_min(H5HP_t *heap, size_t loc); - -/* Declare a free list to manage the H5HP_t struct */ -H5FL_DEFINE_STATIC(H5HP_t); - -/* Declare a free list to manage sequences of H5HP_ent_t */ -H5FL_SEQ_DEFINE_STATIC(H5HP_ent_t); - -/*-------------------------------------------------------------------------- - NAME - H5HP__swim_max - PURPOSE - Restore heap condition by moving an object upward - USAGE - herr_t H5HP__swim_max(heap, loc) - H5HP_t *heap; IN/OUT: Pointer to heap to modify - size_t loc; IN: Location to start from - - RETURNS - Returns non-negative on success, negative on failure. - DESCRIPTION - Restore the heap condition for the heap's array by "swimming" the object - at a location upward. - GLOBAL VARIABLES - COMMENTS, BUGS, ASSUMPTIONS - This routine is for "maximum" value heaps. - EXAMPLES - REVISION LOG ---------------------------------------------------------------------------*/ -static herr_t -H5HP__swim_max(H5HP_t *heap, size_t loc) -{ - int val; /* Temporary copy value of object to move in heap */ - H5HP_info_t *obj; /* Temporary pointer to object to move in heap */ - herr_t ret_value = SUCCEED; /* Return value */ - - FUNC_ENTER_STATIC_NOERR - - /* Get copies of the information about the object to move in the heap */ - val = heap->heap[loc].val; - obj = heap->heap[loc].obj; - - /* Move object up in heap until it's reached the maximum location possible */ - while (heap->heap[loc / 2].val < val) { - /* Move object "above" current location in heap down */ - heap->heap[loc].val = heap->heap[loc / 2].val; - heap->heap[loc].obj = heap->heap[loc / 2].obj; - - /* Update heap location for object which moved */ - heap->heap[loc].obj->heap_loc = loc; - - /* Move to location "above" current location */ - loc = loc / 2; - } /* end while */ - - /* Put object into heap at correct location */ - heap->heap[loc].val = val; - heap->heap[loc].obj = obj; - - /* Update heap location for object */ - heap->heap[loc].obj->heap_loc = loc; - - FUNC_LEAVE_NOAPI(ret_value); -} /* end H5HP__swim_max() */ - -/*-------------------------------------------------------------------------- - NAME - H5HP__swim_min - PURPOSE - Restore heap condition by moving an object upward - USAGE - herr_t H5HP__swim_min(heap, loc) - H5HP_t *heap; IN/OUT: Pointer to heap to modify - size_t loc; IN: Location to start from - - RETURNS - Returns non-negative on success, negative on failure. - DESCRIPTION - Restore the heap condition for the heap's array by "swimming" the object - at a location upward. - GLOBAL VARIABLES - COMMENTS, BUGS, ASSUMPTIONS - This routine is for "minimum" value heaps. - EXAMPLES - REVISION LOG ---------------------------------------------------------------------------*/ -static herr_t -H5HP__swim_min(H5HP_t *heap, size_t loc) -{ - int val; /* Temporary copy value of object to move in heap */ - H5HP_info_t *obj; /* Temporary pointer to object to move in heap */ - herr_t ret_value = SUCCEED; /* Return value */ - - FUNC_ENTER_STATIC_NOERR - - /* Get copies of the information about the object to move in the heap */ - val = heap->heap[loc].val; - obj = heap->heap[loc].obj; - - /* Move object up in heap until it's reached the minimum location possible */ - while (heap->heap[loc / 2].val > val) { - /* Move object "above" current location in heap down */ - heap->heap[loc].val = heap->heap[loc / 2].val; - heap->heap[loc].obj = heap->heap[loc / 2].obj; - - /* Update heap location for object which moved */ - heap->heap[loc].obj->heap_loc = loc; - - /* Move to location "above" current location */ - loc = loc / 2; - } /* end while */ - - /* Put object into heap at correct location */ - heap->heap[loc].val = val; - heap->heap[loc].obj = obj; - - /* Update heap location for object */ - heap->heap[loc].obj->heap_loc = loc; - - FUNC_LEAVE_NOAPI(ret_value); -} /* end H5HP__swim_min() */ - -/*-------------------------------------------------------------------------- - NAME - H5HP__sink_max - PURPOSE - Restore heap condition by moving an object downward - USAGE - herr_t H5HP__sink_max(heap, loc) - H5HP_t *heap; IN/OUT: Pointer to heap to modify - size_t loc; IN: Location to start from - - RETURNS - Returns non-negative on success, negative on failure. - DESCRIPTION - Restore the heap condition for the heap's array by "sinking" the object - at a location downward. - GLOBAL VARIABLES - COMMENTS, BUGS, ASSUMPTIONS - This routine is for "maximum" value heaps. - EXAMPLES - REVISION LOG ---------------------------------------------------------------------------*/ -static herr_t -H5HP__sink_max(H5HP_t *heap, size_t loc) -{ - int val; /* Temporary copy value of object to move in heap */ - void * obj; /* Temporary pointer to object to move in heap */ - herr_t ret_value = SUCCEED; /* Return value */ - - FUNC_ENTER_STATIC_NOERR - - /* Get copies of the information about the object to move in the heap */ - val = heap->heap[loc].val; - obj = heap->heap[loc].obj; - - /* Move object up in heap until it's reached the maximum location possible */ - while ((2 * loc) <= heap->nobjs) { - size_t new_loc = loc * 2; /* New object's potential location area */ - - /* Get the greater of the two objects below the location in heap */ - if (new_loc < heap->nobjs && (heap->heap[new_loc].val < heap->heap[new_loc + 1].val)) - new_loc++; - - /* Check if the object is smaller than the larger of the objects below it */ - /* If so, its in the correct location now, and we can get out */ - if (val >= heap->heap[new_loc].val) - break; - - /* Move the greater of the two objects below the current location up */ - heap->heap[loc].val = heap->heap[new_loc].val; - heap->heap[loc].obj = heap->heap[new_loc].obj; - - /* Update heap location for object which moved */ - heap->heap[loc].obj->heap_loc = loc; - - /* Move to location "below" current location */ - loc = new_loc; - } /* end while */ - - /* Put object into heap at correct location */ - heap->heap[loc].val = val; - heap->heap[loc].obj = (H5HP_info_t *)obj; - - /* Update heap location for object */ - heap->heap[loc].obj->heap_loc = loc; - - FUNC_LEAVE_NOAPI(ret_value); -} /* end H5HP__sink_max() */ - -/*-------------------------------------------------------------------------- - NAME - H5HP__sink_min - PURPOSE - Restore heap condition by moving an object downward - USAGE - herr_t H5HP__sink_min(heap, loc) - H5HP_t *heap; IN/OUT: Pointer to heap to modify - size_t loc; IN: Location to start from - - RETURNS - Returns non-negative on success, negative on failure. - DESCRIPTION - Restore the heap condition for the heap's array by "sinking" the object - at a location downward. - GLOBAL VARIABLES - COMMENTS, BUGS, ASSUMPTIONS - This routine is for "minimum" value heaps. - EXAMPLES - REVISION LOG ---------------------------------------------------------------------------*/ -static herr_t -H5HP__sink_min(H5HP_t *heap, size_t loc) -{ - int val; /* Temporary copy value of object to move in heap */ - void * obj; /* Temporary pointer to object to move in heap */ - herr_t ret_value = SUCCEED; /* Return value */ - - FUNC_ENTER_STATIC_NOERR - - /* Get copies of the information about the object to move in the heap */ - val = heap->heap[loc].val; - obj = heap->heap[loc].obj; - - /* Move object up in heap until it's reached the maximum location possible */ - while ((2 * loc) <= heap->nobjs) { - size_t new_loc = loc * 2; /* New object's potential location area */ - - /* Get the lesser of the two objects below the location in heap */ - if (new_loc < heap->nobjs && (heap->heap[new_loc].val > heap->heap[new_loc + 1].val)) - new_loc++; - - /* Check if the object is greater than the larger of the objects below it */ - /* If so, its in the correct location now, and we can get out */ - if (val <= heap->heap[new_loc].val) - break; - - /* Move the greater of the two objects below the current location up */ - heap->heap[loc].val = heap->heap[new_loc].val; - heap->heap[loc].obj = heap->heap[new_loc].obj; - - /* Update heap location for object which moved */ - heap->heap[loc].obj->heap_loc = loc; - - /* Move to location "below" current location */ - loc = new_loc; - } /* end while */ - - /* Put object into heap at correct location */ - heap->heap[loc].val = val; - heap->heap[loc].obj = (H5HP_info_t *)obj; - - /* Update heap location for object */ - heap->heap[loc].obj->heap_loc = loc; - - FUNC_LEAVE_NOAPI(ret_value); -} /* end H5HP__sink_min() */ - -/*-------------------------------------------------------------------------- - NAME - H5HP_create - PURPOSE - Create a heap - USAGE - H5HP_t *H5HP_create(heap_type) - H5HP_type_t heap_type; IN: Type of heap to create - - RETURNS - Returns a pointer to a heap on success, NULL on failure. - DESCRIPTION - Create a priority queue. The SIZE is used to set the initial number of - entries allocated. - GLOBAL VARIABLES - COMMENTS, BUGS, ASSUMPTIONS - EXAMPLES - REVISION LOG ---------------------------------------------------------------------------*/ -H5HP_t * -H5HP_create(H5HP_type_t heap_type) -{ - H5HP_t *new_heap = NULL; /* Pointer to new heap object created */ - H5HP_t *ret_value; /* Return value */ - - FUNC_ENTER_NOAPI(NULL) - - /* Check args */ - HDassert(heap_type == H5HP_MIN_HEAP || heap_type == H5HP_MAX_HEAP); - - /* Allocate ref-counted string structure */ - if ((new_heap = H5FL_MALLOC(H5HP_t)) == NULL) - HGOTO_ERROR(H5E_HEAP, H5E_NOSPACE, NULL, "memory allocation failed"); - - /* Allocate the array to store the heap entries */ - if ((new_heap->heap = H5FL_SEQ_MALLOC(H5HP_ent_t, (size_t)(H5HP_START_SIZE + 1))) == NULL) - HGOTO_ERROR(H5E_HEAP, H5E_NOSPACE, NULL, "memory allocation failed"); - - /* Set the internal fields */ - new_heap->type = heap_type; - new_heap->nobjs = 0; - new_heap->nalloc = H5HP_START_SIZE + 1; - - /* Set the information in the 0'th location based on the type of heap */ - if (heap_type == H5HP_MIN_HEAP) { - /* Set the value in the '0' location to be the minimum value, to - * simplify the algorithms - */ - new_heap->heap[0].val = INT_MIN; - new_heap->heap[0].obj = NULL; - } /* end if */ - else { - /* Set the value in the '0' location to be the maximum value, to - * simplify the algorithms - */ - new_heap->heap[0].val = INT_MAX; - new_heap->heap[0].obj = NULL; - } /* end else */ - - /* Set the return value */ - ret_value = new_heap; - -done: - /* Error cleanup */ - if (NULL == ret_value) { - if (NULL != new_heap) { - if (NULL != new_heap->heap) - new_heap->heap = H5FL_SEQ_FREE(H5HP_ent_t, new_heap->heap); - new_heap = H5FL_FREE(H5HP_t, new_heap); - } /* end if */ - } /* end if */ - - FUNC_LEAVE_NOAPI(ret_value); -} /* end H5HP_create() */ - -/*-------------------------------------------------------------------------- - NAME - H5HP_count - PURPOSE - Check the number of elements in a heap - USAGE - ssize_t H5HP_count(heap) - const H5HP_t *heap; IN: Pointer to heap to query - - RETURNS - Returns non-negative on success, negative on failure. - DESCRIPTION - Checks the number of elements in heap - GLOBAL VARIABLES - COMMENTS, BUGS, ASSUMPTIONS - EXAMPLES - REVISION LOG ---------------------------------------------------------------------------*/ -ssize_t -H5HP_count(const H5HP_t *heap) -{ - ssize_t ret_value; /* Return value */ - - FUNC_ENTER_NOAPI_NOINIT_NOERR - - /* Check args */ - HDassert(heap); - - /* Check internal consistency */ - /* (Pre-condition) */ - HDassert(heap->nobjs < heap->nalloc); - HDassert(heap->heap); - HDassert((heap->type == H5HP_MAX_HEAP && heap->heap[0].val == INT_MAX) || - (heap->type == H5HP_MIN_HEAP && heap->heap[0].val == INT_MIN)); - HDassert(heap->heap[0].obj == NULL); - - /* Return the number of objects in the heap */ - H5_CHECK_OVERFLOW(heap->nobjs, size_t, ssize_t); - ret_value = (ssize_t)heap->nobjs; - - /* No post-condition check necessary, since heap is constant */ - FUNC_LEAVE_NOAPI(ret_value); -} /* end H5HP_count() */ - -/*-------------------------------------------------------------------------- - NAME - H5HP_insert - PURPOSE - Insert an object into a heap, with an initial value - USAGE - herr_t H5HP_insert(heap, val, obj) - H5HP_t *heap; IN/OUT: Pointer to heap to modify - int val; IN: Initial value for object in heap - void *obj; IN: Pointer to object to insert into heap - - RETURNS - Returns non-negative on success, negative on failure. - DESCRIPTION - Inserts a OBJ into a HEAP, with an initial VALue. - GLOBAL VARIABLES - COMMENTS, BUGS, ASSUMPTIONS - EXAMPLES - REVISION LOG ---------------------------------------------------------------------------*/ -herr_t -H5HP_insert(H5HP_t *heap, int val, void *obj) -{ - herr_t ret_value = SUCCEED; /* Return value */ - - FUNC_ENTER_NOAPI(FAIL) - - /* Check args */ - HDassert(heap); - HDassert(obj); - - /* Check internal consistency */ - /* (Pre-condition) */ - HDassert(heap->nobjs < heap->nalloc); - HDassert(heap->heap); - HDassert((heap->type == H5HP_MAX_HEAP && heap->heap[0].val == INT_MAX) || - (heap->type == H5HP_MIN_HEAP && heap->heap[0].val == INT_MIN)); - HDassert(heap->heap[0].obj == NULL); - - /* Increment number of objects in heap */ - heap->nobjs++; - - /* Check if we need to allocate more room for heap array */ - if (heap->nobjs >= heap->nalloc) { - size_t n = MAX(H5HP_START_SIZE, 2 * (heap->nalloc - 1)) + 1; - H5HP_ent_t *new_heap = H5FL_SEQ_REALLOC(H5HP_ent_t, heap->heap, n); - - if (!new_heap) - HGOTO_ERROR(H5E_RESOURCE, H5E_NOSPACE, FAIL, "unable to extend heap array"); - heap->heap = new_heap; - heap->nalloc = n; - } /* end if */ - - /* Insert new object at end of heap */ - heap->heap[heap->nobjs].val = val; - heap->heap[heap->nobjs].obj = (H5HP_info_t *)obj; - heap->heap[heap->nobjs].obj->heap_loc = heap->nobjs; - - /* Restore heap condition */ - if (heap->type == H5HP_MAX_HEAP) { - if (H5HP__swim_max(heap, heap->nobjs) < 0) - HGOTO_ERROR(H5E_HEAP, H5E_CANTINSERT, FAIL, "unable to restore heap condition"); - } /* end if */ - else { - if (H5HP__swim_min(heap, heap->nobjs) < 0) - HGOTO_ERROR(H5E_HEAP, H5E_CANTINSERT, FAIL, "unable to restore heap condition"); - } /* end else */ - -done: - - /* Check internal consistency */ - /* (Post-condition) */ - HDassert(heap->nobjs < heap->nalloc); - HDassert(heap->heap); - HDassert((heap->type == H5HP_MAX_HEAP && heap->heap[0].val == INT_MAX) || - (heap->type == H5HP_MIN_HEAP && heap->heap[0].val == INT_MIN)); - HDassert(heap->heap[0].obj == NULL); - - FUNC_LEAVE_NOAPI(ret_value); -} /* end H5HP_insert() */ - -/*-------------------------------------------------------------------------- - NAME - H5HP_top - PURPOSE - Check the value of the top object in the heap - USAGE - herr_t H5HP_top(heap, val) - const H5HP_t *heap; IN: Pointer to heap to modify - int val; IN/OUT: Initial value for object in heap - - RETURNS - Returns non-negative on success, negative on failure. - DESCRIPTION - Checks the value of the top object in a heap - GLOBAL VARIABLES - COMMENTS, BUGS, ASSUMPTIONS - EXAMPLES - REVISION LOG ---------------------------------------------------------------------------*/ -herr_t -H5HP_top(const H5HP_t *heap, int *val) -{ - FUNC_ENTER_NOAPI_NOINIT_NOERR - - /* Check args */ - HDassert(heap); - HDassert(val); - - /* Check internal consistency */ - /* (Pre-condition) */ - HDassert(heap->nobjs < heap->nalloc); - HDassert(heap->heap); - HDassert((heap->type == H5HP_MAX_HEAP && heap->heap[0].val == INT_MAX) || - (heap->type == H5HP_MIN_HEAP && heap->heap[0].val == INT_MIN)); - HDassert(heap->heap[0].obj == NULL); - - /* Get value of the top object in the heap */ - *val = heap->heap[1].val; - - /* No post-condition check necessary, since heap is constant */ - FUNC_LEAVE_NOAPI(SUCCEED); -} /* end H5HP_top() */ - -/*-------------------------------------------------------------------------- - NAME - H5HP_remove - PURPOSE - Remove an object into a heap - USAGE - herr_t H5HP_remove(heap, val, obj) - H5HP_t *heap; IN/OUT: Pointer to heap to modify - int *val; OUT: Pointer to value of object removed from heap - void **obj; OUT: Pointer to object removed from heap - - RETURNS - Returns non-negative on success, negative on failure. - DESCRIPTION - Removes the top object on a heap, returning its value and object pointer - GLOBAL VARIABLES - COMMENTS, BUGS, ASSUMPTIONS - EXAMPLES - REVISION LOG ---------------------------------------------------------------------------*/ -herr_t -H5HP_remove(H5HP_t *heap, int *val, void **obj) -{ - herr_t ret_value = SUCCEED; /* Return value */ - - FUNC_ENTER_NOAPI(FAIL) - - /* Check args */ - HDassert(heap); - HDassert(val); - HDassert(obj); - - /* Check internal consistency */ - /* (Pre-condition) */ - HDassert(heap->nobjs < heap->nalloc); - HDassert(heap->heap); - HDassert((heap->type == H5HP_MAX_HEAP && heap->heap[0].val == INT_MAX) || - (heap->type == H5HP_MIN_HEAP && heap->heap[0].val == INT_MIN)); - HDassert(heap->heap[0].obj == NULL); - - /* Check if there are any objects on the heap to remove */ - if (heap->nobjs == 0) - HGOTO_ERROR(H5E_HEAP, H5E_NOTFOUND, FAIL, "heap is empty"); - - /* Get the information for the top object on the heap */ - HDassert(heap->heap[1].obj->heap_loc == 1); - *val = heap->heap[1].val; - *obj = heap->heap[1].obj; - - /* Move the last element in the heap to the top */ - heap->heap[1].val = heap->heap[heap->nobjs].val; - heap->heap[1].obj = heap->heap[heap->nobjs].obj; - heap->heap[1].obj->heap_loc = 1; - - /* Decrement number of objects in heap */ - heap->nobjs--; - - /* Restore heap condition, if there are objects on the heap */ - if (heap->nobjs > 0) { - if (heap->type == H5HP_MAX_HEAP) { - if (H5HP__sink_max(heap, (size_t)1) < 0) - HGOTO_ERROR(H5E_HEAP, H5E_CANTDELETE, FAIL, "unable to restore heap condition"); - } /* end if */ - else { - if (H5HP__sink_min(heap, (size_t)1) < 0) - HGOTO_ERROR(H5E_HEAP, H5E_CANTDELETE, FAIL, "unable to restore heap condition"); - } /* end else */ - } /* end if */ - -done: - - /* Check internal consistency */ - /* (Post-condition) */ - HDassert(heap->nobjs < heap->nalloc); - HDassert(heap->heap); - HDassert((heap->type == H5HP_MAX_HEAP && heap->heap[0].val == INT_MAX) || - (heap->type == H5HP_MIN_HEAP && heap->heap[0].val == INT_MIN)); - HDassert(heap->heap[0].obj == NULL); - - FUNC_LEAVE_NOAPI(ret_value); -} /* end H5HP_remove() */ - -/*-------------------------------------------------------------------------- - NAME - H5HP_change - PURPOSE - Change the priority of an object on a heap - USAGE - herr_t H5HP_change(heap, val, obj) - H5HP_t *heap; IN/OUT: Pointer to heap to modify - int val; IN: New priority value for object - void *obj; IN: Pointer to object to modify - - RETURNS - Returns non-negative on success, negative on failure. - DESCRIPTION - Changes the priority of an object on a heap. - GLOBAL VARIABLES - COMMENTS, BUGS, ASSUMPTIONS - EXAMPLES - REVISION LOG ---------------------------------------------------------------------------*/ -herr_t -H5HP_change(H5HP_t *heap, int val, void *_obj) -{ - H5HP_info_t *obj = (H5HP_info_t *)_obj; /* Alias for object */ - size_t obj_loc; /* Location of object in heap */ - int old_val; /* Object's old priority value */ - herr_t ret_value = SUCCEED; /* Return value */ - - FUNC_ENTER_NOAPI(FAIL) - - /* Check args */ - HDassert(heap); - HDassert(obj); - - /* Check internal consistency */ - /* (Pre-condition) */ - HDassert(heap->nobjs < heap->nalloc); - HDassert(heap->heap); - HDassert((heap->type == H5HP_MAX_HEAP && heap->heap[0].val == INT_MAX) || - (heap->type == H5HP_MIN_HEAP && heap->heap[0].val == INT_MIN)); - HDassert(heap->heap[0].obj == NULL); - - /* Get the location of the object in the heap */ - obj_loc = obj->heap_loc; - HDassert(obj_loc > 0 && obj_loc <= heap->nobjs); - - /* Change the heap object's priority */ - old_val = heap->heap[obj_loc].val; - heap->heap[obj_loc].val = val; - - /* Restore heap condition */ - if (val < old_val) { - if (heap->type == H5HP_MAX_HEAP) { - if (H5HP__sink_max(heap, obj_loc) < 0) - HGOTO_ERROR(H5E_HEAP, H5E_CANTRESTORE, FAIL, "unable to restore heap condition"); - } /* end if */ - else { - if (H5HP__swim_min(heap, obj_loc) < 0) - HGOTO_ERROR(H5E_HEAP, H5E_CANTRESTORE, FAIL, "unable to restore heap condition"); - } /* end else */ - } /* end if */ - else { - if (heap->type == H5HP_MAX_HEAP) { - if (H5HP__swim_max(heap, obj_loc) < 0) - HGOTO_ERROR(H5E_HEAP, H5E_CANTRESTORE, FAIL, "unable to restore heap condition"); - } /* end if */ - else { - if (H5HP__sink_min(heap, obj_loc) < 0) - HGOTO_ERROR(H5E_HEAP, H5E_CANTRESTORE, FAIL, "unable to restore heap condition"); - } /* end else */ - } /* end else */ - -done: - - /* Check internal consistency */ - /* (Post-condition) */ - HDassert(heap->nobjs < heap->nalloc); - HDassert(heap->heap); - HDassert((heap->type == H5HP_MAX_HEAP && heap->heap[0].val == INT_MAX) || - (heap->type == H5HP_MIN_HEAP && heap->heap[0].val == INT_MIN)); - HDassert(heap->heap[0].obj == NULL); - - FUNC_LEAVE_NOAPI(ret_value); -} /* end H5HP_change() */ - -/*-------------------------------------------------------------------------- - NAME - H5HP_incr - PURPOSE - Increment the priority of an object on a heap - USAGE - herr_t H5HP_incr(heap, amt, obj) - H5HP_t *heap; IN/OUT: Pointer to heap to modify - unsigned amt; IN: Amount to increase priority by - void *obj; IN: Pointer to object to modify - - RETURNS - Returns non-negative on success, negative on failure. - DESCRIPTION - Increments the priority of an object on a heap by one. - GLOBAL VARIABLES - COMMENTS, BUGS, ASSUMPTIONS - EXAMPLES - REVISION LOG ---------------------------------------------------------------------------*/ -herr_t -H5HP_incr(H5HP_t *heap, unsigned amt, void *_obj) -{ - H5HP_info_t *obj = (H5HP_info_t *)_obj; /* Alias for object */ - size_t obj_loc; /* Location of object in heap */ - herr_t ret_value = SUCCEED; /* Return value */ - - FUNC_ENTER_NOAPI(FAIL) - - /* Check args */ - HDassert(heap); - HDassert(obj); - - /* Check internal consistency */ - /* (Pre-condition) */ - HDassert(heap->nobjs < heap->nalloc); - HDassert(heap->heap); - HDassert((heap->type == H5HP_MAX_HEAP && heap->heap[0].val == INT_MAX) || - (heap->type == H5HP_MIN_HEAP && heap->heap[0].val == INT_MIN)); - HDassert(heap->heap[0].obj == NULL); - - /* Get the location of the object in the heap */ - obj_loc = obj->heap_loc; - HDassert(obj_loc > 0 && obj_loc <= heap->nobjs); - - /* Change the heap object's priority */ - heap->heap[obj_loc].val += (int)amt; - - /* Restore heap condition */ - if (H5HP_MAX_HEAP == heap->type) { - if (H5HP__swim_max(heap, obj_loc) < 0) - HGOTO_ERROR(H5E_HEAP, H5E_CANTRESTORE, FAIL, "unable to restore heap condition") - } /* end if */ - else { - if (H5HP__sink_min(heap, obj_loc) < 0) - HGOTO_ERROR(H5E_HEAP, H5E_CANTRESTORE, FAIL, "unable to restore heap condition") - } /* end else */ - -done: - - /* Check internal consistency */ - /* (Post-condition) */ - HDassert(heap->nobjs < heap->nalloc); - HDassert(heap->heap); - HDassert((heap->type == H5HP_MAX_HEAP && heap->heap[0].val == INT_MAX) || - (heap->type == H5HP_MIN_HEAP && heap->heap[0].val == INT_MIN)); - HDassert(heap->heap[0].obj == NULL); - - FUNC_LEAVE_NOAPI(ret_value); -} /* end H5HP_incr() */ - -/*-------------------------------------------------------------------------- - NAME - H5HP_decr - PURPOSE - Decrement the priority of an object on a heap - USAGE - herr_t H5HP_dec(heap, amt, obj) - H5HP_t *heap; IN/OUT: Pointer to heap to modify - unsigned amt; IN: Amount to decrease priority by - void *obj; IN: Pointer to object to modify - - RETURNS - Returns non-negative on success, negative on failure. - DESCRIPTION - Decrements the priority of an object on a heap by one. - GLOBAL VARIABLES - COMMENTS, BUGS, ASSUMPTIONS - EXAMPLES - REVISION LOG ---------------------------------------------------------------------------*/ -herr_t -H5HP_decr(H5HP_t *heap, unsigned amt, void *_obj) -{ - H5HP_info_t *obj = (H5HP_info_t *)_obj; /* Alias for object */ - size_t obj_loc; /* Location of object in heap */ - herr_t ret_value = SUCCEED; /* Return value */ - - FUNC_ENTER_NOAPI(FAIL) - - /* Check args */ - HDassert(heap); - HDassert(obj); - - /* Check internal consistency */ - /* (Pre-condition) */ - HDassert(heap->nobjs < heap->nalloc); - HDassert(heap->heap); - HDassert((heap->type == H5HP_MAX_HEAP && heap->heap[0].val == INT_MAX) || - (heap->type == H5HP_MIN_HEAP && heap->heap[0].val == INT_MIN)); - HDassert(heap->heap[0].obj == NULL); - - /* Get the location of the object in the heap */ - obj_loc = obj->heap_loc; - HDassert(obj_loc > 0 && obj_loc <= heap->nobjs); - - /* Change the heap object's priority */ - H5_CHECK_OVERFLOW(amt, unsigned, int); - heap->heap[obj_loc].val -= (int)amt; - - /* Restore heap condition */ - if (heap->type == H5HP_MAX_HEAP) { - if (H5HP__sink_max(heap, obj_loc) < 0) - HGOTO_ERROR(H5E_HEAP, H5E_CANTRESTORE, FAIL, "unable to restore heap condition"); - } /* end if */ - else { - if (H5HP__swim_min(heap, obj_loc) < 0) - HGOTO_ERROR(H5E_HEAP, H5E_CANTRESTORE, FAIL, "unable to restore heap condition"); - } /* end else */ - -done: - - /* Check internal consistency */ - /* (Post-condition) */ - HDassert(heap->nobjs < heap->nalloc); - HDassert(heap->heap); - HDassert((heap->type == H5HP_MAX_HEAP && heap->heap[0].val == INT_MAX) || - (heap->type == H5HP_MIN_HEAP && heap->heap[0].val == INT_MIN)); - HDassert(heap->heap[0].obj == NULL); - - FUNC_LEAVE_NOAPI(ret_value); -} /* end H5HP_decr() */ - -/*-------------------------------------------------------------------------- - NAME - H5HP_close - PURPOSE - Close a heap, deallocating it. - USAGE - herr_t H5HP_close(heap) - H5HP_t *heap; IN/OUT: Pointer to heap to close - - RETURNS - Returns non-negative on success, negative on failure. - DESCRIPTION - Close a heap, freeing all internal information. Any objects left in - the heap are not deallocated. - GLOBAL VARIABLES - COMMENTS, BUGS, ASSUMPTIONS - EXAMPLES - REVISION LOG ---------------------------------------------------------------------------*/ -herr_t -H5HP_close(H5HP_t *heap) -{ - FUNC_ENTER_NOAPI_NOINIT_NOERR - - /* Check args */ - HDassert(heap); - - /* Check internal consistency */ - /* (Pre-condition) */ - HDassert(heap->nobjs < heap->nalloc); - HDassert(heap->heap); - HDassert((heap->type == H5HP_MAX_HEAP && heap->heap[0].val == INT_MAX) || - (heap->type == H5HP_MIN_HEAP && heap->heap[0].val == INT_MIN)); - HDassert(NULL == heap->heap[0].obj); - - /* Free internal structures for heap */ - heap->heap = H5FL_SEQ_FREE(H5HP_ent_t, heap->heap); - - /* Free actual heap object */ - heap = H5FL_FREE(H5HP_t, heap); - - FUNC_LEAVE_NOAPI(SUCCEED) -} /* end H5HP_close() */ diff --git a/src/H5HPprivate.h b/src/H5HPprivate.h deleted file mode 100644 index 50020bc..0000000 --- a/src/H5HPprivate.h +++ /dev/null @@ -1,68 +0,0 @@ -/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * - * 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. * - * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ - -/* - * This file contains private information about the H5HP module - */ -#ifndef H5HPprivate_H -#define H5HPprivate_H - -/**************************************/ -/* Public headers needed by this file */ -/**************************************/ -#ifdef LATER -#include "H5HPpublic.h" -#endif /* LATER */ - -/***************************************/ -/* Private headers needed by this file */ -/***************************************/ -#include "H5private.h" - -/************/ -/* Typedefs */ -/************/ - -/* Typedef for heap struct (defined in H5HP.c) */ -typedef struct H5HP_t H5HP_t; - -/* Typedef for objects which can be inserted into heaps */ -/* This _must_ be the first field in objects which can be inserted into heaps */ -typedef struct H5HP_info_t { - size_t heap_loc; /* Location of object in heap */ -} H5HP_info_t; - -/* Typedef for type of heap to create */ -typedef enum { - H5HP_MIN_HEAP, /* Minimum values in heap are at the "top" */ - H5HP_MAX_HEAP /* Maximum values in heap are at the "top" */ -} H5HP_type_t; - -/**********/ -/* Macros */ -/**********/ - -/********************/ -/* Private routines */ -/********************/ -H5_DLL H5HP_t *H5HP_create(H5HP_type_t heap_type); -H5_DLL herr_t H5HP_insert(H5HP_t *heap, int val, void *obj); -H5_DLL ssize_t H5HP_count(const H5HP_t *heap); -H5_DLL herr_t H5HP_top(const H5HP_t *heap, int *val); -H5_DLL herr_t H5HP_remove(H5HP_t *heap, int *val, void **ptr); -H5_DLL herr_t H5HP_change(H5HP_t *heap, int val, void *obj); -H5_DLL herr_t H5HP_incr(H5HP_t *heap, unsigned amt, void *obj); -H5_DLL herr_t H5HP_decr(H5HP_t *heap, unsigned amt, void *obj); -H5_DLL herr_t H5HP_close(H5HP_t *heap); - -#endif /* H5HPprivate_H */ diff --git a/src/Makefile.am b/src/Makefile.am index dfed557..edfd9b0 100644 --- a/src/Makefile.am +++ b/src/Makefile.am @@ -74,7 +74,6 @@ libhdf5_la_SOURCES= H5.c H5checksum.c H5dbg.c H5lib_settings.c H5system.c \ H5HFspace.c H5HFstat.c H5HFtest.c H5HFtiny.c \ H5HG.c H5HGcache.c H5HGdbg.c H5HGquery.c \ H5HL.c H5HLcache.c H5HLdbg.c H5HLint.c H5HLprfx.c H5HLdblk.c \ - H5HP.c \ H5I.c H5Idbg.c H5Iint.c H5Itest.c \ H5L.c H5Ldeprec.c H5Lexternal.c H5Lint.c \ H5M.c \ diff --git a/test/CMakeLists.txt b/test/CMakeLists.txt index 7e69c09..f9e6e4b 100644 --- a/test/CMakeLists.txt +++ b/test/CMakeLists.txt @@ -266,7 +266,6 @@ set (testhdf5_SOURCES ${HDF5_TEST_SOURCE_DIR}/tgenprop.c ${HDF5_TEST_SOURCE_DIR}/th5o.c ${HDF5_TEST_SOURCE_DIR}/th5s.c - ${HDF5_TEST_SOURCE_DIR}/theap.c ${HDF5_TEST_SOURCE_DIR}/tid.c ${HDF5_TEST_SOURCE_DIR}/titerate.c ${HDF5_TEST_SOURCE_DIR}/tmeta.c diff --git a/test/CMakeTests.cmake b/test/CMakeTests.cmake index 6abef3b..a534e60 100644 --- a/test/CMakeTests.cmake +++ b/test/CMakeTests.cmake @@ -205,18 +205,12 @@ add_test ( ) set_tests_properties (H5TEST-testhdf5-clear-objects PROPERTIES FIXTURES_SETUP clear_testhdf5) -add_test (NAME H5TEST-testhdf5-base COMMAND ${CMAKE_CROSSCOMPILING_EMULATOR} $<TARGET_FILE:testhdf5> -x heap -x file -x select) +add_test (NAME H5TEST-testhdf5-base COMMAND ${CMAKE_CROSSCOMPILING_EMULATOR} $<TARGET_FILE:testhdf5> -x file -x select) set_tests_properties (H5TEST-testhdf5-base PROPERTIES FIXTURES_REQUIRED clear_testhdf5 ENVIRONMENT "HDF5_ALARM_SECONDS=3600;srcdir=${HDF5_TEST_BINARY_DIR}/H5TEST" WORKING_DIRECTORY ${HDF5_TEST_BINARY_DIR}/H5TEST ) -add_test (NAME H5TEST-testhdf5-heap COMMAND ${CMAKE_CROSSCOMPILING_EMULATOR} $<TARGET_FILE:testhdf5> -o heap) -set_tests_properties (H5TEST-testhdf5-heap PROPERTIES - FIXTURES_REQUIRED clear_testhdf5 - ENVIRONMENT "HDF5_ALARM_SECONDS=3600;srcdir=${HDF5_TEST_BINARY_DIR}/H5TEST" - WORKING_DIRECTORY ${HDF5_TEST_BINARY_DIR}/H5TEST -) add_test (NAME H5TEST-testhdf5-file COMMAND ${CMAKE_CROSSCOMPILING_EMULATOR} $<TARGET_FILE:testhdf5> -o file) set_tests_properties (H5TEST-testhdf5-file PROPERTIES FIXTURES_REQUIRED clear_testhdf5 diff --git a/test/Makefile.am b/test/Makefile.am index 63d8f43..fcfd34e 100644 --- a/test/Makefile.am +++ b/test/Makefile.am @@ -230,7 +230,7 @@ CHECK_CLEANFILES+=accum.h5 cmpd_dset.h5 compact_dataset.h5 dataset.h5 dset_offse # Sources for testhdf5 executable testhdf5_SOURCES=testhdf5.c tarray.c tattr.c tchecksum.c tconfig.c tfile.c \ - tgenprop.c th5o.c th5s.c tcoords.c theap.c tid.c titerate.c tmeta.c tmisc.c \ + tgenprop.c th5o.c th5s.c tcoords.c tid.c titerate.c tmeta.c tmisc.c \ trefer.c trefer_deprec.c trefstr.c tselect.c tskiplist.c tsohm.c ttime.c tunicode.c \ tvlstr.c tvltypes.c diff --git a/test/testhdf5.c b/test/testhdf5.c index dc5f0aa..b5db71b 100644 --- a/test/testhdf5.c +++ b/test/testhdf5.c @@ -45,7 +45,6 @@ main(int argc, char *argv[]) AddTest("config", test_configure, cleanup_configure, "Configure definitions", NULL); AddTest("metadata", test_metadata, cleanup_metadata, "Encoding/decoding metadata", NULL); AddTest("checksum", test_checksum, cleanup_checksum, "Checksum algorithm", NULL); - AddTest("heap", test_heap, NULL, "Memory Heaps", NULL); AddTest("skiplist", test_skiplist, NULL, "Skip Lists", NULL); AddTest("refstr", test_refstr, NULL, "Reference Counted Strings", NULL); AddTest("file", test_file, cleanup_file, "Low-Level File I/O", NULL); diff --git a/test/testhdf5.h b/test/testhdf5.h index ba5fa71..c5b8246 100644 --- a/test/testhdf5.h +++ b/test/testhdf5.h @@ -203,7 +203,6 @@ extern "C" { /* Prototypes for the test routines */ void test_metadata(void); void test_checksum(void); -void test_heap(void); void test_refstr(void); void test_file(void); void test_h5o(void); diff --git a/test/theap.c b/test/theap.c deleted file mode 100644 index 9d5787b..0000000 --- a/test/theap.c +++ /dev/null @@ -1,1081 +0,0 @@ -/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * - * 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() */ |