H5B2pkg.h

00001 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
00002  * Copyright by The HDF Group.                                               *
00003  * Copyright by the Board of Trustees of the University of Illinois.         *
00004  * All rights reserved.                                                      *
00005  *                                                                           *
00006  * This file is part of HDF5.  The full HDF5 copyright notice, including     *
00007  * terms governing use, modification, and redistribution, is contained in    *
00008  * the files COPYING and Copyright.html.  COPYING can be found at the root   *
00009  * of the source code distribution tree; Copyright.html can be found at the  *
00010  * root level of an installed copy of the electronic HDF5 document set and   *
00011  * is linked from the top-level documents page.  It can also be found at     *
00012  * http://hdfgroup.org/HDF5/doc/Copyright.html.  If you do not have          *
00013  * access to either file, you may request a copy from help@hdfgroup.org.     *
00014  * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
00015 
00016 /*
00017  * Programmer:  Quincey Koziol <koziol@ncsa.uiuc.edu>
00018  *              Monday, January 31, 2005
00019  *
00020  * Purpose:     This file contains declarations which are visible only within
00021  *              the H5B2 package.  Source files outside the H5B2 package should
00022  *              include H5B2private.h instead.
00023  */
00024 #ifndef H5B2_PACKAGE
00025 #error "Do not include this file outside the H5B2 package!"
00026 #endif
00027 
00028 #ifndef _H5B2pkg_H
00029 #define _H5B2pkg_H
00030 
00031 /* Get package's private header */
00032 #include "H5B2private.h"
00033 
00034 /* Other private headers needed by this file */
00035 #include "H5ACprivate.h"        /* Metadata cache                       */
00036 #include "H5FLprivate.h"        /* Free Lists                           */
00037 
00038 
00039 /**************************/
00040 /* Package Private Macros */
00041 /**************************/
00042 
00043 /* Size of storage for number of records per node (on disk) */
00044 #define H5B2_SIZEOF_RECORDS_PER_NODE    (unsigned)2
00045 
00046 /* Size of a "tree pointer" (on disk) */
00047 /* (essentially, the largest internal pointer allowed) */
00048 #define H5B2_TREE_POINTER_SIZE(h)       (                                     \
00049     (h)->sizeof_addr +                                                        \
00050     H5B2_SIZEOF_RECORDS_PER_NODE +                                            \
00051     (h)->sizeof_size                                                          \
00052     )
00053 
00054 /* Size of a internal node pointer (on disk) */
00055 #define H5B2_INT_POINTER_SIZE(h, d) (                                         \
00056     (h)->sizeof_addr            /* Address of child node */                   \
00057     + (h)->max_nrec_size        /* # of records in child node */              \
00058     + (h)->node_info[(d) - 1].cum_max_nrec_size /* Total # of records in child & below */ \
00059     )
00060 
00061 /* Size of checksum information (on disk) */
00062 #define H5B2_SIZEOF_CHKSUM      4
00063 
00064 /* Format overhead for all v2 B-tree metadata in the file */
00065 #define H5B2_METADATA_PREFIX_SIZE (                                           \
00066     (unsigned)H5_SIZEOF_MAGIC   /* Signature */                               \
00067     + (unsigned)1 /* Version */                                               \
00068     + (unsigned)1 /* Tree type */                                             \
00069     + (unsigned)H5B2_SIZEOF_CHKSUM /* Metadata checksum */                    \
00070     )
00071 
00072 /* Size of the v2 B-tree header on disk */
00073 #define H5B2_HEADER_SIZE(h)   (                                             \
00074     /* General metadata fields */                                             \
00075     H5B2_METADATA_PREFIX_SIZE                                                 \
00076                                                                               \
00077     /* Header specific fields */                                              \
00078     + (unsigned)4 /* Node size, in bytes */                                   \
00079     + (unsigned)2 /* Record size, in bytes */                                 \
00080     + (unsigned)2 /* Depth of tree */                                         \
00081     + (unsigned)1 /* Split % of full (as integer, ie. "98" means 98%) */      \
00082     + (unsigned)1 /* Merge % of full (as integer, ie. "98" means 98%) */      \
00083     + H5B2_TREE_POINTER_SIZE(h)  /* Node pointer to root node in tree */      \
00084     )
00085 
00086 /* Size of the v2 B-tree internal node prefix */
00087 #define H5B2_INT_PREFIX_SIZE (                                                \
00088     /* General metadata fields */                                             \
00089     H5B2_METADATA_PREFIX_SIZE                                                 \
00090                                                                               \
00091     /* Header specific fields */                                              \
00092     /* <none> */                                                              \
00093     )
00094 
00095 /* Size of the v2 B-tree leaf node prefix */
00096 #define H5B2_LEAF_PREFIX_SIZE (                                               \
00097     /* General metadata fields */                                             \
00098     H5B2_METADATA_PREFIX_SIZE                                                 \
00099                                                                               \
00100     /* Header specific fields */                                              \
00101     /* <none> */                                                              \
00102     )
00103 
00104 /* Macro to retrieve pointer to i'th native record for native record buffer */
00105 #define H5B2_NAT_NREC(b, hdr, idx)  ((b) + (hdr)->nat_off[(idx)])
00106 
00107 /* Macro to retrieve pointer to i'th native record for internal node */
00108 #define H5B2_INT_NREC(i, hdr, idx)  H5B2_NAT_NREC((i)->int_native, (hdr), (idx))
00109 
00110 /* Macro to retrieve pointer to i'th native record for leaf node */
00111 #define H5B2_LEAF_NREC(l, hdr, idx)  H5B2_NAT_NREC((l)->leaf_native, (hdr), (idx))
00112 
00113 /* Number of records that fit into internal node */
00114 /* (accounts for extra node pointer by counting it in with the prefix bytes) */
00115 #define H5B2_NUM_INT_REC(h, d) \
00116     (((h)->node_size - (H5B2_INT_PREFIX_SIZE + H5B2_INT_POINTER_SIZE(h, d))) / ((h)->rrec_size + H5B2_INT_POINTER_SIZE(h, d)))
00117 
00118 
00119 /****************************/
00120 /* Package Private Typedefs */
00121 /****************************/
00122 
00123 /* A "node pointer" to another B-tree node */
00124 typedef struct {
00125     haddr_t     addr;           /* Address of other node */
00126     uint16_t    node_nrec;      /* Number of records used in node pointed to */
00127     hsize_t     all_nrec;       /* Number of records in node pointed to and all it's children */
00128 } H5B2_node_ptr_t;
00129 
00130 /* Information about a node at a given depth */
00131 typedef struct {
00132     unsigned    max_nrec;       /* Max. number of records in node */
00133     unsigned    split_nrec;     /* Number of records to split node at */
00134     unsigned    merge_nrec;     /* Number of records to merge node at */
00135     hsize_t     cum_max_nrec;   /* Cumulative max. # of records below this node's depth */
00136     uint8_t     cum_max_nrec_size; /* Size to store cumulative max. # of records for this node (in bytes) */
00137     H5FL_fac_head_t *nat_rec_fac;   /* Factory for native record blocks */
00138     H5FL_fac_head_t *node_ptr_fac;  /* Factory for node pointer blocks */
00139 } H5B2_node_info_t;
00140 
00141 /* The B-tree header information */
00142 typedef struct H5B2_hdr_t {
00143     /* Information for H5AC cache functions, _must_ be first field in structure */
00144     H5AC_info_t cache_info;
00145 
00146     /* Internal B-tree information (stored) */
00147     H5B2_node_ptr_t root;       /* Node pointer to root node in B-tree        */
00148 
00149     /* Information set by user (stored) */
00150     uint8_t     split_percent;  /* Percent full at which to split the node, when inserting */
00151     uint8_t     merge_percent;  /* Percent full at which to merge the node, when deleting */
00152     uint32_t    node_size;      /* Size of B-tree nodes, in bytes             */
00153     uint32_t    rrec_size;      /* Size of "raw" (on disk) record, in bytes   */
00154 
00155     /* Dynamic information (stored) */
00156     uint16_t    depth;          /* B-tree's overall depth                     */
00157 
00158     /* Derived information from user's information (not stored) */
00159     uint8_t     max_nrec_size;  /* Size to store max. # of records in any node (in bytes) */
00160 
00161     /* Shared internal data structures (not stored) */
00162     H5F_t       *f;             /* Pointer to the file that the B-tree is in */
00163     haddr_t     addr;           /* Address of B-tree header in the file */
00164     size_t      rc;             /* Reference count of nodes using this header */
00165     size_t      file_rc;        /* Reference count of files using this header */
00166     hbool_t     pending_delete; /* B-tree is pending deletion */
00167     uint8_t     sizeof_size;    /* Size of file sizes */
00168     uint8_t     sizeof_addr;    /* Size of file addresses */
00169     H5B2_remove_t remove_op;    /* Callback operator for deleting B-tree */
00170     void        *remove_op_data;/* B-tree deletion callback's context */
00171     uint8_t     *page;          /* Common disk page for I/O */
00172     size_t      *nat_off;       /* Array of offsets of native records */
00173     H5B2_node_info_t *node_info; /* Table of node info structs for current depth of B-tree */
00174 
00175     /* Client information (not stored) */
00176     const H5B2_class_t *cls;    /* Class of B-tree client */
00177     void        *cb_ctx;        /* Client callback context */
00178 } H5B2_hdr_t;
00179 
00180 /* B-tree leaf node information */
00181 typedef struct H5B2_leaf_t {
00182     /* Information for H5AC cache functions, _must_ be first field in structure */
00183     H5AC_info_t cache_info;
00184 
00185     /* Internal B-tree information */
00186     H5B2_hdr_t  *hdr;           /* Pointer to the [pinned] v2 B-tree header   */
00187     uint8_t     *leaf_native;   /* Pointer to native records                  */
00188     uint16_t    nrec;           /* Number of records in node                  */
00189 } H5B2_leaf_t;
00190 
00191 /* B-tree internal node information */
00192 typedef struct H5B2_internal_t {
00193     /* Information for H5AC cache functions, _must_ be first field in structure */
00194     H5AC_info_t cache_info;
00195 
00196     /* Internal B-tree information */
00197     H5B2_hdr_t  *hdr;           /* Pointer to the [pinned] v2 B-tree header   */
00198     uint8_t     *int_native;    /* Pointer to native records                  */
00199     H5B2_node_ptr_t *node_ptrs; /* Pointer to node pointers                   */
00200     uint16_t    nrec;           /* Number of records in node                  */
00201     uint16_t    depth;          /* Depth of this node in the B-tree           */
00202 } H5B2_internal_t;
00203 
00204 /* v2 B-tree */
00205 struct H5B2_t {
00206     H5B2_hdr_t  *hdr;           /* Pointer to internal v2 B-tree header info */
00207     H5F_t      *f;              /* Pointer to file for v2 B-tree */
00208 };
00209 
00210 /* User data for metadata cache 'load' callback */
00211 typedef struct {
00212     H5B2_hdr_t  *hdr;           /* Pointer to the [pinned] v2 B-tree header   */
00213     uint16_t    nrec;           /* Number of records in node to load */
00214     uint16_t    depth;          /* Depth of node to load */
00215 } H5B2_int_load_ud1_t;
00216 
00217 #ifdef H5B2_TESTING
00218 /* Node information for testing */
00219 typedef struct {
00220     unsigned depth;             /* Depth of node */
00221     unsigned nrec;              /* Number of records in node */
00222 } H5B2_node_info_test_t;
00223 #endif /* H5B2_TESTING */
00224 
00225 
00226 /*****************************/
00227 /* Package Private Variables */
00228 /*****************************/
00229 
00230 /* H5B2 header inherits cache-like properties from H5AC */
00231 H5_DLLVAR const H5AC_class_t H5AC_BT2_HDR[1];
00232 
00233 /* H5B2 internal node inherits cache-like properties from H5AC */
00234 H5_DLLVAR const H5AC_class_t H5AC_BT2_INT[1];
00235 
00236 /* H5B2 leaf node inherits cache-like properties from H5AC */
00237 H5_DLLVAR const H5AC_class_t H5AC_BT2_LEAF[1];
00238 
00239 /* Declare a free list to manage the H5B2_internal_t struct */
00240 H5FL_EXTERN(H5B2_internal_t);
00241 
00242 /* Declare a free list to manage the H5B2_leaf_t struct */
00243 H5FL_EXTERN(H5B2_leaf_t);
00244 
00245 /* Internal v2 B-tree testing class */
00246 #ifdef H5B2_TESTING
00247 H5_DLLVAR const H5B2_class_t H5B2_TEST[1];
00248 #endif /* H5B2_TESTING */
00249 
00250 /* Array of v2 B-tree client ID -> client class mappings */
00251 extern const H5B2_class_t *const H5B2_client_class_g[];
00252 
00253 
00254 /******************************/
00255 /* Package Private Prototypes */
00256 /******************************/
00257 
00258 /* Routines for managing B-tree header info */
00259 H5_DLL H5B2_hdr_t *H5B2_hdr_alloc(H5F_t *f);
00260 H5_DLL haddr_t H5B2_hdr_create(H5F_t *f, hid_t dxpl_id,
00261     const H5B2_create_t *cparam, void *ctx_udata);
00262 H5_DLL herr_t H5B2_hdr_init(H5F_t *f, H5B2_hdr_t *hdr,
00263     const H5B2_create_t *cparam, void *ctx_udata, uint16_t depth);
00264 H5_DLL herr_t H5B2_hdr_incr(H5B2_hdr_t *hdr);
00265 H5_DLL herr_t H5B2_hdr_decr(H5B2_hdr_t *hdr);
00266 H5_DLL herr_t H5B2_hdr_fuse_incr(H5B2_hdr_t *hdr);
00267 H5_DLL size_t H5B2_hdr_fuse_decr(H5B2_hdr_t *hdr);
00268 H5_DLL herr_t H5B2_hdr_dirty(H5B2_hdr_t *hdr);
00269 H5_DLL herr_t H5B2_hdr_free(H5B2_hdr_t *hdr);
00270 H5_DLL herr_t H5B2_hdr_delete(H5B2_hdr_t *hdr, hid_t dxpl_id);
00271 
00272 /* Routines for operating on internal nodes */
00273 H5_DLL H5B2_internal_t *H5B2_protect_internal(H5B2_hdr_t *hdr, hid_t dxpl_id,
00274     haddr_t addr, unsigned nrec, unsigned depth, H5AC_protect_t rw);
00275 
00276 /* Routines for allocating nodes */
00277 H5_DLL herr_t H5B2_split_root(H5B2_hdr_t *hdr, hid_t dxpl_id);
00278 H5_DLL herr_t H5B2_create_leaf(H5B2_hdr_t *hdr, hid_t dxpl_id,
00279     H5B2_node_ptr_t *node_ptr);
00280 
00281 /* Routines for inserting records */
00282 H5_DLL herr_t H5B2_insert_internal(H5B2_hdr_t *hdr, hid_t dxpl_id,
00283     unsigned depth, unsigned *parent_cache_info_flags_ptr,
00284     H5B2_node_ptr_t *curr_node_ptr, void *udata);
00285 H5_DLL herr_t H5B2_insert_leaf(H5B2_hdr_t *hdr, hid_t dxpl_id,
00286     H5B2_node_ptr_t *curr_node_ptr, void *udata);
00287 
00288 /* Routines for iterating over nodes/records */
00289 H5_DLL herr_t H5B2_iterate_node(H5B2_hdr_t *hdr, hid_t dxpl_id, unsigned depth,
00290     const H5B2_node_ptr_t *curr_node, H5B2_operator_t op, void *op_data);
00291 H5_DLL herr_t H5B2_node_size(H5B2_hdr_t *hdr, hid_t dxpl_id,
00292     unsigned depth, const H5B2_node_ptr_t *curr_node, hsize_t *op_data);
00293 
00294 /* Routines for locating records */
00295 H5_DLL int H5B2_locate_record(const H5B2_class_t *type, unsigned nrec,
00296     size_t *rec_off, const uint8_t *native, const void *udata, unsigned *idx);
00297 H5_DLL herr_t H5B2_neighbor_internal(H5B2_hdr_t *hdr, hid_t dxpl_id,
00298     unsigned depth, H5B2_node_ptr_t *curr_node_ptr, void *neighbor_loc,
00299     H5B2_compare_t comp, void *udata, H5B2_found_t op, void *op_data);
00300 H5_DLL herr_t H5B2_neighbor_leaf(H5B2_hdr_t *hdr, hid_t dxpl_id,
00301     H5B2_node_ptr_t *curr_node_ptr, void *neighbor_loc,
00302     H5B2_compare_t comp, void *udata, H5B2_found_t op, void *op_data);
00303 
00304 /* Routines for removing records */
00305 H5_DLL herr_t H5B2_remove_internal(H5B2_hdr_t *hdr, hid_t dxpl_id,
00306     hbool_t *depth_decreased, void *swap_loc, unsigned depth, H5AC_info_t *parent_cache_info,
00307     hbool_t * parent_cache_info_dirtied_ptr, H5B2_node_ptr_t *curr_node_ptr, void *udata,
00308     H5B2_remove_t op, void *op_data);
00309 H5_DLL herr_t H5B2_remove_leaf(H5B2_hdr_t *hdr, hid_t dxpl_id,
00310     H5B2_node_ptr_t *curr_node_ptr, void *udata, H5B2_remove_t op,
00311     void *op_data);
00312 H5_DLL herr_t H5B2_remove_internal_by_idx(H5B2_hdr_t *hdr, hid_t dxpl_id,
00313     hbool_t *depth_decreased, void *swap_loc, unsigned depth, H5AC_info_t *parent_cache_info,
00314     hbool_t * parent_cache_info_dirtied_ptr, H5B2_node_ptr_t *curr_node_ptr, hsize_t idx,
00315     H5B2_remove_t op, void *op_data);
00316 H5_DLL herr_t H5B2_remove_leaf_by_idx(H5B2_hdr_t *hdr, hid_t dxpl_id,
00317     H5B2_node_ptr_t *curr_node_ptr, unsigned idx, H5B2_remove_t op,
00318     void *op_data);
00319 
00320 /* Routines for deleting nodes */
00321 H5_DLL herr_t H5B2_delete_node(H5B2_hdr_t *hdr, hid_t dxpl_id, unsigned depth,
00322     const H5B2_node_ptr_t *curr_node, H5B2_remove_t op, void *op_data);
00323 
00324 /* Metadata cache callbacks */
00325 H5_DLL herr_t H5B2_cache_hdr_dest(H5F_t *f, H5B2_hdr_t *b);
00326 H5_DLL herr_t H5B2_cache_leaf_dest(H5F_t *f, H5B2_leaf_t *l);
00327 H5_DLL herr_t H5B2_cache_internal_dest(H5F_t *f, H5B2_internal_t *i);
00328 
00329 /* Debugging routines for dumping file structures */
00330 H5_DLL herr_t H5B2_hdr_debug(H5F_t *f, hid_t dxpl_id, haddr_t addr,
00331     FILE *stream, int indent, int fwidth, const H5B2_class_t *type);
00332 H5_DLL herr_t H5B2_int_debug(H5F_t *f, hid_t dxpl_id, haddr_t addr,
00333     FILE *stream, int indent, int fwidth, const H5B2_class_t *type,
00334     haddr_t hdr_addr, unsigned nrec, unsigned depth);
00335 H5_DLL herr_t H5B2_leaf_debug(H5F_t *f, hid_t dxpl_id, haddr_t addr,
00336     FILE *stream, int indent, int fwidth, const H5B2_class_t *type,
00337     haddr_t hdr_addr, unsigned nrec);
00338 
00339 /* Testing routines */
00340 #ifdef H5B2_TESTING
00341 H5_DLL herr_t H5B2_get_root_addr_test(H5B2_t *bt2, haddr_t *root_addr);
00342 H5_DLL int H5B2_get_node_depth_test(H5B2_t *bt2, hid_t dxpl_id, void *udata);
00343 H5_DLL herr_t H5B2_get_node_info_test(H5B2_t *bt2, hid_t dxpl_id,
00344     void *udata, H5B2_node_info_test_t *ninfo);
00345 #endif /* H5B2_TESTING */
00346 
00347 #endif /* _H5B2pkg_H */
00348