diff options
| -rw-r--r-- | MANIFEST | 1 | ||||
| -rw-r--r-- | src/H5AC.c | 1 | ||||
| -rw-r--r-- | src/H5ACprivate.h | 5 | ||||
| -rw-r--r-- | src/H5B2.c | 1007 | ||||
| -rw-r--r-- | src/H5B2cache.c | 1003 | ||||
| -rw-r--r-- | src/H5B2dbg.c | 3 | ||||
| -rw-r--r-- | src/H5B2pkg.h | 69 | ||||
| -rw-r--r-- | src/H5B2private.h | 7 | ||||
| -rw-r--r-- | src/H5FLprivate.h | 32 | ||||
| -rwxr-xr-x | src/Makefile.am | 7 | ||||
| -rw-r--r-- | src/Makefile.in | 56 | ||||
| -rw-r--r-- | test/btree2.c | 155 |
12 files changed, 1590 insertions, 756 deletions
@@ -775,6 +775,7 @@ ./src/H5Bprivate.h ./src/H5Bpublic.h ./src/H5B2.c +./src/H5B2cache.c ./src/H5B2dbg.c ./src/H5B2pkg.h ./src/H5B2private.h @@ -345,6 +345,7 @@ static const char * H5AC_entry_type_names[H5AC_NTYPES] = "global heaps", "object headers", "v2 B-tree headers", + "v2 B-tree internal nodes", "v2 B-tree leaf nodes" }; diff --git a/src/H5ACprivate.h b/src/H5ACprivate.h index 51f5b5a..44bd862 100644 --- a/src/H5ACprivate.h +++ b/src/H5ACprivate.h @@ -45,8 +45,9 @@ #define H5AC_GHEAP_ID 3 /*global heap */ #define H5AC_OHDR_ID 4 /*object header */ #define H5AC_BT2_HDR_ID 5 /*v2 B-tree header */ -#define H5AC_BT2_LEAF_ID 6 /*v2 B-tree leaf */ -#define H5AC_NTYPES 7 +#define H5AC_BT2_INT_ID 6 /*v2 B-tree internal node */ +#define H5AC_BT2_LEAF_ID 7 /*v2 B-tree leaf node */ +#define H5AC_NTYPES 8 /* H5AC_DUMP_STATS_ON_CLOSE should always be FALSE when * H5C_COLLECT_CACHE_STATS is FALSE. @@ -38,16 +38,6 @@ /* Local macros */ -/* B-tree version #'s */ -#define H5B2_HDR_VERSION 0 /* Header */ -#define H5B2_LEAF_VERSION 0 /* Leaf node */ - -/* Size of storage for number of records per node (on disk) */ -#define H5B2_SIZEOF_RECORDS_PER_NODE 2 - -/* Size of a "node pointer" (on disk) */ -#define H5B2_NODE_POINTER_SIZE(f) (H5F_SIZEOF_ADDR(f)+H5B2_SIZEOF_RECORDS_PER_NODE+H5F_SIZEOF_SIZE(f)) - /* Format overhead for each node (on disk) */ #define H5B2_OVERHEAD_SIZE (H5B2_SIZEOF_MAGIC+1) /* Signature + version # */ @@ -57,21 +47,9 @@ /* Number of records that fit into leaf node */ #define H5B2_NUM_LEAF_REC(n,r) (((n)-H5B2_OVERHEAD_SIZE)/(r)) -/* Size of the B-tree header on disk */ -#define H5B2_HEADER_SIZE(f) ( \ - 4 + /* Signature */ \ - 1 + /* Version */ \ - 1 + /* Tree type */ \ - 4 + /* Node size, in bytes */ \ - 2 + /* Key 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%) */ \ - H5B2_NODE_POINTER_SIZE(f)) /* Node pointer to root node in tree */ - /* Macro to retrieve pointer to i'th native key for leaf node */ -#define H5B2_INT_NKEY(i,shared,idx) ((i)->int_native+(shared)->int_nat_off[(idx)]) -#define H5B2_LEAF_NKEY(l,shared,idx) ((l)->leaf_native+(shared)->leaf_nat_off[(idx)]) +#define H5B2_INT_NKEY(i,shared,idx) ((i)->int_native+(shared)->nat_off[(idx)]) +#define H5B2_LEAF_NKEY(l,shared,idx) ((l)->leaf_native+(shared)->nat_off[(idx)]) /* Local typedefs */ @@ -79,69 +57,39 @@ /* Local prototypes */ /* Helper functions */ -static herr_t H5B2_shared_free (void *_shared); -static herr_t H5B2_shared_init (H5F_t *f, H5B2_t *bt2, const H5B2_class_t *type, - size_t node_size, size_t rkey_size, unsigned split_percent, unsigned merge_percent); static herr_t H5B2_create_leaf(H5F_t *f, hid_t dxpl_id, H5B2_t *bt2, H5B2_node_ptr_t *node_ptr); static int H5B2_locate_record(H5F_t *f, hid_t dxpl_id, const H5B2_class_t *type, unsigned nrec, size_t *rec_off, const uint8_t *native, const void *udata); +static herr_t H5B2_split_root(H5F_t *f, hid_t dxpl_id, H5B2_t *bt2, + const H5B2_shared_t *shared); +static herr_t H5B2_create_internal(H5F_t *f, hid_t dxpl_id, H5B2_t *bt2, + H5B2_node_ptr_t *node_ptr); -/* Metadata cache callbacks */ -static H5B2_t *H5B2_cache_hdr_load(H5F_t *f, hid_t dxpl_id, haddr_t addr, const void *_type, void *udata); -static herr_t H5B2_cache_hdr_flush(H5F_t *f, hid_t dxpl_id, hbool_t destroy, haddr_t addr, H5B2_t *b); -static herr_t H5B2_cache_hdr_dest(H5F_t *f, H5B2_t *b); -static herr_t H5B2_cache_hdr_clear(H5F_t *f, H5B2_t *b, hbool_t destroy); -static herr_t H5B2_cache_hdr_size(const H5F_t *f, const H5B2_t *bt, size_t *size_ptr); -static H5B2_leaf_t *H5B2_cache_leaf_load(H5F_t *f, hid_t dxpl_id, haddr_t addr, const void *_type, void *udata); -static herr_t H5B2_cache_leaf_flush(H5F_t *f, hid_t dxpl_id, hbool_t destroy, haddr_t addr, H5B2_leaf_t *l); -static herr_t H5B2_cache_leaf_dest(H5F_t *f, H5B2_leaf_t *l); -static herr_t H5B2_cache_leaf_clear(H5F_t *f, H5B2_leaf_t *l, hbool_t destroy); -static herr_t H5B2_cache_leaf_size(const H5F_t *f, const H5B2_leaf_t *l, size_t *size_ptr); -/* Static variables */ +/* Package variables */ + +/* Declare a free list to manage the H5B2_t struct */ +H5FL_DEFINE(H5B2_t); + +/* Declare a free list to manage the H5B2_internal_t struct */ +H5FL_DEFINE(H5B2_internal_t); + +/* Declare a free list to manage the H5B2_leaf_t struct */ +H5FL_DEFINE(H5B2_leaf_t); + -/* H5B2 inherits cache-like properties from H5AC */ -const H5AC_class_t H5AC_BT2_HDR[1] = {{ - H5AC_BT2_HDR_ID, - (H5AC_load_func_t)H5B2_cache_hdr_load, - (H5AC_flush_func_t)H5B2_cache_hdr_flush, - (H5AC_dest_func_t)H5B2_cache_hdr_dest, - (H5AC_clear_func_t)H5B2_cache_hdr_clear, - (H5AC_size_func_t)H5B2_cache_hdr_size, -}}; - -/* H5B2 inherits cache-like properties from H5AC */ -static const H5AC_class_t H5AC_BT2_LEAF[1] = {{ - H5AC_BT2_LEAF_ID, - (H5AC_load_func_t)H5B2_cache_leaf_load, - (H5AC_flush_func_t)H5B2_cache_leaf_flush, - (H5AC_dest_func_t)H5B2_cache_leaf_dest, - (H5AC_clear_func_t)H5B2_cache_leaf_clear, - (H5AC_size_func_t)H5B2_cache_leaf_size, -}}; - - -/* Declare a free list to manage B-tree header data to/from disk */ -H5FL_BLK_DEFINE_STATIC(header_block); +/* 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 'H5B2_node_ptr_t' sequence information */ -H5FL_SEQ_DEFINE_STATIC(H5B2_node_ptr_t); - /* Declare a free list to manage the 'size_t' sequence information */ H5FL_SEQ_DEFINE_STATIC(size_t); -/* Declare a free list to manage the H5B2_t struct */ -H5FL_DEFINE_STATIC(H5B2_t); - /* Declare a free list to manage the H5B2_shared_t struct */ H5FL_DEFINE_STATIC(H5B2_shared_t); -/* Declare a free list to manage the H5B2_leaf_t struct */ -H5FL_DEFINE_STATIC(H5B2_leaf_t); /*------------------------------------------------------------------------- @@ -157,7 +105,7 @@ H5FL_DEFINE_STATIC(H5B2_leaf_t); * *------------------------------------------------------------------------- */ -static herr_t +herr_t H5B2_shared_init (H5F_t *f, H5B2_t *bt2, const H5B2_class_t *type, size_t node_size, size_t rkey_size, unsigned split_percent, unsigned merge_percent) @@ -207,28 +155,12 @@ H5B2_shared_init (H5F_t *f, H5B2_t *bt2, const H5B2_class_t *type, HGOTO_ERROR (H5E_RESOURCE, H5E_CANTINIT, NULL, "can't create internal node node pointer block factory") /* Allocate array of pointers to internal node native keys */ - if((shared->int_nat_off=H5FL_SEQ_MALLOC(size_t,shared->internal_nrec))==NULL) + if((shared->nat_off=H5FL_SEQ_MALLOC(size_t,MAX(shared->internal_nrec,shared->leaf_nrec)))==NULL) HGOTO_ERROR (H5E_RESOURCE, H5E_NOSPACE, NULL, "memory allocation failed"); - /* Allocate array of pointers to leaf node native keys */ - if((shared->leaf_nat_off=H5FL_SEQ_MALLOC(size_t,shared->leaf_nrec))==NULL) - HGOTO_ERROR (H5E_RESOURCE, H5E_NOSPACE, NULL, "memory allocation failed"); - - /* Allocate array of pointers to internal node node pointers */ - if((shared->node_ptr_off=H5FL_SEQ_MALLOC(H5B2_node_ptr_t,(shared->internal_nrec+1)))==NULL) - HGOTO_ERROR (H5E_RESOURCE, H5E_NOSPACE, NULL, "memory allocation failed"); - - /* Initialize offsets in internal node native key block */ - for(u=0; u<shared->internal_nrec; u++) - shared->int_nat_off[u]=type->nkey_size*u; - - /* Initialize offsets in leaf node native key block */ - for(u=0; u<shared->leaf_nrec; u++) - shared->leaf_nat_off[u]=type->nkey_size*u; - - /* Initialize offsets in internal node node pointer block */ - for(u=0; u<(shared->internal_nrec+1); u++) - shared->node_ptr_off[u]=sizeof(H5B2_node_ptr_t)*u; + /* Initialize offsets in native key block */ + for(u=0; u<MAX(shared->internal_nrec,shared->leaf_nrec); u++) + shared->nat_off[u]=type->nkey_size*u; /* Make shared B-tree info reference counted */ if(NULL==(bt2->shared=H5RC_create(shared,H5B2_shared_free))) @@ -256,7 +188,7 @@ done: * *------------------------------------------------------------------------- */ -static herr_t +herr_t H5B2_shared_free (void *_shared) { H5B2_shared_t *shared = (H5B2_shared_t *)_shared; @@ -286,17 +218,9 @@ H5B2_shared_free (void *_shared) if(H5FL_fac_term(shared->node_ptr_fac)<0) HGOTO_ERROR (H5E_RESOURCE, H5E_CANTRELEASE, FAIL, "can't destroy internal node node pointer block factory") - /* Free the array of offsets into the internal node native key block */ - if(shared->int_nat_off) - H5FL_SEQ_FREE(size_t,shared->int_nat_off); - - /* Free the array of offsets into the leaf node native key block */ - if(shared->leaf_nat_off) - H5FL_SEQ_FREE(size_t,shared->leaf_nat_off); - - /* Free the array of offsets into the internal node node pointer block */ - if(shared->node_ptr_off) - H5FL_SEQ_FREE(H5B2_node_ptr_t,shared->node_ptr_off); + /* Free the array of offsets into the native key block */ + if(shared->nat_off) + H5FL_SEQ_FREE(size_t,shared->nat_off); /* Free the shared B-tree info itself */ H5FL_FREE(H5B2_shared_t,shared); @@ -378,340 +302,158 @@ done: /*------------------------------------------------------------------------- - * Function: H5B2_cache_hdr_load + * Function: H5B2_locate_record * - * Purpose: Loads a B-tree header from the disk. + * Purpose: Performs a binary search to locate a record in a sorted + * array of records. * - * Return: Success: Pointer to a new B-tree. + * Return: Success: Non-negative array index where new record + * should be inserted * - * Failure: NULL + * Failure: Negative, if record already is in array of + * records. * * Programmer: Quincey Koziol * koziol@ncsa.uiuc.edu - * Feb 1 2005 + * Feb 3 2005 * *------------------------------------------------------------------------- */ -static H5B2_t * -H5B2_cache_hdr_load(H5F_t *f, hid_t dxpl_id, haddr_t addr, const void *_type, void UNUSED *udata) +static int +H5B2_locate_record(H5F_t *f, hid_t dxpl_id, const H5B2_class_t *type, + unsigned nrec, size_t *rec_off, const uint8_t *native, + const void *udata) { - const H5B2_class_t *type = (const H5B2_class_t *) _type; - size_t node_size, rkey_size; /* Size info for B-tree */ - unsigned split_percent, merge_percent; /* Split & merge info for B-tree */ - H5B2_t *bt2 = NULL; - size_t size; - uint8_t *buf = NULL; - uint8_t *p; /* Pointer into raw data buffer */ - H5B2_t *ret_value; - - FUNC_ENTER_NOAPI(H5B2_cache_hdr_load, NULL) - - /* Check arguments */ - HDassert(f); - HDassert(H5F_addr_defined(addr)); - HDassert(type); - - if (NULL==(bt2 = H5FL_MALLOC(H5B2_t))) - HGOTO_ERROR (H5E_RESOURCE, H5E_NOSPACE, NULL, "memory allocation failed") - HDmemset(&bt2->cache_info,0,sizeof(H5AC_info_t)); - - /* Compute the size of the B-tree header on disk */ - size = H5B2_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, H5B2_HDR_MAGIC, H5B2_SIZEOF_MAGIC)) - HGOTO_ERROR(H5E_BTREE, H5E_CANTLOAD, NULL, "wrong B-tree header signature") - p += H5B2_SIZEOF_MAGIC; - - /* version */ - if (*p++ != H5B2_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); - - /* raw key size (in bytes) */ - UINT16DECODE(p, rkey_size); - - /* depth of tree */ - UINT16DECODE(p, bt2->depth); - - /* split & merge %s */ - UINT16DECODE(p, split_percent); - UINT16DECODE(p, merge_percent); - - /* root node pointer */ - H5F_addr_decode(f, (const uint8_t **)&p, &(bt2->root.addr)); - UINT16DECODE(p, bt2->root.node_nrec); - H5F_DECODE_LENGTH(f, p, bt2->root.all_nrec); + unsigned lo = 0, hi; /* Low & high index values */ + int idx = 0; /* Final index value */ + int cmp = -1; /* Key comparison value */ - /* Initialize shared B-tree info */ - if(H5B2_shared_init(f, bt2, type, node_size, rkey_size, split_percent, merge_percent)<0) - HGOTO_ERROR (H5E_RESOURCE, H5E_NOSPACE, NULL, "can't create shared B-tree info") + FUNC_ENTER_NOAPI_NOINIT_NOFUNC(H5B2_locate_record) - /* Set return value */ - ret_value = bt2; + hi = nrec; + while (lo < hi && cmp) { + idx = (lo + hi) / 2; + if ((cmp = (type->compare)(f, dxpl_id, udata, native+rec_off[idx])) < 0) + hi = idx; + else + lo = idx + 1; + } + if(cmp==0) + idx=(-1); + else if(cmp>0) + idx++; -done: - if(buf) - H5FL_BLK_FREE(header_block,buf); - if (!ret_value && bt2) - (void)H5B2_cache_hdr_dest(f,bt2); - FUNC_LEAVE_NOAPI(ret_value) -} /*lint !e818 Can't make udata a pointer to const */ + FUNC_LEAVE_NOAPI(idx); +} /* end H5B2_locate_record */ /*------------------------------------------------------------------------- - * Function: H5B2_cache_hdr_flush + * Function: H5B2_split_root * - * Purpose: Flushes a dirty B-tree header to disk. + * Purpose: Split the root node * - * Return: Non-negative on success/Negative on failure + * Return: Success: Non-negative + * + * Failure: Negative * * Programmer: Quincey Koziol * koziol@ncsa.uiuc.edu - * Feb 1 2005 + * Feb 3 2005 * *------------------------------------------------------------------------- */ static herr_t -H5B2_cache_hdr_flush(H5F_t *f, hid_t dxpl_id, hbool_t destroy, haddr_t addr, H5B2_t *bt2) +H5B2_split_root(H5F_t *f, hid_t dxpl_id, H5B2_t *bt2, const H5B2_shared_t *shared) { - herr_t ret_value = SUCCEED; /* Return value */ + herr_t ret_value=SUCCEED; /* Return value */ - FUNC_ENTER_NOAPI(H5B2_cache_hdr_flush, FAIL) + FUNC_ENTER_NOAPI_NOINIT(H5B2_split_root) - /* check arguments */ HDassert(f); - HDassert(H5F_addr_defined(addr)); HDassert(bt2); + HDassert(shared); - if (bt2->cache_info.is_dirty) { - H5B2_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(bt2->shared); - HDassert(shared); - - /* Compute the size of the B-tree header on disk */ - size = H5B2_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, H5B2_HDR_MAGIC, H5B2_SIZEOF_MAGIC); - p += H5B2_SIZEOF_MAGIC; - - /* version # */ - *p++ = H5B2_HDR_VERSION; - - /* b-tree type */ - *p++ = shared->type->id; - - /* node size (in bytes) */ - UINT32ENCODE(p, shared->node_size); - - /* raw key size (in bytes) */ - UINT16ENCODE(p, shared->rkey_size); + if(bt2->depth==0) { + H5B2_internal_t *new_int=NULL; /* Pointer to new internal node */ + H5B2_leaf_t *old_leaf=NULL, *new_leaf=NULL; /* Pointers to old & new leaf nodes */ + H5B2_node_ptr_t new_int_ptr; /* Node pointer to manage new internal node */ + H5B2_node_ptr_t new_leaf_ptr; /* Node pointer to manage new leaf node */ + unsigned mid_record; /* Index of "middle" record in current node */ - /* depth of tree */ - UINT16ENCODE(p, bt2->depth); + /* Create new leaf node */ + new_leaf_ptr.all_nrec=new_leaf_ptr.node_nrec=0; + if(H5B2_create_leaf(f, dxpl_id, bt2, &new_leaf_ptr)<0) + HGOTO_ERROR(H5E_BTREE, H5E_CANTINIT, FAIL, "unable to create new leaf node") - /* split & merge %s */ - UINT16ENCODE(p, shared->split_percent); - UINT16ENCODE(p, shared->merge_percent); + /* Determine "middle" record to promote to new root */ + mid_record = shared->split_leaf_nrec/2; - /* root node pointer */ - H5F_addr_encode(f, &p, bt2->root.addr); - UINT16ENCODE(p, bt2->root.node_nrec); - H5F_ENCODE_LENGTH(f, p, bt2->root.all_nrec); + /* Protect both leafs */ + if (NULL == (old_leaf = H5AC_protect(f, dxpl_id, H5AC_BT2_LEAF, bt2->root.addr, shared->type, &(bt2->root), H5AC_WRITE))) + HGOTO_ERROR(H5E_BTREE, H5E_CANTLOAD, FAIL, "unable to load B-tree leaf node") + if (NULL == (new_leaf = H5AC_protect(f, dxpl_id, H5AC_BT2_LEAF, new_leaf_ptr.addr, shared->type, &new_leaf_ptr, H5AC_WRITE))) + HGOTO_ERROR(H5E_BTREE, H5E_CANTLOAD, FAIL, "unable to load B-tree leaf node") - /* 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") + /* Copy "upper half" of records to new leaf */ + HDmemcpy(new_leaf->leaf_native,H5B2_LEAF_NKEY(old_leaf,shared,mid_record+1),shared->type->nkey_size*(shared->split_leaf_nrec-(mid_record+1))); - H5FL_BLK_FREE(header_block,buf); + /* Create new internal node */ + new_int_ptr.all_nrec=new_int_ptr.node_nrec=0; + if(H5B2_create_internal(f, dxpl_id, bt2, &new_int_ptr)<0) + HGOTO_ERROR(H5E_BTREE, H5E_CANTINIT, FAIL, "unable to create new internal node") - bt2->cache_info.is_dirty = FALSE; - } /* end if */ + /* Protect new internal node */ + if (NULL == (new_int = H5AC_protect(f, dxpl_id, H5AC_BT2_INT, new_int_ptr.addr, shared->type, &new_int_ptr, H5AC_WRITE))) + HGOTO_ERROR(H5E_BTREE, H5E_CANTLOAD, FAIL, "unable to load B-tree internal node") - if (destroy) - if (H5B2_cache_hdr_dest(f,bt2) < 0) - HGOTO_ERROR(H5E_BTREE, H5E_CANTFREE, FAIL, "unable to destroy B-tree header") + /* Copy "middle" record to new internal node */ + HDmemcpy(new_int->int_native,H5B2_LEAF_NKEY(old_leaf,shared,mid_record),shared->type->nkey_size); -done: - FUNC_LEAVE_NOAPI(ret_value) -} /* H5B2_cache_hdr_flush() */ + /* Update record counts in leaf nodes */ + bt2->root.all_nrec=bt2->root.node_nrec=old_leaf->nrec=mid_record; + new_leaf_ptr.all_nrec=new_leaf_ptr.node_nrec=new_leaf->nrec=shared->split_leaf_nrec-(mid_record+1); - -/*------------------------------------------------------------------------- - * Function: H5B_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 - * Feb 1 2005 - * - *------------------------------------------------------------------------- - */ -/* ARGSUSED */ -static herr_t -H5B2_cache_hdr_dest(H5F_t UNUSED *f, H5B2_t *bt2) -{ - FUNC_ENTER_NOAPI_NOINIT_NOFUNC(H5B2_cache_hdr_dest) + /* Mark leaf nodes as dirty */ + old_leaf->cache_info.is_dirty = TRUE; + new_leaf->cache_info.is_dirty = TRUE; - /* - * Check arguments. - */ - HDassert(bt2); + /* Release leaf nodes */ + if (H5AC_unprotect(f, dxpl_id, H5AC_BT2_LEAF, bt2->root.addr, old_leaf, H5AC__NO_FLAGS_SET) < 0) + HGOTO_ERROR(H5E_BTREE, H5E_PROTECT, FAIL, "unable to release B-tree leaf node") + if (H5AC_unprotect(f, dxpl_id, H5AC_BT2_LEAF, new_leaf_ptr.addr, new_leaf, H5AC__NO_FLAGS_SET) < 0) + HGOTO_ERROR(H5E_BTREE, H5E_PROTECT, FAIL, "unable to release B-tree leaf node") - /* Decrement reference count on shared B-tree info */ - if(bt2->shared) - H5RC_DEC(bt2->shared); + /* Set internal node pointers to leaf nodes */ + new_int->node_ptrs[0]=bt2->root; + new_int->node_ptrs[1]=new_leaf_ptr; - /* Free B-tree header info */ - H5FL_FREE(H5B2_t,bt2); + /* Update record count in new internal node */ + new_int->nrec = 1; - FUNC_LEAVE_NOAPI(SUCCEED) -} /* end H5B2_cache_hdr_dest() */ + /* Mark new internal node as dirty */ + new_int->cache_info.is_dirty = TRUE; - -/*------------------------------------------------------------------------- - * Function: H5B2_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 - * Feb 1 2005 - * - *------------------------------------------------------------------------- - */ -static herr_t -H5B2_cache_hdr_clear(H5F_t *f, H5B2_t *bt2, hbool_t destroy) -{ - herr_t ret_value = SUCCEED; + /* Release new internal node */ + if (H5AC_unprotect(f, dxpl_id, H5AC_BT2_INT, new_int_ptr.addr, new_int, H5AC__NO_FLAGS_SET) < 0) + HGOTO_ERROR(H5E_BTREE, H5E_PROTECT, FAIL, "unable to release B-tree internal node") - FUNC_ENTER_NOAPI_NOINIT(H5B2_cache_hdr_clear) + /* Update depth of B-tree */ + bt2->depth++; - /* - * Check arguments. - */ - HDassert(bt2); + /* Update pointer to B-tree's root node to pointer to new internal node */ + bt2->root = new_int_ptr; - /* Reset the dirty flag. */ - bt2->cache_info.is_dirty = FALSE; - - if (destroy) - if (H5B2_cache_hdr_dest(f, bt2) < 0) - HGOTO_ERROR(H5E_BTREE, H5E_CANTFREE, FAIL, "unable to destroy B-tree header") + /* Mark B-tree header as dirty */ + bt2->cache_info.is_dirty = TRUE; + } /* end if */ + else { +HDfprintf(stderr,"%s: Need to split internal root! shared->split_int_nrec=%Zu\n",FUNC,shared->split_int_nrec); +HGOTO_ERROR(H5E_BTREE, H5E_CANTSPLIT, FAIL, "unable to split internal root node yet") + } /* end else */ done: - FUNC_LEAVE_NOAPI(ret_value) -} /* end H5B2_cache_hdr_clear() */ - - -/*------------------------------------------------------------------------- - * Function: H5B2_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 - * Feb 1 2005 - * - *------------------------------------------------------------------------- - */ -static herr_t -H5B2_cache_hdr_size(const H5F_t *f, const H5B2_t UNUSED *bt2, size_t *size_ptr) -{ - FUNC_ENTER_NOAPI_NOINIT_NOFUNC(H5B2_cache_hdr_size) - - /* check arguments */ - HDassert(f); - HDassert(size_ptr); - - /* Set size value */ - *size_ptr = H5B2_HEADER_SIZE(f); - - FUNC_LEAVE_NOAPI(SUCCEED) -} /* H5B2_cache_hdr_size() */ - - -/*------------------------------------------------------------------------- - * Function: H5B2_locate_record - * - * Purpose: Performs a binary search to locate a record in a sorted - * array of records. - * - * Return: Success: Non-negative array index where new record - * should be inserted - * - * Failure: Negative, if record already is in array of - * records. - * - * Programmer: Quincey Koziol - * koziol@ncsa.uiuc.edu - * Feb 3 2005 - * - *------------------------------------------------------------------------- - */ -static int -H5B2_locate_record(H5F_t *f, hid_t dxpl_id, const H5B2_class_t *type, - unsigned nrec, size_t *rec_off, const uint8_t *native, - const void *udata) -{ - unsigned lo = 0, hi; /* Low & high index values */ - int idx = 0; /* Final index value */ - int cmp = -1; /* Key comparison value */ - - FUNC_ENTER_NOAPI_NOINIT_NOFUNC(H5B2_locate_record) - - hi = nrec; - while (lo < hi && cmp) { - idx = (lo + hi) / 2; - if ((cmp = (type->compare)(f, dxpl_id, udata, native+rec_off[idx])) < 0) - hi = idx; - else - lo = idx + 1; - } - if(cmp==0) - idx=(-1); - else if(cmp>0) - idx++; - - FUNC_LEAVE_NOAPI(idx); -} /* end H5B2_locate_record */ + FUNC_LEAVE_NOAPI(ret_value); +} /* end H5B2_split_root */ /*------------------------------------------------------------------------- @@ -733,11 +475,11 @@ herr_t H5B2_insert(H5F_t *f, hid_t dxpl_id, const H5B2_class_t *type, haddr_t addr, void *udata) { - H5AC_info_t *cache_info; /* Parent node's cache info */ H5B2_t *bt2=NULL; /* Pointer to the B-tree header */ H5B2_shared_t *shared; /* Pointer to B-tree's shared information */ - H5B2_node_ptr_t *node_ptr; /* Pointer to node pointer info for current node */ - unsigned depth; /* Current depth of node */ + H5B2_node_ptr_t leaf_ptr; /* Node pointer info for leaf node */ + H5B2_leaf_t *leaf=NULL; /* Pointer to leaf node */ + int idx; /* Location of record which matches key */ herr_t ret_value = SUCCEED; FUNC_ENTER_NOAPI(H5B2_insert, FAIL) @@ -764,71 +506,174 @@ H5B2_insert(H5F_t *f, hid_t dxpl_id, const H5B2_class_t *type, haddr_t addr, /* Mark B-tree header as dirty, since we updated the address of the root node */ bt2->cache_info.is_dirty = TRUE; } /* end if */ -depth=bt2->depth; -node_ptr=&(bt2->root); -cache_info=&(bt2->cache_info); + /* Check if we need to split the root node */ + else if((bt2->depth==0 && bt2->root.node_nrec==shared->split_leaf_nrec) || + (bt2->depth>0 && bt2->root.node_nrec==shared->split_int_nrec)) { + /* Split root node */ + if(H5B2_split_root(f, dxpl_id, bt2, shared)<0) + HGOTO_ERROR(H5E_BTREE, H5E_CANTSPLIT, FAIL, "unable to split root node") + } /* end if */ + + /* Check for non-trivial B-tree */ + if(bt2->depth>0) { + H5B2_internal_t *internal; /* Pointer to internal node in B-tree */ + H5AC_info_t *parent_cache_info; /* Parent node's cache info */ + haddr_t parent_addr; /* Address of parent which contain's node pointer to current node */ + void *parent_ptr; /* Pointer to parent structure in memory */ + H5AC_info_t *curr_cache_info=NULL; /* Current node's cache info */ + H5B2_node_ptr_t *curr_node_ptr; /* Pointer to node pointer info for current node (in parent node) */ + haddr_t curr_addr=HADDR_UNDEF; /* Address of current node */ + void *curr_ptr=NULL; /* Pointer to current structure in memory */ + H5B2_node_ptr_t *child_node_ptr=NULL; /* Pointer to node pointer info for child node */ + unsigned depth; /* Depth of current node */ + + /* Track the depth of current node (leaves are depth 0) */ + depth=bt2->depth; + + /* Set initial "parent" information to the B-tree header */ + parent_cache_info=&(bt2->cache_info); + parent_addr=addr; + parent_ptr=bt2; + + /* Set initial node pointer for "current" node */ + curr_node_ptr=&(bt2->root); + + /* Find correct leaf to insert node into */ + while(depth>0) { + /* Lock B-tree current node */ + if (NULL == (internal = H5AC_protect(f, dxpl_id, H5AC_BT2_INT, curr_node_ptr->addr, shared->type, curr_node_ptr, H5AC_WRITE))) + HGOTO_ERROR(H5E_BTREE, H5E_CANTLOAD, FAIL, "unable to load B-tree internal node") + + /* Set information for current (root) node */ + curr_cache_info=&(internal->cache_info); + curr_addr=curr_node_ptr->addr; + curr_ptr=internal; + + /* Locate node pointer for child */ + if((idx=H5B2_locate_record(f,dxpl_id,shared->type,internal->nrec,shared->nat_off,internal->int_native,udata))<0) + HGOTO_ERROR(H5E_BTREE, H5E_EXISTS, FAIL, "record is already in B-tree") - /* Check if we are inserting in internal or leaf node */ - if(depth==0) { - H5B2_leaf_t *leaf=NULL; /* Pointer to leaf node */ - int idx; /* Location of record which matches key */ + /* Get node pointer for child */ + child_node_ptr=&(internal->node_ptrs[idx]); + + /* Preemptively split/redistribute a node we will enter */ + if((depth==1 && child_node_ptr->node_nrec==shared->split_leaf_nrec) || + (depth>1 && child_node_ptr->node_nrec==shared->split_int_nrec)) { +HDfprintf(stderr,"%s: need to split child node!, depth=%u\n",FUNC,depth); +HGOTO_ERROR(H5E_BTREE, H5E_CANTSPLIT, FAIL, "unable to split child node") + /* Attempt to redistribute records among children */ + /* Split children, if can't redistribute */ + /* Update record count info for current node to reflect new # of records (in parent) */ + /* Update child_node_ptr (to reflect change in location from split/redistribution) */ + } /* end if */ - /* Look up the B-tree leaf node */ - if (NULL == (leaf = H5AC_protect(f, dxpl_id, H5AC_BT2_LEAF, node_ptr->addr, shared->type, node_ptr, H5AC_WRITE))) - HGOTO_ERROR(H5E_BTREE, H5E_CANTLOAD, FAIL, "unable to load B-tree leaf node") + /* Update record count (in parent) */ + curr_node_ptr->all_nrec++; - /* Check for inserting into empty leaf */ - if(node_ptr->node_nrec==0) - idx=0; - else { - /* Find correct location to insert this record and make room for it */ - if((idx=H5B2_locate_record(f,dxpl_id,shared->type,leaf->nrec,shared->leaf_nat_off,leaf->leaf_native,udata))<0) { - /* Release the B-tree leaf node */ - if (H5AC_unprotect(f, dxpl_id, H5AC_BT2_LEAF, node_ptr->addr, leaf, H5AC__NO_FLAGS_SET) < 0) - HGOTO_ERROR(H5E_BTREE, H5E_PROTECT, FAIL, "unable to release B-tree leaf node") + /* Mark parent node as dirty */ + parent_cache_info->is_dirty = TRUE; - HGOTO_ERROR(H5E_BTREE, H5E_EXISTS, FAIL, "record is already in B-tree") - } /* end if */ + /* Unlock parent node (possibly the B-tree header) */ + if (H5AC_unprotect(f, dxpl_id, parent_cache_info->type, parent_addr, parent_ptr, H5AC__NO_FLAGS_SET) < 0) + HGOTO_ERROR(H5E_BTREE, H5E_PROTECT, FAIL, "unable to release B-tree info") - /* Make room for new record */ - if((unsigned)idx<leaf->nrec) - HDmemmove(H5B2_LEAF_NKEY(leaf,shared,idx+1),H5B2_LEAF_NKEY(leaf,shared,idx),shared->type->nkey_size*(leaf->nrec-idx)); - } /* end else */ + /* Transition "current" info into "parent" info */ + parent_cache_info = curr_cache_info; + parent_addr = curr_addr; + parent_ptr = curr_ptr; - /* Make callback to store record in native form */ - if((shared->type->store)(f,dxpl_id,udata,H5B2_LEAF_NKEY(leaf,shared,idx))<0) { - /* Release the B-tree leaf node */ - if (H5AC_unprotect(f, dxpl_id, H5AC_BT2_LEAF, node_ptr->addr, leaf, H5AC__NO_FLAGS_SET) < 0) - HGOTO_ERROR(H5E_BTREE, H5E_PROTECT, FAIL, "unable to release B-tree leaf node") + /* Transition "child" node pointer to "current" node pointer */ + curr_node_ptr = child_node_ptr; - HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, FAIL, "unable to insert record into leaf node") - } /* end if */ + /* Decrement depth of current node */ + depth--; + } /* end while */ + + /* Update record count for leaf (in current node) */ + HDassert(curr_node_ptr); + curr_node_ptr->all_nrec++; + curr_node_ptr->node_nrec++; + + /* Mark parent node as dirty */ + curr_cache_info->is_dirty = TRUE; + + /* Copy node pointer info for leaf */ + leaf_ptr = *curr_node_ptr; + + /* Release current node */ + if (H5AC_unprotect(f, dxpl_id, curr_cache_info->type, curr_addr, curr_ptr, H5AC__NO_FLAGS_SET) < 0) + HGOTO_ERROR(H5E_BTREE, H5E_PROTECT, FAIL, "unable to release B-tree node") + } /* end if */ + else { + /* Update record count for root node */ + bt2->root.all_nrec++; + bt2->root.node_nrec++; + + /* Mark parent node as dirty */ + bt2->cache_info.is_dirty = TRUE; + + /* Copy node pointer info for leaf */ + leaf_ptr = bt2->root; - /* Update record # info in node pointer */ - node_ptr->all_nrec++; - node_ptr->node_nrec++; + /* Release parent node */ + if (H5AC_unprotect(f, dxpl_id, H5AC_BT2_HDR, addr, bt2, H5AC__NO_FLAGS_SET) < 0) + HGOTO_ERROR(H5E_BTREE, H5E_PROTECT, FAIL, "unable to release B-tree header info") + bt2=NULL; + } /* end else */ + + /* Must have a leaf node with enough space to insert a record now */ + HDassert(H5F_addr_defined(leaf_ptr.addr)); + HDassert((leaf_ptr.node_nrec-1)<shared->split_leaf_nrec); /* node pointer to leaf has already been incremented */ + + /* Look up the B-tree leaf node */ + if (NULL == (leaf = H5AC_protect(f, dxpl_id, H5AC_BT2_LEAF, leaf_ptr.addr, shared->type, &leaf_ptr, H5AC_WRITE))) + HGOTO_ERROR(H5E_BTREE, H5E_CANTLOAD, FAIL, "unable to load B-tree leaf node") + + /* Sanity check number of records */ + HDassert(leaf_ptr.all_nrec==leaf_ptr.node_nrec); + HDassert(leaf->nrec==(leaf_ptr.node_nrec-1)); /* node pointer to leaf has already been incremented */ + + /* Check for inserting into empty leaf */ + if(leaf->nrec==0) + idx=0; + else { + /* Sanity check for the leaf node being full */ + HDassert(leaf->nrec!=shared->split_leaf_nrec); - /* Update number of records in node */ - leaf->nrec++; - HDassert(node_ptr->node_nrec==leaf->nrec); + /* Find correct location to insert this record and make room for it */ + if((idx=H5B2_locate_record(f,dxpl_id,shared->type,leaf->nrec,shared->nat_off,leaf->leaf_native,udata))<0) { + /* Release the B-tree leaf node */ + if (H5AC_unprotect(f, dxpl_id, H5AC_BT2_LEAF, leaf_ptr.addr, leaf, H5AC__NO_FLAGS_SET) < 0) + HGOTO_ERROR(H5E_BTREE, H5E_PROTECT, FAIL, "unable to release B-tree leaf node") - /* Mark parent's node as dirty now */ - cache_info->is_dirty = TRUE; + HGOTO_ERROR(H5E_BTREE, H5E_EXISTS, FAIL, "record is already in B-tree") + } /* end if */ - /* Mark leaf node as dirty also */ - leaf->cache_info.is_dirty = TRUE; + /* Make room for new record */ + if((unsigned)idx<leaf->nrec) + HDmemmove(H5B2_LEAF_NKEY(leaf,shared,idx+1),H5B2_LEAF_NKEY(leaf,shared,idx),shared->type->nkey_size*(leaf->nrec-idx)); + } /* end else */ + /* Make callback to store record in native form */ + if((shared->type->store)(f,dxpl_id,udata,H5B2_LEAF_NKEY(leaf,shared,idx))<0) { /* Release the B-tree leaf node */ - if (H5AC_unprotect(f, dxpl_id, H5AC_BT2_LEAF, node_ptr->addr, leaf, H5AC__NO_FLAGS_SET) < 0) + if (H5AC_unprotect(f, dxpl_id, H5AC_BT2_LEAF, leaf_ptr.addr, leaf, H5AC__NO_FLAGS_SET) < 0) HGOTO_ERROR(H5E_BTREE, H5E_PROTECT, FAIL, "unable to release B-tree leaf node") + + HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, FAIL, "unable to insert record into leaf node") } /* end if */ - else { - } /* end else */ -done: - if (bt2 && H5AC_unprotect(f, dxpl_id, H5AC_BT2_HDR, addr, bt2, H5AC__NO_FLAGS_SET) < 0) - HDONE_ERROR(H5E_BTREE, H5E_PROTECT, FAIL, "unable to release B-tree header") + /* Update number of records in node */ + leaf->nrec++; + + /* Mark leaf node as dirty also */ + leaf->cache_info.is_dirty = TRUE; + + /* Release the B-tree leaf node */ + if (H5AC_unprotect(f, dxpl_id, H5AC_BT2_LEAF, leaf_ptr.addr, leaf, H5AC__NO_FLAGS_SET) < 0) + HGOTO_ERROR(H5E_BTREE, H5E_PROTECT, FAIL, "unable to release B-tree leaf node") +done: FUNC_LEAVE_NOAPI(ret_value) } /* H5B2_insert() */ @@ -847,7 +692,7 @@ done: * *------------------------------------------------------------------------- */ -herr_t +static herr_t H5B2_create_leaf(H5F_t *f, hid_t dxpl_id, H5B2_t *bt2, H5B2_node_ptr_t *node_ptr) { H5B2_leaf_t *leaf=NULL; /* Pointer to new leaf node created */ @@ -886,7 +731,7 @@ H5B2_create_leaf(H5F_t *f, hid_t dxpl_id, H5B2_t *bt2, H5B2_node_ptr_t *node_ptr /* 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 header") + 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_BT2_LEAF, node_ptr->addr, leaf, H5AC__NO_FLAGS_SET) < 0) @@ -903,274 +748,74 @@ done: /*------------------------------------------------------------------------- - * Function: H5B2_cache_leaf_load + * Function: H5B2_create_internal * - * Purpose: Loads a B-tree leaf from the disk. - * - * Return: Success: Pointer to a new B-tree leaf node. + * Purpose: Creates empty internal node of a B-tree and update node pointer + * to point to it. * - * Failure: NULL + * Return: Non-negative on success/Negative on failure * * Programmer: Quincey Koziol * koziol@ncsa.uiuc.edu - * Feb 2 2005 + * Feb 3 2005 * *------------------------------------------------------------------------- */ -static H5B2_leaf_t * -H5B2_cache_leaf_load(H5F_t *f, hid_t dxpl_id, haddr_t addr, const void *_bt2, void *_node_ptr) +static herr_t +H5B2_create_internal(H5F_t *f, hid_t dxpl_id, H5B2_t *bt2, H5B2_node_ptr_t *node_ptr) { - const H5B2_t *bt2 = (const H5B2_t *)_bt2; - H5B2_node_ptr_t *node_ptr = (H5B2_node_ptr_t *)_node_ptr; - H5B2_leaf_t *leaf = NULL; - H5B2_shared_t *shared; /* Shared B-tree information */ - uint8_t *p; /* Pointer into raw data buffer */ - H5B2_leaf_t *ret_value; + H5B2_internal_t *internal=NULL; /* Pointer to new internal node created */ + H5B2_shared_t *shared; /* Shared B-tree information */ + herr_t ret_value = SUCCEED; - FUNC_ENTER_NOAPI(H5B2_cache_leaf_load, NULL) + FUNC_ENTER_NOAPI(H5B2_create_internal, FAIL) - /* Check arguments */ + /* Check arguments. */ HDassert(f); - HDassert(H5F_addr_defined(addr)); HDassert(bt2); + HDassert(node_ptr); - if (NULL==(leaf = H5FL_MALLOC(H5B2_leaf_t))) - HGOTO_ERROR (H5E_RESOURCE, H5E_NOSPACE, NULL, "memory allocation failed") - HDmemset(&leaf->cache_info,0,sizeof(H5AC_info_t)); + /* Allocate memory for internal node information */ + if (NULL==(internal = H5FL_MALLOC(H5B2_internal_t))) + HGOTO_ERROR (H5E_RESOURCE, H5E_NOSPACE, FAIL, "memory allocation failed for B-tree internal info") + + /* Set metadata cache info */ + HDmemset(&internal->cache_info,0,sizeof(H5AC_info_t)); + internal->cache_info.is_dirty = TRUE; /* Share common B-tree information */ - leaf->shared = bt2->shared; - H5RC_INC(leaf->shared); + internal->shared = bt2->shared; + H5RC_INC(internal->shared); /* Get the pointer to the shared B-tree info */ - shared=H5RC_GET_OBJ(leaf->shared); + shared=H5RC_GET_OBJ(internal->shared); HDassert(shared); - /* 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, H5B2_LEAF_MAGIC, H5B2_SIZEOF_MAGIC)) - HGOTO_ERROR(H5E_BTREE, H5E_CANTLOAD, NULL, "wrong B-tree leaf node signature") - p += H5B2_SIZEOF_MAGIC; - - /* version */ - if (*p++ != H5B2_LEAF_VERSION) - HGOTO_ERROR(H5E_BTREE, H5E_CANTLOAD, NULL, "wrong B-tree header version") - - /* B-tree type */ - if (*p++ != (uint8_t)shared->type->id) - HGOTO_ERROR(H5E_BTREE, H5E_CANTLOAD, NULL, "incorrect B-tree type") - /* Allocate space for the native keys in memory */ - if((leaf->leaf_native=H5FL_FAC_MALLOC(shared->leaf_fac))==NULL) - HGOTO_ERROR (H5E_RESOURCE, H5E_NOSPACE, NULL, "memory allocation failed for B-tree leaf native keys") - -HDfprintf(stderr,"%s: Deserialize leaf node records here!, node_ptr->node_nrec=%u\n",FUNC,node_ptr->node_nrec); - - /* Set return value */ - ret_value = leaf; - -done: - if (!ret_value && leaf) - (void)H5B2_cache_leaf_dest(f,leaf); - FUNC_LEAVE_NOAPI(ret_value) -} /* H5B2_cache_leaf_load() */ /*lint !e818 Can't make udata a pointer to const */ - - -/*------------------------------------------------------------------------- - * Function: H5B2_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 - * Feb 2 2005 - * - *------------------------------------------------------------------------- - */ -static herr_t -H5B2_cache_leaf_flush(H5F_t *f, hid_t dxpl_id, hbool_t destroy, haddr_t addr, H5B2_leaf_t *leaf) -{ - herr_t ret_value = SUCCEED; /* Return value */ - - FUNC_ENTER_NOAPI(H5B2_cache_leaf_flush, FAIL) - - /* check arguments */ - HDassert(f); - HDassert(H5F_addr_defined(addr)); - HDassert(leaf); - - if (leaf->cache_info.is_dirty) { - H5B2_shared_t *shared; /* Shared B-tree information */ - uint8_t *p; /* Pointer into raw data buffer */ - uint8_t *native; /* Pointer to native keys */ - unsigned u; /* Local index variable */ - - /* Get the pointer to the shared B-tree info */ - shared=H5RC_GET_OBJ(leaf->shared); - HDassert(shared); - - p = shared->page; - - /* magic number */ - HDmemcpy(p, H5B2_HDR_MAGIC, H5B2_SIZEOF_MAGIC); - p += H5B2_SIZEOF_MAGIC; + if((internal->int_native=H5FL_FAC_MALLOC(shared->int_fac))==NULL) + HGOTO_ERROR (H5E_RESOURCE, H5E_NOSPACE, FAIL, "memory allocation failed for B-tree internal native keys") - /* version # */ - *p++ = H5B2_LEAF_VERSION; + /* Allocate space for the node pointers in memory */ + if((internal->node_ptrs=H5FL_FAC_MALLOC(shared->node_ptr_fac))==NULL) + HGOTO_ERROR (H5E_RESOURCE, H5E_NOSPACE, FAIL, "memory allocation failed for B-tree internal node pointers") - /* b-tree type */ - *p++ = shared->type->id; - - /* Serialize records for leaf node */ - native=leaf->leaf_native; - for(u=0; u<leaf->nrec; u++) { - /* Encode record */ - if((shared->type->encode)(f,p,native)<0) - HGOTO_ERROR(H5E_BTREE, H5E_CANTENCODE, FAIL, "enable to encode B-tree record"); - - /* Move to next record */ - p += shared->rkey_size; - native += shared->type->nkey_size; - } /* end for */ - - /* 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") + /* Set number of records */ + internal->nrec=0; - leaf->cache_info.is_dirty = FALSE; - } /* end if */ + /* Allocate space on disk for the internal node */ + 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 internal node") - if (destroy) - if (H5B2_cache_leaf_dest(f,leaf) < 0) - HGOTO_ERROR(H5E_BTREE, H5E_CANTFREE, FAIL, "unable to destroy B-tree leaf node") + /* Cache the new B-tree node */ + if (H5AC_set(f, dxpl_id, H5AC_BT2_INT, node_ptr->addr, internal, H5AC__NO_FLAGS_SET) < 0) + HGOTO_ERROR(H5E_BTREE, H5E_CANTINIT, FAIL, "can't add B-tree internal node to cache") done: - FUNC_LEAVE_NOAPI(ret_value) -} /* H5B2_cache_leaf_flush() */ - - -/*------------------------------------------------------------------------- - * Function: H5B_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 - * Feb 2 2005 - * - *------------------------------------------------------------------------- - */ -/* ARGSUSED */ -static herr_t -H5B2_cache_leaf_dest(H5F_t UNUSED *f, H5B2_leaf_t *leaf) -{ - H5B2_shared_t *shared; /* Shared B-tree information */ - - FUNC_ENTER_NOAPI_NOINIT_NOFUNC(H5B2_cache_leaf_dest) - - /* - * Check arguments. - */ - HDassert(leaf); - - /* Get the pointer to the shared B-tree info */ - shared=H5RC_GET_OBJ(leaf->shared); - HDassert(shared); - - /* Release leaf's native key buffer */ - if(leaf->leaf_native) - H5FL_FAC_FREE(shared->leaf_fac,leaf->leaf_native); - - /* Decrement reference count on shared B-tree info */ - if(leaf->shared) - H5RC_DEC(leaf->shared); - - /* Free B-tree leaf node info */ - H5FL_FREE(H5B2_leaf_t,leaf); - - FUNC_LEAVE_NOAPI(SUCCEED) -} /* end H5B2_cache_leaf_dest() */ - - -/*------------------------------------------------------------------------- - * Function: H5B2_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 - * Feb 2 2005 - * - *------------------------------------------------------------------------- - */ -static herr_t -H5B2_cache_leaf_clear(H5F_t *f, H5B2_leaf_t *leaf, hbool_t destroy) -{ - herr_t ret_value = SUCCEED; - - FUNC_ENTER_NOAPI_NOINIT(H5B2_cache_leaf_clear) - - /* - * Check arguments. - */ - HDassert(leaf); - - /* Reset the dirty flag. */ - leaf->cache_info.is_dirty = FALSE; - - if (destroy) - if (H5B2_cache_leaf_dest(f, leaf) < 0) - HGOTO_ERROR(H5E_BTREE, H5E_CANTFREE, FAIL, "unable to destroy B-tree leaf node") + if (ret_value<0) { + if (internal) + (void)H5B2_cache_internal_dest(f,internal); + } /* end if */ -done: FUNC_LEAVE_NOAPI(ret_value) -} /* end H5B2_cache_leaf_clear() */ - - -/*------------------------------------------------------------------------- - * Function: H5B2_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 - * Feb 2 2005 - * - *------------------------------------------------------------------------- - */ -static herr_t -H5B2_cache_leaf_size(const H5F_t UNUSED *f, const H5B2_leaf_t *leaf, size_t *size_ptr) -{ - H5B2_shared_t *shared; /* Shared B-tree information */ - - FUNC_ENTER_NOAPI_NOINIT_NOFUNC(H5B2_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) -} /* H5B2_cache_leaf_size() */ +} /* H5B2_create_internal() */ diff --git a/src/H5B2cache.c b/src/H5B2cache.c new file mode 100644 index 0000000..fa9538d --- /dev/null +++ b/src/H5B2cache.c @@ -0,0 +1,1003 @@ +/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * + * 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: H5B2.c + * Jan 31 2005 + * Quincey Koziol <koziol@ncsa.uiuc.edu> + * + * 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 H5B2_PACKAGE /*suppress error about including H5B2pkg */ + +/* Private headers */ +#include "H5private.h" /* Generic Functions */ +#include "H5B2pkg.h" /* B-trees */ +#include "H5Eprivate.h" /* Error handling */ + +/* Local macros */ + +/* B-tree format version #'s */ +#define H5B2_HDR_VERSION 0 /* Header */ +#define H5B2_INT_VERSION 0 /* Internal node */ +#define H5B2_LEAF_VERSION 0 /* Leaf node */ + + +/* Local typedefs */ + +/* Local prototypes */ + +/* Metadata cache callbacks */ +static H5B2_t *H5B2_cache_hdr_load(H5F_t *f, hid_t dxpl_id, haddr_t addr, const void *_type, void *udata); +static herr_t H5B2_cache_hdr_flush(H5F_t *f, hid_t dxpl_id, hbool_t destroy, haddr_t addr, H5B2_t *b); +static herr_t H5B2_cache_hdr_clear(H5F_t *f, H5B2_t *b, hbool_t destroy); +static herr_t H5B2_cache_hdr_size(const H5F_t *f, const H5B2_t *bt, size_t *size_ptr); +static H5B2_leaf_t *H5B2_cache_leaf_load(H5F_t *f, hid_t dxpl_id, haddr_t addr, const void *_type, void *udata); +static herr_t H5B2_cache_leaf_flush(H5F_t *f, hid_t dxpl_id, hbool_t destroy, haddr_t addr, H5B2_leaf_t *l); +static herr_t H5B2_cache_leaf_clear(H5F_t *f, H5B2_leaf_t *l, hbool_t destroy); +static herr_t H5B2_cache_leaf_size(const H5F_t *f, const H5B2_leaf_t *l, size_t *size_ptr); +static H5B2_internal_t *H5B2_cache_internal_load(H5F_t *f, hid_t dxpl_id, haddr_t addr, const void *_type, void *udata); +static herr_t H5B2_cache_internal_flush(H5F_t *f, hid_t dxpl_id, hbool_t destroy, haddr_t addr, H5B2_internal_t *i); +static herr_t H5B2_cache_internal_clear(H5F_t *f, H5B2_internal_t *i, hbool_t destroy); +static herr_t H5B2_cache_internal_size(const H5F_t *f, const H5B2_internal_t *i, size_t *size_ptr); + +/* Package variables */ + +/* H5B2 inherits cache-like properties from H5AC */ +const H5AC_class_t H5AC_BT2_HDR[1] = {{ + H5AC_BT2_HDR_ID, + (H5AC_load_func_t)H5B2_cache_hdr_load, + (H5AC_flush_func_t)H5B2_cache_hdr_flush, + (H5AC_dest_func_t)H5B2_cache_hdr_dest, + (H5AC_clear_func_t)H5B2_cache_hdr_clear, + (H5AC_size_func_t)H5B2_cache_hdr_size, +}}; + +/* H5B2 inherits cache-like properties from H5AC */ +const H5AC_class_t H5AC_BT2_LEAF[1] = {{ + H5AC_BT2_LEAF_ID, + (H5AC_load_func_t)H5B2_cache_leaf_load, + (H5AC_flush_func_t)H5B2_cache_leaf_flush, + (H5AC_dest_func_t)H5B2_cache_leaf_dest, + (H5AC_clear_func_t)H5B2_cache_leaf_clear, + (H5AC_size_func_t)H5B2_cache_leaf_size, +}}; + +/* H5B2 inherits cache-like properties from H5AC */ +const H5AC_class_t H5AC_BT2_INT[1] = {{ + H5AC_BT2_INT_ID, + (H5AC_load_func_t)H5B2_cache_internal_load, + (H5AC_flush_func_t)H5B2_cache_internal_flush, + (H5AC_dest_func_t)H5B2_cache_internal_dest, + (H5AC_clear_func_t)H5B2_cache_internal_clear, + (H5AC_size_func_t)H5B2_cache_internal_size, +}}; + +/* Static variables */ + +/* Declare a free list to manage B-tree header data to/from disk */ +H5FL_BLK_DEFINE_STATIC(header_block); + + + +/*------------------------------------------------------------------------- + * Function: H5B2_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 + * Feb 1 2005 + * + *------------------------------------------------------------------------- + */ +static H5B2_t * +H5B2_cache_hdr_load(H5F_t *f, hid_t dxpl_id, haddr_t addr, const void *_type, void UNUSED *udata) +{ + const H5B2_class_t *type = (const H5B2_class_t *) _type; + size_t node_size, rkey_size; /* Size info for B-tree */ + unsigned split_percent, merge_percent; /* Split & merge info for B-tree */ + H5B2_t *bt2 = NULL; + size_t size; + uint8_t *buf = NULL; + uint8_t *p; /* Pointer into raw data buffer */ + H5B2_t *ret_value; + + FUNC_ENTER_NOAPI(H5B2_cache_hdr_load, NULL) + + /* Check arguments */ + HDassert(f); + HDassert(H5F_addr_defined(addr)); + HDassert(type); + + if (NULL==(bt2 = H5FL_MALLOC(H5B2_t))) + HGOTO_ERROR (H5E_RESOURCE, H5E_NOSPACE, NULL, "memory allocation failed") + HDmemset(&bt2->cache_info,0,sizeof(H5AC_info_t)); + + /* Compute the size of the B-tree header on disk */ + size = H5B2_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, H5B2_HDR_MAGIC, H5B2_SIZEOF_MAGIC)) + HGOTO_ERROR(H5E_BTREE, H5E_CANTLOAD, NULL, "wrong B-tree header signature") + p += H5B2_SIZEOF_MAGIC; + + /* version */ + if (*p++ != H5B2_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); + + /* raw key size (in bytes) */ + UINT16DECODE(p, rkey_size); + + /* depth of tree */ + UINT16DECODE(p, bt2->depth); + + /* split & merge %s */ + UINT16DECODE(p, split_percent); + UINT16DECODE(p, merge_percent); + + /* root node pointer */ + H5F_addr_decode(f, (const uint8_t **)&p, &(bt2->root.addr)); + UINT16DECODE(p, bt2->root.node_nrec); + H5F_DECODE_LENGTH(f, p, bt2->root.all_nrec); + + /* Initialize shared B-tree info */ + if(H5B2_shared_init(f, bt2, type, node_size, rkey_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 = bt2; + +done: + if(buf) + H5FL_BLK_FREE(header_block,buf); + if (!ret_value && bt2) + (void)H5B2_cache_hdr_dest(f,bt2); + FUNC_LEAVE_NOAPI(ret_value) +} /*lint !e818 Can't make udata a pointer to const */ + + +/*------------------------------------------------------------------------- + * Function: H5B2_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 + * Feb 1 2005 + * + *------------------------------------------------------------------------- + */ +static herr_t +H5B2_cache_hdr_flush(H5F_t *f, hid_t dxpl_id, hbool_t destroy, haddr_t addr, H5B2_t *bt2) +{ + herr_t ret_value = SUCCEED; /* Return value */ + + FUNC_ENTER_NOAPI(H5B2_cache_hdr_flush, FAIL) + + /* check arguments */ + HDassert(f); + HDassert(H5F_addr_defined(addr)); + HDassert(bt2); + + if (bt2->cache_info.is_dirty) { + H5B2_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(bt2->shared); + HDassert(shared); + + /* Compute the size of the B-tree header on disk */ + size = H5B2_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, H5B2_HDR_MAGIC, H5B2_SIZEOF_MAGIC); + p += H5B2_SIZEOF_MAGIC; + + /* version # */ + *p++ = H5B2_HDR_VERSION; + + /* b-tree type */ + *p++ = shared->type->id; + + /* node size (in bytes) */ + UINT32ENCODE(p, shared->node_size); + + /* raw key size (in bytes) */ + UINT16ENCODE(p, shared->rkey_size); + + /* depth of tree */ + UINT16ENCODE(p, bt2->depth); + + /* split & merge %s */ + UINT16ENCODE(p, shared->split_percent); + UINT16ENCODE(p, shared->merge_percent); + + /* root node pointer */ + H5F_addr_encode(f, &p, bt2->root.addr); + UINT16ENCODE(p, bt2->root.node_nrec); + H5F_ENCODE_LENGTH(f, p, bt2->root.all_nrec); + + /* 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); + + bt2->cache_info.is_dirty = FALSE; + } /* end if */ + + if (destroy) + if (H5B2_cache_hdr_dest(f,bt2) < 0) + HGOTO_ERROR(H5E_BTREE, H5E_CANTFREE, FAIL, "unable to destroy B-tree header") + +done: + FUNC_LEAVE_NOAPI(ret_value) +} /* H5B2_cache_hdr_flush() */ + + +/*------------------------------------------------------------------------- + * Function: H5B_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 + * Feb 1 2005 + * + *------------------------------------------------------------------------- + */ +/* ARGSUSED */ +herr_t +H5B2_cache_hdr_dest(H5F_t UNUSED *f, H5B2_t *bt2) +{ + FUNC_ENTER_NOAPI_NOINIT_NOFUNC(H5B2_cache_hdr_dest) + + /* + * Check arguments. + */ + HDassert(bt2); + + /* Decrement reference count on shared B-tree info */ + if(bt2->shared) + H5RC_DEC(bt2->shared); + + /* Free B-tree header info */ + H5FL_FREE(H5B2_t,bt2); + + FUNC_LEAVE_NOAPI(SUCCEED) +} /* end H5B2_cache_hdr_dest() */ + + +/*------------------------------------------------------------------------- + * Function: H5B2_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 + * Feb 1 2005 + * + *------------------------------------------------------------------------- + */ +static herr_t +H5B2_cache_hdr_clear(H5F_t *f, H5B2_t *bt2, hbool_t destroy) +{ + herr_t ret_value = SUCCEED; + + FUNC_ENTER_NOAPI_NOINIT(H5B2_cache_hdr_clear) + + /* + * Check arguments. + */ + HDassert(bt2); + + /* Reset the dirty flag. */ + bt2->cache_info.is_dirty = FALSE; + + if (destroy) + if (H5B2_cache_hdr_dest(f, bt2) < 0) + HGOTO_ERROR(H5E_BTREE, H5E_CANTFREE, FAIL, "unable to destroy B-tree header") + +done: + FUNC_LEAVE_NOAPI(ret_value) +} /* end H5B2_cache_hdr_clear() */ + + +/*------------------------------------------------------------------------- + * Function: H5B2_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 + * Feb 1 2005 + * + *------------------------------------------------------------------------- + */ +static herr_t +H5B2_cache_hdr_size(const H5F_t *f, const H5B2_t UNUSED *bt2, size_t *size_ptr) +{ + FUNC_ENTER_NOAPI_NOINIT_NOFUNC(H5B2_cache_hdr_size) + + /* check arguments */ + HDassert(f); + HDassert(size_ptr); + + /* Set size value */ + *size_ptr = H5B2_HEADER_SIZE(f); + + FUNC_LEAVE_NOAPI(SUCCEED) +} /* H5B2_cache_hdr_size() */ + + +/*------------------------------------------------------------------------- + * Function: H5B2_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 + * Feb 2 2005 + * + *------------------------------------------------------------------------- + */ +static H5B2_leaf_t * +H5B2_cache_leaf_load(H5F_t *f, hid_t dxpl_id, haddr_t addr, const void *_bt2, void *_node_ptr) +{ + const H5B2_t *bt2 = (const H5B2_t *)_bt2; + H5B2_node_ptr_t *node_ptr = (H5B2_node_ptr_t *)_node_ptr; + H5B2_leaf_t *leaf = NULL; + H5B2_shared_t *shared; /* Shared B-tree information */ + uint8_t *p; /* Pointer into raw data buffer */ + uint8_t *native; /* Pointer to native keys */ + unsigned u; /* Local index variable */ + H5B2_leaf_t *ret_value; + + FUNC_ENTER_NOAPI(H5B2_cache_leaf_load, NULL) + + /* Check arguments */ + HDassert(f); + HDassert(H5F_addr_defined(addr)); + HDassert(bt2); + + if (NULL==(leaf = H5FL_MALLOC(H5B2_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 = bt2->shared; + H5RC_INC(leaf->shared); + + /* Get the pointer to the shared B-tree info */ + shared=H5RC_GET_OBJ(leaf->shared); + HDassert(shared); + + /* 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, H5B2_LEAF_MAGIC, H5B2_SIZEOF_MAGIC)) + HGOTO_ERROR(H5E_BTREE, H5E_CANTLOAD, NULL, "wrong B-tree leaf node signature") + p += H5B2_SIZEOF_MAGIC; + + /* version */ + if (*p++ != H5B2_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") + + /* Allocate space for the native keys in memory */ + if((leaf->leaf_native=H5FL_FAC_MALLOC(shared->leaf_fac))==NULL) + HGOTO_ERROR (H5E_RESOURCE, H5E_NOSPACE, NULL, "memory allocation failed for B-tree leaf native keys") + + /* Set the number of records in the leaf */ + leaf->nrec = node_ptr->node_nrec; + + /* Deserialize records for leaf node */ + native=leaf->leaf_native; + for(u=0; u<leaf->nrec; u++) { + /* Decode record */ + if((shared->type->decode)(f,p,native)<0) + HGOTO_ERROR(H5E_BTREE, H5E_CANTENCODE, NULL, "unable to decode B-tree record"); + + /* Move to next record */ + p += shared->rkey_size; + native += shared->type->nkey_size; + } /* end for */ + + /* Set return value */ + ret_value = leaf; + +done: + if (!ret_value && leaf) + (void)H5B2_cache_leaf_dest(f,leaf); + FUNC_LEAVE_NOAPI(ret_value) +} /* H5B2_cache_leaf_load() */ /*lint !e818 Can't make udata a pointer to const */ + + +/*------------------------------------------------------------------------- + * Function: H5B2_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 + * Feb 2 2005 + * + *------------------------------------------------------------------------- + */ +static herr_t +H5B2_cache_leaf_flush(H5F_t *f, hid_t dxpl_id, hbool_t destroy, haddr_t addr, H5B2_leaf_t *leaf) +{ + herr_t ret_value = SUCCEED; /* Return value */ + + FUNC_ENTER_NOAPI(H5B2_cache_leaf_flush, FAIL) + + /* check arguments */ + HDassert(f); + HDassert(H5F_addr_defined(addr)); + HDassert(leaf); + + if (leaf->cache_info.is_dirty) { + H5B2_shared_t *shared; /* Shared B-tree information */ + uint8_t *p; /* Pointer into raw data buffer */ + uint8_t *native; /* Pointer to native keys */ + unsigned u; /* Local index variable */ + + /* Get the pointer to the shared B-tree info */ + shared=H5RC_GET_OBJ(leaf->shared); + HDassert(shared); + + p = shared->page; + + /* magic number */ + HDmemcpy(p, H5B2_LEAF_MAGIC, H5B2_SIZEOF_MAGIC); + p += H5B2_SIZEOF_MAGIC; + + /* version # */ + *p++ = H5B2_LEAF_VERSION; + + /* b-tree type */ + *p++ = shared->type->id; + + /* Serialize records for leaf node */ + native=leaf->leaf_native; + for(u=0; u<leaf->nrec; 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->rkey_size; + native += shared->type->nkey_size; + } /* end for */ + + /* 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 (H5B2_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) +} /* H5B2_cache_leaf_flush() */ + + +/*------------------------------------------------------------------------- + * Function: H5B_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 + * Feb 2 2005 + * + *------------------------------------------------------------------------- + */ +/* ARGSUSED */ +herr_t +H5B2_cache_leaf_dest(H5F_t UNUSED *f, H5B2_leaf_t *leaf) +{ + H5B2_shared_t *shared; /* Shared B-tree information */ + + FUNC_ENTER_NOAPI_NOINIT_NOFUNC(H5B2_cache_leaf_dest) + + /* + * Check arguments. + */ + HDassert(leaf); + + /* Get the pointer to the shared B-tree info */ + shared=H5RC_GET_OBJ(leaf->shared); + HDassert(shared); + + /* Release leaf's native key buffer */ + if(leaf->leaf_native) + H5FL_FAC_FREE(shared->leaf_fac,leaf->leaf_native); + + /* Decrement reference count on shared B-tree info */ + if(leaf->shared) + H5RC_DEC(leaf->shared); + + /* Free B-tree leaf node info */ + H5FL_FREE(H5B2_leaf_t,leaf); + + FUNC_LEAVE_NOAPI(SUCCEED) +} /* end H5B2_cache_leaf_dest() */ + + +/*------------------------------------------------------------------------- + * Function: H5B2_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 + * Feb 2 2005 + * + *------------------------------------------------------------------------- + */ +static herr_t +H5B2_cache_leaf_clear(H5F_t *f, H5B2_leaf_t *leaf, hbool_t destroy) +{ + herr_t ret_value = SUCCEED; + + FUNC_ENTER_NOAPI_NOINIT(H5B2_cache_leaf_clear) + + /* + * Check arguments. + */ + HDassert(leaf); + + /* Reset the dirty flag. */ + leaf->cache_info.is_dirty = FALSE; + + if (destroy) + if (H5B2_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 H5B2_cache_leaf_clear() */ + + +/*------------------------------------------------------------------------- + * Function: H5B2_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 + * Feb 2 2005 + * + *------------------------------------------------------------------------- + */ +static herr_t +H5B2_cache_leaf_size(const H5F_t UNUSED *f, const H5B2_leaf_t *leaf, size_t *size_ptr) +{ + H5B2_shared_t *shared; /* Shared B-tree information */ + + FUNC_ENTER_NOAPI_NOINIT_NOFUNC(H5B2_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) +} /* H5B2_cache_leaf_size() */ + + +/*------------------------------------------------------------------------- + * Function: H5B2_cache_internal_load + * + * Purpose: Loads a B-tree internal node from the disk. + * + * Return: Success: Pointer to a new B-tree internal node. + * + * Failure: NULL + * + * Programmer: Quincey Koziol + * koziol@ncsa.uiuc.edu + * Feb 2 2005 + * + *------------------------------------------------------------------------- + */ +static H5B2_internal_t * +H5B2_cache_internal_load(H5F_t *f, hid_t dxpl_id, haddr_t addr, const void *_bt2, void *_node_ptr) +{ + const H5B2_t *bt2 = (const H5B2_t *)_bt2; + H5B2_node_ptr_t *node_ptr = (H5B2_node_ptr_t *)_node_ptr; + H5B2_internal_t *internal = NULL; + H5B2_shared_t *shared; /* Shared B-tree information */ + uint8_t *p; /* Pointer into raw data buffer */ + uint8_t *native; /* Pointer to native record info */ + H5B2_node_ptr_t *int_node_ptr; /* Pointer to node pointer info */ + unsigned u; /* Local index variable */ + H5B2_internal_t *ret_value; + + FUNC_ENTER_NOAPI(H5B2_cache_internal_load, NULL) + + /* Check arguments */ + HDassert(f); + HDassert(H5F_addr_defined(addr)); + HDassert(bt2); + + if (NULL==(internal = H5FL_MALLOC(H5B2_internal_t))) + HGOTO_ERROR (H5E_RESOURCE, H5E_NOSPACE, NULL, "memory allocation failed") + HDmemset(&internal->cache_info,0,sizeof(H5AC_info_t)); + + /* Share common B-tree information */ + internal->shared = bt2->shared; + H5RC_INC(internal->shared); + + /* Get the pointer to the shared B-tree info */ + shared=H5RC_GET_OBJ(internal->shared); + HDassert(shared); + + /* 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 internal node") + + p = shared->page; + + /* magic number */ + if (HDmemcmp(p, H5B2_INT_MAGIC, H5B2_SIZEOF_MAGIC)) + HGOTO_ERROR(H5E_BTREE, H5E_CANTLOAD, NULL, "wrong B-tree internal node signature") + p += H5B2_SIZEOF_MAGIC; + + /* version */ + if (*p++ != H5B2_INT_VERSION) + HGOTO_ERROR(H5E_BTREE, H5E_CANTLOAD, NULL, "wrong B-tree internal node version") + + /* B-tree type */ + if (*p++ != (uint8_t)shared->type->id) + HGOTO_ERROR(H5E_BTREE, H5E_CANTLOAD, NULL, "incorrect B-tree type") + + /* Allocate space for the native keys in memory */ + if((internal->int_native=H5FL_FAC_MALLOC(shared->int_fac))==NULL) + HGOTO_ERROR (H5E_RESOURCE, H5E_NOSPACE, NULL, "memory allocation failed for B-tree internal native keys") + + /* Allocate space for the node pointers in memory */ + if((internal->node_ptrs=H5FL_FAC_MALLOC(shared->node_ptr_fac))==NULL) + HGOTO_ERROR (H5E_RESOURCE, H5E_NOSPACE, NULL, "memory allocation failed for B-tree internal node pointers") + + /* Set the number of records in the leaf */ + internal->nrec = node_ptr->node_nrec; + + /* Deserialize records for internal node */ + native=internal->int_native; + for(u=0; u<internal->nrec; u++) { + /* Decode record */ + if((shared->type->decode)(f,p,native)<0) + HGOTO_ERROR(H5E_BTREE, H5E_CANTENCODE, NULL, "unable to decode B-tree record"); + + /* Move to next record */ + p += shared->rkey_size; + native += shared->type->nkey_size; + } /* end for */ + + /* Serialize node pointers for internal node */ + int_node_ptr=internal->node_ptrs; + for(u=0; u<internal->nrec+1; u++) { + /* Decode node pointer */ + H5F_addr_decode(f, (const uint8_t **)&p, &(int_node_ptr->addr)); + UINT16DECODE(p, int_node_ptr->node_nrec); + H5F_DECODE_LENGTH(f, p, int_node_ptr->all_nrec); + + /* Move to next node pointer */ + int_node_ptr++; + } /* end for */ + + /* Set return value */ + ret_value = internal; + +done: + if (!ret_value && internal) + (void)H5B2_cache_internal_dest(f,internal); + FUNC_LEAVE_NOAPI(ret_value) +} /* H5B2_cache_internal_load() */ /*lint !e818 Can't make udata a pointer to const */ + + +/*------------------------------------------------------------------------- + * Function: H5B2_cache_internal_flush + * + * Purpose: Flushes a dirty B-tree internal node to disk. + * + * Return: Non-negative on success/Negative on failure + * + * Programmer: Quincey Koziol + * koziol@ncsa.uiuc.edu + * Feb 3 2005 + * + *------------------------------------------------------------------------- + */ +static herr_t +H5B2_cache_internal_flush(H5F_t *f, hid_t dxpl_id, hbool_t destroy, haddr_t addr, H5B2_internal_t *internal) +{ + herr_t ret_value = SUCCEED; /* Return value */ + + FUNC_ENTER_NOAPI(H5B2_cache_internal_flush, FAIL) + + /* check arguments */ + HDassert(f); + HDassert(H5F_addr_defined(addr)); + HDassert(internal); + + if (internal->cache_info.is_dirty) { + H5B2_shared_t *shared; /* Shared B-tree information */ + uint8_t *p; /* Pointer into raw data buffer */ + uint8_t *native; /* Pointer to native record info */ + H5B2_node_ptr_t *int_node_ptr; /* Pointer to node pointer info */ + unsigned u; /* Local index variable */ + + /* Get the pointer to the shared B-tree info */ + shared=H5RC_GET_OBJ(internal->shared); + HDassert(shared); + + p = shared->page; + + /* magic number */ + HDmemcpy(p, H5B2_INT_MAGIC, H5B2_SIZEOF_MAGIC); + p += H5B2_SIZEOF_MAGIC; + + /* version # */ + *p++ = H5B2_INT_VERSION; + + /* b-tree type */ + *p++ = shared->type->id; + + /* Serialize records for internal node */ + native=internal->int_native; + for(u=0; u<internal->nrec; 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->rkey_size; + native += shared->type->nkey_size; + } /* end for */ + + /* Serialize node pointers for internal node */ + int_node_ptr=internal->node_ptrs; + for(u=0; u<internal->nrec+1; u++) { + /* Encode node pointer */ + H5F_addr_encode(f, &p, int_node_ptr->addr); + UINT16ENCODE(p, int_node_ptr->node_nrec); + H5F_ENCODE_LENGTH(f, p, int_node_ptr->all_nrec); + + /* Move to next node pointer */ + int_node_ptr++; + } /* end for */ + + /* Write the B-tree internal 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 internal node to disk") + + internal->cache_info.is_dirty = FALSE; + } /* end if */ + + if (destroy) + if (H5B2_cache_internal_dest(f,internal) < 0) + HGOTO_ERROR(H5E_BTREE, H5E_CANTFREE, FAIL, "unable to destroy B-tree internal node") + +done: + FUNC_LEAVE_NOAPI(ret_value) +} /* H5B2_cache_internal_flush() */ + + +/*------------------------------------------------------------------------- + * Function: H5B_cache_internal_dest + * + * Purpose: Destroys a B-tree internal node in memory. + * + * Return: Non-negative on success/Negative on failure + * + * Programmer: Quincey Koziol + * koziol@ncsa.uiuc.edu + * Feb 2 2005 + * + *------------------------------------------------------------------------- + */ +/* ARGSUSED */ +herr_t +H5B2_cache_internal_dest(H5F_t UNUSED *f, H5B2_internal_t *internal) +{ + H5B2_shared_t *shared; /* Shared B-tree information */ + + FUNC_ENTER_NOAPI_NOINIT_NOFUNC(H5B2_cache_internal_dest) + + /* + * Check arguments. + */ + HDassert(internal); + + /* Get the pointer to the shared B-tree info */ + shared=H5RC_GET_OBJ(internal->shared); + HDassert(shared); + + /* Release internal node's native key buffer */ + if(internal->int_native) + H5FL_FAC_FREE(shared->int_fac,internal->int_native); + + /* Release internal node's node pointer buffer */ + if(internal->node_ptrs) + H5FL_FAC_FREE(shared->node_ptr_fac,internal->node_ptrs); + + /* Decrement reference count on shared B-tree info */ + if(internal->shared) + H5RC_DEC(internal->shared); + + /* Free B-tree internal node info */ + H5FL_FREE(H5B2_internal_t,internal); + + FUNC_LEAVE_NOAPI(SUCCEED) +} /* end H5B2_cache_internal_dest() */ + + +/*------------------------------------------------------------------------- + * Function: H5B2_cache_internal_clear + * + * Purpose: Mark a B-tree internal node in memory as non-dirty. + * + * Return: Non-negative on success/Negative on failure + * + * Programmer: Quincey Koziol + * koziol@ncsa.uiuc.edu + * Feb 2 2005 + * + *------------------------------------------------------------------------- + */ +static herr_t +H5B2_cache_internal_clear(H5F_t *f, H5B2_internal_t *internal, hbool_t destroy) +{ + herr_t ret_value = SUCCEED; + + FUNC_ENTER_NOAPI_NOINIT(H5B2_cache_internal_clear) + + /* + * Check arguments. + */ + HDassert(internal); + + /* Reset the dirty flag. */ + internal->cache_info.is_dirty = FALSE; + + if (destroy) + if (H5B2_cache_internal_dest(f, internal) < 0) + HGOTO_ERROR(H5E_BTREE, H5E_CANTFREE, FAIL, "unable to destroy B-tree internal node") + +done: + FUNC_LEAVE_NOAPI(ret_value) +} /* end H5B2_cache_internal_clear() */ + + +/*------------------------------------------------------------------------- + * Function: H5B2_cache_internal_size + * + * Purpose: Compute the size in bytes of a B-tree internal 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 + * Feb 2 2005 + * + *------------------------------------------------------------------------- + */ +static herr_t +H5B2_cache_internal_size(const H5F_t UNUSED *f, const H5B2_internal_t *internal, size_t *size_ptr) +{ + H5B2_shared_t *shared; /* Shared B-tree information */ + + FUNC_ENTER_NOAPI_NOINIT_NOFUNC(H5B2_cache_internal_size) + + /* check arguments */ + HDassert(internal); + HDassert(size_ptr); + + /* Get the pointer to the shared B-tree info */ + shared=H5RC_GET_OBJ(internal->shared); + HDassert(shared); + + /* Set size value */ + *size_ptr = shared->node_size; + + FUNC_LEAVE_NOAPI(SUCCEED) +} /* H5B2_cache_internal_size() */ + + diff --git a/src/H5B2dbg.c b/src/H5B2dbg.c index 6e8af60..bd18582 100644 --- a/src/H5B2dbg.c +++ b/src/H5B2dbg.c @@ -31,9 +31,6 @@ #include "H5Eprivate.h" /* Error handling */ #include "H5FLprivate.h" /* Free Lists */ -/* H5B2 inherits cache-like properties from H5AC */ -extern const H5AC_class_t H5AC_BT2_HDR[1]; - /*------------------------------------------------------------------------- * Function: H5B2_hdr_debug diff --git a/src/H5B2pkg.h b/src/H5B2pkg.h index 1f98cac..001d0ca 100644 --- a/src/H5B2pkg.h +++ b/src/H5B2pkg.h @@ -44,8 +44,27 @@ /* B-tree signatures */ #define H5B2_HDR_MAGIC "BTHD" /* Header */ +#define H5B2_INT_MAGIC "BTND" /* Internal node */ #define H5B2_LEAF_MAGIC "BTLF" /* Leaf node */ +/* Size of storage for number of records per node (on disk) */ +#define H5B2_SIZEOF_RECORDS_PER_NODE 2 + +/* Size of a "node pointer" (on disk) */ +#define H5B2_NODE_POINTER_SIZE(f) (H5F_SIZEOF_ADDR(f)+H5B2_SIZEOF_RECORDS_PER_NODE+H5F_SIZEOF_SIZE(f)) + +/* Size of the B-tree header on disk */ +#define H5B2_HEADER_SIZE(f) ( \ + 4 + /* Signature */ \ + 1 + /* Version */ \ + 1 + /* Tree type */ \ + 4 + /* Node size, in bytes */ \ + 2 + /* Key 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%) */ \ + H5B2_NODE_POINTER_SIZE(f)) /* Node pointer to root node in tree */ + /****************************/ /* Package Private Typedefs */ /****************************/ @@ -67,9 +86,7 @@ typedef struct H5B2_shared_t { H5FL_fac_head_t *int_fac; /* Factory for internal node native key blocks */ H5FL_fac_head_t *leaf_fac; /* Factory for leaf node native key blocks */ H5FL_fac_head_t *node_ptr_fac; /* Factory for internal node node pointer blocks */ - size_t *int_nat_off; /* Array of offsets of native keys in internal node block */ - size_t *leaf_nat_off; /* Array of offsets of native keys in leaf node block */ - size_t *node_ptr_off; /* Array of offsets of node pointers in internal node block */ + size_t *nat_off; /* Array of offsets of native keys */ /* Information set by user */ unsigned split_percent; /* Percent full at which to split the node, when inserting */ @@ -97,7 +114,7 @@ typedef struct H5B2_t { H5RC_t *shared; /* Ref-counted shared info */ } H5B2_t; -/* B-tree leaf information */ +/* B-tree leaf node information */ typedef struct H5B2_leaf_t { /* Information for H5AC cache functions, _must_ be first field in structure */ H5AC_info_t cache_info; @@ -105,12 +122,54 @@ typedef struct H5B2_leaf_t { /* Internal B-tree information */ H5RC_t *shared; /* Ref-counted shared info */ uint8_t *leaf_native; /* Pointer to native keys */ - unsigned nrec; /* Number of records in leaf node */ + unsigned nrec; /* Number of records in node */ } H5B2_leaf_t; +/* B-tree internal node information */ +typedef struct H5B2_internal_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 keys */ + H5B2_node_ptr_t *node_ptrs; /* Pointer to node pointers */ + unsigned nrec; /* Number of records in node */ +} H5B2_internal_t; + + +/*****************************/ +/* Package Private Variables */ +/*****************************/ + +/* H5B2 header inherits cache-like properties from H5AC */ +H5_DLLVAR const H5AC_class_t H5AC_BT2_HDR[1]; + +/* H5B2 internal node inherits cache-like properties from H5AC */ +H5_DLLVAR const H5AC_class_t H5AC_BT2_INT[1]; + +/* H5B2 leaf node inherits cache-like properties from H5AC */ +H5_DLLVAR const H5AC_class_t H5AC_BT2_LEAF[1]; + +/* Declare a free list to manage the H5B2_t struct */ +H5FL_EXTERN(H5B2_t); + +/* Declare a free list to manage the H5B2_internal_t struct */ +H5FL_EXTERN(H5B2_internal_t); + +/* Declare a free list to manage the H5B2_leaf_t struct */ +H5FL_EXTERN(H5B2_leaf_t); + + /******************************/ /* Package Private Prototypes */ /******************************/ +H5_DLL herr_t H5B2_shared_free (void *_shared); +H5_DLL herr_t H5B2_shared_init (H5F_t *f, H5B2_t *bt2, const H5B2_class_t *type, + size_t node_size, size_t rkey_size, unsigned split_percent, unsigned merge_percent); +H5_DLL herr_t H5B2_cache_hdr_dest(H5F_t *f, H5B2_t *b); +H5_DLL herr_t H5B2_cache_leaf_dest(H5F_t *f, H5B2_leaf_t *l); +H5_DLL herr_t H5B2_cache_internal_dest(H5F_t *f, H5B2_internal_t *i); H5_DLL herr_t H5B2_hdr_debug(H5F_t *f, hid_t dxpl_id, haddr_t addr, FILE *stream, int indent, int fwidth, const H5B2_class_t *type); diff --git a/src/H5B2private.h b/src/H5B2private.h index 5d8d42a..bd1515a 100644 --- a/src/H5B2private.h +++ b/src/H5B2private.h @@ -72,8 +72,11 @@ typedef struct H5B2_class_t { /* Compare records, according to a key */ herr_t (*compare)(const H5F_t *f, hid_t dxpl_id, const void *rec1, const void *rec2); /* Compare two native records */ - /* Encode, decode, debug record values */ - herr_t (*encode)(const H5F_t *f, uint8_t *raw, const void *record); /* Store record in native key table */ + /* Encode & decode record values */ + herr_t (*encode)(const H5F_t *f, uint8_t *raw, const void *record); /* Encode record from native form to disk storage form */ + herr_t (*decode)(const H5F_t *f, const uint8_t *raw, void *record); /* Decode record from disk storage form to native form */ + + /* Debug record values */ } H5B2_class_t; diff --git a/src/H5FLprivate.h b/src/H5FLprivate.h index cc19d99..1ced06a 100644 --- a/src/H5FLprivate.h +++ b/src/H5FLprivate.h @@ -73,10 +73,10 @@ typedef struct H5FL_reg_head_t { #define H5FL_DEFINE_COMMON(t) H5FL_reg_head_t H5FL_REG_NAME(t)={0,0,0,0,#t,sizeof(t),NULL} /* Declare a free list to manage objects of type 't' */ -#define H5FL_DEFINE(t) H5_DLL H5FL_DEFINE_COMMON(t) +#define H5FL_DEFINE(t) H5FL_DEFINE_COMMON(t) /* Reference a free list for type 't' defined in another file */ -#define H5FL_EXTERN(t) extern H5_DLL H5FL_reg_head_t H5FL_REG_NAME(t) +#define H5FL_EXTERN(t) H5_DLLVAR H5FL_reg_head_t H5FL_REG_NAME(t) /* Declare a static free list to manage objects of type 't' */ #define H5FL_DEFINE_STATIC(t) static H5FL_DEFINE_COMMON(t) @@ -99,8 +99,8 @@ typedef struct H5FL_reg_head_t { /* Common macro for H5FL_DEFINE & H5FL_DEFINE_STATIC */ #define H5FL_DEFINE_COMMON(t) int H5FL_REG_NAME(t) -#define H5FL_DEFINE(t) H5_DLL H5FL_DEFINE_COMMON(t) -#define H5FL_EXTERN(t) extern H5_DLL int H5FL_REG_NAME(t) +#define H5FL_DEFINE(t) H5FL_DEFINE_COMMON(t) +#define H5FL_EXTERN(t) H5_DLLVAR int H5FL_REG_NAME(t) #define H5FL_DEFINE_STATIC(t) static H5FL_DEFINE_COMMON(t) #define H5FL_MALLOC(t) H5MM_malloc(sizeof(t)) #define H5FL_CALLOC(t) H5MM_calloc(sizeof(t)) @@ -142,10 +142,10 @@ typedef struct H5FL_blk_head_t { #define H5FL_BLK_DEFINE_COMMON(t) H5FL_blk_head_t H5FL_BLK_NAME(t)={0,0,0,0,#t"_blk",NULL} /* Declare a free list to manage objects of type 't' */ -#define H5FL_BLK_DEFINE(t) H5_DLL H5FL_BLK_DEFINE_COMMON(t) +#define H5FL_BLK_DEFINE(t) H5FL_BLK_DEFINE_COMMON(t) /* Reference a free list for type 't' defined in another file */ -#define H5FL_BLK_EXTERN(t) extern H5_DLL H5FL_blk_head_t H5FL_BLK_NAME(t) +#define H5FL_BLK_EXTERN(t) H5_DLLVAR H5FL_blk_head_t H5FL_BLK_NAME(t) /* Declare a static free list to manage objects of type 't' */ #define H5FL_BLK_DEFINE_STATIC(t) static H5FL_BLK_DEFINE_COMMON(t) @@ -169,8 +169,8 @@ typedef struct H5FL_blk_head_t { /* Common macro for H5FL_BLK_DEFINE & H5FL_BLK_DEFINE_STATIC */ #define H5FL_BLK_DEFINE_COMMON(t) int H5FL_BLK_NAME(t) -#define H5FL_BLK_DEFINE(t) H5_DLL H5FL_BLK_DEFINE_COMMON(t) -#define H5FL_BLK_EXTERN(t) extern H5_DLL int H5FL_BLK_NAME(t) +#define H5FL_BLK_DEFINE(t) H5FL_BLK_DEFINE_COMMON(t) +#define H5FL_BLK_EXTERN(t) H5_DLLVAR int H5FL_BLK_NAME(t) #define H5FL_BLK_DEFINE_STATIC(t) static H5FL_BLK_DEFINE_COMMON(t) #define H5FL_BLK_MALLOC(t,size) H5MM_malloc(size) #define H5FL_BLK_CALLOC(t,size) H5MM_calloc(size) @@ -214,10 +214,10 @@ typedef struct H5FL_arr_head_t { #define H5FL_ARR_DEFINE_COMMON(t,m) H5FL_arr_head_t H5FL_ARR_NAME(t)={0,0,0,#t"_arr",m+1,sizeof(t),NULL} /* Declare a free list to manage arrays of type 't' */ -#define H5FL_ARR_DEFINE(t,m) H5_DLL H5FL_ARR_DEFINE_COMMON(t,m) +#define H5FL_ARR_DEFINE(t,m) H5FL_ARR_DEFINE_COMMON(t,m) /* Reference a free list for arrays of type 't' defined in another file */ -#define H5FL_ARR_EXTERN(t) extern H5_DLL H5FL_arr_head_t H5FL_ARR_NAME(t) +#define H5FL_ARR_EXTERN(t) H5_DLLVAR H5FL_arr_head_t H5FL_ARR_NAME(t) /* Declare a static free list to manage arrays of type 't' */ #define H5FL_ARR_DEFINE_STATIC(t,m) static H5FL_ARR_DEFINE_COMMON(t,m) @@ -238,8 +238,8 @@ typedef struct H5FL_arr_head_t { /* Common macro for H5FL_ARR_DEFINE & H5FL_ARR_DEFINE_STATIC */ #define H5FL_ARR_DEFINE_COMMON(t,m) int H5FL_ARR_NAME(t) -#define H5FL_ARR_DEFINE(t,m) H5_DLL H5FL_ARR_DEFINE_COMMON(t,m) -#define H5FL_ARR_EXTERN(t) extern H5_DLL int H5FL_ARR_NAME(t) +#define H5FL_ARR_DEFINE(t,m) H5FL_ARR_DEFINE_COMMON(t,m) +#define H5FL_ARR_EXTERN(t) H5_DLLVAR int H5FL_ARR_NAME(t) #define H5FL_ARR_DEFINE_STATIC(t,m) static H5FL_ARR_DEFINE_COMMON(t,m) #define H5FL_ARR_MALLOC(t,elem) H5MM_malloc((elem)*sizeof(t)) #define H5FL_ARR_CALLOC(t,elem) H5MM_calloc((elem)*sizeof(t)) @@ -265,10 +265,10 @@ typedef struct H5FL_seq_head_t { #define H5FL_SEQ_DEFINE_COMMON(t) H5FL_seq_head_t H5FL_SEQ_NAME(t)={{0,0,0,0,#t"_seq",NULL},sizeof(t)} /* Declare a free list to manage sequences of type 't' */ -#define H5FL_SEQ_DEFINE(t) H5_DLL H5FL_SEQ_DEFINE_COMMON(t) +#define H5FL_SEQ_DEFINE(t) H5FL_SEQ_DEFINE_COMMON(t) /* Reference a free list for sequences of type 't' defined in another file */ -#define H5FL_SEQ_EXTERN(t) extern H5_DLL H5FL_seq_head_t H5FL_SEQ_NAME(t) +#define H5FL_SEQ_EXTERN(t) H5_DLLVAR H5FL_seq_head_t H5FL_SEQ_NAME(t) /* Declare a static free list to manage sequences of type 't' */ #define H5FL_SEQ_DEFINE_STATIC(t) static H5FL_SEQ_DEFINE_COMMON(t) @@ -289,8 +289,8 @@ typedef struct H5FL_seq_head_t { /* Common macro for H5FL_BLK_DEFINE & H5FL_BLK_DEFINE_STATIC */ #define H5FL_SEQ_DEFINE_COMMON(t) int H5FL_SEQ_NAME(t) -#define H5FL_SEQ_DEFINE(t) H5_DLL H5FL_SEQ_DEFINE_COMMON(t) -#define H5FL_SEQ_EXTERN(t) extern H5_DLL int H5FL_SEQ_NAME(t) +#define H5FL_SEQ_DEFINE(t) H5FL_SEQ_DEFINE_COMMON(t) +#define H5FL_SEQ_EXTERN(t) H5_DLLVAR int H5FL_SEQ_NAME(t) #define H5FL_SEQ_DEFINE_STATIC(t) static H5FL_SEQ_DEFINE_COMMON(t) #define H5FL_SEQ_MALLOC(t,elem) H5MM_malloc((elem)*sizeof(t)) #define H5FL_SEQ_CALLOC(t,elem) H5MM_calloc((elem)*sizeof(t)) diff --git a/src/Makefile.am b/src/Makefile.am index 112b9e9..d3a9fba 100755 --- a/src/Makefile.am +++ b/src/Makefile.am @@ -39,12 +39,13 @@ MOSTLYCLEANFILES=H5detect.o H5detect.lo H5detect H5Tinit.o H5Tinit.lo H5Tinit.c DISTCLEAN=libhdf5.settings # library sources -libhdf5_la_SOURCES= H5.c H5A.c H5AC.c H5B.c H5B2.c H5B2dbg.c H5C.c H5D.c \ +libhdf5_la_SOURCES= H5.c H5A.c H5AC.c H5B.c H5B2.c H5B2cache.c H5B2dbg.c H5C.c \ + H5D.c \ H5Dcontig.c \ H5Dcompact.c \ H5Defl.c H5Dio.c H5Distore.c H5Dmpio.c H5Dselect.c H5Dtest.c H5E.c H5F.c \ H5Fdbg.c H5FD.c H5FDcore.c \ - H5FDfamily.c H5FDfphdf5.c H5FDgass.c H5FDlog.c H5FDmpi.c H5FDmpio.c \ + H5FDfamily.c H5FDfphdf5.c H5FDgass.c H5FDlog.c H5FDmpi.c H5FDmpio.c \ H5FDmpiposix.c H5FDmulti.c H5FDsec2.c H5FDsrb.c H5FDstdio.c \ H5FDstream.c H5FL.c H5FO.c H5FP.c H5FPclient.c H5FPserver.c H5FS.c \ H5G.c H5Gent.c H5Gnode.c H5Gstab.c \ @@ -54,7 +55,7 @@ libhdf5_la_SOURCES= H5.c H5A.c H5AC.c H5B.c H5B2.c H5B2dbg.c H5C.c H5D.c \ H5Oname.c H5Onull.c H5Opline.c H5Osdspace.c H5Oshared.c H5Ostab.c \ H5P.c H5Pdcpl.c H5Pdxpl.c H5Pfapl.c H5Pfcpl.c H5Ptest.c H5R.c H5RC.c \ H5RS.c H5S.c H5Sall.c H5Shyper.c H5Smpio.c H5Snone.c H5Spoint.c \ - H5Sselect.c H5Stest.c H5SL.c H5ST.c H5T.c H5Tarray.c H5Tbit.c H5Tcommit.c \ + H5Sselect.c H5Stest.c H5SL.c H5ST.c H5T.c H5Tarray.c H5Tbit.c H5Tcommit.c \ H5Tcompound.c H5Tconv.c H5Tcset.c H5Tenum.c H5Tfields.c H5Tfixed.c \ H5Tfloat.c H5Tinit.c H5Tnative.c H5Toffset.c H5Topaque.c H5Torder.c \ H5Tpad.c H5Tprecis.c H5Tstrpad.c H5Tvlen.c H5TS.c H5V.c H5Z.c \ diff --git a/src/Makefile.in b/src/Makefile.in index 0d69855..3299112 100644 --- a/src/Makefile.in +++ b/src/Makefile.in @@ -219,12 +219,13 @@ MOSTLYCLEANFILES = H5detect.o H5detect.lo H5detect H5Tinit.o H5Tinit.lo H5Tinit. DISTCLEAN = libhdf5.settings # library sources -libhdf5_la_SOURCES = H5.c H5A.c H5AC.c H5B.c H5B2.c H5B2dbg.c H5C.c H5D.c \ +libhdf5_la_SOURCES = H5.c H5A.c H5AC.c H5B.c H5B2.c H5B2cache.c H5B2dbg.c H5C.c \ + H5D.c \ H5Dcontig.c \ H5Dcompact.c \ H5Defl.c H5Dio.c H5Distore.c H5Dmpio.c H5Dselect.c H5Dtest.c H5E.c H5F.c \ H5Fdbg.c H5FD.c H5FDcore.c \ - H5FDfamily.c H5FDfphdf5.c H5FDgass.c H5FDlog.c H5FDmpi.c H5FDmpio.c \ + H5FDfamily.c H5FDfphdf5.c H5FDgass.c H5FDlog.c H5FDmpi.c H5FDmpio.c \ H5FDmpiposix.c H5FDmulti.c H5FDsec2.c H5FDsrb.c H5FDstdio.c \ H5FDstream.c H5FL.c H5FO.c H5FP.c H5FPclient.c H5FPserver.c H5FS.c \ H5G.c H5Gent.c H5Gnode.c H5Gstab.c \ @@ -234,7 +235,7 @@ libhdf5_la_SOURCES = H5.c H5A.c H5AC.c H5B.c H5B2.c H5B2dbg.c H5C.c H5D.c \ H5Oname.c H5Onull.c H5Opline.c H5Osdspace.c H5Oshared.c H5Ostab.c \ H5P.c H5Pdcpl.c H5Pdxpl.c H5Pfapl.c H5Pfcpl.c H5Ptest.c H5R.c H5RC.c \ H5RS.c H5S.c H5Sall.c H5Shyper.c H5Smpio.c H5Snone.c H5Spoint.c \ - H5Sselect.c H5Stest.c H5SL.c H5ST.c H5T.c H5Tarray.c H5Tbit.c H5Tcommit.c \ + H5Sselect.c H5Stest.c H5SL.c H5ST.c H5T.c H5Tarray.c H5Tbit.c H5Tcommit.c \ H5Tcompound.c H5Tconv.c H5Tcset.c H5Tenum.c H5Tfields.c H5Tfixed.c \ H5Tfloat.c H5Tinit.c H5Tnative.c H5Toffset.c H5Topaque.c H5Torder.c \ H5Tpad.c H5Tprecis.c H5Tstrpad.c H5Tvlen.c H5TS.c H5V.c H5Z.c \ @@ -288,27 +289,27 @@ LTLIBRARIES = $(lib_LTLIBRARIES) libhdf5_la_LDFLAGS = libhdf5_la_LIBADD = -am_libhdf5_la_OBJECTS = H5.lo H5A.lo H5AC.lo H5B.lo H5B2.lo H5B2dbg.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 H5FD.lo H5FDcore.lo H5FDfamily.lo H5FDfphdf5.lo \ - H5FDgass.lo H5FDlog.lo H5FDmpi.lo H5FDmpio.lo H5FDmpiposix.lo \ - H5FDmulti.lo H5FDsec2.lo H5FDsrb.lo H5FDstdio.lo H5FDstream.lo \ - H5FL.lo H5FO.lo H5FP.lo H5FPclient.lo H5FPserver.lo H5FS.lo \ - H5G.lo H5Gent.lo H5Gnode.lo H5Gstab.lo H5HG.lo H5HGdbg.lo \ - H5HL.lo H5HLdbg.lo H5HP.lo H5I.lo H5MF.lo H5MM.lo H5O.lo \ - H5Oattr.lo H5Obogus.lo H5Ocont.lo H5Odtype.lo H5Oefl.lo \ - H5Ofill.lo H5Olayout.lo H5Omtime.lo H5Oname.lo H5Onull.lo \ - H5Opline.lo H5Osdspace.lo H5Oshared.lo H5Ostab.lo H5P.lo \ - H5Pdcpl.lo H5Pdxpl.lo H5Pfapl.lo H5Pfcpl.lo H5Ptest.lo H5R.lo \ - H5RC.lo H5RS.lo H5S.lo H5Sall.lo H5Shyper.lo H5Smpio.lo \ - H5Snone.lo H5Spoint.lo H5Sselect.lo H5Stest.lo H5SL.lo H5ST.lo \ - H5T.lo H5Tarray.lo H5Tbit.lo H5Tcommit.lo H5Tcompound.lo \ - H5Tconv.lo H5Tcset.lo H5Tenum.lo H5Tfields.lo H5Tfixed.lo \ - H5Tfloat.lo H5Tinit.lo H5Tnative.lo H5Toffset.lo H5Topaque.lo \ - H5Torder.lo H5Tpad.lo H5Tprecis.lo H5Tstrpad.lo H5Tvlen.lo \ - H5TS.lo H5V.lo H5Z.lo H5Zdeflate.lo H5Zfletcher32.lo H5Znbit.lo \ - H5Zshuffle.lo H5Zszip.lo H5Ztrans.lo +am_libhdf5_la_OBJECTS = H5.lo H5A.lo H5AC.lo H5B.lo H5B2.lo H5B2cache.lo \ + H5B2dbg.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 H5FD.lo H5FDcore.lo H5FDfamily.lo \ + H5FDfphdf5.lo H5FDgass.lo H5FDlog.lo H5FDmpi.lo H5FDmpio.lo \ + H5FDmpiposix.lo H5FDmulti.lo H5FDsec2.lo H5FDsrb.lo \ + H5FDstdio.lo H5FDstream.lo H5FL.lo H5FO.lo H5FP.lo \ + H5FPclient.lo H5FPserver.lo H5FS.lo H5G.lo H5Gent.lo H5Gnode.lo \ + H5Gstab.lo H5HG.lo H5HGdbg.lo H5HL.lo H5HLdbg.lo H5HP.lo H5I.lo \ + H5MF.lo H5MM.lo H5O.lo H5Oattr.lo H5Obogus.lo H5Ocont.lo \ + H5Odtype.lo H5Oefl.lo H5Ofill.lo H5Olayout.lo H5Omtime.lo \ + H5Oname.lo H5Onull.lo H5Opline.lo H5Osdspace.lo H5Oshared.lo \ + H5Ostab.lo H5P.lo H5Pdcpl.lo H5Pdxpl.lo H5Pfapl.lo H5Pfcpl.lo \ + H5Ptest.lo H5R.lo H5RC.lo H5RS.lo H5S.lo H5Sall.lo H5Shyper.lo \ + H5Smpio.lo H5Snone.lo H5Spoint.lo H5Sselect.lo H5Stest.lo \ + H5SL.lo H5ST.lo H5T.lo H5Tarray.lo H5Tbit.lo H5Tcommit.lo \ + H5Tcompound.lo H5Tconv.lo H5Tcset.lo H5Tenum.lo H5Tfields.lo \ + H5Tfixed.lo H5Tfloat.lo H5Tinit.lo H5Tnative.lo H5Toffset.lo \ + H5Topaque.lo H5Torder.lo H5Tpad.lo H5Tprecis.lo H5Tstrpad.lo \ + H5Tvlen.lo H5TS.lo H5V.lo H5Z.lo H5Zdeflate.lo H5Zfletcher32.lo \ + H5Znbit.lo H5Zshuffle.lo H5Zszip.lo H5Ztrans.lo libhdf5_la_OBJECTS = $(am_libhdf5_la_OBJECTS) noinst_PROGRAMS = H5detect$(EXEEXT) PROGRAMS = $(noinst_PROGRAMS) @@ -327,9 +328,9 @@ depcomp = $(SHELL) $(top_srcdir)/bin/depcomp am__depfiles_maybe = depfiles @AMDEP_TRUE@DEP_FILES = ./$(DEPDIR)/H5.Plo ./$(DEPDIR)/H5A.Plo \ @AMDEP_TRUE@ ./$(DEPDIR)/H5AC.Plo ./$(DEPDIR)/H5B.Plo \ -@AMDEP_TRUE@ ./$(DEPDIR)/H5B2.Plo ./$(DEPDIR)/H5B2dbg.Plo \ -@AMDEP_TRUE@ ./$(DEPDIR)/H5C.Plo ./$(DEPDIR)/H5D.Plo \ -@AMDEP_TRUE@ ./$(DEPDIR)/H5Dcompact.Plo \ +@AMDEP_TRUE@ ./$(DEPDIR)/H5B2.Plo ./$(DEPDIR)/H5B2cache.Plo \ +@AMDEP_TRUE@ ./$(DEPDIR)/H5B2dbg.Plo ./$(DEPDIR)/H5C.Plo \ +@AMDEP_TRUE@ ./$(DEPDIR)/H5D.Plo ./$(DEPDIR)/H5Dcompact.Plo \ @AMDEP_TRUE@ ./$(DEPDIR)/H5Dcontig.Plo ./$(DEPDIR)/H5Defl.Plo \ @AMDEP_TRUE@ ./$(DEPDIR)/H5Dio.Plo ./$(DEPDIR)/H5Distore.Plo \ @AMDEP_TRUE@ ./$(DEPDIR)/H5Dmpio.Plo ./$(DEPDIR)/H5Dselect.Plo \ @@ -484,6 +485,7 @@ distclean-compile: @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/H5AC.Plo@am__quote@ @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/H5B.Plo@am__quote@ @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/H5B2.Plo@am__quote@ +@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)/H5C.Plo@am__quote@ @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/H5D.Plo@am__quote@ diff --git a/test/btree2.c b/test/btree2.c index 182c4fa..312f149 100644 --- a/test/btree2.c +++ b/test/btree2.c @@ -31,6 +31,8 @@ const char *FILENAME[] = { NULL }; +#define INSERT_SPLIT_ROOT_NREC 80 + /*------------------------------------------------------------------------- * Function: store @@ -115,7 +117,44 @@ HDfprintf(stderr,"encode: data=%Hu\n",*(const hsize_t *)nrecord); /*------------------------------------------------------------------------- - * Function: test_basic + * Function: decode + * + * Purpose: Decode raw disk form of record into native form + * + * Return: Success: non-negative + * + * Failure: negative + * + * Programmer: Quincey Koziol + * Friday, February 4, 2005 + * + * Modifications: + * + *------------------------------------------------------------------------- + */ +static herr_t +decode(const H5F_t *f, const uint8_t *raw, void *nrecord) +{ + H5F_DECODE_LENGTH(f, raw, *(hsize_t *)nrecord); + +#ifdef QAK +HDfprintf(stderr,"encode: data=%Hu\n",*(const hsize_t *)nrecord); +#endif /* QAK */ + return(SUCCEED); +} + +H5B2_class_t type={ /* B-tree class information */ + 0, /* Type of B-tree */ + sizeof(hsize_t), /* Size of native key */ + store, /* Record storage callback */ + compare, /* Record comparison callback */ + encode, /* Record encoding callback */ + decode /* Record decoding callback */ +}; + + +/*------------------------------------------------------------------------- + * Function: test_insert_basic * * Purpose: Basic tests for the B-tree v2 code * @@ -131,18 +170,11 @@ HDfprintf(stderr,"encode: data=%Hu\n",*(const hsize_t *)nrecord); *------------------------------------------------------------------------- */ static int -test_basic_insert(hid_t fapl) +test_insert_basic(hid_t fapl) { hid_t file=-1; char filename[1024]; H5F_t *f=NULL; - H5B2_class_t type={ /* B-tree class information */ - 0, /* Type of B-tree */ - sizeof(hsize_t), /* Size of native key */ - store, /* Record storage callback */ - compare, /* Record comparison callback */ - encode /* Record encoding callback */ - }; hsize_t record; /* Record to insert into tree */ haddr_t bt2_addr; /* Address of B-tree created */ @@ -164,7 +196,7 @@ test_basic_insert(hid_t fapl) if (H5B2_create(f, H5P_DATASET_XFER_DEFAULT, &type, 512, 8, 100, 40, &bt2_addr/*out*/)<0) { H5_FAILED(); H5Eprint_stack(H5E_DEFAULT, stdout); - TEST_ERROR; + goto error; } PASSED(); @@ -176,7 +208,7 @@ test_basic_insert(hid_t fapl) if (H5B2_insert(f, H5P_DATASET_XFER_DEFAULT, &type, bt2_addr, &record)<0) { H5_FAILED(); H5Eprint_stack(H5E_DEFAULT, stdout); - TEST_ERROR; + goto error; } /* @@ -186,7 +218,7 @@ test_basic_insert(hid_t fapl) if (H5B2_insert(f, H5P_DATASET_XFER_DEFAULT, &type, bt2_addr, &record)<0) { H5_FAILED(); H5Eprint_stack(H5E_DEFAULT, stdout); - TEST_ERROR; + goto error; } /* @@ -196,7 +228,7 @@ test_basic_insert(hid_t fapl) if (H5B2_insert(f, H5P_DATASET_XFER_DEFAULT, &type, bt2_addr, &record)<0) { H5_FAILED(); H5Eprint_stack(H5E_DEFAULT, stdout); - TEST_ERROR; + goto error; } /* @@ -206,7 +238,7 @@ test_basic_insert(hid_t fapl) if (H5B2_insert(f, H5P_DATASET_XFER_DEFAULT, &type, bt2_addr, &record)<0) { H5_FAILED(); H5Eprint_stack(H5E_DEFAULT, stdout); - TEST_ERROR; + goto error; } PASSED(); @@ -219,7 +251,96 @@ error: H5Fclose(file); } H5E_END_TRY; return 1; -} +} /* test_insert_basic() */ + + +/*------------------------------------------------------------------------- + * Function: test_insert_split_root + * + * Purpose: Basic tests for the B-tree v2 code. This test inserts enough + * records to split the root node and force the tree to depth 1. + * It also continues to add a few more records to each of the + * left and right leaf nodes after the split + * + * Return: Success: 0 + * + * Failure: 1 + * + * Programmer: Quincey Koziol + * Thursday, February 3, 2005 + * + * Modifications: + * + *------------------------------------------------------------------------- + */ +static int +test_insert_split_root(hid_t fapl) +{ + hid_t file=-1; + char filename[1024]; + H5F_t *f=NULL; + hsize_t record; /* Record to insert into tree */ + haddr_t bt2_addr; /* Address of B-tree created */ + unsigned u; /* Local index variable */ + + 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) TEST_ERROR; + + /* Get a pointer to the internal file object */ + if (NULL==(f=H5I_object(file))) { + H5Eprint_stack(H5E_DEFAULT, stdout); + goto error; + } + + /* + * Test v2 B-tree creation + */ + if (H5B2_create(f, H5P_DATASET_XFER_DEFAULT, &type, 512, 8, 100, 40, &bt2_addr/*out*/)<0) { + H5_FAILED(); + H5Eprint_stack(H5E_DEFAULT, stdout); + goto error; + } + + /* + * Test inserting many records into v2 B-tree + */ + TESTING("B-tree many - split root"); + + for(u=0; u<INSERT_SPLIT_ROOT_NREC; u++) { + record=u+10; + if (H5B2_insert(f, H5P_DATASET_XFER_DEFAULT, &type, bt2_addr, &record)<0) { + H5_FAILED(); + H5Eprint_stack(H5E_DEFAULT, stdout); + goto error; + } + } + record=0; + if (H5B2_insert(f, H5P_DATASET_XFER_DEFAULT, &type, bt2_addr, &record)<0) { + H5_FAILED(); + H5Eprint_stack(H5E_DEFAULT, stdout); + goto error; + } + record=1; + if (H5B2_insert(f, H5P_DATASET_XFER_DEFAULT, &type, bt2_addr, &record)<0) { + H5_FAILED(); + H5Eprint_stack(H5E_DEFAULT, stdout); + goto error; + } + + PASSED(); + + if (H5Fclose(file)<0) TEST_ERROR; + + return 0; + +error: + H5E_BEGIN_TRY { + H5Fclose(file); + } H5E_END_TRY; + return 1; +} /* test_insert_split_root() */ /*------------------------------------------------------------------------- @@ -249,8 +370,8 @@ main(void) fapl = h5_fileaccess(); /* Test basic B-tree insertion */ - nerrors += test_basic_insert(fapl); -/* nerrors += test_many_insert(fapl); */ + nerrors += test_insert_basic(fapl); + nerrors += test_insert_split_root(fapl); if (nerrors) goto error; puts("All v2 B-tree tests passed."); |