[svn-r12349] Purpose:

    Code checkpoint

Description:
    Checkpoint fractal heap improvements, as well as move the free space
manager code that it's using into a separate package.

Platforms tested:
    FreeBSD 4.11 (sleipnir)
    Linux 2.4/64 (mir) w/C++ & FORTRAN
    Linux 2.4/32 (heping)
    Solaris 2.9 (shanti)
    AIX 5.? (copper) w/FORTRAN & parallel

1 files changed, 70 insertions, 119 deletions

diff --git a/src/H5HFpkg.h b/src/H5HFpkg.h
index af06770..96e5b57 100644
--- a/src/H5HFpkg.h
+++ b/src/H5HFpkg.h
@@ -33,7 +33,7 @@
 /* Other private headers needed by this file */
 #include "H5ACprivate.h"	/* Metadata cache			*/
 #include "H5FLprivate.h"	/* Free Lists                           */
-#include "H5RCprivate.h"	/* Reference counted object functions	*/
+#include "H5FSprivate.h"	/* File free space                      */
 #include "H5SLprivate.h"	/* Skip lists				*/
 
 /**************************/
@@ -77,6 +77,7 @@
     + 4 /* Min. size of standalone object */                                  \
     + (h)->sizeof_size /* Total man. free space */                            \
     + (h)->sizeof_size /* Total std. free entries */                          \
+    + (h)->sizeof_addr /* File address of free section header */              \
     + (h)->sizeof_size /* Total size of heap */                               \
     + (h)->sizeof_size /* Size of man. space in heap */                       \
     + (h)->sizeof_size /* Size of alloacted man. space in heap */             \
@@ -85,32 +86,14 @@
     + H5HF_DTABLE_INFO_SIZE(h) /* Size of managed obj. doubling-table info */ \
     )
 
-/* Size of free space description in an absolute managed direct block */
-#define H5HF_MAN_ABS_DIRECT_FREE_NODE_SIZE(d) (2 * (d)->blk_off_size)
-
-/* Size of header for each object in an absolute managed direct block */
-#define H5HF_MAN_ABS_DIRECT_OBJ_PREFIX_LEN(h) (                               \
-    + 1                         /* Free space fragment length */              \
-    )
-
 /* Size of overhead for a direct block */
-#define H5HF_MAN_ABS_DIRECT_OVERHEAD_SIZE(h, s) (                             \
-    /* General metadata fields */                                             \
-    H5HF_METADATA_PREFIX_SIZE                                                 \
-                                                                              \
-    /* Fractal heap managed, absolutely mapped direct block specific fields */ \
-    + (h)->sizeof_addr          /* File address of heap owning the block */   \
-    + (h)->heap_off_size        /* Offset of the block in the heap */         \
-    + H5HF_SIZEOF_OFFSET_LEN(s) /* Offset of first descriptor in free list */ \
-    )
-#define H5HF_MAN_ABS_DIRECT_OVERHEAD_DBLOCK(h, d) (                           \
+#define H5HF_MAN_ABS_DIRECT_OVERHEAD(h) (                                     \
     /* General metadata fields */                                             \
     H5HF_METADATA_PREFIX_SIZE                                                 \
                                                                               \
     /* Fractal heap managed, absolutely mapped direct block specific fields */ \
     + (h)->sizeof_addr          /* File address of heap owning the block */   \
     + (h)->heap_off_size        /* Offset of the block in the heap */         \
-    + (d)->blk_off_size         /* Offset of first descriptor in free list */ \
     )
 
 /* Size of managed indirect block (absolute & mapped) */
@@ -121,8 +104,8 @@
     /* Fractal heap managed, absolutely mapped indirect block specific fields */ \
     + (h)->sizeof_addr          /* File address of heap owning the block */   \
     + (h)->heap_off_size        /* Offset of the block in the heap */         \
