[svn-r6436] Purpose:

    New internal feature

Description:
    Add internal API for building and working with heaps (H5HP).  This will be
    used for the LRU algorithm in the new metadata cache code.

Platforms tested:
    Tested h5committest {arabica (fortran), eirene (fortran, C++)
	modi4 (parallel, fortran)}
    FreeBSD 4.7 (sleipnir)

8 files changed, 2107 insertions, 20 deletions

diff --git a/MANIFEST b/MANIFEST
index 137ada6..ca0c161 100644
--- a/MANIFEST
+++ b/MANIFEST
@@ -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() */
+