diff options
| -rw-r--r-- | MANIFEST | 3 | ||||
| -rw-r--r-- | src/H5HP.c | 934 | ||||
| -rw-r--r-- | src/H5HPprivate.h | 70 | ||||
| -rw-r--r-- | src/Makefile.in | 19 | ||||
| -rw-r--r-- | test/Dependencies | 13 | ||||
| -rw-r--r-- | test/Makefile.in | 30 | ||||
| -rw-r--r-- | test/testhdf5.c | 1 | ||||
| -rw-r--r-- | test/theap.c | 1057 |
8 files changed, 2107 insertions, 20 deletions
@@ -855,6 +855,8 @@ ./src/H5HL.c ./src/H5HLprivate.h ./src/H5HLpublic.h +./src/H5HP.c +./src/H5HPprivate.h ./src/H5I.c ./src/H5Iprivate.h ./src/H5Ipublic.h @@ -1005,6 +1007,7 @@ ./test/tgenprop.c ./test/th5s.c ./test/th5s.h5 +./test/theap.c ./test/titerate.c ./test/tmeta.c ./test/tmisc.c diff --git a/src/H5HP.c b/src/H5HP.c new file mode 100644 index 0000000..325392a --- /dev/null +++ b/src/H5HP.c @@ -0,0 +1,934 @@ +/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * + * 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 files COPYING and Copyright.html. COPYING can be found at the root * + * of the source code distribution tree; Copyright.html can be found at the * + * root level of an installed copy of the electronic HDF5 document set and * + * is linked from the top-level documents page. It can also be found at * + * http://hdf.ncsa.uiuc.edu/HDF5/doc/Copyright.html. If you do not have * + * access to either file, you may request a copy from hdfhelp@ncsa.uiuc.edu. * + * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ + +/* + * 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 */ + +/* Pablo information */ +#define PABLO_MASK H5HP_mask + +/* Interface initialization? */ +static int interface_initialize_g = 0; +#define INTERFACE_INIT NULL + +/* 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 arrays of H5HP_ent_t */ +H5FL_ARR_DEFINE_STATIC(H5HP_ent_t,-1); + + +/*-------------------------------------------------------------------------- + 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_NOINIT(H5HP_swim_max); + + /* 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_NOINIT(H5HP_swim_min); + + /* 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_NOINIT(H5HP_sink_max); + + /* 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=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_NOINIT(H5HP_sink_min); + + /* 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=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(H5HP_create,NULL); + + /* Check args */ + assert(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_ARR_MALLOC(H5HP_ent_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(ret_value==NULL) { + if(new_heap!=NULL) { + if(new_heap->heap!=NULL) + H5FL_ARR_FREE(H5HP_ent_t,new_heap->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(H5HP_count,FAIL); + + /* Check args */ + assert(heap); + + /* Check internal consistency */ + /* (Pre-condition) */ + assert(heap->nobjs<heap->nalloc); + assert(heap->heap); + assert((heap->type==H5HP_MAX_HEAP && heap->heap[0].val==INT_MAX) || + (heap->type==H5HP_MIN_HEAP && heap->heap[0].val==INT_MIN)); + assert(heap->heap[0].obj==NULL); + + /* Return the number of objects in the heap */ + ret_value=heap->nobjs; + +done: + /* 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(H5HP_insert,FAIL); + + /* Check args */ + assert(heap); + assert(obj); + + /* Check internal consistency */ + /* (Pre-condition) */ + assert(heap->nobjs<heap->nalloc); + assert(heap->heap); + assert((heap->type==H5HP_MAX_HEAP && heap->heap[0].val==INT_MAX) || + (heap->type==H5HP_MIN_HEAP && heap->heap[0].val==INT_MIN)); + assert(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_ARR_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=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) */ + assert(heap->nobjs<heap->nalloc); + assert(heap->heap); + assert((heap->type==H5HP_MAX_HEAP && heap->heap[0].val==INT_MAX) || + (heap->type==H5HP_MIN_HEAP && heap->heap[0].val==INT_MIN)); + assert(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) +{ + herr_t ret_value=SUCCEED; /* Return value */ + + FUNC_ENTER_NOAPI(H5HP_top,FAIL); + + /* Check args */ + assert(heap); + assert(val); + + /* Check internal consistency */ + /* (Pre-condition) */ + assert(heap->nobjs<heap->nalloc); + assert(heap->heap); + assert((heap->type==H5HP_MAX_HEAP && heap->heap[0].val==INT_MAX) || + (heap->type==H5HP_MIN_HEAP && heap->heap[0].val==INT_MIN)); + assert(heap->heap[0].obj==NULL); + + /* Get value of the top object in the heap */ + *val=heap->heap[1].val; + +done: + + /* No post-condition check necessary, since heap is constant */ + + FUNC_LEAVE_NOAPI(ret_value); +} /* 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(H5HP_remove,FAIL); + + /* Check args */ + assert(heap); + assert(val); + assert(obj); + + /* Check internal consistency */ + /* (Pre-condition) */ + assert(heap->nobjs<heap->nalloc); + assert(heap->heap); + assert((heap->type==H5HP_MAX_HEAP && heap->heap[0].val==INT_MAX) || + (heap->type==H5HP_MIN_HEAP && heap->heap[0].val==INT_MIN)); + assert(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 */ + assert(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,1)<0) + HGOTO_ERROR(H5E_HEAP, H5E_CANTDELETE, FAIL, "unable to restore heap condition"); + } /* end if */ + else { + if(H5HP_sink_min(heap,1)<0) + HGOTO_ERROR(H5E_HEAP, H5E_CANTDELETE, FAIL, "unable to restore heap condition"); + } /* end else */ + } /* end if */ + +done: + + /* Check internal consistency */ + /* (Post-condition) */ + assert(heap->nobjs<heap->nalloc); + assert(heap->heap); + assert((heap->type==H5HP_MAX_HEAP && heap->heap[0].val==INT_MAX) || + (heap->type==H5HP_MIN_HEAP && heap->heap[0].val==INT_MIN)); + assert(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(H5HP_change,FAIL); + + /* Check args */ + assert(heap); + assert(obj); + + /* Check internal consistency */ + /* (Pre-condition) */ + assert(heap->nobjs<heap->nalloc); + assert(heap->heap); + assert((heap->type==H5HP_MAX_HEAP && heap->heap[0].val==INT_MAX) || + (heap->type==H5HP_MIN_HEAP && heap->heap[0].val==INT_MIN)); + assert(heap->heap[0].obj==NULL); + + /* Get the location of the object in the heap */ + obj_loc=obj->heap_loc; + assert(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_CANTCHANGE, FAIL, "unable to restore heap condition"); + } /* end if */ + else { + if(H5HP_swim_min(heap,obj_loc)<0) + HGOTO_ERROR(H5E_HEAP, H5E_CANTCHANGE, 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_CANTCHANGE, FAIL, "unable to restore heap condition"); + } /* end if */ + else { + if(H5HP_sink_min(heap,obj_loc)<0) + HGOTO_ERROR(H5E_HEAP, H5E_CANTCHANGE, FAIL, "unable to restore heap condition"); + } /* end else */ + } /* end else */ + +done: + + /* Check internal consistency */ + /* (Post-condition) */ + assert(heap->nobjs<heap->nalloc); + assert(heap->heap); + assert((heap->type==H5HP_MAX_HEAP && heap->heap[0].val==INT_MAX) || + (heap->type==H5HP_MIN_HEAP && heap->heap[0].val==INT_MIN)); + assert(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(H5HP_incr,FAIL); + + /* Check args */ + assert(heap); + assert(obj); + + /* Check internal consistency */ + /* (Pre-condition) */ + assert(heap->nobjs<heap->nalloc); + assert(heap->heap); + assert((heap->type==H5HP_MAX_HEAP && heap->heap[0].val==INT_MAX) || + (heap->type==H5HP_MIN_HEAP && heap->heap[0].val==INT_MIN)); + assert(heap->heap[0].obj==NULL); + + /* Get the location of the object in the heap */ + obj_loc=obj->heap_loc; + assert(obj_loc>0 && obj_loc<=heap->nobjs); + + /* Change the heap object's priority */ + heap->heap[obj_loc].val+=amt; + + /* Restore heap condition */ + if(heap->type==H5HP_MAX_HEAP) { + if(H5HP_swim_max(heap,obj_loc)<0) + HGOTO_ERROR(H5E_HEAP, H5E_CANTCHANGE, FAIL, "unable to restore heap condition"); + } /* end if */ + else { + if(H5HP_sink_min(heap,obj_loc)<0) + HGOTO_ERROR(H5E_HEAP, H5E_CANTCHANGE, FAIL, "unable to restore heap condition"); + } /* end else */ + +done: + + /* Check internal consistency */ + /* (Post-condition) */ + assert(heap->nobjs<heap->nalloc); + assert(heap->heap); + assert((heap->type==H5HP_MAX_HEAP && heap->heap[0].val==INT_MAX) || + (heap->type==H5HP_MIN_HEAP && heap->heap[0].val==INT_MIN)); + assert(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(H5HP_decr,FAIL); + + /* Check args */ + assert(heap); + assert(obj); + + /* Check internal consistency */ + /* (Pre-condition) */ + assert(heap->nobjs<heap->nalloc); + assert(heap->heap); + assert((heap->type==H5HP_MAX_HEAP && heap->heap[0].val==INT_MAX) || + (heap->type==H5HP_MIN_HEAP && heap->heap[0].val==INT_MIN)); + assert(heap->heap[0].obj==NULL); + + /* Get the location of the object in the heap */ + obj_loc=obj->heap_loc; + assert(obj_loc>0 && obj_loc<=heap->nobjs); + + /* Change the heap object's priority */ + heap->heap[obj_loc].val-=amt; + + /* Restore heap condition */ + if(heap->type==H5HP_MAX_HEAP) { + if(H5HP_sink_max(heap,obj_loc)<0) + HGOTO_ERROR(H5E_HEAP, H5E_CANTCHANGE, FAIL, "unable to restore heap condition"); + } /* end if */ + else { + if(H5HP_swim_min(heap,obj_loc)<0) + HGOTO_ERROR(H5E_HEAP, H5E_CANTCHANGE, FAIL, "unable to restore heap condition"); + } /* end else */ + +done: + + /* Check internal consistency */ + /* (Post-condition) */ + assert(heap->nobjs<heap->nalloc); + assert(heap->heap); + assert((heap->type==H5HP_MAX_HEAP && heap->heap[0].val==INT_MAX) || + (heap->type==H5HP_MIN_HEAP && heap->heap[0].val==INT_MIN)); + assert(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) +{ + herr_t ret_value=SUCCEED; /* Return value */ + + FUNC_ENTER_NOAPI(H5HP_close,FAIL); + + /* Check args */ + assert(heap); + + /* Check internal consistency */ + /* (Pre-condition) */ + assert(heap->nobjs<heap->nalloc); + assert(heap->heap); + assert((heap->type==H5HP_MAX_HEAP && heap->heap[0].val==INT_MAX) || + (heap->type==H5HP_MIN_HEAP && heap->heap[0].val==INT_MIN)); + assert(heap->heap[0].obj==NULL); + + /* Free internal structures for heap */ + H5FL_ARR_FREE(H5HP_ent_t,heap->heap); + + /* Free actual heap object */ + H5FL_FREE(H5HP_t,heap); + +done: + FUNC_LEAVE_NOAPI(ret_value); +} /* end H5HP_close() */ + diff --git a/src/H5HPprivate.h b/src/H5HPprivate.h new file mode 100644 index 0000000..2c16ffe --- /dev/null +++ b/src/H5HPprivate.h @@ -0,0 +1,70 @@ +/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * + * 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 files COPYING and Copyright.html. COPYING can be found at the root * + * of the source code distribution tree; Copyright.html can be found at the * + * root level of an installed copy of the electronic HDF5 document set and * + * is linked from the top-level documents page. It can also be found at * + * http://hdf.ncsa.uiuc.edu/HDF5/doc/Copyright.html. If you do not have * + * access to either file, you may request a copy from hdfhelp@ncsa.uiuc.edu. * + * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ + +/* + * 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.in b/src/Makefile.in index ea0e957..2fe150b 100644 --- a/src/Makefile.in +++ b/src/Makefile.in @@ -33,12 +33,12 @@ LIB_SRC=H5.c H5A.c H5AC.c H5B.c H5D.c H5E.c H5F.c H5Farray.c H5Fcontig.c \ H5FDfphdf5.c H5FDgass.c H5FDlog.c H5FDmpio.c H5FDmpiposix.c \ H5FDmulti.c H5FDsec2.c H5FDsrb.c H5FDstdio.c H5FDstream.c H5FL.c \ H5FO.c H5FP.c H5FPclient.c H5FPserver.c H5FS.c H5G.c H5Gent.c \ - H5Gnode.c H5Gstab.c H5HG.c H5HL.c H5I.c H5MF.c H5MM.c H5O.c H5Oattr.c \ - H5Obogus.c H5Ocont.c H5Odtype.c H5Oefl.c H5Ofill.c H5Olayout.c \ - H5Omtime.c H5Oname.c H5Onull.c H5Opline.c H5Osdspace.c \ + H5Gnode.c H5Gstab.c H5HG.c H5HL.c H5HP.c H5I.c H5MF.c H5MM.c H5O.c \ + H5Oattr.c H5Obogus.c H5Ocont.c H5Odtype.c H5Oefl.c H5Ofill.c \ + H5Olayout.c H5Omtime.c H5Oname.c H5Onull.c H5Opline.c H5Osdspace.c \ H5Oshared.c H5Ostab.c H5P.c H5Pdcpl.c H5Pdxpl.c H5Pfapl.c H5Pfcpl.c \ - H5R.c H5RS.c H5S.c H5Sall.c H5Shyper.c H5Smpio.c H5Snone.c H5Spoint.c \ - H5Sselect.c H5ST.c H5T.c H5Tarray.c H5Tbit.c H5Tcommit.c \ + H5R.c H5RS.c H5S.c H5Sall.c H5Shyper.c H5Smpio.c H5Snone.c \ + H5Spoint.c H5Sselect.c H5ST.c H5T.c H5Tarray.c H5Tbit.c H5Tcommit.c \ H5Tcompound.c H5Tconv.c H5Tcset.c H5Tenum.c H5Tfields.c H5Tfixed.c \ H5Tfloat.c H5Tinit.c H5Tnative.c H5Toffset.c H5Topaque.c H5Torder.c \ H5Tpad.c H5Tprecis.c H5Tstrpad.c H5Tvlen.c H5TB.c H5TS.c H5V.c H5Z.c \ @@ -62,10 +62,11 @@ PUB_HDR=H5public.h H5Apublic.h H5ACpublic.h H5Bpublic.h H5Dpublic.h \ PRIVATE_HDR=H5private.h H5Aprivate.h H5Apkg.h H5ACprivate.h H5Bprivate.h \ H5Dprivate.h H5Eprivate.h H5Fprivate.h H5FDprivate.h H5FLprivate.h \ H5FOprivate.h H5FPprivate.h H5FSprivate.h H5Gprivate.h H5Gpkg.h \ - H5HGprivate.h H5HLprivate.h H5Iprivate.h H5MFprivate.h H5MMprivate.h \ - H5Oprivate.h H5Pprivate.h H5Ppkg.h H5Rprivate.h H5RSprivate.h \ - H5Sprivate.h H5STprivate.h H5Tprivate.h H5TBprivate.h H5Tpkg.h \ - H5TSprivate.h H5Vprivate.h H5Zprivate.h H5config.h + H5HGprivate.h H5HLprivate.h H5HPprivate.h H5Iprivate.h H5MFprivate.h \ + H5MMprivate.h H5Oprivate.h H5Opkg.h H5Pprivate.h H5Ppkg.h \ + H5Rprivate.h H5RSprivate.h H5Sprivate.h H5STprivate.h \ + H5Tprivate.h H5TBprivate.h H5Tpkg.h H5TSprivate.h H5Vprivate.h \ + H5Zprivate.h H5config.h ## Number format detection ## The LD_LIBRARY_PATH setting is a klutch. diff --git a/test/Dependencies b/test/Dependencies index bf71e7b..d214d45 100644 --- a/test/Dependencies +++ b/test/Dependencies @@ -1541,6 +1541,19 @@ ttbbt.lo: \ $(top_srcdir)/src/H5Epublic.h \ $(top_srcdir)/src/H5Ipublic.h \ $(top_srcdir)/src/H5TBprivate.h +theap.lo: \ + $(srcdir)/theap.c \ + $(srcdir)/testhdf5.h \ + $(top_srcdir)/src/H5private.h \ + $(top_srcdir)/src/H5public.h \ + $(top_builddir)/src/H5pubconf.h \ + $(top_srcdir)/src/H5api_adpt.h \ + $(top_srcdir)/src/H5MPprivate.h \ + $(top_srcdir)/src/H5FSprivate.h \ + $(top_srcdir)/src/H5Eprivate.h \ + $(top_srcdir)/src/H5Epublic.h \ + $(top_srcdir)/src/H5Ipublic.h \ + $(top_srcdir)/src/H5HPprivate.h ttst.lo: \ $(srcdir)/ttst.c \ $(srcdir)/testhdf5.h \ diff --git a/test/Makefile.in b/test/Makefile.in index 699a099..9ef6006 100644 --- a/test/Makefile.in +++ b/test/Makefile.in @@ -1,10 +1,18 @@ -## HDF5 Library Test Makefile(.in) ## -## Copyright (C) 1997, 2002 -## National Center for Supercomputing Applications. -## All rights reserved. +## 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 files COPYING and Copyright.html. COPYING can be found at the root +## of the source code distribution tree; Copyright.html can be found at the +## root level of an installed copy of the electronic HDF5 document set and +## is linked from the top-level documents page. It can also be found at +## http://hdf.ncsa.uiuc.edu/HDF5/doc/Copyright.html. If you do not have +## access to either file, you may request a copy from hdfhelp@ncsa.uiuc.edu. +## +## HDF5 Library Test Makefile(.in) ## -## top_srcdir=@top_srcdir@ top_builddir=.. srcdir=@srcdir@ @@ -65,8 +73,8 @@ TEST_SRC=big.c bittests.c cmpd_dset.c dsets.c dtypes.c extend.c \ external.c fillval.c flush1.c flush2.c gheap.c h5test.c hyperslab.c \ istore.c lheap.c links.c mount.c mtime.c ohdr.c stab.c tarray.c \ tattr.c tconfig.c testhdf5.c testmeta.c tfile.c tgenprop.c th5s.c \ - titerate.c tmeta.c trefer.c trefstr.c tselect.c ttime.c ttbbt.c \ - ttst.c tvltypes.c tvlstr.c tmisc.c unlink.c enum.c ttsafe.c \ + theap.c titerate.c tmeta.c trefer.c trefstr.c tselect.c ttime.c \ + ttbbt.c ttst.c tvltypes.c tvlstr.c tmisc.c unlink.c enum.c ttsafe.c \ ttsafe_dcreate.c ttsafe_error.c ttsafe_cancel.c ttsafe_acreate.c \ gass_write.c gass_read.c gass_append.c srb_read.c srb_write.c \ srb_append.c stream_test.c set_extent.c getname.c file_handle.c \ @@ -90,11 +98,11 @@ timings _timings: $(TIMINGS) ## How to build the tests... They all depend on the test and hdf5 libraries. $(TEST_PROGS): $(LIB) $(LIBHDF5) -TESTHDF5_OBJ=testhdf5.lo tarray.lo tattr.lo tconfig.lo tfile.lo tgenprop.lo \ - th5s.lo titerate.lo tmeta.lo ttime.lo trefer.lo trefstr.lo tselect.lo \ - ttbbt.lo ttst.lo tvltypes.lo tvlstr.lo tmisc.lo +TESTHDF5_OBJ=testhdf5.lo tarray.lo tattr.lo tconfig.lo tfile.lo tgenprop.lo \ + th5s.lo theap.lo titerate.lo tmeta.lo ttime.lo trefer.lo trefstr.lo \ + tselect.lo ttbbt.lo ttst.lo tvltypes.lo tvlstr.lo tmisc.lo -TTS_OBJ=ttsafe.lo ttsafe_dcreate.lo ttsafe_error.lo ttsafe_cancel.lo \ +TTS_OBJ=ttsafe.lo ttsafe_dcreate.lo ttsafe_error.lo ttsafe_cancel.lo \ ttsafe_acreate.lo testhdf5: $(TESTHDF5_OBJ) diff --git a/test/testhdf5.c b/test/testhdf5.c index 08d718a..b3c29a7 100644 --- a/test/testhdf5.c +++ b/test/testhdf5.c @@ -158,6 +158,7 @@ main(int argc, char *argv[]) InitTest("metadata", test_metadata, cleanup_metadata, "Encode/decode metadata code"); InitTest("tbbt", test_tbbt, NULL, "Threaded, Balanced, Binary Trees"); InitTest("tst", test_tst, NULL, "Ternary Search Trees"); + InitTest("heap", test_heap, NULL, "Memory Heaps"); InitTest("refstr", test_refstr, NULL, "Reference Counted Strings"); InitTest("file", test_file, cleanup_file, "Low-Level File I/O"); InitTest("h5s", test_h5s, cleanup_h5s, "Dataspaces"); diff --git a/test/theap.c b/test/theap.c new file mode 100644 index 0000000..b02055e --- /dev/null +++ b/test/theap.c @@ -0,0 +1,1057 @@ +/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * + * 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 files COPYING and Copyright.html. COPYING can be found at the root * + * of the source code distribution tree; Copyright.html can be found at the * + * root level of an installed copy of the electronic HDF5 document set and * + * is linked from the top-level documents page. It can also be found at * + * http://hdf.ncsa.uiuc.edu/HDF5/doc/Copyright.html. If you do not have * + * access to either file, you may request a copy from hdfhelp@ncsa.uiuc.edu. * + * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ + +/* + Test HDF Heap routines. + + REMARKS + + DESIGN + + BUGS/LIMITATIONS + + EXPORTED ROUTINES + + AUTHOR + Quincey Koziol + + MODIFICATION HISTORY + 2/18/03 - Started coding + */ + +#include <time.h> +#include <stdlib.h> + +#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[NUM_ELEMS]; + +/* Array of random elements values, sorted in increasing order */ +static test_obj inc_sort_num[NUM_ELEMS]; + +/* Array of random elements values, sorted in decreasing order */ +static test_obj dec_sort_num[NUM_ELEMS]; + +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 */ + + /* Create randomized set of numbers */ + curr_time=time(NULL); + HDsrandom((unsigned long)curr_time); + for(u=0; u<NUM_ELEMS; u++) + /* Generate random numbers from -1000 to 1000 */ + rand_num[u].val=(HDrandom()%2001)-1001; + + /* Sort random numbers into increasing order */ + HDmemcpy(inc_sort_num,rand_num,sizeof(test_obj)*NUM_ELEMS); + HDqsort(inc_sort_num,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,NUM_ELEMS,sizeof(test_obj),tst_dec_sort); +} /* end test_tst_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(heap, NULL, "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(heap, NULL, "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(heap, NULL, "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(heap, NULL, "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(heap, NULL, "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,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,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,NUM_ELEMS,dec_sort_num[0].val); + + /* Test creating a heap from random elements */ + test_heap_insert_many_core(H5HP_MIN_HEAP, rand_num,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,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,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(heap, NULL, "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"); + VERIFY(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"); + VERIFY(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"); + VERIFY(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(heap, NULL, "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"); + VERIFY(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"); + VERIFY(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"); + VERIFY(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(heap, NULL, "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) { + num_errs++; + printf("Error on line %d: incorrect value from heap=%d, last_val=%d\n",__LINE__,val,last_val); + } /* end if */ + } /* end if */ + else { + if(val<last_val) { + num_errs++; + printf("Error on line %d: incorrect value from heap=%d, last_val=%d\n",__LINE__,val,last_val); + } /* end if */ + } /* 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) { + num_errs++; + printf("Error on line %d: incorrect value from heap=%d, last_val=%d\n",__LINE__,val,last_val); + } /* end if */ + } /* end if */ + else { + if(val<last_val) { + num_errs++; + printf("Error on line %d: incorrect value from heap=%d, last_val=%d\n",__LINE__,val,last_val); + } /* end if */ + } /* 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,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,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,NUM_ELEMS); + + /* Test removing objects from minimum heap with random elements */ + test_heap_remove_many_core(H5HP_MIN_HEAP, rand_num,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,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,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(heap, NULL, "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(heap, NULL, "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(heap, NULL, "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(heap, NULL, "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(): 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 */ + +} /* end test_heap() */ + |