-    + (MIN((i)->nrows, (h)->man_dtable.max_direct_rows) * (h)->man_dtable.cparam.width * ((h)->sizeof_addr + (h)->man_dtable.max_dir_blk_off_size)) /* Size of entries for direct blocks */ \
-    + ((((i)->nrows > (h)->man_dtable.max_direct_rows) ? ((i)->nrows - (h)->man_dtable.max_direct_rows) : 0)  * (h)->man_dtable.cparam.width * ((h)->sizeof_addr + (h)->heap_off_size)) /* Size of entries for indirect blocks */ \
+    + (MIN((i)->nrows, (h)->man_dtable.max_direct_rows) * (h)->man_dtable.cparam.width * (h)->sizeof_addr) /* Size of entries for direct blocks */ \
+    + ((((i)->nrows > (h)->man_dtable.max_direct_rows) ? ((i)->nrows - (h)->man_dtable.max_direct_rows) : 0)  * (h)->man_dtable.cparam.width * (h)->sizeof_addr) /* Size of entries for indirect blocks */ \
     )
 
 
@@ -130,6 +113,12 @@
 #define H5HF_SIZEOF_OFFSET_BITS(b)   (((b) + 7) / 8)
 #define H5HF_SIZEOF_OFFSET_LEN(l)   H5HF_SIZEOF_OFFSET_BITS(H5V_log2_of2((unsigned)(l)))
 
+/* Free space section types for fractal heap */
+/* (values stored in free space data structures in file) */
+#define H5FS_SECT_FHEAP_SINGLE        0       /* Section is actual bytes in a direct block */
+#define H5FS_SECT_FHEAP_RANGE         1       /* Section is a range of direct blocks */
+#define H5FS_SECT_FHEAP_INDIRECT      2       /* Section is a range of _indirect_ blocks in an indirect block row */
+
 /****************************/
 /* Package Private Typedefs */
 /****************************/
@@ -189,6 +178,36 @@ typedef struct H5HF_block_iter_t {
     H5HF_block_loc_t *curr;     /* Pointer to the current level information for iterator */
 } H5HF_block_iter_t;
 
+/* Fractal heap free space section info */
+typedef struct H5HF_free_section_t {
+    H5FS_section_info_t sect_info;              /* Free space section information (must be first in struct) */
+    union {
+        struct {
+            H5HF_indirect_t *parent;            /* Indirect block parent for free section's direct block */
+            unsigned par_entry;                 /* Entry of free section's direct block in parent indirect block */
+                                                /* (Needed to retrieve direct block) */
+
+            haddr_t     dblock_addr;            /* Address of direct block for free section */
+            size_t      dblock_size;            /* Size of direct block */
+                                                /* (Needed to retrieve direct block) */
+        } single;
+        struct {
+            H5HF_indirect_t *iblock;            /* Indirect block for free section */
+            unsigned    row;                    /* Row for range of blocks */
+            unsigned    col;                    /* Column for range of blocks */
+            unsigned    num_entries;            /* Number of entries covered */
+        } range;
+        struct {
+            H5HF_indirect_t *iblock;            /* Indirect block for free section */
+            unsigned    row;                    /* Row for range of blocks */
+            unsigned    col;                    /* Column for range of blocks */
+            unsigned    num_entries;            /* Number of entries covered */
+            unsigned    indir_row;              /* Row for indirect range of blocks */
+            unsigned    indir_nrows;            /* Number of rows in indirect blocks */
+        } indirect;
+    } u;
+} H5HF_free_section_t;
+
 /* The fractal heap header information */
 /* (Each fractal heap header has certain information that is shared across all
  * the instances of blocks in that fractal heap)
@@ -200,6 +219,7 @@ typedef struct H5HF_hdr_t {
     /* Shared internal information (varies during lifetime of heap) */
     hsize_t     total_man_free; /* Total amount of free space in managed blocks */
     hsize_t     total_std_free; /* Total # of free standalone ID entries */
+    haddr_t     fs_addr;        /* Address of free space header on disk */
 
     /* Statistics for heap */
     hsize_t     total_size;     /* Total amount of space used by heap (managed & standalone) */
