[svn-r9582] Purpose:

    Add new internal data structure

Description:
    Add an implementation of skip lists to the library (see comment in
src/H5SL.c for references to the papers describing them) as a potential
replacement for our current threaded, balanced binary tree container.
Skip lists are much simpler to implement and should be faster to use.

    Also, added new error codes to release branch, so bump the minor version
number to indicate that the library is no longer perfectly compatible with
the 1.6.3 release.

Platforms tested:
    FreeBSD 4.10 (sleipnir) w/parallel
    Solaris 2.7 (arabica)
    Too minor to require further testing (the skip lists aren't actually
    used by any library code yet)

6 files changed, 58 insertions, 34 deletions

diff --git a/src/H5E.c b/src/H5E.c
index 16f8b03..daf45ae 100644
--- a/src/H5E.c
+++ b/src/H5E.c
@@ -71,9 +71,9 @@ static const H5E_major_mesg_t H5E_major_mesg_g[] = {
     {H5E_REFERENCE,	"References layer"},
     {H5E_VFL,		"Virtual File Layer"},
     {H5E_TBBT,		"Threaded, Balanced, Binary Trees"},
-    {H5E_FPHDF5,	"Flexible Parallel HDF5"},
     {H5E_TST,		"Ternary Search Trees"},
     {H5E_RS,		"Reference Counted Strings"},
+    {H5E_SLIST,		"Skip Lists"},
 };
 
 static const H5E_minor_mesg_t H5E_minor_mesg_g[] = {
@@ -93,6 +93,8 @@ static const H5E_minor_mesg_t H5E_minor_mesg_g[] = {
     {H5E_ALREADYEXISTS, "Object already exists"},
     {H5E_CANTLOCK, 	"Unable to lock object"},
     {H5E_CANTUNLOCK, 	"Unable to unlock object"},
+    {H5E_CANTGC, 	"Unable to garbage collect"},
+    {H5E_CANTGETSIZE, 	"Unable to compute size"},
 
     /* File accessability errors */
     {H5E_FILEEXISTS, 	"File already exists"},
@@ -128,9 +130,15 @@ static const H5E_minor_mesg_t H5E_minor_mesg_g[] = {
 
     /* Cache related errors */
     {H5E_CANTFLUSH, 	"Unable to flush data from cache"},
-    {H5E_CANTLOAD, 	"Unable to load meta data into cache"},
-    {H5E_PROTECT, 	"Protected meta data error"},
-    {H5E_NOTCACHED, 	"Meta data not currently cached"},
+    {H5E_CANTSERIALIZE, "Unable to serialize data from cache"},
+    {H5E_CANTLOAD, 	"Unable to load metadata into cache"},
+    {H5E_PROTECT, 	"Protected metadata error"},
+    {H5E_NOTCACHED, 	"Metadata not currently cached"},
+    {H5E_SYSTEM, 	"Internal error detected"},
+    {H5E_CANTINS, 	"Unable to insert metadata into cache"},
+    {H5E_CANTRENAME, 	"Unable to rename metadata"},
+    {H5E_CANTPROTECT, 	"Unable to protect metadata"},
+    {H5E_CANTUNPROTECT,	"Unable to unprotect metadata"},
 
     /* B-tree related errors */
     {H5E_NOTFOUND, 	"Object not found"},
@@ -150,6 +158,7 @@ static const H5E_minor_mesg_t H5E_minor_mesg_g[] = {
 
     /* Group related errors */
     {H5E_CANTOPENOBJ, 	"Can't open object"},
+    {H5E_CANTCLOSEOBJ, 	"Can't close object"},
     {H5E_COMPLEN, 	"Name component is too long"},
     {H5E_CWG, 		"Problem with current working group"},
     {H5E_LINK, 		"Link count failure"},
@@ -176,12 +185,11 @@ static const H5E_minor_mesg_t H5E_minor_mesg_g[] = {
     {H5E_MPI,		"Some MPI function failed"},
     {H5E_MPIERRSTR,     "MPI Error String"},
 
-    /* FPHDF5 errors */
-    {H5E_CANTMAKETREE,  "Can't create a binary tree node"},
-    {H5E_CANTRECV,      "Can't receive messages from processes"},
-    {H5E_CANTSENDMDATA, "Can't send metadata message"},
-    {H5E_CANTCHANGE,    "Can't register change with server"},
-    {H5E_CANTALLOC,     "Can't allocate from file"},
+    /* Heap errors */
+    {H5E_CANTRESTORE,	"Can't restore condition"},
+
+    /* TBBT errors */
+    {H5E_CANTMAKETREE,	"Can't create TBBT tree"},
 
     /* I/O pipeline errors */
     {H5E_NOFILTER,      "Requested filter is not available"},
diff --git a/src/H5Epublic.h b/src/H5Epublic.h
index 3ac6fd0..bbf2e20 100644
--- a/src/H5Epublic.h
+++ b/src/H5Epublic.h
@@ -101,9 +101,9 @@ typedef enum H5E_major_t {
     H5E_REFERENCE,              /*References                                 */
     H5E_VFL,			/*Virtual File Layer			     */
     H5E_TBBT, 		        /*Threaded, Balanced, Binary Trees           */
-    H5E_FPHDF5,		        /*Flexible Parallel HDF5                     */
     H5E_TST, 		        /*Ternary Search Trees                       */
-    H5E_RS  		        /*Reference Counted Strings                  */
+    H5E_RS,  		        /*Reference Counted Strings                  */
+    H5E_SLIST  		        /*Skip Lists                                 */
 } H5E_major_t;
 
 /* Declare an enumerated type which holds all the valid minor HDF error codes */
@@ -124,6 +124,8 @@ typedef enum H5E_minor_t {
     H5E_ALREADYEXISTS,          /*Object already exists */
     H5E_CANTLOCK,               /*Unable to lock object                      */
     H5E_CANTUNLOCK,             /*Unable to unlock object                    */
+    H5E_CANTGC,                 /*Unable to garbage collect                  */
+    H5E_CANTGETSIZE,            /*Unable to compute size                     */
 
     /* File accessability errors */
     H5E_FILEEXISTS,             /*file already exists                        */
@@ -159,9 +161,15 @@ typedef enum H5E_minor_t {
 
     /* Cache related errors */
     H5E_CANTFLUSH,              /*Can't flush object from cache              */
+    H5E_CANTSERIALIZE,          /*Unable to serialize data from cache        */
     H5E_CANTLOAD,               /*Can't load object into cache               */
     H5E_PROTECT,                /*protected object error                     */
     H5E_NOTCACHED,              /*object not currently cached                */
+    H5E_SYSTEM,                 /*Internal error detected                    */
+    H5E_CANTINS,                /*Unable to insert metadata into cache       */
+    H5E_CANTRENAME,             /*Unable to rename metadata                  */
+    H5E_CANTPROTECT,            /*Unable to protect metadata                 */
+    H5E_CANTUNPROTECT,          /*Unable to unprotect metadata               */
 
     /* B-tree related errors */
     H5E_NOTFOUND,               /*object not found                           */
@@ -181,6 +189,7 @@ typedef enum H5E_minor_t {
 
     /* Group related errors */
     H5E_CANTOPENOBJ,            /*Can't open object                          */
+    H5E_CANTCLOSEOBJ,           /*Can't close object                         */
     H5E_COMPLEN,                /*name component is too long                 */
     H5E_CWG,                    /*problem with current working group         */
     H5E_LINK,                   /*link count failure                         */
@@ -207,12 +216,11 @@ typedef enum H5E_minor_t {
     H5E_MPI,			/*some MPI function failed		     */
     H5E_MPIERRSTR,		/*MPI Error String 			     */
 
-    /* FPHDF5 errors */
-    H5E_CANTMAKETREE,           /*can't make a TBBT tree                     */
-    H5E_CANTRECV,               /*can't receive messages from processes      */
-    H5E_CANTSENDMDATA,          /*can't send metadata message                */
-    H5E_CANTCHANGE,             /*can't register change on server            */
-    H5E_CANTALLOC,              /*can't allocate from file                   */
+    /* Heap errors */
+    H5E_CANTRESTORE,		/*Can't restore condition                    */
+
+    /* TBBT errors */
+    H5E_CANTMAKETREE,		/*Can't create TBBT tree                     */
 
     /* I/O pipeline errors */
     H5E_NOFILTER,               /*requested filter is not available          */
diff --git a/src/H5HP.c b/src/H5HP.c
index bfcce4e..26b6f39 100644
--- a/src/H5HP.c
+++ b/src/H5HP.c
@@ -20,15 +20,16 @@
  *
  */
 
+/* Pablo information */
+/* (Put before include files to avoid problems with inline functions) */
+#define PABLO_MASK	H5HP_mask
+
 /* 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
@@ -710,21 +711,21 @@ H5HP_change(H5HP_t *heap, int val, void *_obj)
     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");
+                HGOTO_ERROR(H5E_HEAP, H5E_CANTRESTORE, FAIL, "unable to restore heap condition");
         } /* end if */
         else {
             if(H5HP_swim_min(heap,obj_loc)<0)
-                HGOTO_ERROR(H5E_HEAP, H5E_CANTCHANGE, FAIL, "unable to restore heap condition");
+                HGOTO_ERROR(H5E_HEAP, H5E_CANTRESTORE, FAIL, "unable to restore heap condition");
         } /* end else */
     } /* end if */
     else {
         if(heap->type==H5HP_MAX_HEAP) {
             if(H5HP_swim_max(heap,obj_loc)<0)
-                HGOTO_ERROR(H5E_HEAP, H5E_CANTCHANGE, FAIL, "unable to restore heap condition");
+                HGOTO_ERROR(H5E_HEAP, H5E_CANTRESTORE, FAIL, "unable to restore heap condition");
         } /* end if */
         else {
             if(H5HP_sink_min(heap,obj_loc)<0)
-                HGOTO_ERROR(H5E_HEAP, H5E_CANTCHANGE, FAIL, "unable to restore heap condition");
+                HGOTO_ERROR(H5E_HEAP, H5E_CANTRESTORE, FAIL, "unable to restore heap condition");
         } /* end else */
     } /* end else */
 
@@ -793,11 +794,11 @@ H5HP_incr(H5HP_t *heap, unsigned amt, void *_obj)
     /* 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");
+            HGOTO_ERROR(H5E_HEAP, H5E_CANTRESTORE, FAIL, "unable to restore heap condition");
     } /* end if */
     else {
         if(H5HP_sink_min(heap,obj_loc)<0)
-            HGOTO_ERROR(H5E_HEAP, H5E_CANTCHANGE, FAIL, "unable to restore heap condition");
+            HGOTO_ERROR(H5E_HEAP, H5E_CANTRESTORE, FAIL, "unable to restore heap condition");
     } /* end else */
 
 done:
@@ -865,11 +866,11 @@ H5HP_decr(H5HP_t *heap, unsigned amt, void *_obj)
     /* 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");
+            HGOTO_ERROR(H5E_HEAP, H5E_CANTRESTORE, FAIL, "unable to restore heap condition");
     } /* end if */
     else {
         if(H5HP_swim_min(heap,obj_loc)<0)
-            HGOTO_ERROR(H5E_HEAP, H5E_CANTCHANGE, FAIL, "unable to restore heap condition");
+            HGOTO_ERROR(H5E_HEAP, H5E_CANTRESTORE, FAIL, "unable to restore heap condition");
     } /* end else */
 
 done:
diff --git a/src/H5SL.c b/src/H5SL.c
index 4e2e646..7f4b187 100644
--- a/src/H5SL.c
+++ b/src/H5SL.c
@@ -130,7 +130,12 @@ struct H5SL_t {
     H5SL_node_t *header;        /* Header for nodes in skip list */
 };
 
+/* Interface initialization */
+static int interface_initialize_g = 0;
+#define INTERFACE_INIT H5SL_init_interface
+
 /* Static functions */
+static herr_t H5SL_init_interface(void);
 static size_t H5SL_random_level(double p, size_t max_level);
 static H5SL_node_t * H5SL_new_node(size_t lvl, void *item, void *key);
 
diff --git a/src/H5public.h b/src/H5public.h
index e1051c5..56a93c9 100644
--- a/src/H5public.h
+++ b/src/H5public.h
@@ -77,10 +77,10 @@ extern "C" {
 /* Version numbers */
 #define H5_VERS_MAJOR	1	/* For major interface/format changes  	     */
 #define H5_VERS_MINOR	6	/* For minor interface/format changes  	     */
-#define H5_VERS_RELEASE	3	/* For tweaks, bug-fixes, or development     */
-#define H5_VERS_SUBRELEASE "post2"	/* For pre-releases like snap0       */
+#define H5_VERS_RELEASE	4	/* For tweaks, bug-fixes, or development     */
+#define H5_VERS_SUBRELEASE "pre1"	/* For pre-releases like snap0       */
 				/* Empty string for real releases.           */
-#define H5_VERS_INFO    "HDF5 library version: 1.6.3-post2"      /* Full version string */
+#define H5_VERS_INFO    "HDF5 library version: 1.6.4-pre1"      /* Full version string */
 
 #define H5check()	H5check_version(H5_VERS_MAJOR,H5_VERS_MINOR,	      \
 				        H5_VERS_RELEASE)
diff --git a/src/Makefile.in b/src/Makefile.in
index f8c6e68..9247513 100644
--- a/src/Makefile.in
+++ b/src/Makefile.in
@@ -42,7 +42,8 @@ LIB_SRC=H5.c H5A.c H5AC.c H5B.c H5C.c H5D.c H5Dcontig.c H5Dcompact.c H5Defl.c \
         H5Oname.c H5Onull.c H5Opline.c H5Osdspace.c H5Oshared.c H5Ostab.c     \
         H5P.c H5Pdcpl.c H5Pdxpl.c H5Pfapl.c H5Pfcpl.c H5Ptest.c H5R.c H5RC.c  \
         H5RS.c H5S.c H5Sall.c H5Shyper.c H5Smpio.c H5Snone.c H5Spoint.c       \
-        H5Sselect.c H5Stest.c H5ST.c H5T.c H5Tarray.c H5Tbit.c H5Tcommit.c    \
+        H5Sselect.c H5Stest.c H5SL.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  \
@@ -70,7 +71,8 @@ PRIVATE_HDR=H5private.h H5Aprivate.h H5Apkg.h H5ACprivate.h H5Bprivate.h      \
         H5FOprivate.h H5FSprivate.h H5Gprivate.h H5Gpkg.h                     \
         H5HGprivate.h H5HLprivate.h H5HPprivate.h H5Iprivate.h H5MFprivate.h  \
         H5MMprivate.h H5Oprivate.h H5Opkg.h H5Pprivate.h H5Ppkg.h             \
-        H5Rprivate.h H5RCprivate.h H5RSprivate.h H5Sprivate.h H5STprivate.h   \
+        H5Rprivate.h H5RCprivate.h H5RSprivate.h H5Sprivate.h H5SLprivate.h   \
+        H5STprivate.h \
         H5Tprivate.h H5TBprivate.h H5Tpkg.h H5TSprivate.h H5Vprivate.h        \
         H5Zprivate.h H5Zpkg.h H5config.h