[svn-r12084] Purpose:

    Code checkpoint

Description:
    The fractal heap code is reasonably stable and is passing all its
current tests, so checkpoint everything with CVS.

    Also, add "statistics" module for v2 B-trees code, which is only a
stub right now.

Platforms tested:
    FreeBSD 4.11 (sleipnir)
    Mac OSX (amazon)
    Linux 2.4 (chicago)

1 files changed, 138 insertions, 19 deletions

diff --git a/src/H5HFpkg.h b/src/H5HFpkg.h
index c633919..27085fd 100644
--- a/src/H5HFpkg.h
+++ b/src/H5HFpkg.h
@@ -34,6 +34,7 @@
 #include "H5ACprivate.h"	/* Metadata cache			*/
 #include "H5FLprivate.h"	/* Free Lists                           */
 #include "H5RCprivate.h"	/* Reference counted object functions	*/
+#include "H5SLprivate.h"	/* Skip lists				*/
 
 /**************************/
 /* Package Private Macros */
@@ -45,6 +46,7 @@
 /* Fractal heap signatures */
 #define H5HF_HDR_MAGIC                  "FRHP"          /* Header */
 #define H5HF_DBLOCK_MAGIC               "FHDB"          /* Direct block */
+#define H5HF_IBLOCK_MAGIC               "FHIB"          /* Indirect block */
 
 /* "Standard" size of prefix information for fractal heap metadata */
 #define H5HF_METADATA_PREFIX_SIZE (                                           \
@@ -63,6 +65,9 @@
     + 2 /* Starting # of rows in root indirect block */                       \
     + H5F_SIZEOF_ADDR(f) /* File address of table managed */                  \
     + 2 /* Current # of rows in root indirect block */                        \
+    + H5F_SIZEOF_SIZE(f) /* Next direct block's heap offset */                \
+    + H5F_SIZEOF_SIZE(f) /* Next direct block's size */                       \
+    + 2 /* Next direct block's column */                                      \
     )
 
 /* Size of the fractal heap header on disk */
@@ -73,18 +78,28 @@
     /* Fractal heap header specific fields */                                 \
     + 1 /* Address mapping */                                                 \
     + 4 /* Min. size of standalone object */                                  \
-    + 4 /* Length of fixed-size objects */                                    \
     + 1 /* Size of ref. count for objects */                                  \
+    + H5F_SIZEOF_SIZE(f) /* Total man. free space */                          \
+    + H5F_SIZEOF_SIZE(f) /* Total std. free entries */                        \
+    + H5F_SIZEOF_SIZE(f) /* Total size of heap */                             \
+    + H5F_SIZEOF_SIZE(f) /* Size of man. space in heap */                     \
+    + H5F_SIZEOF_SIZE(f) /* Size of std. space in heap */                     \
+    + H5F_SIZEOF_SIZE(f) /* Number of objects in heap */                      \
     + H5HF_DTABLE_INFO_SIZE(f) /* 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_SIZE(s, o) (                       \
-    ((s)->fixed_len_obj ? 0 : H5HF_SIZEOF_OFFSET_LEN(o))  /* Length of object in block */ \
+    H5HF_SIZEOF_OFFSET_LEN(o)   /* Length of object in block */               \
+    + 1                         /* Free space fragment length */              \
     + (s)->ref_count_size       /* Ref. count of object in block */           \
     )
 #define H5HF_MAN_ABS_DIRECT_OBJ_PREFIX_LEN_DBLOCK(s, d) (                     \
-    ((s)->fixed_len_obj ? 0 : (d)->blk_off_size)  /* Length of object in block */ \
+    (d)->blk_off_size           /* Length of object in block */               \
+    + 1                         /* Free space fragment length */              \
     + (s)->ref_count_size       /* Ref. count of object in block */           \
     )
 
@@ -110,6 +125,19 @@
     + (d)->blk_off_size         /* Offset of first descriptor in free list */ \
     )
 
