From 82a12612e389fc618163a6a6d16a4908600a5a05 Mon Sep 17 00:00:00 2001 From: Quincey Koziol Date: Wed, 6 Jul 2005 13:13:32 -0500 Subject: [svn-r11031] Purpose: New feature Description: Initial checkin of B+ Tree code. Platforms tested: FreeBSD 4.11 (sleipnir) h5committest Misc. update: --- src/H5AC.c | 4 +- src/H5ACprivate.h | 4 +- src/H5B2cache.c | 6 +- src/H5BP.c | 469 ++++++++++++++++++++++++++++++++++ src/H5BPcache.c | 710 +++++++++++++++++++++++++++++++++++++++++++++++++++ src/H5BPdbg.c | 120 +++++++++ src/H5BPpkg.h | 212 +++++++++++++++ src/H5BPprivate.h | 86 +++++++ src/H5BPpublic.h | 53 ++++ src/H5BPtest.c | 237 +++++++++++++++++ src/H5Cpkg.h | 2 +- src/Makefile.am | 5 +- src/Makefile.in | 14 +- test/Makefile.am | 5 +- test/Makefile.in | 61 +++-- test/b+tree.c | 209 +++++++++++++++ test/h5test.h | 3 + tools/misc/h5debug.c | 27 +- 18 files changed, 2182 insertions(+), 45 deletions(-) create mode 100644 src/H5BP.c create mode 100644 src/H5BPcache.c create mode 100644 src/H5BPdbg.c create mode 100644 src/H5BPpkg.h create mode 100644 src/H5BPprivate.h create mode 100644 src/H5BPpublic.h create mode 100644 src/H5BPtest.c create mode 100644 test/b+tree.c diff --git a/src/H5AC.c b/src/H5AC.c index 116dd94..a7f5aa1 100644 --- a/src/H5AC.c +++ b/src/H5AC.c @@ -365,7 +365,9 @@ static const char * H5AC_entry_type_names[H5AC_NTYPES] = "v2 B-tree internal nodes", "v2 B-tree leaf nodes", "block tracker nodes", - "segmented heaps" + "segmented heaps", + "B+ tree headers", + "B+ tree leaves" }; herr_t diff --git a/src/H5ACprivate.h b/src/H5ACprivate.h index 314c96b..3d35028 100644 --- a/src/H5ACprivate.h +++ b/src/H5ACprivate.h @@ -49,7 +49,9 @@ #define H5AC_BT2_LEAF_ID 7 /*v2 B-tree leaf node */ #define H5AC_BLTR_ID 8 /*block tracker */ #define H5AC_SHEAP_ID 9 /*segmented heap */ -#define H5AC_NTYPES 10 +#define H5AC_BPT_HDR_ID 10 /*B+ tree header */ +#define H5AC_BPT_LEAF_ID 11 /*B+ tree leaf */ +#define H5AC_NTYPES 12 /* H5AC_DUMP_STATS_ON_CLOSE should always be FALSE when * H5C_COLLECT_CACHE_STATS is FALSE. diff --git a/src/H5B2cache.c b/src/H5B2cache.c index ddc402b..9f7d9db 100644 --- a/src/H5B2cache.c +++ b/src/H5B2cache.c @@ -284,7 +284,7 @@ done: /*------------------------------------------------------------------------- - * Function: H5B_cache_hdr_dest + * Function: H5B2_cache_hdr_dest * * Purpose: Destroys a B-tree header in memory. * @@ -556,7 +556,7 @@ done: /*------------------------------------------------------------------------- - * Function: H5B_cache_leaf_dest + * Function: H5B2_cache_leaf_dest * * Purpose: Destroys a B-tree leaf node in memory. * @@ -874,7 +874,7 @@ done: /*------------------------------------------------------------------------- - * Function: H5B_cache_internal_dest + * Function: H5B2_cache_internal_dest * * Purpose: Destroys a B-tree internal node in memory. * diff --git a/src/H5BP.c b/src/H5BP.c new file mode 100644 index 0000000..55d0095 --- /dev/null +++ b/src/H5BP.c @@ -0,0 +1,469 @@ +/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * + * 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. * + * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ + +/*------------------------------------------------------------------------- + * + * Created: H5BP.c + * Apr 14 2005 + * Quincey Koziol + * + * Purpose: Implements a B+ tree, with several modifications from + * the "standard" methods. + * + * Please see the documentation in: + * doc/html/TechNotes/Btrees.html for a full description + * of how they work, etc. + * + *------------------------------------------------------------------------- + */ + +#define H5BP_PACKAGE /*suppress error about including H5BPpkg */ + +/* Private headers */ +#include "H5private.h" /* Generic Functions */ +#include "H5BPpkg.h" /* B+ trees */ +#include "H5Eprivate.h" /* Error handling */ +#include "H5MFprivate.h" /* File memory management */ +#include "H5MMprivate.h" /* Memory management */ + +/* Local macros */ + +/* Uncomment this macro to enable extra sanity checking */ +/* #define H5BP_DEBUG */ + + +/* Local typedefs */ + +/* Local prototypes */ + +/* Helper functions */ + + +/* Package variables */ + +/* Declare a free list to manage the H5BP_t struct */ +H5FL_DEFINE(H5BP_t); + +/* Declare a free list to manage the H5BP_branch_t struct */ +H5FL_DEFINE(H5BP_branch_t); + +/* Declare a free list to manage the H5BP_twig_t struct */ +H5FL_DEFINE(H5BP_twig_t); + +/* Declare a free list to manage the H5BP_leaf_t struct */ +H5FL_DEFINE(H5BP_leaf_t); + + +/* Static variables */ + +/* Declare a free list to manage B-tree node pages to/from disk */ +H5FL_BLK_DEFINE_STATIC(node_page); + +/* Declare a free list to manage the H5BP_shared_t struct */ +H5FL_DEFINE_STATIC(H5BP_shared_t); + + + +/*------------------------------------------------------------------------- + * Function: H5BP_shared_init + * + * Purpose: Allocate & initialize shared B-tree info + * + * Return: Non-negative on success/Negative on failure + * + * Programmer: Quincey Koziol + * koziol@ncsa.uiuc.edu + * Apr 14 2005 + * + *------------------------------------------------------------------------- + */ +herr_t +H5BP_shared_init (H5BP_t *bpt, const H5BP_class_t *type, + size_t node_size, unsigned split_percent, unsigned merge_percent) +{ + H5BP_shared_t *shared = NULL; /* Shared B+ tree information */ + herr_t ret_value=SUCCEED; /* Return value */ + + FUNC_ENTER_NOAPI_NOINIT(H5BP_shared_init) + + /* Allocate space for the shared information */ + if(NULL==(shared = H5FL_CALLOC(H5BP_shared_t))) + HGOTO_ERROR (H5E_RESOURCE, H5E_NOSPACE, FAIL, "memory allocation failed for B+ tree shared information") + + /* Assign user's information */ + shared->split_percent = split_percent; + shared->merge_percent = merge_percent; + shared->node_size = node_size; + + /* Assign common type information */ + shared->type = type; + + /* Allocate "page" for node I/O */ + if((shared->page=H5FL_BLK_MALLOC(node_page,shared->node_size))==NULL) + HGOTO_ERROR (H5E_RESOURCE, H5E_NOSPACE, FAIL, "memory allocation failed") +#ifdef H5_USING_PURIFY +HDmemset(shared->page,0,shared->node_size); +#endif /* H5_USING_PURIFY */ + + /* Make shared B-tree info reference counted */ + if(NULL==(bpt->shared=H5RC_create(shared,H5BP_shared_free))) + HGOTO_ERROR (H5E_RESOURCE, H5E_NOSPACE, FAIL, "can't create ref-count wrapper for shared B+ tree info") + +done: + if(ret_value<0) + if(shared) + H5BP_shared_free(shared); + + FUNC_LEAVE_NOAPI(ret_value) +} /* end H5BP_shared_init() */ + + +/*------------------------------------------------------------------------- + * Function: H5BP_shared_free + * + * Purpose: Free shared B+ tree info + * + * Return: Non-negative on success/Negative on failure + * + * Programmer: Quincey Koziol + * koziol@ncsa.uiuc.edu + * Apr 14 2005 + * + *------------------------------------------------------------------------- + */ +herr_t +H5BP_shared_free (void *_shared) +{ + H5BP_shared_t *shared = (H5BP_shared_t *)_shared; + herr_t ret_value=SUCCEED; + + FUNC_ENTER_NOAPI_NOINIT_NOFUNC(H5BP_shared_free) + + /* Sanity check */ + HDassert(shared); + + /* Free the B-tree node buffer */ + if(shared->page) + H5FL_BLK_FREE(node_page,shared->page); + + /* Free the shared B-tree info itself */ + H5FL_FREE(H5BP_shared_t,shared); + + FUNC_LEAVE_NOAPI(ret_value) +} /* end H5BP_shared_free() */ + + +/*------------------------------------------------------------------------- + * Function: H5BP_create + * + * Purpose: Creates a new empty B+ tree in the file. + * + * Return: Non-negative on success (with address of new B-tree + * filled in), negative on failure + * + * Programmer: Quincey Koziol + * koziol@ncsa.uiuc.edu + * Apr 19 2005 + * + *------------------------------------------------------------------------- + */ +herr_t +H5BP_create(H5F_t *f, hid_t dxpl_id, const H5BP_class_t *type, + size_t node_size, unsigned split_percent, unsigned merge_percent, + haddr_t *addr_p) +{ + H5BP_t *bpt = NULL; /* The new B+ tree header information */ + herr_t ret_value=SUCCEED; + + FUNC_ENTER_NOAPI(H5BP_create, FAIL) + + /* + * Check arguments. + */ + HDassert(f); + HDassert(type); + HDassert(node_size>0); + HDassert(merge_percent>0 && merge_percent<=100); + HDassert(split_percent>0 && split_percent<=100); + HDassert(merge_percent<(split_percent/2)); + + /* + * Allocate file and memory data structures. + */ + if (NULL==(bpt = H5FL_MALLOC(H5BP_t))) + HGOTO_ERROR (H5E_RESOURCE, H5E_NOSPACE, FAIL, "memory allocation failed for B-tree header") + + /* Assign internal information */ + HDmemset(&bpt->cache_info,0,sizeof(H5AC_info_t)); + bpt->cache_info.is_dirty = TRUE; + bpt->depth = 0; + bpt->root.addr = HADDR_UNDEF; + bpt->root.all_nrec = 0; + bpt->root.util = 0; + + /* Initialize shared B-tree info */ + if(H5BP_shared_init(bpt, type, node_size, split_percent, merge_percent)<0) + HGOTO_ERROR (H5E_RESOURCE, H5E_NOSPACE, FAIL, "can't create shared B+ tree info") + + /* Allocate space for the header on disk */ + if (HADDR_UNDEF==(*addr_p=H5MF_alloc(f, H5FD_MEM_BTREE, dxpl_id, (hsize_t)H5BP_HEADER_SIZE(f)))) + HGOTO_ERROR(H5E_RESOURCE, H5E_NOSPACE, FAIL, "file allocation failed for B-tree header") + + /* Cache the new B-tree node */ + if (H5AC_set(f, dxpl_id, H5AC_BPT_HDR, *addr_p, bpt, H5AC__NO_FLAGS_SET) < 0) + HGOTO_ERROR(H5E_BTREE, H5E_CANTINIT, FAIL, "can't add B+ tree header to cache") + +done: + if (ret_value<0) { + if (bpt) + (void)H5BP_cache_hdr_dest(f,bpt); + } /* end if */ + + FUNC_LEAVE_NOAPI(ret_value) +} /* end H5BP_create() */ + + +/*------------------------------------------------------------------------- + * Function: H5BP_create_leaf + * + * Purpose: Creates empty leaf node of a B+ tree and updates node pointer + * to point to it. + * + * Return: Non-negative on success/Negative on failure + * + * Programmer: Quincey Koziol + * koziol@ncsa.uiuc.edu + * Apr 19 2005 + * + *------------------------------------------------------------------------- + */ +static herr_t +H5BP_create_leaf(H5F_t *f, hid_t dxpl_id, H5RC_t *bpt_shared, H5BP_node_ptr_t *node_ptr) +{ + H5BP_leaf_t *leaf=NULL; /* Pointer to new leaf node created */ + H5BP_shared_t *shared; /* Shared B+ tree information */ + herr_t ret_value = SUCCEED; + + FUNC_ENTER_NOAPI(H5BP_create_leaf, FAIL) + + /* Check arguments. */ + HDassert(f); + HDassert(bpt_shared); + HDassert(node_ptr); + + /* Allocate memory for leaf information */ + if (NULL==(leaf = H5FL_MALLOC(H5BP_leaf_t))) + HGOTO_ERROR (H5E_RESOURCE, H5E_NOSPACE, FAIL, "memory allocation failed for B+ tree leaf info") + + /* Set metadata cache info */ + HDmemset(&leaf->cache_info,0,sizeof(H5AC_info_t)); + leaf->cache_info.is_dirty = TRUE; + + /* Share common B+ tree information */ + leaf->shared = bpt_shared; + H5RC_INC(leaf->shared); + + /* Get the pointer to the shared B-tree info */ + shared=H5RC_GET_OBJ(leaf->shared); + HDassert(shared); + + /* Create record pool for leaf node */ + if((leaf->rec_pool = H5MP_create(H5BP_LEAF_POOL_PAGE, H5MP_FLG_DEFAULT)) == NULL) + HGOTO_ERROR(H5E_BTREE, H5E_NOSPACE, NULL, "can't allocate memory pool") + + /* Set number of records */ + leaf->nrec=0; + leaf->flags=0; + + /* Allocate space on disk for the leaf */ + if (HADDR_UNDEF==(node_ptr->addr=H5MF_alloc(f, H5FD_MEM_BTREE, dxpl_id, (hsize_t)shared->node_size))) + HGOTO_ERROR(H5E_RESOURCE, H5E_NOSPACE, FAIL, "file allocation failed for B+ tree leaf node") + + /* Cache the new B+ tree node */ + if (H5AC_set(f, dxpl_id, H5AC_BPT_LEAF, node_ptr->addr, leaf, H5AC__NO_FLAGS_SET) < 0) + HGOTO_ERROR(H5E_BTREE, H5E_CANTINIT, FAIL, "can't add B+ tree leaf to cache") + +done: + if (ret_value<0) { + if (leaf) + (void)H5BP_cache_leaf_dest(f,leaf); + } /* end if */ + + FUNC_LEAVE_NOAPI(ret_value) +} /* H5BP_create_leaf() */ + + +/*------------------------------------------------------------------------- + * Function: H5BP_insert_leaf + * + * Purpose: Adds a new record to a B+ tree leaf node. + * + * Return: Non-negative on success/Negative on failure + * + * Programmer: Quincey Koziol + * koziol@ncsa.uiuc.edu + * Apr 22 2005 + * + *------------------------------------------------------------------------- + */ +static herr_t +H5BP_insert_leaf(H5F_t *f, hid_t dxpl_id, H5RC_t *bpt_shared, + H5BP_node_ptr_t *curr_node_ptr, void *udata) +{ + H5BP_leaf_t *leaf; /* Pointer to leaf node */ + H5BP_shared_t *shared; /* Pointer to B+ tree's shared information */ + int cmp; /* Comparison value of records */ + unsigned idx; /* Location of record which matches key */ + herr_t ret_value = SUCCEED; + + FUNC_ENTER_NOAPI_NOINIT(H5BP_insert_leaf) + + /* Check arguments. */ + HDassert(f); + HDassert(bpt_shared); + HDassert(curr_node_ptr); + HDassert(H5F_addr_defined(curr_node_ptr->addr)); + +if( H5BP_NODE_OVERSIZE(curr_node_ptr->util)) { + HDfprintf(stderr,"%s: attempting to insert record into extent node\n",FUNC); + HGOTO_ERROR(H5E_BTREE, H5E_UNSUPPORTED, FAIL, "Can't handle extent node!") +} + /* Lock B+ tree node */ + if (NULL == (leaf = H5AC_protect(f, dxpl_id, H5AC_BPT_LEAF, curr_node_ptr->addr, &(curr_node_ptr->util), bpt_shared, H5AC_WRITE))) + HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to load B+ tree leaf node") + + /* Get the pointer to the shared B+ tree info */ + shared=H5RC_GET_OBJ(bpt_shared); + HDassert(shared); + +#ifndef LATER +HDfprintf(stderr,"%s: finish record insertion code\n",FUNC); +HGOTO_ERROR(H5E_BTREE, H5E_UNSUPPORTED, FAIL, "Can't handle record insertion!") +#else /* LATER */ + /* Check for inserting into empty leaf */ + if(leaf->nrec==0) + idx=0; + else { + /* Find correct location to insert this record */ + if((cmp = H5BP_locate_record(shared->type,leaf->nrec,shared->nat_off,leaf->leaf_native,udata,&idx)) == 0) + HGOTO_ERROR(H5E_BTREE, H5E_EXISTS, FAIL, "record is already in B+ tree") + if(cmp > 0) + idx++; + + /* Make room for new record */ + if(idxnrec) + HDmemmove(H5BP_LEAF_NREC(leaf,shared,idx+1),H5BP_LEAF_NREC(leaf,shared,idx),shared->type->nrec_size*(leaf->nrec-idx)); + } /* end else */ + + /* Make callback to store record in native form */ + if((shared->type->store)(H5BP_LEAF_NREC(leaf,shared,idx),udata)<0) + HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, FAIL, "unable to insert record into leaf node") +#endif /* LATER */ + + /* Update record count for node pointer to current node */ + curr_node_ptr->all_nrec++; + + /* Update record count for current node */ + leaf->nrec++; + +done: + /* Release the B+ tree leaf node */ + if (leaf && H5AC_unprotect(f, dxpl_id, H5AC_BPT_LEAF, curr_node_ptr->addr, leaf, H5AC__DIRTIED_FLAG) < 0) + HDONE_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release leaf B+ tree node") + + FUNC_LEAVE_NOAPI(ret_value) +} /* H5BP_insert_leaf() */ + + +/*------------------------------------------------------------------------- + * Function: H5BP_insert + * + * Purpose: Adds a new record to the B+ tree. + * + * Return: Non-negative on success/Negative on failure + * + * Programmer: Quincey Koziol + * koziol@ncsa.uiuc.edu + * Apr 19 2005 + * + *------------------------------------------------------------------------- + */ +herr_t +H5BP_insert(H5F_t *f, hid_t dxpl_id, const H5BP_class_t *type, haddr_t addr, + void *udata) +{ + H5BP_t *bpt=NULL; /* Pointer to the B+ tree header */ + H5BP_shared_t *shared; /* Pointer to B+ tree's shared information */ + herr_t ret_value = SUCCEED; + + FUNC_ENTER_NOAPI(H5BP_insert, FAIL) + + /* Check arguments. */ + HDassert(f); + HDassert(type); + HDassert(H5F_addr_defined(addr)); + + /* Look up the B+ tree header */ + if (NULL == (bpt = H5AC_protect(f, dxpl_id, H5AC_BPT_HDR, addr, type, NULL, H5AC_WRITE))) + HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to load B+ tree header") + + /* Get the pointer to the shared B+ tree info */ + shared=H5RC_GET_OBJ(bpt->shared); + HDassert(shared); + + /* Check if the root node is allocated yet */ + if(!H5F_addr_defined(bpt->root.addr)) { + /* Create root node as leaf node in B+ tree */ + if(H5BP_create_leaf(f, dxpl_id, bpt->shared, &(bpt->root))<0) + HGOTO_ERROR(H5E_BTREE, H5E_CANTINIT, FAIL, "unable to create root node") + + /* Mark B+ tree header as dirty, since we updated the address of the root node */ + bpt->cache_info.is_dirty = TRUE; + } /* end if */ + /* Check if we need to split the root node (equiv. to a 1->2 leaf node split) */ + else if(H5BP_NODE_OVERSIZE(bpt->root.util) || + (!H5BP_NODE_OVERSIZE(bpt->root.util) && bpt->root.util>=shared->split_percent)) { + /* Split root node */ +#ifdef LATER + if(H5BP_split_root(f, dxpl_id, bpt, bpt->shared)<0) + HGOTO_ERROR(H5E_BTREE, H5E_CANTSPLIT, FAIL, "unable to split root node") +#else /* LATER */ +HDfprintf(stderr,"%s: attempting to split root node\n",FUNC); +HGOTO_ERROR(H5E_BTREE, H5E_UNSUPPORTED, FAIL, "Can't split root yet!") +#endif /* LATER */ + } /* end if */ + + /* Attempt to insert record into B+ tree */ + if(bpt->depth>0) { +#ifdef LATER + if(H5BP_insert_internal(f,dxpl_id,bpt->shared,bpt->depth,&(bpt->cache_info),&bpt->root,udata)<0) + HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, FAIL, "unable to insert record into B+ tree internal node") +#else /* LATER */ +HDfprintf(stderr,"%s: attempting to insert record with internal node\n",FUNC); +HGOTO_ERROR(H5E_BTREE, H5E_UNSUPPORTED, FAIL, "Can't insert records yet!") +#endif /* LATER */ + } /* end if */ + else { + if(H5BP_insert_leaf(f,dxpl_id,bpt->shared,&bpt->root,udata)<0) + HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, FAIL, "unable to insert record into B+ tree leaf node") + } /* end else */ + +done: + /* Release the B+ tree header info */ + if (bpt && H5AC_unprotect(f, dxpl_id, H5AC_BPT_HDR, addr, bpt, H5AC__DIRTIED_FLAG) < 0) + HDONE_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release B+ tree header info") + + FUNC_LEAVE_NOAPI(ret_value) +} /* H5BP_insert() */ + diff --git a/src/H5BPcache.c b/src/H5BPcache.c new file mode 100644 index 0000000..e511ae2 --- /dev/null +++ b/src/H5BPcache.c @@ -0,0 +1,710 @@ +/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * + * 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. * + * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ + +/*------------------------------------------------------------------------- + * + * Created: H5BPcache.c + * Apr 19 2005 + * Quincey Koziol + * + * Purpose: Implement B+ tree metadata cache methods. + * + *------------------------------------------------------------------------- + */ + +#define H5BP_PACKAGE /*suppress error about including H5BPpkg */ + +/* Private headers */ +#include "H5private.h" /* Generic Functions */ +#include "H5BPpkg.h" /* B+ trees */ +#include "H5Eprivate.h" /* Error handling */ + +/* Local macros */ + +/* B+ tree format version #'s */ +#define H5BP_HDR_VERSION 0 /* Header */ +#define H5BP_LEAF_VERSION 0 /* Leaf nodes */ + + +/* Local typedefs */ + +/* Local prototypes */ + +/* Metadata cache callbacks */ +static H5BP_t *H5BP_cache_hdr_load(H5F_t *f, hid_t dxpl_id, haddr_t addr, const void *_type, void *udata); +static herr_t H5BP_cache_hdr_flush(H5F_t *f, hid_t dxpl_id, hbool_t destroy, haddr_t addr, H5BP_t *b); +static herr_t H5BP_cache_hdr_clear(H5F_t *f, H5BP_t *b, hbool_t destroy); +static herr_t H5BP_cache_hdr_size(const H5F_t *f, const H5BP_t *bt, size_t *size_ptr); +static H5BP_leaf_t *H5BP_cache_leaf_load(H5F_t *f, hid_t dxpl_id, haddr_t addr, const void *_nrec, void *_bpt_shared); +static herr_t H5BP_cache_leaf_flush(H5F_t *f, hid_t dxpl_id, hbool_t destroy, haddr_t addr, H5BP_leaf_t *l); +static herr_t H5BP_cache_leaf_clear(H5F_t *f, H5BP_leaf_t *l, hbool_t destroy); +static herr_t H5BP_cache_leaf_size(const H5F_t *f, const H5BP_leaf_t *l, size_t *size_ptr); + +/* Package variables */ + +/* H5BP headers inherit cache-like properties from H5AC */ +const H5AC_class_t H5AC_BPT_HDR[1] = {{ + H5AC_BPT_HDR_ID, + (H5AC_load_func_t)H5BP_cache_hdr_load, + (H5AC_flush_func_t)H5BP_cache_hdr_flush, + (H5AC_dest_func_t)H5BP_cache_hdr_dest, + (H5AC_clear_func_t)H5BP_cache_hdr_clear, + (H5AC_size_func_t)H5BP_cache_hdr_size, +}}; + +/* H5BP leaves inherit cache-like properties from H5AC */ +const H5AC_class_t H5AC_BPT_LEAF[1] = {{ + H5AC_BPT_LEAF_ID, + (H5AC_load_func_t)H5BP_cache_leaf_load, + (H5AC_flush_func_t)H5BP_cache_leaf_flush, + (H5AC_dest_func_t)H5BP_cache_leaf_dest, + (H5AC_clear_func_t)H5BP_cache_leaf_clear, + (H5AC_size_func_t)H5BP_cache_leaf_size, +}}; + +/* Static variables */ + +/* Declare a free list to manage B+ tree header data to/from disk */ +H5FL_BLK_DEFINE_STATIC(header_block); + +/* Declare a free list to manage 'void *' array data */ +typedef void *voidp; +H5FL_SEQ_DEFINE_STATIC(voidp); + + + +/*------------------------------------------------------------------------- + * Function: H5BP_cache_hdr_load + * + * Purpose: Loads a B+ tree header from the disk. + * + * Return: Success: Pointer to a new B+ tree. + * + * Failure: NULL + * + * Programmer: Quincey Koziol + * koziol@ncsa.uiuc.edu + * Apr 19 2005 + * + *------------------------------------------------------------------------- + */ +static H5BP_t * +H5BP_cache_hdr_load(H5F_t *f, hid_t dxpl_id, haddr_t addr, const void *_type, void UNUSED *udata) +{ + const H5BP_class_t *type = (const H5BP_class_t *) _type; + size_t node_size; /* Size info for B+ tree */ + unsigned split_percent, merge_percent; /* Split & merge info for B+ tree */ + H5BP_t *bpt = NULL; + size_t size; + uint8_t *buf = NULL; + uint8_t *p; /* Pointer into raw data buffer */ + H5BP_t *ret_value; + + FUNC_ENTER_NOAPI(H5BP_cache_hdr_load, NULL) + + /* Check arguments */ + HDassert(f); + HDassert(H5F_addr_defined(addr)); + HDassert(type); + + if (NULL==(bpt = H5FL_MALLOC(H5BP_t))) + HGOTO_ERROR (H5E_RESOURCE, H5E_NOSPACE, NULL, "memory allocation failed") + HDmemset(&bpt->cache_info,0,sizeof(H5AC_info_t)); + + /* Compute the size of the B+ tree header on disk */ + size = H5BP_HEADER_SIZE(f); + + /* Allocate temporary buffer */ + if ((buf=H5FL_BLK_MALLOC(header_block,size))==NULL) + HGOTO_ERROR (H5E_RESOURCE, H5E_NOSPACE, NULL, "memory allocation failed") + + /* Read header from disk */ + if (H5F_block_read(f, H5FD_MEM_BTREE, addr, size, dxpl_id, buf)<0) + HGOTO_ERROR(H5E_BTREE, H5E_READERROR, NULL, "can't read B+ tree header") + + p = buf; + + /* magic number */ + if (HDmemcmp(p, H5BP_HDR_MAGIC, H5BP_SIZEOF_MAGIC)) + HGOTO_ERROR(H5E_BTREE, H5E_CANTLOAD, NULL, "wrong B+ tree header signature") + p += H5BP_SIZEOF_MAGIC; + + /* version */ + if (*p++ != H5BP_HDR_VERSION) + HGOTO_ERROR(H5E_BTREE, H5E_CANTLOAD, NULL, "wrong B+ tree header version") + + /* B+ tree type */ + if (*p++ != (uint8_t)type->id) + HGOTO_ERROR(H5E_BTREE, H5E_CANTLOAD, NULL, "incorrect B+ tree type") + + /* node size (in bytes) */ + UINT32DECODE(p, node_size); + + /* depth of tree */ + UINT16DECODE(p, bpt->depth); + + /* split & merge %s */ + UINT16DECODE(p, split_percent); + UINT16DECODE(p, merge_percent); + + /* root node pointer */ + H5F_addr_decode(f, (const uint8_t **)&p, &(bpt->root.addr)); + H5F_DECODE_LENGTH(f, p, bpt->root.all_nrec); + bpt->root.util = *p++; + + /* Initialize shared B+ tree info */ + if(H5BP_shared_init(bpt, type, node_size, split_percent, merge_percent)<0) + HGOTO_ERROR (H5E_RESOURCE, H5E_NOSPACE, NULL, "can't create shared B+ tree info") + + /* Set return value */ + ret_value = bpt; + +done: + if(buf) + H5FL_BLK_FREE(header_block,buf); + if (!ret_value && bpt) + (void)H5BP_cache_hdr_dest(f,bpt); + FUNC_LEAVE_NOAPI(ret_value) +} /*lint !e818 Can't make udata a pointer to const */ + + +/*------------------------------------------------------------------------- + * Function: H5BP_cache_hdr_flush + * + * Purpose: Flushes a dirty B+ tree header to disk. + * + * Return: Non-negative on success/Negative on failure + * + * Programmer: Quincey Koziol + * koziol@ncsa.uiuc.edu + * Apr 19 2005 + * + *------------------------------------------------------------------------- + */ +static herr_t +H5BP_cache_hdr_flush(H5F_t *f, hid_t dxpl_id, hbool_t destroy, haddr_t addr, H5BP_t *bpt) +{ + herr_t ret_value = SUCCEED; /* Return value */ + + FUNC_ENTER_NOAPI(H5BP_cache_hdr_flush, FAIL) + + /* check arguments */ + HDassert(f); + HDassert(H5F_addr_defined(addr)); + HDassert(bpt); + + if (bpt->cache_info.is_dirty) { + H5BP_shared_t *shared; /* Shared B+ tree information */ + uint8_t *buf = NULL; + uint8_t *p; /* Pointer into raw data buffer */ + size_t size; + + /* Get the pointer to the shared B+ tree info */ + shared=H5RC_GET_OBJ(bpt->shared); + HDassert(shared); + + /* Compute the size of the B+ tree header on disk */ + size = H5BP_HEADER_SIZE(f); + + /* Allocate temporary buffer */ + if ((buf=H5FL_BLK_MALLOC(header_block,size))==NULL) + HGOTO_ERROR (H5E_RESOURCE, H5E_NOSPACE, FAIL, "memory allocation failed") + + p = buf; + + /* magic number */ + HDmemcpy(p, H5BP_HDR_MAGIC, H5BP_SIZEOF_MAGIC); + p += H5BP_SIZEOF_MAGIC; + + /* version # */ + *p++ = H5BP_HDR_VERSION; + + /* B+ tree type */ + *p++ = shared->type->id; + + /* node size (in bytes) */ + UINT32ENCODE(p, shared->node_size); + + /* depth of tree */ + UINT16ENCODE(p, bpt->depth); + + /* split & merge %s */ + UINT16ENCODE(p, shared->split_percent); + UINT16ENCODE(p, shared->merge_percent); + + /* root node pointer */ + H5F_addr_encode(f, &p, bpt->root.addr); + H5F_ENCODE_LENGTH(f, p, bpt->root.all_nrec); + *p++ = bpt->root.util; + + /* Write the B+ tree header. */ + if (H5F_block_write(f, H5FD_MEM_BTREE, addr, size, dxpl_id, buf) < 0) + HGOTO_ERROR(H5E_BTREE, H5E_CANTFLUSH, FAIL, "unable to save B+ tree header to disk") + + H5FL_BLK_FREE(header_block,buf); + + bpt->cache_info.is_dirty = FALSE; + } /* end if */ + + if (destroy) + if (H5BP_cache_hdr_dest(f, bpt) < 0) + HGOTO_ERROR(H5E_BTREE, H5E_CANTFREE, FAIL, "unable to destroy B+ tree header") + +done: + FUNC_LEAVE_NOAPI(ret_value) +} /* H5BP_cache_hdr_flush() */ + + +/*------------------------------------------------------------------------- + * Function: H5BP_cache_hdr_dest + * + * Purpose: Destroys a B+ tree header in memory. + * + * Return: Non-negative on success/Negative on failure + * + * Programmer: Quincey Koziol + * koziol@ncsa.uiuc.edu + * Apr 19 2005 + * + *------------------------------------------------------------------------- + */ +/* ARGSUSED */ +herr_t +H5BP_cache_hdr_dest(H5F_t UNUSED *f, H5BP_t *bpt) +{ + FUNC_ENTER_NOAPI_NOINIT_NOFUNC(H5BP_cache_hdr_dest) + + /* + * Check arguments. + */ + HDassert(bpt); + + /* Decrement reference count on shared B+ tree info */ + if(bpt->shared) + H5RC_DEC(bpt->shared); + + /* Free B+ tree header info */ + H5FL_FREE(H5BP_t,bpt); + + FUNC_LEAVE_NOAPI(SUCCEED) +} /* end H5BP_cache_hdr_dest() */ + + +/*------------------------------------------------------------------------- + * Function: H5BP_cache_hdr_clear + * + * Purpose: Mark a B+ tree header in memory as non-dirty. + * + * Return: Non-negative on success/Negative on failure + * + * Programmer: Quincey Koziol + * koziol@ncsa.uiuc.edu + * Apr 19 2005 + * + *------------------------------------------------------------------------- + */ +static herr_t +H5BP_cache_hdr_clear(H5F_t *f, H5BP_t *bpt, hbool_t destroy) +{ + herr_t ret_value = SUCCEED; + + FUNC_ENTER_NOAPI_NOINIT(H5BP_cache_hdr_clear) + + /* + * Check arguments. + */ + HDassert(bpt); + + /* Reset the dirty flag. */ + bpt->cache_info.is_dirty = FALSE; + + if (destroy) + if (H5BP_cache_hdr_dest(f, bpt) < 0) + HGOTO_ERROR(H5E_BTREE, H5E_CANTFREE, FAIL, "unable to destroy B+ tree header") + +done: + FUNC_LEAVE_NOAPI(ret_value) +} /* end H5BP_cache_hdr_clear() */ + + +/*------------------------------------------------------------------------- + * Function: H5BP_cache_hdr_size + * + * Purpose: Compute the size in bytes of a B+ tree header + * on disk, and return it in *size_ptr. On failure, + * the value of *size_ptr is undefined. + * + * Return: Non-negative on success/Negative on failure + * + * Programmer: Quincey Koziol + * koziol@ncsa.uiuc.edu + * Apr 19 2005 + * + *------------------------------------------------------------------------- + */ +static herr_t +H5BP_cache_hdr_size(const H5F_t *f, const H5BP_t UNUSED *bpt, size_t *size_ptr) +{ + FUNC_ENTER_NOAPI_NOINIT_NOFUNC(H5BP_cache_hdr_size) + + /* check arguments */ + HDassert(f); + HDassert(size_ptr); + + /* Set size value */ + *size_ptr = H5BP_HEADER_SIZE(f); + + FUNC_LEAVE_NOAPI(SUCCEED) +} /* H5BP_cache_hdr_size() */ + + +/*------------------------------------------------------------------------- + * Function: H5BP_cache_leaf_load + * + * Purpose: Loads a B+ tree leaf from the disk. + * + * Return: Success: Pointer to a new B+ tree leaf node. + * + * Failure: NULL + * + * Programmer: Quincey Koziol + * koziol@ncsa.uiuc.edu + * Apr 19 2005 + * + *------------------------------------------------------------------------- + */ +static H5BP_leaf_t * +H5BP_cache_leaf_load(H5F_t *f, hid_t dxpl_id, haddr_t addr, const void *_nrec, void *_bpt_shared) +{ + const unsigned char *nrec = (const unsigned char *)_nrec; + H5RC_t *bpt_shared=(H5RC_t *)_bpt_shared; /* Shared B+ tree information */ + H5BP_shared_t *shared; /* Shared B+ tree information */ + H5BP_leaf_t *leaf = NULL; /* Pointer to new leaf */ + uint8_t *p; /* Pointer into raw data buffer */ + size_t rec_size; /* Size of records */ + unsigned u; /* Local index variable */ + H5BP_leaf_t *ret_value; + + FUNC_ENTER_NOAPI(H5BP_cache_leaf_load, NULL) + + /* Check arguments */ + HDassert(f); + HDassert(H5F_addr_defined(addr)); + HDassert(bpt_shared); + + if (NULL==(leaf = H5FL_MALLOC(H5BP_leaf_t))) + HGOTO_ERROR (H5E_RESOURCE, H5E_NOSPACE, NULL, "memory allocation failed") + HDmemset(&leaf->cache_info,0,sizeof(H5AC_info_t)); + + /* Share common B+ tree information */ + leaf->shared = bpt_shared; + H5RC_INC(leaf->shared); + + /* Get the pointer to the shared B+ tree info */ + shared=H5RC_GET_OBJ(leaf->shared); + HDassert(shared); + + /* Check if we can use existing buffer for node */ + /* Read header from disk */ + if (H5F_block_read(f, H5FD_MEM_BTREE, addr, shared->node_size, dxpl_id, shared->page)<0) + HGOTO_ERROR(H5E_BTREE, H5E_READERROR, NULL, "can't read B+ tree leaf node") + + p = shared->page; + + /* magic number */ + if (HDmemcmp(p, H5BP_LEAF_MAGIC, H5BP_SIZEOF_MAGIC)) + HGOTO_ERROR(H5E_BTREE, H5E_CANTLOAD, NULL, "wrong B+ tree leaf node signature") + p += H5BP_SIZEOF_MAGIC; + + /* version */ + if (*p++ != H5BP_LEAF_VERSION) + HGOTO_ERROR(H5E_BTREE, H5E_CANTLOAD, NULL, "wrong B+ tree leaf node version") + + /* B+ tree type */ + if (*p++ != (uint8_t)shared->type->id) + HGOTO_ERROR(H5E_BTREE, H5E_CANTLOAD, NULL, "incorrect B+ tree type") + + /* Set the number of records in the leaf */ + leaf->nrec = *nrec; + + /* Get the status flags for the leaf */ + leaf->flags = *p++; + + /* Create record pool for leaf node */ + if((leaf->rec_pool = H5MP_create(H5BP_LEAF_POOL_PAGE, H5MP_FLG_DEFAULT)) == NULL) + HGOTO_ERROR(H5E_BTREE, H5E_NOSPACE, NULL, "can't allocate memory pool") + + /* Retrieve variable-length record information, if present */ + if(H5BP_LEAF_REC_VARLEN(leaf->flags)) { + /* Allocate space for the record pointers */ + if((leaf->rec_ptr = H5FL_SEQ_MALLOC(voidp, leaf->nrec)) == NULL) + HGOTO_ERROR(H5E_BTREE, H5E_NOSPACE, NULL, "can't allocate record pointers for node") + + /* Work through the records on disk and insert them into array for node */ + for(u = 0; u < leaf->nrec; u++) { + size_t rec_len; /* Index of current record */ + + /* Determine the length of the record */ + UINT16DECODE(p, rec_len); + + /* Decode the record */ + if((leaf->rec_ptr[u] = (shared->type->decode)(f, leaf->rec_pool, p, rec_len)) == NULL) + HGOTO_ERROR(H5E_BTREE, H5E_CANTDECODE, NULL, "can't decode B+ tree record") + p += rec_len; + } /* end for */ + } /* end if */ + else { + /* Retrieve the records' size */ + UINT16DECODE(p, rec_size); + +HDfprintf(stderr,"%s: attempting to decode fixed-size records from leaf node\n",FUNC); +HGOTO_ERROR(H5E_BTREE, H5E_UNSUPPORTED, NULL, "Can't decode records yet!") + } /* end else */ + + /* Set return value */ + ret_value = leaf; + +done: + if (!ret_value && leaf) + (void)H5BP_cache_leaf_dest(f,leaf); + FUNC_LEAVE_NOAPI(ret_value) +} /* H5BP_cache_leaf_load() */ /*lint !e818 Can't make udata a pointer to const */ + + +/*------------------------------------------------------------------------- + * Function: H5BP_cache_leaf_flush + * + * Purpose: Flushes a dirty B+ tree leaf node to disk. + * + * Return: Non-negative on success/Negative on failure + * + * Programmer: Quincey Koziol + * koziol@ncsa.uiuc.edu + * Apr 19 2005 + * + *------------------------------------------------------------------------- + */ +static herr_t +H5BP_cache_leaf_flush(H5F_t *f, hid_t dxpl_id, hbool_t destroy, haddr_t addr, H5BP_leaf_t *leaf) +{ + herr_t ret_value = SUCCEED; /* Return value */ + + FUNC_ENTER_NOAPI(H5BP_cache_leaf_flush, FAIL) + + /* check arguments */ + HDassert(f); + HDassert(H5F_addr_defined(addr)); + HDassert(leaf); + + if (leaf->cache_info.is_dirty) { + H5BP_shared_t *shared; /* Shared B+ tree information */ + uint8_t *p; /* Pointer into raw data buffer */ +#ifdef LATER + uint8_t *native; /* Pointer to native keys */ + unsigned u; /* Local index variable */ +#endif /* LATER */ + + /* Get the pointer to the shared B+ tree info */ + shared=H5RC_GET_OBJ(leaf->shared); + HDassert(shared); + + p = shared->page; + + /* magic number */ + HDmemcpy(p, H5BP_LEAF_MAGIC, H5BP_SIZEOF_MAGIC); + p += H5BP_SIZEOF_MAGIC; + + /* version # */ + *p++ = H5BP_LEAF_VERSION; + + /* B+ tree type */ + *p++ = shared->type->id; + + /* status flags */ + *p++ = leaf->flags; + + /* Serialize records */ + if(H5BP_LEAF_REC_VARLEN(leaf->flags)) { + unsigned u; /* Local index */ + + /* Work through the records in memory and encode them to disk */ + for(u = 0; u < leaf->nrec; u++) { + size_t rec_len; /* Index of current record */ + uint8_t *tp; /* Temporary pointer into raw data buffer */ + + /* Save the location for the record length */ + tp = p; + + /* Skip over the location for the record length */ + p += 2; + + /* Encode the record */ + if((shared->type->encode)(f, leaf->rec_ptr[u], p, &rec_len) < 0) + HGOTO_ERROR(H5E_BTREE, H5E_CANTENCODE, NULL, "can't encode B+ tree record") + assert(rec_len > 0); + p += rec_len; + + /* Encode the record length */ + UINT16ENCODE(tp, rec_len); + } /* end for */ + } /* end if */ + else { +HDfprintf(stderr,"%s: attempting to decode fixed-size records from leaf node\n",FUNC); +HGOTO_ERROR(H5E_BTREE, H5E_UNSUPPORTED, NULL, "Can't decode records yet!") + } /* end else */ + +#ifdef LATER + /* Serialize records for leaf node */ + native=leaf->leaf_native; + for(u=0; unrec; u++) { + /* Encode record */ + if((shared->type->encode)(f,p,native)<0) + HGOTO_ERROR(H5E_BTREE, H5E_CANTENCODE, FAIL, "unable to encode B+ tree record") + + /* Move to next record */ + p += shared->rrec_size; + native += shared->type->nrec_size; + } /* end for */ +#endif /* LATER */ + + /* Write the B+ tree leaf node */ + if (H5F_block_write(f, H5FD_MEM_BTREE, addr, shared->node_size, dxpl_id, shared->page) < 0) + HGOTO_ERROR(H5E_BTREE, H5E_CANTFLUSH, FAIL, "unable to save B+ tree leaf node to disk") + + leaf->cache_info.is_dirty = FALSE; + } /* end if */ + + if (destroy) + if (H5BP_cache_leaf_dest(f,leaf) < 0) + HGOTO_ERROR(H5E_BTREE, H5E_CANTFREE, FAIL, "unable to destroy B+ tree leaf node") + +done: + FUNC_LEAVE_NOAPI(ret_value) +} /* H5BP_cache_leaf_flush() */ + + +/*------------------------------------------------------------------------- + * Function: H5BP_cache_leaf_dest + * + * Purpose: Destroys a B+ tree leaf node in memory. + * + * Return: Non-negative on success/Negative on failure + * + * Programmer: Quincey Koziol + * koziol@ncsa.uiuc.edu + * Apr 19 2005 + * + *------------------------------------------------------------------------- + */ +/* ARGSUSED */ +herr_t +H5BP_cache_leaf_dest(H5F_t UNUSED *f, H5BP_leaf_t *leaf) +{ + FUNC_ENTER_NOAPI_NOINIT_NOFUNC(H5BP_cache_leaf_dest) + + /* + * Check arguments. + */ + HDassert(leaf); + + /* Decrement reference count on shared B+ tree info */ + if(leaf->shared) + H5RC_DEC(leaf->shared); + + /* Release B+ tree leaf node record pointer array */ + H5FL_SEQ_FREE(voidp, leaf->rec_ptr); + + /* Release B+ tree leaf node record memory pool */ + H5MP_close(leaf->rec_pool); + + /* Free B+ tree leaf node info */ + H5FL_FREE(H5BP_leaf_t, leaf); + + FUNC_LEAVE_NOAPI(SUCCEED) +} /* end H5BP_cache_leaf_dest() */ + + +/*------------------------------------------------------------------------- + * Function: H5BP_cache_leaf_clear + * + * Purpose: Mark a B+ tree leaf node in memory as non-dirty. + * + * Return: Non-negative on success/Negative on failure + * + * Programmer: Quincey Koziol + * koziol@ncsa.uiuc.edu + * Apr 19 2005 + * + *------------------------------------------------------------------------- + */ +static herr_t +H5BP_cache_leaf_clear(H5F_t *f, H5BP_leaf_t *leaf, hbool_t destroy) +{ + herr_t ret_value = SUCCEED; + + FUNC_ENTER_NOAPI_NOINIT(H5BP_cache_leaf_clear) + + /* + * Check arguments. + */ + HDassert(leaf); + + /* Reset the dirty flag. */ + leaf->cache_info.is_dirty = FALSE; + + if (destroy) + if (H5BP_cache_leaf_dest(f, leaf) < 0) + HGOTO_ERROR(H5E_BTREE, H5E_CANTFREE, FAIL, "unable to destroy B+ tree leaf node") + +done: + FUNC_LEAVE_NOAPI(ret_value) +} /* end H5BP_cache_leaf_clear() */ + + +/*------------------------------------------------------------------------- + * Function: H5BP_cache_leaf_size + * + * Purpose: Compute the size in bytes of a B+ tree leaf node + * on disk, and return it in *size_ptr. On failure, + * the value of *size_ptr is undefined. + * + * Return: Non-negative on success/Negative on failure + * + * Programmer: Quincey Koziol + * koziol@ncsa.uiuc.edu + * Apr 19 2005 + * + *------------------------------------------------------------------------- + */ +static herr_t +H5BP_cache_leaf_size(const H5F_t UNUSED *f, const H5BP_leaf_t *leaf, size_t *size_ptr) +{ + H5BP_shared_t *shared; /* Shared B+ tree information */ + + FUNC_ENTER_NOAPI_NOINIT_NOFUNC(H5BP_cache_leaf_size) + + /* check arguments */ + HDassert(leaf); + HDassert(size_ptr); + + /* Get the pointer to the shared B+ tree info */ + shared=H5RC_GET_OBJ(leaf->shared); + HDassert(shared); + + /* Set size value */ + *size_ptr = shared->node_size; + + FUNC_LEAVE_NOAPI(SUCCEED) +} /* H5BP_cache_leaf_size() */ + diff --git a/src/H5BPdbg.c b/src/H5BPdbg.c new file mode 100644 index 0000000..07dd492 --- /dev/null +++ b/src/H5BPdbg.c @@ -0,0 +1,120 @@ +/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * + * 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. * + * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ + +/*------------------------------------------------------------------------- + * + * Created: H5BPdbg.c + * Apr 19 2005 + * Quincey Koziol + * + * Purpose: Dump debugging information about a B+ tree. + * + *------------------------------------------------------------------------- + */ + +#define H5BP_PACKAGE /*suppress error about including H5BPpkg */ + +/* Private headers */ +#include "H5private.h" /* Generic Functions */ +#include "H5BPpkg.h" /* B+ trees */ +#include "H5Eprivate.h" /* Error handling */ +#include "H5FLprivate.h" /* Free Lists */ + + +/*------------------------------------------------------------------------- + * Function: H5BP_hdr_debug + * + * Purpose: Prints debugging info about a B+ tree header. + * + * Return: Non-negative on success/Negative on failure + * + * Programmer: Quincey Koziol + * koziol@ncsa.uiuc.edu + * Apr 19 2005 + * + *------------------------------------------------------------------------- + */ +herr_t +H5BP_hdr_debug(H5F_t *f, hid_t dxpl_id, haddr_t addr, FILE *stream, int indent, int fwidth, + const H5BP_class_t *type) +{ + H5BP_t *bpt = NULL; + H5BP_shared_t *shared; /* Shared B+ tree information */ + herr_t ret_value=SUCCEED; /* Return value */ + + FUNC_ENTER_NOAPI(H5BP_hdr_debug, FAIL) + + /* + * Check arguments. + */ + assert(f); + assert(H5F_addr_defined(addr)); + assert(stream); + assert(indent >= 0); + assert(fwidth >= 0); + + /* + * Load the B+ tree header. + */ + if (NULL == (bpt = H5AC_protect(f, dxpl_id, H5AC_BPT_HDR, addr, type, NULL, H5AC_READ))) + HGOTO_ERROR(H5E_BTREE, H5E_CANTLOAD, FAIL, "unable to load B+ tree header") + + /* Get the pointer to the shared B+ tree info */ + shared=H5RC_GET_OBJ(bpt->shared); + assert(shared); + + /* + * Print the values. + */ + HDfprintf(stream, "%*s%-*s %s\n", indent, "", fwidth, + "Tree type ID:", + (shared->type->id == H5BP_TEST_ID ? "H5BP_TEST_ID" : + "Unknown!")); + HDfprintf(stream, "%*s%-*s %Zu\n", indent, "", fwidth, + "Size of node:", + shared->node_size); + HDfprintf(stream, "%*s%-*s %s\n", indent, "", fwidth, + "Dirty flag:", + bpt->cache_info.is_dirty ? "True" : "False"); + HDfprintf(stream, "%*s%-*s %u\n", indent, "", fwidth, + "Depth:", + bpt->depth); + HDfprintf(stream, "%*s%-*s %Hu\n", indent, "", fwidth, + "Number of records in tree:", + bpt->root.all_nrec); + if(H5BP_NODE_OVERSIZE(bpt->root.util)) + HDfprintf(stream, "%*s%-*s %u\n", indent, "", fwidth, + "Root node size multiplier:", + (unsigned)(bpt->root.util & 0x7f)); + else + HDfprintf(stream, "%*s%-*s %u\n", indent, "", fwidth, + "Root node size utilization:", + (unsigned)bpt->root.util); + HDfprintf(stream, "%*s%-*s %a\n", indent, "", fwidth, + "Address of root node:", + bpt->root.addr); + HDfprintf(stream, "%*s%-*s %u\n", indent, "", fwidth, + "Split percent:", + shared->split_percent); + HDfprintf(stream, "%*s%-*s %u\n", indent, "", fwidth, + "Merge percent:", + shared->merge_percent); + +done: + if (bpt && H5AC_unprotect(f, dxpl_id, H5AC_BPT_HDR, addr, bpt, H5AC__NO_FLAGS_SET) < 0) + HDONE_ERROR(H5E_BTREE, H5E_PROTECT, FAIL, "unable to release B+ tree header") + + FUNC_LEAVE_NOAPI(ret_value) +} /* end H5BP_hdr_debug() */ + diff --git a/src/H5BPpkg.h b/src/H5BPpkg.h new file mode 100644 index 0000000..3ec5667 --- /dev/null +++ b/src/H5BPpkg.h @@ -0,0 +1,212 @@ +/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * + * 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. * + * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ + +/* + * Programmer: Quincey Koziol + * Thursday, April 14, 2005 + * + * Purpose: This file contains declarations which are visible only within + * the H5BP package. Source files outside the H5BP package should + * include H5BPprivate.h instead. + */ +#ifndef H5BP_PACKAGE +#error "Do not include this file outside the H5BP package!" +#endif + +#ifndef _H5BPpkg_H +#define _H5BPpkg_H + +/* Get package's private header */ +#include "H5BPprivate.h" + +/* Other private headers needed by this file */ +#include "H5ACprivate.h" /* Metadata cache */ +#include "H5FLprivate.h" /* Free Lists */ +#include "H5RCprivate.h" /* Reference counted object functions */ + +/**************************/ +/* Package Private Macros */ +/**************************/ + +/* Size of signature information (on disk) */ +#define H5BP_SIZEOF_MAGIC 4 + +/* B+ tree signatures */ +#define H5BP_HDR_MAGIC "BPHD" /* Header */ +#define H5BP_INT_MAGIC "BPBR" /* Branch node */ +#define H5BP_TWIG_MAGIC "BPTW" /* Twig node */ +#define H5BP_LEAF_MAGIC "BPLF" /* Leaf node */ +#define H5BP_EXTENT_MAGIC "BPEX" /* Extent node */ + +/* Size of storage for number of separators per node (on disk) */ +#define H5BP_SIZEOF_SEPS_PER_NODE 2 + +/* Size of storage for "node size multiplier" (on disk) */ +#define H5BP_SIZEOF_NODE_MULT 1 + +/* Size of a "full" node pointer (on disk) */ +#define H5BP_NODE_POINTER_SIZE(f) (H5F_SIZEOF_ADDR(f)+H5F_SIZEOF_SIZE(f)+H5BP_SIZEOF_NODE_MULT) + +/* Size of the B+ tree header on disk */ +#define H5BP_HEADER_SIZE(f) ( \ + 4 + /* Signature */ \ + 1 + /* Version */ \ + 1 + /* Tree type */ \ + 4 + /* Node size, in bytes */ \ + 2 + /* Depth of tree */ \ + 2 + /* Split % of full (as integer, ie. "98" means 98%) */ \ + 2 + /* Merge % of full (as integer, ie. "98" means 98%) */ \ + H5BP_NODE_POINTER_SIZE(f)) /* Node pointer to root node in tree */ + +/* Determine whether a node is oversized */ +/* The high bit is set in utilization field for oversized nodes */ +#define H5BP_NODE_OVERSIZE(u) ((u) & 0x80) + +/* Determine whether a leaf node has variable-length records */ +/* The low bit is set in "flag" field for nodes w/variable-length records */ +#define H5BP_LEAF_REC_VARLEN(u) ((u) & 0x01) + +/* Size of memory pool pages for leaf nodes */ +#define H5BP_LEAF_POOL_PAGE H5MP_PAGE_SIZE_DEFAULT + + +/****************************/ +/* Package Private Typedefs */ +/****************************/ + +/* A "node pointer" to another B+ tree node */ +typedef struct { + haddr_t addr; /* Address of other node */ + hsize_t all_nrec; /* Number of records in node pointed to and all it's children */ + unsigned char util; /* Percent utilization/page node multiple */ +} H5BP_node_ptr_t; + +/* Each B+ tree has certain information that can be shared across all + * the instances of nodes in that B-tree. + */ +typedef struct H5BP_shared_t { + /* Shared internal data structures */ + const H5BP_class_t *type; /* Type of tree */ + uint8_t *page; /* Disk page */ + + /* Information set by user */ + unsigned split_percent; /* Percent full at which to split the node, when inserting */ + unsigned merge_percent; /* Percent full at which to merge the node, when deleting */ + size_t node_size; /* Size of all nodes, in bytes */ +} H5BP_shared_t; + +/* The B+ tree information */ +typedef struct H5BP_t { + /* Information for H5AC cache functions, _must_ be first field in structure */ + H5AC_info_t cache_info; + + /* Internal B+ tree information */ + unsigned depth; /* B+ tree's overall depth */ + H5BP_node_ptr_t root; /* Node pointer to root node in B+ tree */ + H5RC_t *shared; /* Ref-counted shared info */ +} H5BP_t; + +/* B+ tree internal branch node information */ +typedef struct H5BP_branch_t { + /* Information for H5AC cache functions, _must_ be first field in structure */ + H5AC_info_t cache_info; + + /* Internal B+ tree information */ + H5RC_t *shared; /* Ref-counted shared info */ + uint8_t *int_native; /* Pointer to native records */ + H5BP_node_ptr_t *node_ptrs; /* Pointer to node pointers */ + unsigned nrec; /* Number of records in node */ +} H5BP_branch_t; + +/* B+ tree internal twig node information */ +typedef struct H5BP_twig_t { + /* Information for H5AC cache functions, _must_ be first field in structure */ + H5AC_info_t cache_info; + + /* Internal B+ tree information */ + H5RC_t *shared; /* Ref-counted shared info */ + uint8_t *int_native; /* Pointer to native records */ + H5BP_node_ptr_t *node_ptrs; /* Pointer to node pointers */ + unsigned nrec; /* Number of records in node */ +} H5BP_twig_t; + +/* B+ tree leaf node information */ +typedef struct H5BP_leaf_t { + /* Information for H5AC cache functions, _must_ be first field in structure */ + H5AC_info_t cache_info; + + /* Internal B+ tree information */ + H5RC_t *shared; /* Ref-counted shared info */ + H5MP_pool_t *rec_pool; /* Pool containing records for node */ + void **rec_ptr; /* Array of pointers to records in pool */ + unsigned nrec; /* Number of records in node */ + unsigned char flags; /* Status flags for leaf node */ +} H5BP_leaf_t; + +#ifdef H5BP_TESTING +/* Record for testing B+ trees */ +typedef struct { + hsize_t count; + char *name; +} H5BP_test_rec_t; +#endif /* H5BP_TESTING */ + + +/*****************************/ +/* Package Private Variables */ +/*****************************/ + +/* H5BP header inherits cache-like properties from H5AC */ +H5_DLLVAR const H5AC_class_t H5AC_BPT_HDR[1]; + +/* H5BP branch node inherits cache-like properties from H5AC */ +H5_DLLVAR const H5AC_class_t H5AC_BPT_BRANCH[1]; + +/* H5BP twig node inherits cache-like properties from H5AC */ +H5_DLLVAR const H5AC_class_t H5AC_BPT_TWIG[1]; + +/* H5BP leaf node inherits cache-like properties from H5AC */ +H5_DLLVAR const H5AC_class_t H5AC_BPT_LEAF[1]; + +/* Declare a free list to manage the H5BP_t struct */ +H5FL_EXTERN(H5BP_t); + +/* Declare a free list to manage the H5BP_branch_t struct */ +H5FL_EXTERN(H5BP_branch_t); + +/* Declare a free list to manage the H5BP_twig_t struct */ +H5FL_EXTERN(H5BP_twig_t); + +/* Declare a free list to manage the H5BP_leaf_t struct */ +H5FL_EXTERN(H5BP_leaf_t); + +/* Internal B+ tree testing class */ +#ifdef H5BP_TESTING +H5_DLLVAR const H5BP_class_t H5BP_TEST[1]; +#endif /* H5BP_TESTING */ + + +/******************************/ +/* Package Private Prototypes */ +/******************************/ +H5_DLL herr_t H5BP_shared_free (void *_shared); +H5_DLL herr_t H5BP_shared_init (H5BP_t *bpt, const H5BP_class_t *type, + size_t node_size, unsigned split_percent, unsigned merge_percent); +H5_DLL herr_t H5BP_cache_hdr_dest(H5F_t *f, H5BP_t *bpt); +H5_DLL herr_t H5BP_cache_leaf_dest(H5F_t UNUSED *f, H5BP_leaf_t *leaf); +H5_DLL herr_t H5BP_hdr_debug(H5F_t *f, hid_t dxpl_id, haddr_t addr, + FILE *stream, int indent, int fwidth, const H5BP_class_t *type); + +#endif /* _H5BPpkg_H */ + diff --git a/src/H5BPprivate.h b/src/H5BPprivate.h new file mode 100644 index 0000000..88048ef --- /dev/null +++ b/src/H5BPprivate.h @@ -0,0 +1,86 @@ +/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * + * 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. * + * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ + +/*------------------------------------------------------------------------- + * + * Created: H5BPprivate.h + * Apr 14 2005 + * Quincey Koziol + * + * Purpose: Private header for library accessible B+ tree routines. + * + *------------------------------------------------------------------------- + */ + +#ifndef _H5BPprivate_H +#define _H5BPprivate_H + +/* Include package's public header */ +#include "H5BPpublic.h" + +/* Private headers needed by this file */ +#include "H5Fprivate.h" /* File access */ +#include "H5MPprivate.h" /* Memory Pools */ + +/**************************/ +/* Library Private Macros */ +/**************************/ + + +/****************************/ +/* Library Private Typedefs */ +/****************************/ + +/* B+ tree IDs for various internal things. */ +typedef enum H5BP_subid_t { + H5BP_TEST_ID = 0, /* B+ tree is for testing (do not use for actual data) */ + H5BP_NUM_BTREE_ID /* Number of B-tree IDs (must be last) */ +} H5BP_subid_t; + +/* + * Each class of object that can be pointed to by a B+ tree has a + * variable of this type that contains class variables and methods. + */ +typedef struct H5BP_class_t { + H5BP_subid_t id; /*id as found in file*/ + + /* Copy native application record */ + void * (*copy)(const void *record); /* Copy native record */ + + /* Compare key */ + herr_t (*compare)(const void *key1, const void *key2); /* Compare two native keys */ + + /* Encode & decode record values */ + /* (i.e. native application form <-> disk form) */ + herr_t (*raw_len)(const H5F_t *f, const void *record, size_t *len); /* Determine length of raw (disk) form from native form */ + herr_t (*encode)(const H5F_t *f, const uint8_t *native, uint8_t *raw, size_t *rec_len); /* Encode record from native form to disk storage form */ + void * (*decode)(const H5F_t *f, H5MP_pool_t *pool, const uint8_t *raw, size_t rec_len); /* Decode record from disk storage form to native form */ + + /* Debug record values */ + herr_t (*debug) (FILE *stream, const H5F_t *f, hid_t dxpl_id, /* Print a record for debugging */ + int indent, int fwidth, const void *record, const void *udata); + +} H5BP_class_t; + +/***************************************/ +/* Library-private Function Prototypes */ +/***************************************/ +H5_DLL herr_t H5BP_create(H5F_t *f, hid_t dxpl_id, const H5BP_class_t *type, + size_t node_size, unsigned split_percent, unsigned merge_percent, + haddr_t *addr_p); +H5_DLL herr_t H5BP_insert(H5F_t *f, hid_t dxpl_id, const H5BP_class_t *type, + haddr_t addr, void *udata); + +#endif /* _H5BPprivate_H */ + diff --git a/src/H5BPpublic.h b/src/H5BPpublic.h new file mode 100644 index 0000000..8f3dd25 --- /dev/null +++ b/src/H5BPpublic.h @@ -0,0 +1,53 @@ +/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * + * 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. * + * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ + +/*------------------------------------------------------------------------- + * + * Created: H5BPpublic.h + * Apr 19 2005 + * Quincey Koziol + * + * Purpose: Public declarations for the H5BP package. + * + *------------------------------------------------------------------------- + */ +#ifndef _H5BPpublic_H +#define _H5BPpublic_H + +/* Public headers needed by this file */ +#include "H5public.h" + +/*****************/ +/* Public Macros */ +/*****************/ + +/*******************/ +/* Public Typedefs */ +/*******************/ + +/**********************************/ +/* Public API Function Prototypes */ +/**********************************/ + +#ifdef __cplusplus +extern "C" { +#endif + +#ifdef __cplusplus +} +#endif + +#endif /* _H5BPpublic_H */ + + diff --git a/src/H5BPtest.c b/src/H5BPtest.c new file mode 100644 index 0000000..025bdf7 --- /dev/null +++ b/src/H5BPtest.c @@ -0,0 +1,237 @@ +/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * + * 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. * + * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ + +/* Programmer: Quincey Koziol + * Thursday, April 19, 2005 + * + * Purpose: B+ tree testing functions. + */ + +#define H5BP_PACKAGE /*suppress error about including H5BPpkg */ +#define H5BP_TESTING /*suppress warning about H5BP testing funcs*/ + +/* Private headers */ +#include "H5private.h" /* Generic Functions */ +#include "H5BPpkg.h" /* B+ trees */ +#include "H5Eprivate.h" /* Error handling */ +#include "H5MMprivate.h" /* Memory management */ + +/* Static Prototypes */ +static void *H5BP_test_copy(const void *rec); +static herr_t H5BP_test_compare(const void *rec1, const void *rec2); +static herr_t H5BP_test_raw_len(const H5F_t *f, const void *record, size_t *len); +static herr_t H5BP_test_encode(const H5F_t *f, const uint8_t *native, + uint8_t *raw, size_t *rec_len); +static void *H5BP_test_decode(const H5F_t *f, H5MP_pool_t *pool, + const uint8_t *raw, size_t rec_len); +static herr_t H5BP_test_debug(FILE *stream, const H5F_t *f, hid_t dxpl_id, + int indent, int fwidth, const void *record, const void *_udata); + +/* Package variables */ +const H5BP_class_t H5BP_TEST[1]={{ /* B+ tree class information */ + H5BP_TEST_ID, /* Type of B+ tree */ + H5BP_test_copy, /* Record copy callback */ + H5BP_test_compare, /* Record comparison callback */ + H5BP_test_raw_len, /* Record 'raw len' callback */ + H5BP_test_encode, /* Record encoding callback */ + H5BP_test_decode, /* Record decoding callback */ + H5BP_test_debug /* Record debugging callback */ +}}; + + +/*------------------------------------------------------------------------- + * Function: H5BP_test_copy + * + * Purpose: Copy native information record + * + * Return: Pointer to new record on success, NULL on failure + * + * Programmer: Quincey Koziol + * Monday, April 25, 2005 + * + * Modifications: + * + *------------------------------------------------------------------------- + */ +static void * +H5BP_test_copy(const void *rec) +{ + FUNC_ENTER_NOAPI_NOINIT_NOFUNC(H5BP_test_copy) + + /* Copy record */ + FUNC_LEAVE_NOAPI(HDstrdup(rec)); +} /* H5BP_test_copy() */ + + +/*------------------------------------------------------------------------- + * Function: H5BP_test_compare + * + * Purpose: Compare two native information records, according to some key + * + * Return: <0 if rec1 < rec2 + * =0 if rec1 == rec2 + * >0 if rec1 > rec2 + * + * Programmer: Quincey Koziol + * Tuesday, April 19, 2005 + * + * Modifications: + * + *------------------------------------------------------------------------- + */ +static herr_t +H5BP_test_compare(const void *rec1, const void *rec2) +{ + FUNC_ENTER_NOAPI_NOINIT_NOFUNC(H5BP_test_compare) + + FUNC_LEAVE_NOAPI(HDstrcmp(*(const char **)rec1, *(const char **)rec2)); +} /* H5BP_test_compare() */ + + +/*------------------------------------------------------------------------- + * Function: H5BP_test_raw_len + * + * Purpose: Determine the length of the raw form of a record + * + * Return: <0 if rec1 < rec2 + * =0 if rec1 == rec2 + * >0 if rec1 > rec2 + * + * Programmer: Quincey Koziol + * Tuesday, April 19, 2005 + * + * Modifications: + * + *------------------------------------------------------------------------- + */ +static herr_t +H5BP_test_raw_len(const H5F_t UNUSED *f, const void *record, size_t *len) +{ + FUNC_ENTER_NOAPI_NOINIT_NOFUNC(H5BP_test_raw_len) + + *len = HDstrlen((const char *)record); + + FUNC_LEAVE_NOAPI(SUCCEED); +} /* H5BP_test_raw_len() */ + + +/*------------------------------------------------------------------------- + * Function: H5BP_test_encode + * + * Purpose: Encode native information into raw form for storing on disk + * + * Return: Success: non-negative + * + * Failure: negative + * + * Programmer: Quincey Koziol + * Tuesday, April 19, 2005 + * + * Modifications: + * + *------------------------------------------------------------------------- + */ +static herr_t +H5BP_test_encode(const H5F_t *f, const uint8_t *native, uint8_t *raw, size_t *rec_len) +{ + FUNC_ENTER_NOAPI_NOINIT_NOFUNC(H5BP_test_encode) + + /* Sanity check */ + HDassert(f); + HDassert(native); + HDassert(raw); + HDassert(rec_len); + + /* Get the record length */ + *rec_len = HDstrlen((const char *)native); + + /* "Encode" the record */ + HDmemcpy(raw, native, *rec_len); + + FUNC_LEAVE_NOAPI(SUCCEED); +} /* H5BP_test_encode() */ + + +/*------------------------------------------------------------------------- + * Function: H5BP_test_decode + * + * Purpose: Decode raw disk form of record into native form + * + * Return: Success: non-negative + * + * Failure: negative + * + * Programmer: Quincey Koziol + * Tuesday, April 19, 2005 + * + * Modifications: + * + *------------------------------------------------------------------------- + */ +static void * +H5BP_test_decode(const H5F_t *f, H5MP_pool_t *pool, const uint8_t *raw, size_t rec_len) +{ + void *ret_value; /* Return value */ + + FUNC_ENTER_NOAPI_NOINIT(H5BP_test_decode) + + /* Sanity check */ + HDassert(f); + HDassert(pool); + HDassert(raw); + HDassert(rec_len > 0); + + /* Allocate space for the record */ + if((ret_value = H5MP_malloc(pool, rec_len + 1)) == NULL) + HGOTO_ERROR(H5E_BTREE, H5E_NOSPACE, NULL, "Can't allocate space for record") + + /* "Decode" the record */ + HDmemcpy(ret_value, raw, rec_len); + *((unsigned char *)ret_value + rec_len) = '\0'; + +done: + FUNC_LEAVE_NOAPI(ret_value) +} /* H5BP_test_decode() */ + + +/*------------------------------------------------------------------------- + * Function: H5BP_test_debug + * + * Purpose: Debug native form of record + * + * Return: Success: non-negative + * + * Failure: negative + * + * Programmer: Quincey Koziol + * Tuesday, April 19, 2005 + * + * Modifications: + * + *------------------------------------------------------------------------- + */ +static herr_t +H5BP_test_debug(FILE *stream, const H5F_t UNUSED *f, hid_t UNUSED dxpl_id, int indent, int fwidth, + const void *record, const void UNUSED *_udata) +{ + FUNC_ENTER_NOAPI_NOINIT_NOFUNC(H5BP_test_debug) + + HDassert (record); + + HDfprintf(stream, "%*s%-*s %s\n", indent, "", fwidth, "Record:", + *(const char *)record); + + FUNC_LEAVE_NOAPI(SUCCEED); +} /* H5BP_test_debug() */ + diff --git a/src/H5Cpkg.h b/src/H5Cpkg.h index 7d708f8..2ab2e9b 100644 --- a/src/H5Cpkg.h +++ b/src/H5Cpkg.h @@ -574,7 +574,7 @@ ****************************************************************************/ #define H5C__H5C_T_MAGIC 0x005CAC0E -#define H5C__MAX_NUM_TYPE_IDS 10 +#define H5C__MAX_NUM_TYPE_IDS 12 struct H5C_t { diff --git a/src/Makefile.am b/src/Makefile.am index 0349292..4ab403a 100755 --- a/src/Makefile.am +++ b/src/Makefile.am @@ -42,7 +42,8 @@ DISTCLEAN=libhdf5.settings # library sources libhdf5_la_SOURCES= H5.c H5A.c H5AC.c H5B.c H5B2.c H5B2cache.c H5B2dbg.c \ - H5B2test.c H5BT.c H5BTbtree2.c H5BTcache.c H5BTdbg.c H5BTtest.c H5C.c \ + H5B2test.c H5BP.c H5BPcache.c H5BPdbg.c H5BPtest.c \ + H5BT.c H5BTbtree2.c H5BTcache.c H5BTdbg.c H5BTtest.c H5C.c \ H5D.c \ H5Dcontig.c \ H5Dcompact.c \ @@ -72,7 +73,7 @@ libhdf5_la_SOURCES= H5.c H5A.c H5AC.c H5B.c H5B2.c H5B2cache.c H5B2dbg.c \ # Public headers include_HEADERS =H5public.h H5Apublic.h H5ACpublic.h H5Bpublic.h H5B2public.h \ - H5BTpublic.h H5Cpublic.h H5Dpublic.h \ + H5BPpublic.h H5BTpublic.h H5Cpublic.h H5Dpublic.h \ H5Epubgen.h H5Epublic.h H5Fpublic.h H5FDpublic.h H5FDcore.h H5FDfamily.h \ H5FDfphdf5.h H5FDlog.h H5FDmpi.h H5FDmpio.h H5FDmpiposix.h \ H5FDmulti.h H5FDsec2.h H5FDstdio.h H5FDstream.h H5FPpublic.h \ diff --git a/src/Makefile.in b/src/Makefile.in index f22db4c..dbb59a7 100644 --- a/src/Makefile.in +++ b/src/Makefile.in @@ -83,8 +83,9 @@ libLTLIBRARIES_INSTALL = $(INSTALL) LTLIBRARIES = $(lib_LTLIBRARIES) libhdf5_la_LIBADD = am_libhdf5_la_OBJECTS = H5.lo H5A.lo H5AC.lo H5B.lo H5B2.lo \ - H5B2cache.lo H5B2dbg.lo H5B2test.lo H5BT.lo H5BTbtree2.lo \ - H5BTcache.lo H5BTdbg.lo H5BTtest.lo H5C.lo H5D.lo H5Dcontig.lo \ + H5B2cache.lo H5B2dbg.lo H5B2test.lo H5BP.lo H5BPcache.lo \ + H5BPdbg.lo H5BPtest.lo H5BT.lo H5BTbtree2.lo H5BTcache.lo \ + H5BTdbg.lo H5BTtest.lo H5C.lo H5D.lo H5Dcontig.lo \ H5Dcompact.lo H5Defl.lo H5Dio.lo H5Distore.lo H5Dmpio.lo \ H5Dselect.lo H5Dtest.lo H5E.lo H5F.lo H5Fdbg.lo H5Fmount.lo \ H5Fsuper.lo H5FD.lo H5FDcore.lo H5FDfamily.lo H5FDfphdf5.lo \ @@ -362,7 +363,8 @@ DISTCLEAN = libhdf5.settings # library sources libhdf5_la_SOURCES = H5.c H5A.c H5AC.c H5B.c H5B2.c H5B2cache.c H5B2dbg.c \ - H5B2test.c H5BT.c H5BTbtree2.c H5BTcache.c H5BTdbg.c H5BTtest.c H5C.c \ + H5B2test.c H5BP.c H5BPcache.c H5BPdbg.c H5BPtest.c \ + H5BT.c H5BTbtree2.c H5BTcache.c H5BTdbg.c H5BTtest.c H5C.c \ H5D.c \ H5Dcontig.c \ H5Dcompact.c \ @@ -392,7 +394,7 @@ libhdf5_la_SOURCES = H5.c H5A.c H5AC.c H5B.c H5B2.c H5B2cache.c H5B2dbg.c \ # Public headers include_HEADERS = H5public.h H5Apublic.h H5ACpublic.h H5Bpublic.h H5B2public.h \ - H5BTpublic.h H5Cpublic.h H5Dpublic.h \ + H5BPpublic.h H5BTpublic.h H5Cpublic.h H5Dpublic.h \ H5Epubgen.h H5Epublic.h H5Fpublic.h H5FDpublic.h H5FDcore.h H5FDfamily.h \ H5FDfphdf5.h H5FDlog.h H5FDmpi.h H5FDmpio.h H5FDmpiposix.h \ H5FDmulti.h H5FDsec2.h H5FDstdio.h H5FDstream.h H5FPpublic.h \ @@ -529,6 +531,10 @@ distclean-compile: @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/H5B2cache.Plo@am__quote@ @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/H5B2dbg.Plo@am__quote@ @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/H5B2test.Plo@am__quote@ +@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/H5BP.Plo@am__quote@ +@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/H5BPcache.Plo@am__quote@ +@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/H5BPdbg.Plo@am__quote@ +@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/H5BPtest.Plo@am__quote@ @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/H5BT.Plo@am__quote@ @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/H5BTbtree2.Plo@am__quote@ @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/H5BTcache.Plo@am__quote@ diff --git a/test/Makefile.am b/test/Makefile.am index c200e3c..55e6537 100644 --- a/test/Makefile.am +++ b/test/Makefile.am @@ -29,8 +29,7 @@ check_SCRIPTS = $(TEST_SCRIPT) # These are our main targets. They should be listed in the order to be # executed, generally most specific tests to least specific tests. -# JAMES debug: removed btree2 and cache tests since they take so long. -TEST_PROG=testhdf5 lheap ohdr stab gheap cache btree2 blocktrack sheap \ +TEST_PROG=testhdf5 lheap ohdr stab gheap cache b+tree btree2 blocktrack sheap \ pool hyperslab istore bittests dt_arith \ dtypes dsets cmpd_dset extend external links unlink big mtime \ fillval mount flush1 flush2 enum \ @@ -91,7 +90,7 @@ MOSTLYCLEANFILES+=cmpd_dset.h5 compact_dataset.h5 dataset.h5 extend.h5 istore.h5 family_file000[0-3][0-9].h5 multi_file-[rs].h5 core_file \ new_move_[ab].h5 ntypes.h5 dangle.h5 error_test.h5 err_compat.h5 \ dtransform.h5 test_filters.h5 get_file_name.h5 tstint[1-2].h5 \ - unlink_chunked.h5 btree2.h5 blocktrack.h5 sheap.h5 + unlink_chunked.h5 btree2.h5 blocktrack.h5 sheap.h5 b+tree.h5 # Sources for testhdf5 executable testhdf5_SOURCES=testhdf5.c tarray.c tattr.c tconfig.c tfile.c tgenprop.c \ diff --git a/test/Makefile.in b/test/Makefile.in index 94c8887..3e42d63 100644 --- a/test/Makefile.in +++ b/test/Makefile.in @@ -29,7 +29,7 @@ # # HDF5 Library Test Makefile(.in) # -SOURCES = $(libh5test_la_SOURCES) big.c bittests.c blocktrack.c btree2.c cache.c cmpd_dset.c dangle.c dsets.c dt_arith.c dtransform.c dtypes.c enum.c err_compat.c error_test.c extend.c external.c filename.c fillval.c flush1.c flush2.c getname.c gheap.c hyperslab.c istore.c lheap.c links.c mount.c mtime.c ntypes.c ohdr.c pool.c reserved.c set_extent.c sheap.c stab.c stream_test.c $(testhdf5_SOURCES) testmeta.c $(ttsafe_SOURCES) unlink.c vfd.c +SOURCES = $(libh5test_la_SOURCES) b+tree.c big.c bittests.c blocktrack.c btree2.c cache.c cmpd_dset.c dangle.c dsets.c dt_arith.c dtransform.c dtypes.c enum.c err_compat.c error_test.c extend.c external.c filename.c fillval.c flush1.c flush2.c getname.c gheap.c hyperslab.c istore.c lheap.c links.c mount.c mtime.c ntypes.c ohdr.c pool.c reserved.c set_extent.c sheap.c stab.c stream_test.c $(testhdf5_SOURCES) testmeta.c $(ttsafe_SOURCES) unlink.c vfd.c srcdir = @srcdir@ top_srcdir = @top_srcdir@ @@ -71,17 +71,21 @@ libh5test_la_DEPENDENCIES = $(am__DEPENDENCIES_1) am_libh5test_la_OBJECTS = h5test.lo testframe.lo libh5test_la_OBJECTS = $(am_libh5test_la_OBJECTS) am__EXEEXT_1 = testhdf5$(EXEEXT) lheap$(EXEEXT) ohdr$(EXEEXT) \ - stab$(EXEEXT) gheap$(EXEEXT) cache$(EXEEXT) btree2$(EXEEXT) \ - blocktrack$(EXEEXT) sheap$(EXEEXT) pool$(EXEEXT) \ - hyperslab$(EXEEXT) istore$(EXEEXT) bittests$(EXEEXT) \ - dt_arith$(EXEEXT) dtypes$(EXEEXT) dsets$(EXEEXT) \ - cmpd_dset$(EXEEXT) extend$(EXEEXT) external$(EXEEXT) \ - links$(EXEEXT) unlink$(EXEEXT) big$(EXEEXT) mtime$(EXEEXT) \ - fillval$(EXEEXT) mount$(EXEEXT) flush1$(EXEEXT) \ + stab$(EXEEXT) gheap$(EXEEXT) cache$(EXEEXT) b+tree$(EXEEXT) \ + btree2$(EXEEXT) blocktrack$(EXEEXT) sheap$(EXEEXT) \ + pool$(EXEEXT) hyperslab$(EXEEXT) istore$(EXEEXT) \ + bittests$(EXEEXT) dt_arith$(EXEEXT) dtypes$(EXEEXT) \ + dsets$(EXEEXT) cmpd_dset$(EXEEXT) extend$(EXEEXT) \ + external$(EXEEXT) links$(EXEEXT) unlink$(EXEEXT) big$(EXEEXT) \ + mtime$(EXEEXT) fillval$(EXEEXT) mount$(EXEEXT) flush1$(EXEEXT) \ flush2$(EXEEXT) enum$(EXEEXT) set_extent$(EXEEXT) \ ttsafe$(EXEEXT) stream_test$(EXEEXT) getname$(EXEEXT) \ vfd$(EXEEXT) ntypes$(EXEEXT) dangle$(EXEEXT) \ dtransform$(EXEEXT) filename$(EXEEXT) reserved$(EXEEXT) +b_tree_SOURCES = b+tree.c +b_tree_OBJECTS = b+tree.$(OBJEXT) +b_tree_LDADD = $(LDADD) +b_tree_DEPENDENCIES = libh5test.la $(am__DEPENDENCIES_1) big_SOURCES = big.c big_OBJECTS = big.$(OBJEXT) big_LDADD = $(LDADD) @@ -266,22 +270,22 @@ LTCOMPILE = $(LIBTOOL) --tag=CC --mode=compile $(CC) $(DEFS) \ CCLD = $(CC) LINK = $(LIBTOOL) --tag=CC --mode=link $(CCLD) $(AM_CFLAGS) $(CFLAGS) \ $(AM_LDFLAGS) $(LDFLAGS) -o $@ -SOURCES = $(libh5test_la_SOURCES) big.c bittests.c blocktrack.c \ - btree2.c cache.c cmpd_dset.c dangle.c dsets.c dt_arith.c \ - dtransform.c dtypes.c enum.c err_compat.c error_test.c \ - extend.c external.c filename.c fillval.c flush1.c flush2.c \ - getname.c gheap.c hyperslab.c istore.c lheap.c links.c mount.c \ - mtime.c ntypes.c ohdr.c pool.c reserved.c set_extent.c sheap.c \ - stab.c stream_test.c $(testhdf5_SOURCES) testmeta.c \ - $(ttsafe_SOURCES) unlink.c vfd.c -DIST_SOURCES = $(libh5test_la_SOURCES) big.c bittests.c blocktrack.c \ - btree2.c cache.c cmpd_dset.c dangle.c dsets.c dt_arith.c \ - dtransform.c dtypes.c enum.c err_compat.c error_test.c \ - extend.c external.c filename.c fillval.c flush1.c flush2.c \ - getname.c gheap.c hyperslab.c istore.c lheap.c links.c mount.c \ - mtime.c ntypes.c ohdr.c pool.c reserved.c set_extent.c sheap.c \ - stab.c stream_test.c $(testhdf5_SOURCES) testmeta.c \ - $(ttsafe_SOURCES) unlink.c vfd.c +SOURCES = $(libh5test_la_SOURCES) b+tree.c big.c bittests.c \ + blocktrack.c btree2.c cache.c cmpd_dset.c dangle.c dsets.c \ + dt_arith.c dtransform.c dtypes.c enum.c err_compat.c \ + error_test.c extend.c external.c filename.c fillval.c flush1.c \ + flush2.c getname.c gheap.c hyperslab.c istore.c lheap.c \ + links.c mount.c mtime.c ntypes.c ohdr.c pool.c reserved.c \ + set_extent.c sheap.c stab.c stream_test.c $(testhdf5_SOURCES) \ + testmeta.c $(ttsafe_SOURCES) unlink.c vfd.c +DIST_SOURCES = $(libh5test_la_SOURCES) b+tree.c big.c bittests.c \ + blocktrack.c btree2.c cache.c cmpd_dset.c dangle.c dsets.c \ + dt_arith.c dtransform.c dtypes.c enum.c err_compat.c \ + error_test.c extend.c external.c filename.c fillval.c flush1.c \ + flush2.c getname.c gheap.c hyperslab.c istore.c lheap.c \ + links.c mount.c mtime.c ntypes.c ohdr.c pool.c reserved.c \ + set_extent.c sheap.c stab.c stream_test.c $(testhdf5_SOURCES) \ + testmeta.c $(ttsafe_SOURCES) unlink.c vfd.c ETAGS = etags CTAGS = ctags DISTFILES = $(DIST_COMMON) $(DIST_SOURCES) $(TEXINFOS) $(EXTRA_DIST) @@ -514,7 +518,7 @@ MOSTLYCLEANFILES = *.chkexe *.chksh cmpd_dset.h5 compact_dataset.h5 \ new_move_[ab].h5 ntypes.h5 dangle.h5 error_test.h5 \ err_compat.h5 dtransform.h5 test_filters.h5 get_file_name.h5 \ tstint[1-2].h5 unlink_chunked.h5 btree2.h5 blocktrack.h5 \ - sheap.h5 + sheap.h5 b+tree.h5 INCLUDES = -I$(top_srcdir)/src -I$(top_builddir)/src # Test script for error_test and err_compat @@ -523,8 +527,7 @@ check_SCRIPTS = $(TEST_SCRIPT) # These are our main targets. They should be listed in the order to be # executed, generally most specific tests to least specific tests. -# JAMES debug: removed btree2 and cache tests since they take so long. -TEST_PROG = testhdf5 lheap ohdr stab gheap cache btree2 blocktrack sheap \ +TEST_PROG = testhdf5 lheap ohdr stab gheap cache b+tree btree2 blocktrack sheap \ pool hyperslab istore bittests dt_arith \ dtypes dsets cmpd_dset extend external links unlink big mtime \ fillval mount flush1 flush2 enum \ @@ -623,6 +626,9 @@ clean-checkPROGRAMS: echo " rm -f $$p $$f"; \ rm -f $$p $$f ; \ done +b+tree$(EXEEXT): $(b_tree_OBJECTS) $(b_tree_DEPENDENCIES) + @rm -f b+tree$(EXEEXT) + $(LINK) $(b_tree_LDFLAGS) $(b_tree_OBJECTS) $(b_tree_LDADD) $(LIBS) big$(EXEEXT): $(big_OBJECTS) $(big_DEPENDENCIES) @rm -f big$(EXEEXT) $(LINK) $(big_LDFLAGS) $(big_OBJECTS) $(big_LDADD) $(LIBS) @@ -753,6 +759,7 @@ mostlyclean-compile: distclean-compile: -rm -f *.tab.c +@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/b+tree.Po@am__quote@ @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/big.Po@am__quote@ @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/bittests.Po@am__quote@ @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/blocktrack.Po@am__quote@ diff --git a/test/b+tree.c b/test/b+tree.c new file mode 100644 index 0000000..39b174b --- /dev/null +++ b/test/b+tree.c @@ -0,0 +1,209 @@ +/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * + * 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. * + * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ + +/* Programmer: Quincey Koziol + * Tuesday, April 19, 2005 + */ +#include "h5test.h" + +/* + * This file needs to access private datatypes from the H5BP package. + * This file also needs to access the B+ tree testing code. + */ +#define H5BP_PACKAGE +#define H5BP_TESTING +#include "H5BPpkg.h" + +/* Other private headers that this test requires */ +#include "H5Iprivate.h" + +const char *FILENAME[] = { + "b+tree", + NULL +}; + +#define NODE_SIZE 512 + + +/*------------------------------------------------------------------------- + * Function: test_create + * + * Purpose: Basic tests for the B+ tree code + * + * Return: Success: 0 + * + * Failure: 1 + * + * Programmer: Quincey Koziol + * Tuesday, April 19, 2005 + * + * Modifications: + * + *------------------------------------------------------------------------- + */ +static int +test_create(hid_t fapl) +{ + hid_t file=-1; + char filename[1024]; + H5F_t *f=NULL; + haddr_t bpt_addr; /* Address of B+ tree created */ + + h5_fixname(FILENAME[0], fapl, filename, sizeof filename); + + /* Create the file to work on */ + if ((file=H5Fcreate(filename, H5F_ACC_TRUNC, H5P_DEFAULT, fapl))<0) + STACK_ERROR + + /* Get a pointer to the internal file object */ + if (NULL==(f=H5I_object(file))) + STACK_ERROR + + /* + * Test B+ tree creation + */ + TESTING("B+ tree creation"); + if (H5BP_create(f, H5P_DATASET_XFER_DEFAULT, H5BP_TEST, NODE_SIZE, 100, 40, &bpt_addr/*out*/)<0) + FAIL_STACK_ERROR + + PASSED(); + + if (H5Fclose(file)<0) + STACK_ERROR + + return 0; + +error: + H5E_BEGIN_TRY { + H5Fclose(file); + } H5E_END_TRY; + return 1; +} /* test_create() */ + + +/*------------------------------------------------------------------------- + * Function: test_insert_basic + * + * Purpose: Basic tests for the B+ tree code + * + * Return: Success: 0 + * + * Failure: 1 + * + * Programmer: Quincey Koziol + * Tuesday, April 19, 2005 + * + * Modifications: + * + *------------------------------------------------------------------------- + */ +static int +test_insert_basic(hid_t fapl) +{ + hid_t file=-1; + char filename[1024]; + H5F_t *f=NULL; + char *record; /* Record to insert into tree */ + haddr_t bpt_addr; /* Address of B+ tree created */ + herr_t ret; /* Generic error return value */ + + h5_fixname(FILENAME[0], fapl, filename, sizeof filename); + + /* Create the file to work on */ + if ((file=H5Fcreate(filename, H5F_ACC_TRUNC, H5P_DEFAULT, fapl))<0) + STACK_ERROR + + /* Get a pointer to the internal file object */ + if (NULL==(f=H5I_object(file))) + STACK_ERROR + + /* Create B+ tree */ + if (H5BP_create(f, H5P_DATASET_XFER_DEFAULT, H5BP_TEST, NODE_SIZE, 100, 40, &bpt_addr/*out*/)<0) + FAIL_STACK_ERROR + + /* + * Test B+ tree creation + */ + TESTING("B+ tree single record insert"); + record="Foo!"; + if (H5BP_insert(f, H5P_DATASET_XFER_DEFAULT, H5BP_TEST, bpt_addr, &record)<0) + FAIL_STACK_ERROR + + PASSED(); + + if (H5Fclose(file)<0) + STACK_ERROR + + return 0; + +error: + H5E_BEGIN_TRY { + H5Fclose(file); + } H5E_END_TRY; + return 1; +} /* test_insert_basic() */ + + +/*------------------------------------------------------------------------- + * Function: main + * + * Purpose: Test the B+ tree code + * + * Return: Success: + * + * Failure: + * + * Programmer: Quincey Koziol + * Tuesday, April 19, 2005 + * + * Modifications: + * + *------------------------------------------------------------------------- + */ +int +main(void) +{ + hid_t fapl=-1; + int nerrors=0; + + /* Reset library */ + h5_reset(); + fapl = h5_fileaccess(); + + /* Test B+ tree creation */ + nerrors += test_create(fapl); + + /* Test B+ tree record insertion */ + /* Iteration, find & index routines tested in these routines as well */ +#ifdef QAK + nerrors += test_insert_basic(fapl); +#endif /* QAK */ + + if (nerrors) goto error; + puts("All B+ tree tests passed."); +#ifndef QAK + h5_cleanup(FILENAME, fapl); +#else /* QAK */ +HDfprintf(stderr,"Uncomment cleanup!\n"); +#endif /* QAK */ + return 0; + +error: + puts("*** TESTS FAILED ***"); + H5E_BEGIN_TRY { + H5Pclose(fapl); + } H5E_END_TRY; + return 1; +} + diff --git a/test/h5test.h b/test/h5test.h index f261876..2d08ab7 100644 --- a/test/h5test.h +++ b/test/h5test.h @@ -103,6 +103,9 @@ extern MPI_Info h5_io_info_g; /* MPI INFO object for IO */ #define H5_WARNING() {puts("*WARNING*");fflush(stdout);} #define SKIPPED() {puts(" -SKIP-");fflush(stdout);} #define TEST_ERROR {H5_FAILED(); AT(); goto error;} +#define STACK_ERROR {H5Eprint_stack(H5E_DEFAULT, stdout); goto error;} +#define FAIL_STACK_ERROR {H5_FAILED(); AT(); \ + H5Eprint_stack(H5E_DEFAULT, stdout); goto error;} #ifdef __cplusplus extern "C" { diff --git a/tools/misc/h5debug.c b/tools/misc/h5debug.c index cc2aa3a..75004fc 100644 --- a/tools/misc/h5debug.c +++ b/tools/misc/h5debug.c @@ -28,12 +28,15 @@ #define H5O_PACKAGE /*suppress error about including H5Opkg */ #define H5B2_PACKAGE /*suppress error about including H5B2pkg */ #define H5B2_TESTING /*suppress warning about H5B2 testing funcs*/ +#define H5BP_PACKAGE /*suppress error about including H5BPpkg */ +#define H5BP_TESTING /*suppress warning about H5BP testing funcs*/ #define H5BT_PACKAGE /*suppress error about including H5BTpkg */ #define H5SH_PACKAGE /*suppress error about including H5SHpkg */ #include "H5private.h" /* Generic Functions */ #include "H5Bprivate.h" #include "H5B2pkg.h" /* B-trees */ +#include "H5BPpkg.h" /* B+ trees */ #include "H5BTpkg.h" /* Block tracker */ #include "H5Dprivate.h" #include "H5Fpkg.h" @@ -189,7 +192,7 @@ main(int argc, char *argv[]) * subclass. The subclass identifier is two bytes after the * B-tree signature. */ - H5B2_subid_t subtype = (H5B_subid_t)sig[H5B2_SIZEOF_MAGIC+1]; + H5B2_subid_t subtype = (H5B2_subid_t)sig[H5B2_SIZEOF_MAGIC+1]; switch (subtype) { case H5B2_TEST_ID: @@ -211,7 +214,7 @@ main(int argc, char *argv[]) * subclass. The subclass identifier is two bytes after the * B-tree signature. */ - H5B2_subid_t subtype = (H5B_subid_t)sig[H5B2_SIZEOF_MAGIC+1]; + H5B2_subid_t subtype = (H5B2_subid_t)sig[H5B2_SIZEOF_MAGIC+1]; switch (subtype) { case H5B2_TEST_ID: @@ -233,7 +236,7 @@ main(int argc, char *argv[]) * subclass. The subclass identifier is two bytes after the * B-tree signature. */ - H5B2_subid_t subtype = (H5B_subid_t)sig[H5B2_SIZEOF_MAGIC+1]; + H5B2_subid_t subtype = (H5B2_subid_t)sig[H5B2_SIZEOF_MAGIC+1]; switch (subtype) { case H5B2_TEST_ID: @@ -261,6 +264,24 @@ main(int argc, char *argv[]) */ status = H5SH_debug(f, H5P_DATASET_XFER_DEFAULT, addr, stdout, 0, VCOL); + } else if (!HDmemcmp(sig, H5BP_HDR_MAGIC, H5BP_SIZEOF_MAGIC)) { + /* + * Debug a B+ tree. B+ trees are debugged through the B+ tree + * subclass. The subclass identifier is two bytes after the + * B+ tree signature. + */ + H5BP_subid_t subtype = (H5BP_subid_t)sig[H5BP_SIZEOF_MAGIC+1]; + + switch (subtype) { + case H5BP_TEST_ID: + status = H5BP_hdr_debug(f, H5P_DATASET_XFER_DEFAULT, addr, stdout, 0, VCOL, H5BP_TEST); + break; + + default: + fprintf(stderr, "Unknown B+ tree subtype %u\n", (unsigned)(subtype)); + HDexit(4); + } /* end switch */ + } else if (sig[0] == H5O_VERSION) { /* * This could be an object header. Since they don't have a signature -- cgit v0.12