@@ -217,15 +237,11 @@ typedef struct H5HF_hdr_t {
     size_t      sizeof_size;    /* Size of file sizes */
     size_t      sizeof_addr;    /* Size of file addresses */
     size_t      id_len;         /* Size of heap IDs */
-    H5HF_freelist_t *flist;     /* Free list for objects in heap */
-    unsigned    fl_gen;         /* Free list "generation" */
+    size_t      nsect_classes;  /* Number of free space section classes */
+    H5FS_section_class_t *sect_cls;     /* Array of free space section classes */
+    H5FS_t      *fspace;        /* Free space list for objects in heap */
+    hbool_t     fspace_open;    /* Whether free space is ready */
     H5HF_block_iter_t next_block;   /* Block iterator for searching for next block with space */
-    hbool_t     freelist_sync;  /* If the heap's free list in memory is in sync with the free list on disk */
-                                /* (ie. all existing blocks have been scanned
-                                 *  for free space (or heap is new and there are
-                                 *  no blocks with unknown free space) and new
-                                 *  free space is added by adding new blocks)
-                                 */
 
     /* Doubling table information */
     /* (Partially set by user, partially derived/updated internally) */
@@ -246,7 +262,6 @@ typedef struct H5HF_hdr_t {
 /* Indirect block entry */
 typedef struct H5HF_indirect_ent_t {
     haddr_t     addr;           /* Direct block's address                     */
-    hsize_t     free_space;     /* Amount of free space in block pointed to   */
 /* XXX: Will need space for block size, for blocks with I/O filters */
 } H5HF_indirect_ent_t;
 
@@ -259,10 +274,8 @@ struct H5HF_indirect_t {
     size_t      rc;             /* Reference count of child blocks            */
     hbool_t     dirty;          /* Info is modified                           */
     H5HF_hdr_t	*hdr;	        /* Shared heap header info	              */
-    unsigned    fl_gen;         /* Free list "generation"                     */
     struct H5HF_indirect_t *parent;	/* Shared parent indirect block info  */
     unsigned    par_entry;      /* Entry in parent's table                    */
-    hsize_t     child_free_space;   /* Total amount of free space in children */
     haddr_t     addr;           /* Address of this indirect block on disk     */
     unsigned    nrows;          /* Total # of rows in indirect block          */
     unsigned    max_rows;       /* Max. # of rows in indirect block           */
@@ -273,22 +286,6 @@ struct H5HF_indirect_t {
     H5HF_indirect_ent_t *ents;  /* Pointer to block entry table               */
 };
 
-/* Direct block free list node */
-typedef struct H5HF_direct_free_node_t {
-    /* Direct block free list info */
-    size_t      size;                           /* Size of free space */
-    size_t      my_offset;                      /* Offset of free space in block */
-    size_t      next_offset;                    /* Offset of next free space in block */
-    struct H5HF_direct_free_node_t *prev;       /* Previous node in free list */
-    struct H5HF_direct_free_node_t *next;       /* Next node in free list */
-} H5HF_direct_free_node_t;
-
-/* Direct block free list header */
-typedef struct H5HF_direct_free_head_t {
-    H5HF_direct_free_node_t *first;     /* First node in free list */
-    hbool_t dirty;                      /* Free list is modified */
-} H5HF_direct_free_head_t;
-
 /* A fractal heap direct block */
 typedef struct H5HF_direct_t {
     /* Information for H5AC cache functions, _must_ be first field in structure */
@@ -296,18 +293,14 @@ typedef struct H5HF_direct_t {
 
     /* Internal heap information */
     H5HF_hdr_t	*hdr;	        /* Shared heap header info	              */
-    unsigned    fl_gen;         /* Free list "generation"                     */
     H5HF_indirect_t *parent;	/* Shared parent indirect block info          */
     unsigned    par_entry;      /* Entry in parent's table                    */
     size_t      size;           /* Size of direct block                       */
     unsigned    blk_off_size;   /* Size of offsets in the block               */
-    size_t      blk_free_space; /* Total amount of free space in block        */
-    H5HF_direct_free_head_t *free_list; /* Pointer to free list for block     */
     uint8_t     *blk;           /* Pointer to buffer containing block data    */
 
     /* Stored values */
     hsize_t     block_off;      /* Offset of the block within the heap's address space */
-    size_t      free_list_head; /* Offset of head of free list in block       */
 } H5HF_direct_t;
 
 /* Fractal heap */
@@ -325,50 +318,6 @@ typedef struct H5HF_stat_t {
     hsize_t nobjs;              /* Number of objects in heap                  */
 } H5HF_stat_t;
 
-/* Fractal heap free list section info */
-typedef struct H5HF_free_section_t {
-    haddr_t     sect_addr;                      /* Address of free list section in the file */
-                                                /* (Not actually used as address, used as unique ID for free list node) */
-    size_t      sect_size;                      /* Size of free space section */
-                                                /* (section size is "object size", without the metadata overhead, since metadata overhead varies from block to block) */
-                                                /* (for range sections, this is the largest single section within the range) */
-    enum {
-            H5HF_SECT_SINGLE,                   /* Section is actual bytes in a direct block */
-            H5HF_SECT_OPAQUE,                   /* Section is an opaque # of bytes in child of an indirect block */
-            H5HF_SECT_RANGE,                    /* Section is a range of direct blocks in an indirect block row */
-            H5HF_SECT_INDIRECT}                 /* Section is a range of _indirect_ blocks in an indirect block row */
-        type;                                   /* Type of free space section */
-    union {
-        struct {
-            H5HF_indirect_t *parent;            /* Indirect block parent for free section's direct block */
-            unsigned par_entry;                 /* Entry of free section's direct block in parent indirect block */
-                                                /* (Needed to retrieve direct block) */
-
-            haddr_t     dblock_addr;            /* Address of direct block for free section */
-            size_t      dblock_size;            /* Size of direct block */
-                                                /* (Needed to retrieve direct block) */
-        } single;
-        struct {
-            H5HF_indirect_t *iblock;            /* Indirect block parent for free section's child block */
-            unsigned entry;                     /* Entry of free section's child block in parent indirect block */
-        } opaque;
-        struct {
-            H5HF_indirect_t *iblock;            /* Indirect block for free section */
-            unsigned    row;                    /* Row for range of blocks */
-            unsigned    col;                    /* Column for range of blocks */
-            unsigned    num_entries;            /* Number of entries covered */
-        } range;
-        struct {
-            H5HF_indirect_t *iblock;            /* Indirect block for free section */
-            unsigned    row;                    /* Row for range of blocks */
-            unsigned    col;                    /* Column for range of blocks */
-            unsigned    num_entries;            /* Number of entries covered */
-            unsigned    indir_row;              /* Row for indirect range of blocks */
-            unsigned    indir_nrows;            /* Number of rows in indirect blocks */
-        } indirect;
-    } u;
-} H5HF_free_section_t;
-
 /* Fractal heap "parent info" (for loading a block) */
 typedef struct H5HF_parent_t {
     H5HF_hdr_t *hdr;                /* Pointer to heap header info */
@@ -389,18 +338,21 @@ H5_DLLVAR const H5AC_class_t H5AC_FHEAP_DBLOCK[1];
 /* H5HF indirect block inherits cache-like properties from H5AC */
 H5_DLLVAR const H5AC_class_t H5AC_FHEAP_IBLOCK[1];
 
+/* H5HF single section inherits serializable properties from H5FS_section_class_t */
+H5_DLLVAR H5FS_section_class_t H5FS_SECT_CLS_FHEAP_SINGLE[1];
+
+/* H5HF range section inherits serializable properties from H5FS_section_class_t */
+H5_DLLVAR H5FS_section_class_t H5FS_SECT_CLS_FHEAP_RANGE[1];
+
+/* H5HF indirect section inherits serializable properties from H5FS_section_class_t */
+H5_DLLVAR H5FS_section_class_t H5FS_SECT_CLS_FHEAP_INDIRECT[1];
+
 /* Declare a free list to manage the H5HF_hdr_t struct */
 H5FL_EXTERN(H5HF_hdr_t);
 
 /* Declare a free list to manage the H5HF_direct_t struct */
 H5FL_EXTERN(H5HF_direct_t);
 
-/* Declare a free list to manage the H5HF_direct_free_head_t struct */
-H5FL_EXTERN(H5HF_direct_free_head_t);
-
-/* Declare a free list to manage the H5HF_direct_free_node_t struct */
-H5FL_EXTERN(H5HF_direct_free_node_t);
-
 /* Declare a free list to manage heap direct block data to/from disk */
 H5FL_BLK_EXTERN(direct_block);
 
@@ -434,6 +386,7 @@ H5_DLL unsigned H5HF_dtable_size_to_row(H5HF_dtable_t *dtable, size_t block_size
 H5_DLL herr_t H5HF_hdr_incr(H5HF_hdr_t *hdr);
 H5_DLL herr_t H5HF_hdr_decr(H5HF_hdr_t *hdr);
 H5_DLL herr_t H5HF_hdr_dirty(H5HF_hdr_t *hdr);
+H5_DLL herr_t H5HF_hdr_adj_free(H5HF_hdr_t *hdr, ssize_t amt);
 H5_DLL herr_t H5HF_hdr_extend_heap(H5HF_hdr_t *hdr, hsize_t new_size, hsize_t extra_free);
 H5_DLL herr_t H5HF_hdr_inc_alloc(H5HF_hdr_t *hdr, hsize_t new_alloc_size,
     unsigned nentries);
@@ -444,12 +397,12 @@ H5_DLL herr_t H5HF_iblock_decr(H5HF_indirect_t *iblock);
 H5_DLL herr_t H5HF_iblock_dirty(H5HF_indirect_t *iblock);
 H5_DLL H5HF_indirect_t * H5HF_man_iblock_place_dblock(H5HF_hdr_t *fh, hid_t dxpl_id,
     size_t min_dblock_size, size_t *entry_p, size_t *dblock_size);
+H5_DLL herr_t H5HF_man_iblock_alloc_single(H5HF_hdr_t *hdr, hid_t dxpl_id,
+    H5HF_free_section_t *sec_node);
 H5_DLL herr_t H5HF_man_iblock_alloc_range(H5HF_hdr_t *hdr, hid_t dxpl_id,
     H5HF_free_section_t **sec_node);
 H5_DLL herr_t H5HF_man_iblock_alloc_indirect(H5HF_hdr_t *hdr, hid_t dxpl_id,
     H5HF_free_section_t **sec_node);
-H5_DLL herr_t H5HF_man_iblock_alloc_opaque(H5HF_hdr_t *hdr, hid_t dxpl_id,
-    H5HF_free_section_t **sec_node);
 H5_DLL H5HF_indirect_t *H5HF_man_iblock_protect(H5HF_hdr_t *hdr, hid_t dxpl_id,
     haddr_t iblock_addr, unsigned iblock_nrows,
     H5HF_indirect_t *par_iblock, unsigned par_entry,
@@ -457,9 +410,6 @@ H5_DLL H5HF_indirect_t *H5HF_man_iblock_protect(H5HF_hdr_t *hdr, hid_t dxpl_id,
 
 /* Direct block routines */
 H5_DLL herr_t H5HF_man_dblock_new(H5HF_hdr_t *fh, hid_t dxpl_id, size_t request);
-H5_DLL herr_t H5HF_man_dblock_build_freelist(H5HF_direct_t *dblock, haddr_t dblock_addr);
-H5_DLL herr_t H5HF_man_dblock_destroy_freelist(H5HF_direct_t *dblock);
-H5_DLL herr_t H5HF_man_dblock_adj_free(H5HF_direct_t *dblock, ssize_t amt);
 H5_DLL herr_t H5HF_man_dblock_create(hid_t dxpl_id, H5HF_hdr_t *hdr,
     H5HF_indirect_t *par_iblock, unsigned par_entry, size_t block_size,
     hsize_t block_off, haddr_t *addr_p, H5HF_free_section_t **ret_sec_node);
@@ -471,6 +421,9 @@ H5_DLL H5HF_direct_t *H5HF_man_dblock_protect(H5HF_hdr_t *hdr, hid_t dxpl_id,
 /* Routines for internal operations */
 H5_DLL herr_t H5HF_free_section_free_cb(void *item, void UNUSED *key,
     void UNUSED *op_data);
+H5_DLL herr_t H5HF_man_locate_block(H5HF_hdr_t *hdr, hid_t dxpl_id,
+    hsize_t obj_off, hbool_t locate_indirect, H5HF_indirect_t **par_iblock,
+    unsigned *par_entry, H5AC_protect_t rw);
 H5_DLL herr_t H5HF_man_find(H5HF_hdr_t *fh, hid_t dxpl_id, size_t request,
     H5HF_free_section_t **sec_node/*out*/);
 H5_DLL herr_t H5HF_man_insert(H5HF_hdr_t *fh, hid_t dxpl_id,
@@ -480,7 +433,7 @@ H5_DLL herr_t H5HF_man_read(H5HF_hdr_t *fh, hid_t dxpl_id, hsize_t obj_off,
     size_t obj_len, void *obj);
 
 /* Metadata cache callbacks */
-H5_DLL herr_t H5HF_cache_hdr_dest(H5F_t *f, H5HF_hdr_t *fh);
+H5_DLL herr_t H5HF_cache_hdr_dest(H5F_t *f, H5HF_hdr_t *hdr);
 H5_DLL herr_t H5HF_cache_dblock_dest(H5F_t *f, H5HF_direct_t *dblock);
 H5_DLL herr_t H5HF_cache_iblock_dest(H5F_t *f, H5HF_indirect_t *iblock);
 
@@ -495,16 +448,6 @@ H5_DLL herr_t H5HF_iblock_debug(H5F_t *f, hid_t dxpl_id, haddr_t addr,
 /* Statistics routines */
 H5_DLL herr_t H5HF_stat_info(H5HF_t *fh, H5HF_stat_t *stats);
 
-/* Free list routines */
-H5_DLL H5HF_freelist_t * H5HF_flist_create(unsigned max_index_bits,
-    H5SL_operator_t node_free_op);
-H5_DLL herr_t H5HF_flist_add(H5HF_freelist_t *flist, void *node, size_t *size_key,
-    haddr_t *addr_key);
-H5_DLL htri_t H5HF_flist_find(H5HF_freelist_t *flist, size_t request,
-    void **node);
-H5_DLL herr_t H5HF_flist_reset(H5HF_freelist_t *flist);
-H5_DLL herr_t H5HF_flist_free(H5HF_freelist_t *flist);
-
 /* Block iteration routines */
 H5_DLL herr_t H5HF_man_iter_init(H5HF_block_iter_t *biter);
 H5_DLL herr_t H5HF_man_iter_start_offset(H5HF_hdr_t *hdr, hid_t dxpl_id,
@@ -523,10 +466,18 @@ H5_DLL herr_t H5HF_man_iter_offset(H5HF_hdr_t *hdr, H5HF_block_iter_t *biter,
     hsize_t *offset);
 H5_DLL hbool_t H5HF_man_iter_ready(H5HF_block_iter_t *biter);
 
+/* Free space manipulation routines */
+H5_DLL herr_t H5HF_space_start(H5HF_hdr_t *hdr, hid_t dxpl_id);
+H5_DLL htri_t H5HF_space_find(H5HF_hdr_t *hdr, hid_t dxpl_id, hsize_t request,
+    H5HF_free_section_t **node);
+H5_DLL herr_t H5HF_space_add(H5HF_hdr_t *hdr, hid_t dxpl_id, H5HF_free_section_t *node);
+H5_DLL herr_t H5HF_space_close(H5HF_hdr_t *hdr, hid_t dxpl_id);
+
 /* Testing routines */
 #ifdef H5HF_TESTING
 H5_DLL herr_t H5HF_get_cparam_test(H5HF_t *fh, H5HF_create_t *cparam);
 H5_DLL hsize_t H5HF_get_dblock_free_test(H5HF_t *fh, unsigned row);
+H5_DLL size_t H5HF_get_dblock_overhead(H5HF_t *fh);
 #endif /* H5HF_TESTING */
 
 #endif /* _H5HFpkg_H */