+/* Size of managed indirect block (absolute & mapped) */
+#define H5HF_MAN_INDIRECT_SIZE(s, i) (                                        \
+    /* General metadata fields */                                             \
+    H5HF_METADATA_PREFIX_SIZE                                                 \
+                                                                              \
+    /* Fractal heap managed, absolutely mapped indirect block specific fields */ \
+    + H5F_SIZEOF_ADDR((s)->f)   /* File address of heap owning the block */   \
+    + (s)->heap_off_size        /* Offset of the block in the heap */         \
+    + ((i)->ndir_rows * (s)->man_dtable.cparam.width * (H5F_SIZEOF_ADDR((s)->f) + (s)->man_dtable.max_dir_blk_off_size)) /* Size of entries for direct blocks */ \
+    + ((i)->nindir_rows * (s)->man_dtable.cparam.width * H5F_SIZEOF_ADDR((s)->f)) /* Size of entries for indirect blocks */ \
+    )
+
+
 /* Compute the # of bytes required to store an offset into a given buffer size */
 #define H5HF_SIZEOF_OFFSET_BITS(b)   (((b) + 7) / 8)
 #define H5HF_SIZEOF_OFFSET_LEN(l)   H5HF_SIZEOF_OFFSET_BITS(H5V_log2_of2((unsigned)(l)))
@@ -119,11 +147,11 @@
 /****************************/
 
 /* Doubling-table info */
