summaryrefslogtreecommitdiffstats
path: root/src/H5HP.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/H5HP.c')
-rw-r--r--src/H5HP.c934
1 files changed, 934 insertions, 0 deletions
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() */
+