-typedef struct H5HF_dtable_param_t {
+typedef struct H5HF_dtable_t {
     /* Immutable, pre-set information for table */
     H5HF_dtable_cparam_t    cparam;     /* Creation parameters for table */
 
-    /* Derived information (varies during lifetime of table) */
+    /* Derived information (stored, vary during lifetime of table) */
     haddr_t     table_addr;     /* Address of first block for table */
                                 /* Undefined if no space allocated for table */
     unsigned    curr_root_rows; /* Current number of rows in the root indirect block */
@@ -131,39 +159,60 @@ typedef struct H5HF_dtable_param_t {
                                  * to direct block (of START_BLOCK_SIZE) instead
                                  * of indirect root block.
                                  */
-} H5HF_dtable_param_t;
+    hsize_t     next_dir_block; /* Offset of next direct managed block */
+    size_t      next_dir_size;  /* Size of next managed direct block */
+    unsigned    next_dir_col;   /* "Column" of next managed direct block (in doubling table) */
+
+    /* Computed information (not stored) */
+    unsigned    max_root_indirect_rows; /* Maximum # of rows in root indirect block */
+    unsigned    max_direct_rows; /* Maximum # of direct rows in any indirect block */
+    unsigned    max_dir_blk_off_size;   /* Max. size of offsets in direct blocks */
+    unsigned    first_row_bits;  /* # of bits in address of first row */
+    hsize_t     num_id_first_row;   /* Number of IDs in first row of table */
+    hsize_t     *row_block_size;    /* Block size per row of indirect block */
+} H5HF_dtable_t;
+
+/* Fractal heap free list info (forward decl - defined in H5HFflist.c) */
+typedef struct H5HF_freelist_t H5HF_freelist_t;
+
+/* Fractal heap free list section info (forward decl - defined in H5HFint.c) */
+typedef struct H5HF_section_free_node_t H5HF_section_free_node_t;
 
 /* Each fractal heap has certain information that can be shared across all
  * the instances of blocks in that fractal heap.
  */
 typedef struct H5HF_shared_t {
     /* Shared internal information (varies during lifetime of heap) */
-    hsize_t     next_man_block; /* Offset of next direct managed block */
-    hsize_t     next_std_block; /* Offset of next direct standalone block */
     hsize_t     total_man_free; /* Total amount of free space in managed blocks */
     hsize_t     total_std_free; /* Total # of free standalone ID entries */
 
-    /* Cached/computed values */
+    /* Statistics for heap */
+    hsize_t     total_size;     /* Total amount of space used by heap (managed & standalone) */
+    hsize_t     man_size;       /* Total amount of managed space in heap */
+    hsize_t     std_size;       /* Total amount of standalone space in heap */
+    hsize_t     nobjs;          /* Number of objects in heap */
+
+    /* Cached/computed values (not stored in header) */
+    hbool_t     dirty;          /* Shared info is modified */
     haddr_t     heap_addr;      /* Address of heap header in the file */
     H5F_t      *f;              /* Pointer to file for heap */
+    H5HF_freelist_t *flist;     /* Free list for objects in heap */
 
     /* Doubling table information */
     /* (Partially set by user, partially derived/updated internally) */
-    H5HF_dtable_param_t man_dtable_info;        /* Doubling-table info for managed objects */
-    H5HF_dtable_param_t std_dtable_info;        /* Doubling-table info for standalone objects */
+    H5HF_dtable_t man_dtable;   /* Doubling-table info for managed objects */
+    H5HF_dtable_t std_dtable;   /* Doubling-table info for standalone objects */
 
     /* Information set by user */
     H5HF_addrmap_t addrmap;     /* Type of address mapping */
     uint32_t standalone_size;   /* Size of object to store standalone */
-    uint32_t fixed_len_size;    /* Size of objects (only for heaps w/fixed-length objects) */
     unsigned char ref_count_size; /* Size of ref. count for objects (only for heaps w/ref. counted objects) */
 
-    /* Information derived from user parameters */
-    hbool_t     fixed_len_obj;  /* Are objects in the heap fixed length? */
+    /* Information derived from user parameters (not stored in header) */
+    unsigned char heap_off_size; /* Size of heap offsets (in bytes) */
     hbool_t     ref_count_obj;  /* Are objects in the heap ref. counted? */
     hbool_t     have_io_filter; /* Does the heap have I/O filters for the direct blocks? */
     hbool_t     write_once;     /* Is heap being written in "write once" mode? */
-    unsigned char heap_off_size; /* Size of heap offsets (in bytes) */
 } H5HF_shared_t;
 
 /* The fractal heap header information */
@@ -177,6 +226,7 @@ typedef struct H5HF_t {
 
 /* 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 */
@@ -198,7 +248,7 @@ typedef struct H5HF_direct_t {
     /* Internal heap information */
     H5RC_t	*shared;	/* Ref-counted shared info	              */
     size_t      size;           /* Size of direct block                       */
-    size_t      blk_off_size;   /* Size of offsets in the block               */
+    unsigned    blk_off_size;   /* Size of offsets in the block               */
     H5HF_direct_free_head_t *free_list; /* Pointer to free list for block     */
     uint8_t     *blk;           /* Pointer to buffer containing block data    */
 
@@ -208,6 +258,45 @@ typedef struct H5HF_direct_t {
     size_t      free_list_head; /* Offset of head of free list in block       */
 } H5HF_direct_t;
 
+/* Indirect block direct block entry */
+typedef struct H5HF_indirect_dblock_ent_t {
+    haddr_t     addr;           /* Direct block's address                     */
+    size_t      free_space;     /* Amount of free space in direct block       */
+/* XXX: Will need space for block size, for blocks with I/O filters */
+} H5HF_indirect_dblock_ent_t;
+
+/* Indirect block indirect block entry */
+typedef struct H5HF_indirect_iblock_ent_t {
+    haddr_t     addr;           /* Indirect block's address                   */
+} H5HF_indirect_iblock_ent_t;
+
+/* Fractal heap indirect block */
+typedef struct H5HF_indirect_t {
+    /* Information for H5AC cache functions, _must_ be first field in structure */
+    H5AC_info_t cache_info;
+
+    /* Internal heap information */
+    H5RC_t	*shared;	/* Ref-counted shared info	              */
+    unsigned    nrows;          /* Total # of rows in indirect block          */
+    unsigned    ndir_rows;      /* # of direct rows in indirect block         */
+    unsigned    nindir_rows;    /* # of indirect rows in indirect block       */
+    size_t      size;           /* Size of indirect block on disk             */
+    H5HF_indirect_dblock_ent_t *dblock_ents;    /* Pointer to direct block entry table */
+    H5HF_indirect_iblock_ent_t *iblock_ents;    /* Pointer to indirect block entry table */
+
+    /* Stored values */
+    hsize_t     block_off;      /* Offset of the block within the heap's address space */
+} H5HF_indirect_t;
+
+/* Fractal heap metadata statistics info */
+typedef struct H5HF_stat_t {
+    hsize_t total_size;         /* Total size of heap allocated (man & std)   */
+    hsize_t man_size;           /* Total size of managed space in heap        */
+    hsize_t std_size;           /* Total size of standalone space in heap     */
+    hsize_t man_free_space;     /* Free space within heap                     */
+    hsize_t nobjs;              /* Number of objects in heap                  */
+} H5HF_stat_t;
+
 
 /*****************************/
 /* Package Private Variables */
@@ -219,6 +308,9 @@ H5_DLLVAR const H5AC_class_t H5AC_FHEAP_HDR[1];
 /* H5HF direct block inherits cache-like properties from H5AC */
 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];
+
 /* Declare a free list to manage the H5HF_t struct */
 H5FL_EXTERN(H5HF_t);
 
@@ -234,6 +326,14 @@ 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);
 
+/* Declare a free list to manage the H5HF_indirect_t struct */
+H5FL_EXTERN(H5HF_indirect_t);
+
+/* Declare a free list to manage the H5HF_indirect_dblock_ent_t sequence information */
+H5FL_SEQ_EXTERN(H5HF_indirect_dblock_ent_t);
+
+/* Declare a free list to manage the H5HF_indirect_iblock_ent_t sequence information */
+H5FL_SEQ_EXTERN(H5HF_indirect_iblock_ent_t);
 
 
 /******************************/
@@ -246,19 +346,38 @@ H5_DLL herr_t H5HF_shared_create(H5F_t *f, H5HF_t *fh, haddr_t heap_addr, H5HF_c
 H5_DLL herr_t H5HF_shared_own(H5HF_t *fh, H5HF_shared_t *shared);
 
 /* Routines for allocating space */
-H5_DLL herr_t H5HF_man_alloc_end(H5RC_t *fh_shared, hid_t dxpl_id, unsigned *fh_flags_ptr,
-    size_t size, const void *obj, void *id/*out*/);
-H5_DLL herr_t H5HF_man_dblock_build_freelist(H5HF_direct_t *dblock);
+H5_DLL herr_t H5HF_man_dblock_build_freelist(H5HF_direct_t *dblock, haddr_t dblock_addr);
+H5_DLL herr_t H5HF_man_find(H5RC_t *fh_shared, hid_t dxpl_id, size_t request,
+    H5HF_section_free_node_t **sec_node/*out*/);
+H5_DLL herr_t H5HF_man_insert(H5RC_t *fh_shared, hid_t dxpl_id,
+    H5HF_section_free_node_t *sec_node, size_t obj_size, const void *obj,
+    void *id);
 
 /* Metadata cache callbacks */
 H5_DLL herr_t H5HF_cache_hdr_dest(H5F_t *f, H5HF_t *fh);
 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);
 
 /* Debugging routines for dumping file structures */
 H5_DLL herr_t H5HF_hdr_debug(H5F_t *f, hid_t dxpl_id, haddr_t addr,
     FILE *stream, int indent, int fwidth);
 H5_DLL herr_t H5HF_dblock_debug(H5F_t *f, hid_t dxpl_id, haddr_t addr,
     FILE *stream, int indent, int fwidth, haddr_t hdr_addr, size_t nrec);
+H5_DLL herr_t H5HF_iblock_debug(H5F_t *f, hid_t dxpl_id, haddr_t addr,
+    FILE *stream, int indent, int fwidth, haddr_t hdr_addr, unsigned nrows);
+
+/* Statistics routines */
+H5_DLL herr_t H5HF_stat_info(H5F_t *f, hid_t dxpl_id, haddr_t fh_addr,
+    H5HF_stat_t *stats);
+
+/* Free list routines */
+H5_DLL H5HF_freelist_t * H5HF_flist_create(size_t max_block_size,
+    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_free(H5HF_freelist_t *flist);
 
 /* Testing routines */
 #ifdef H5HF_TESTING