diff options
Diffstat (limited to 'src/H5B.c')
| -rw-r--r-- | src/H5B.c | 332 |
1 files changed, 61 insertions, 271 deletions
@@ -98,31 +98,28 @@ /****************/ #define H5B_PACKAGE /*suppress error about including H5Bpkg */ -#define H5F_PACKAGE /*suppress error about including H5Fpkg */ /***********/ /* Headers */ /***********/ #include "H5private.h" /* Generic Functions */ -#include "H5ACprivate.h" /* Metadata cache */ #include "H5Bpkg.h" /* B-link trees */ #include "H5Dprivate.h" /* Datasets */ #include "H5Eprivate.h" /* Error handling */ -#include "H5Fpkg.h" /* File access */ #include "H5Iprivate.h" /* IDs */ #include "H5MFprivate.h" /* File memory management */ -#include "H5MMprivate.h" /* Memory management */ #include "H5Pprivate.h" /* Property lists */ + /****************/ /* Local Macros */ /****************/ #define H5B_SIZEOF_HDR(F) \ - (H5B_SIZEOF_MAGIC + /*magic number */ \ + (H5_SIZEOF_MAGIC + /*magic number */ \ 4 + /*type, level, num entries */ \ 2*H5F_SIZEOF_ADDR(F)) /*left and right sibling addresses */ -#define H5B_NKEY(b,shared,idx) ((b)->native+(shared)->nkey[(idx)]) + /******************/ /* Local Typedefs */ @@ -153,10 +150,7 @@ static herr_t H5B_split(H5F_t *f, hid_t dxpl_id, H5B_t *old_bt, unsigned *old_bt_flags, haddr_t old_addr, unsigned idx, void *udata, haddr_t *new_addr/*out*/); static H5B_t * H5B_copy(const H5B_t *old_bt); -#ifdef H5B_DEBUG -static herr_t H5B_assert(H5F_t *f, hid_t dxpl_id, haddr_t addr, const H5B_class_t *type, - void *udata); -#endif + /*********************/ /* Package Variables */ @@ -171,10 +165,12 @@ H5FL_BLK_DEFINE(native_block); /* Declare a free list to manage the H5B_t struct */ H5FL_DEFINE(H5B_t); + /*****************************/ /* Library Private Variables */ /*****************************/ + /*******************/ /* Local Variables */ /*******************/ @@ -281,9 +277,9 @@ done: * pointers since it assumes that all nodes can be reached * from the parent node. * - * Return: Non-negative on success (if found, values returned through the - * UDATA argument). Negative on failure (if not found, UDATA is - * undefined). + * Return: Non-negative (TRUE/FALSE) on success (if found, values returned + * through the UDATA argument). Negative on failure (if not found, + * UDATA is undefined). * * Programmer: Robb Matzke * matzke@llnl.gov @@ -291,14 +287,14 @@ done: * *------------------------------------------------------------------------- */ -herr_t +htri_t H5B_find(H5F_t *f, hid_t dxpl_id, const H5B_class_t *type, haddr_t addr, void *udata) { H5B_t *bt = NULL; H5B_shared_t *shared; /* Pointer to shared B-tree info */ - unsigned idx=0, lt = 0, rt; /* Final, left & right key indices */ + unsigned idx = 0, lt = 0, rt; /* Final, left & right key indices */ int cmp = 1; /* Key comparison value */ - int ret_value = SUCCEED; /* Return value */ + htri_t ret_value; /* Return value */ FUNC_ENTER_NOAPI(H5B_find, FAIL) @@ -318,28 +314,21 @@ H5B_find(H5F_t *f, hid_t dxpl_id, const H5B_class_t *type, haddr_t addr, void *u */ if(NULL == (bt = (H5B_t *)H5AC_protect(f, dxpl_id, H5AC_BT, addr, type, udata, H5AC_READ))) HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to load B-tree node") - shared=(H5B_shared_t *)H5RC_GET_OBJ(bt->rc_shared); + shared = (H5B_shared_t *)H5RC_GET_OBJ(bt->rc_shared); HDassert(shared); - rt = bt->nchildren; + rt = bt->nchildren; while(lt < rt && cmp) { idx = (lt + rt) / 2; /* compare */ - if((cmp = (type->cmp3)(f, dxpl_id, H5B_NKEY(bt, shared, idx), udata, H5B_NKEY(bt, shared, idx + 1))) < 0) + if((cmp = (type->cmp3)(f, dxpl_id, H5B_NKEY(bt, shared, idx), udata, H5B_NKEY(bt, shared, (idx + 1)))) < 0) rt = idx; else lt = idx + 1; } /* end while */ + /* Check if not found */ if(cmp) - /* Note: don't push error on stack, leave that to next higher level, - * since many times the B-tree is searched in order to determine - * if an object exists in the B-tree or not. -QAK - */ -#ifdef OLD_WAY - HGOTO_ERROR(H5E_BTREE, H5E_NOTFOUND, FAIL, "B-tree key not found") -#else /* OLD_WAY */ - HGOTO_DONE(FAIL) -#endif /* OLD_WAY */ + HGOTO_DONE(FALSE) /* * Follow the link to the subtree or to the data node. @@ -347,28 +336,13 @@ H5B_find(H5F_t *f, hid_t dxpl_id, const H5B_class_t *type, haddr_t addr, void *u HDassert(idx < bt->nchildren); if(bt->level > 0) { - if(H5B_find(f, dxpl_id, type, bt->child[idx], udata) < 0) - /* Note: don't push error on stack, leave that to next higher level, - * since many times the B-tree is searched in order to determine - * if an object exists in the B-tree or not. -QAK - */ -#ifdef OLD_WAY - HGOTO_ERROR(H5E_BTREE, H5E_NOTFOUND, FAIL, "key not found in subtree") -#else /* OLD_WAY */ - HGOTO_DONE(FAIL) -#endif /* OLD_WAY */ - } else { - if((type->found)(f, dxpl_id, bt->child[idx], H5B_NKEY(bt, shared, idx), udata) < 0) - /* Note: don't push error on stack, leave that to next higher level, - * since many times the B-tree is searched in order to determine - * if an object exists in the B-tree or not. -QAK - */ -#ifdef OLD_WAY - HGOTO_ERROR(H5E_BTREE, H5E_NOTFOUND, FAIL, "key not found in leaf node") -#else /* OLD_WAY */ - HGOTO_DONE(FAIL) -#endif /* OLD_WAY */ - } + if((ret_value = H5B_find(f, dxpl_id, type, bt->child[idx], udata)) < 0) + HGOTO_ERROR(H5E_BTREE, H5E_NOTFOUND, FAIL, "can't lookup key in subtree") + } /* end if */ + else { + if((ret_value = (type->found)(f, dxpl_id, bt->child[idx], H5B_NKEY(bt, shared, idx), udata)) < 0) + HGOTO_ERROR(H5E_BTREE, H5E_NOTFOUND, FAIL, "can't lookup key in leaf node") + } /* end else */ done: if(bt && H5AC_unprotect(f, dxpl_id, H5AC_BT, addr, bt, H5AC__NO_FLAGS_SET) < 0) @@ -1218,7 +1192,7 @@ H5B_iterate(H5F_t *f, hid_t dxpl_id, const H5B_class_t *type, haddr_t addr, { herr_t ret_value; /* Return value */ - FUNC_ENTER_NOAPI(H5B_iterate, FAIL) + FUNC_ENTER_NOAPI_NOERR(H5B_iterate, -) /* * Check arguments. @@ -1423,8 +1397,7 @@ H5B_remove_helper(H5F_t *f, hid_t dxpl_id, haddr_t addr, const H5B_class_t *type bt->left = HADDR_UNDEF; bt->right = HADDR_UNDEF; H5_CHECK_OVERFLOW(shared->sizeof_rnode, size_t, hsize_t); - if(H5MF_xfree(f, H5FD_MEM_BTREE, dxpl_id, addr, (hsize_t)shared->sizeof_rnode) < 0 - || H5AC_unprotect(f, dxpl_id, H5AC_BT, addr, bt, bt_flags | H5C__DELETED_FLAG) < 0) { + if(H5AC_unprotect(f, dxpl_id, H5AC_BT, addr, bt, bt_flags | H5AC__DELETED_FLAG | H5AC__FREE_FILE_SPACE_FLAG) < 0) { bt = NULL; bt_flags = H5AC__NO_FLAGS_SET; HGOTO_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, H5B_INS_ERROR, "unable to free B-tree node") @@ -1635,12 +1608,8 @@ H5B_delete(H5F_t *f, hid_t dxpl_id, const H5B_class_t *type, haddr_t addr, void } /* end if */ } /* end else */ - /* Delete this node from disk */ - if(H5MF_xfree(f, H5FD_MEM_BTREE, dxpl_id, addr, (hsize_t)shared->sizeof_rnode) < 0) - HGOTO_ERROR(H5E_BTREE, H5E_CANTFREE, FAIL, "unable to free B-tree node") - done: - if(bt && H5AC_unprotect(f, dxpl_id, H5AC_BT, addr, bt, H5C__DELETED_FLAG) < 0) + if(bt && H5AC_unprotect(f, dxpl_id, H5AC_BT, addr, bt, H5AC__DELETED_FLAG | H5AC__FREE_FILE_SPACE_FLAG) < 0) HDONE_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release B-tree node in cache") FUNC_LEAVE_NOAPI(ret_value) @@ -1664,7 +1633,7 @@ done: H5B_shared_t * H5B_shared_new(const H5F_t *f, const H5B_class_t *type, size_t sizeof_rkey) { - H5B_shared_t *shared; /* New shared B-tree struct */ + H5B_shared_t *shared = NULL; /* New shared B-tree struct */ size_t u; /* Local index variable */ H5B_shared_t *ret_value; /* Return value */ @@ -1676,7 +1645,7 @@ H5B_shared_new(const H5F_t *f, const H5B_class_t *type, size_t sizeof_rkey) HDassert(type); /* Allocate space for the shared structure */ - if(NULL == (shared = H5FL_MALLOC(H5B_shared_t))) + if(NULL == (shared = H5FL_CALLOC(H5B_shared_t))) HGOTO_ERROR(H5E_BTREE, H5E_CANTALLOC, NULL, "memory allocation failed for shared B-tree info") /* Set up the "global" information for this file's groups */ @@ -1696,17 +1665,26 @@ H5B_shared_new(const H5F_t *f, const H5B_class_t *type, size_t sizeof_rkey) #ifdef H5_CLEAR_MEMORY HDmemset(shared->page, 0, shared->sizeof_rnode); #endif /* H5_CLEAR_MEMORY */ - if(NULL == (shared->nkey = H5FL_SEQ_MALLOC(size_t, (size_t)(2 * H5F_KVALUE(f, type) + 1)))) - HGOTO_ERROR(H5E_BTREE, H5E_CANTALLOC, NULL, "memory allocation failed for B-tree page") + if(NULL == (shared->nkey = H5FL_SEQ_MALLOC(size_t, (size_t)(shared->two_k + 1)))) + HGOTO_ERROR(H5E_BTREE, H5E_CANTALLOC, NULL, "memory allocation failed for B-tree native keys") /* Initialize the offsets into the native key buffer */ - for(u = 0; u < (2 * H5F_KVALUE(f, type) + 1); u++) + for(u = 0; u < (shared->two_k + 1); u++) shared->nkey[u] = u * type->sizeof_nkey; /* Set return value */ ret_value = shared; done: + if(NULL == ret_value) + if(shared) { + if(shared->page) + shared->page = H5FL_BLK_FREE(page, shared->page); + if(shared->nkey) + shared->nkey = H5FL_SEQ_FREE(size_t, shared->nkey); + shared = H5FL_FREE(H5B_shared_t, shared); + } /* end if */ + FUNC_LEAVE_NOAPI(ret_value) } /* end H5B_shared_new() */ @@ -1771,7 +1749,7 @@ H5B_copy(const H5B_t *old_bt) * Check arguments. */ HDassert(old_bt); - shared=(H5B_shared_t *)H5RC_GET_OBJ(old_bt->rc_shared); + shared = (H5B_shared_t *)H5RC_GET_OBJ(old_bt->rc_shared); HDassert(shared); /* Allocate memory for the new H5B_t object */ @@ -1799,7 +1777,7 @@ H5B_copy(const H5B_t *old_bt) ret_value = new_node; done: - if(ret_value == NULL) { + if(NULL == ret_value) { if(new_node) { new_node->native = H5FL_BLK_FREE(native_block, new_node->native); new_node->child = H5FL_SEQ_FREE(haddr_t, new_node->child); @@ -1808,7 +1786,7 @@ done: } /* end if */ FUNC_LEAVE_NOAPI(ret_value) -} /* H5B_copy */ +} /* end H5B_copy() */ /*------------------------------------------------------------------------- @@ -1964,231 +1942,43 @@ done: /*------------------------------------------------------------------------- - * Function: H5B_debug + * Function: H5B_valid * - * Purpose: Prints debugging info about a B-tree. + * Purpose: Attempt to load a b-tree node. * - * Return: Non-negative on success/Negative on failure + * Return: Non-negative on success/Negative on failure * - * Programmer: Robb Matzke - * matzke@llnl.gov - * Aug 4 1997 + * Programmer: Neil Fortner + * March 17, 2009 * *------------------------------------------------------------------------- */ -herr_t -H5B_debug(H5F_t *f, hid_t dxpl_id, haddr_t addr, FILE *stream, int indent, int fwidth, - const H5B_class_t *type, void *udata) +htri_t +H5B_valid(H5F_t *f, hid_t dxpl_id, const H5B_class_t *type, haddr_t addr) { - H5B_t *bt = NULL; - H5B_shared_t *shared; /* Pointer to shared B-tree info */ - unsigned u; /* Local index variable */ - herr_t ret_value=SUCCEED; /* Return value */ + H5B_t *bt = NULL; /* The btree */ + htri_t ret_value = SUCCEED; /* Return value */ - FUNC_ENTER_NOAPI(H5B_debug, FAIL) + FUNC_ENTER_NOAPI(H5B_valid, FAIL) /* * Check arguments. */ HDassert(f); - HDassert(H5F_addr_defined(addr)); - HDassert(stream); - HDassert(indent >= 0); - HDassert(fwidth >= 0); HDassert(type); - /* - * Load the tree node. - */ - if(NULL == (bt = (H5B_t *)H5AC_protect(f, dxpl_id, H5AC_BT, addr, type, udata, H5AC_READ))) - HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to load B-tree node") - shared = (H5B_shared_t *)H5RC_GET_OBJ(bt->rc_shared); - HDassert(shared); - - /* - * Print the values. - */ - HDfprintf(stream, "%*s%-*s %s\n", indent, "", fwidth, - "Tree type ID:", - ((shared->type->id)==H5B_SNODE_ID ? "H5B_SNODE_ID" : - ((shared->type->id)==H5B_ISTORE_ID ? "H5B_ISTORE_ID" : "Unknown!"))); - HDfprintf(stream, "%*s%-*s %Zu\n", indent, "", fwidth, - "Size of node:", - shared->sizeof_rnode); - HDfprintf(stream, "%*s%-*s %Zu\n", indent, "", fwidth, - "Size of raw (disk) key:", - shared->sizeof_rkey); - HDfprintf(stream, "%*s%-*s %s\n", indent, "", fwidth, - "Dirty flag:", - bt->cache_info.is_dirty ? "True" : "False"); - HDfprintf(stream, "%*s%-*s %u\n", indent, "", fwidth, - "Level:", - bt->level); - - HDfprintf(stream, "%*s%-*s %a\n", indent, "", fwidth, - "Address of left sibling:", - bt->left); - - HDfprintf(stream, "%*s%-*s %a\n", indent, "", fwidth, - "Address of right sibling:", - bt->right); - - HDfprintf(stream, "%*s%-*s %u (%u)\n", indent, "", fwidth, - "Number of children (max):", - bt->nchildren, shared->two_k); + if(!H5F_addr_defined(addr)) + HGOTO_ERROR(H5E_BTREE, H5E_BADVALUE, FAIL, "address is undefined") - /* - * Print the child addresses - */ - for(u = 0; u < bt->nchildren; u++) { - HDfprintf(stream, "%*sChild %d...\n", indent, "", u); - HDfprintf(stream, "%*s%-*s %a\n", indent + 3, "", MAX(0, fwidth - 3), - "Address:", bt->child[u]); - - /* If there is a key debugging routine, use it to display the left & right keys */ - if(type->debug_key) { - /* Decode the 'left' key & print it */ - HDfprintf(stream, "%*s%-*s\n", indent + 3, "", MAX(0, fwidth - 3), - "Left Key:"); - HDassert(H5B_NKEY(bt, shared, u)); - (void)(type->debug_key)(stream, f, dxpl_id, indent + 6, MAX(0, fwidth - 6), - H5B_NKEY(bt, shared, u), udata); - - /* Decode the 'right' key & print it */ - HDfprintf(stream, "%*s%-*s\n", indent + 3, "", MAX(0, fwidth - 3), - "Right Key:"); - HDassert(H5B_NKEY(bt, shared, u + 1)); - (void)(type->debug_key)(stream, f, dxpl_id, indent + 6, MAX(0, fwidth - 6), - H5B_NKEY(bt, shared, u + 1), udata); - } /* end if */ - } /* end for */ + /* Protect the node */ + if(NULL == (bt = (H5B_t *)H5AC_protect(f, dxpl_id, H5AC_BT, addr, type, NULL, H5AC_READ))) + HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to load B-tree node") done: + /* Release the node */ if(bt && H5AC_unprotect(f, dxpl_id, H5AC_BT, addr, bt, H5AC__NO_FLAGS_SET) < 0) HDONE_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release B-tree node") FUNC_LEAVE_NOAPI(ret_value) -} - - -/*------------------------------------------------------------------------- - * Function: H5B_assert - * - * Purpose: Verifies that the tree is structured correctly. - * - * Return: Success: SUCCEED - * - * Failure: aborts if something is wrong. - * - * Programmer: Robb Matzke - * Tuesday, November 4, 1997 - * - *------------------------------------------------------------------------- - */ -#ifdef H5B_DEBUG -static herr_t -H5B_assert(H5F_t *f, hid_t dxpl_id, haddr_t addr, const H5B_class_t *type, void *udata) -{ - H5B_t *bt = NULL; - H5B_shared_t *shared; /* Pointer to shared B-tree info */ - int i, ncell, cmp; - static int ncalls = 0; - herr_t status; - herr_t ret_value = SUCCEED; /* Return value */ - - /* A queue of child data */ - struct child_t { - haddr_t addr; - unsigned level; - struct child_t *next; - } *head = NULL, *tail = NULL, *prev = NULL, *cur = NULL, *tmp = NULL; - - FUNC_ENTER_NOAPI(H5B_assert, FAIL) - - if(0 == ncalls++) { - if(H5DEBUG(B)) - fprintf(H5DEBUG(B), "H5B: debugging B-trees (expensive)\n"); - } /* end if */ - /* Initialize the queue */ - bt = (H5B_t *)H5AC_protect(f, dxpl_id, H5AC_BT, addr, type, udata, H5AC_READ); - HDassert(bt); - shared=(H5B_shared_t *)H5RC_GET_OBJ(bt->rc_shared); - HDassert(shared); - cur = H5MM_calloc(sizeof(struct child_t)); - HDassert(cur); - cur->addr = addr; - cur->level = bt->level; - head = tail = cur; - - status = H5AC_unprotect(f, dxpl_id, H5AC_BT, addr, bt, H5AC__NO_FLAGS_SET); - HDassert(status >= 0); - bt = NULL; /* Make certain future references will be caught */ - - /* - * Do a breadth-first search of the tree. New nodes are added to the end - * of the queue as the `cur' pointer is advanced toward the end. We don't - * remove any nodes from the queue because we need them in the uniqueness - * test. - */ - for(ncell = 0; cur; ncell++) { - bt = (H5B_t *)H5AC_protect(f, dxpl_id, H5AC_BT, cur->addr, type, udata, H5AC_READ); - HDassert(bt); - - /* Check node header */ - HDassert(bt->level == cur->level); - if(cur->next && cur->next->level == bt->level) - HDassert(H5F_addr_eq(bt->right, cur->next->addr)); - else - HDassert(!H5F_addr_defined(bt->right)); - if(prev && prev->level == bt->level) - HDassert(H5F_addr_eq(bt->left, prev->addr)); - else - HDassert(!H5F_addr_defined(bt->left)); - - if(cur->level > 0) { - for(i = 0; i < bt->nchildren; i++) { - - /* - * Check that child nodes haven't already been seen. If they - * have then the tree has a cycle. - */ - for(tmp = head; tmp; tmp = tmp->next) - HDassert(H5F_addr_ne(tmp->addr, bt->child[i])); - - /* Add the child node to the end of the queue */ - tmp = H5MM_calloc(sizeof(struct child_t)); - HDassert(tmp); - tmp->addr = bt->child[i]; - tmp->level = bt->level - 1; - tail->next = tmp; - tail = tmp; - - /* Check that the keys are monotonically increasing */ - cmp = (type->cmp2)(f, dxpl_id, H5B_NKEY(bt, shared, i), udata, - H5B_NKEY(bt, shared, i + 1)); - HDassert(cmp < 0); - } /* end for */ - } /* end if */ - - /* Release node */ - status = H5AC_unprotect(f, dxpl_id, H5AC_BT, cur->addr, bt, H5AC__NO_FLAGS_SET); - HDassert(status >= 0); - bt = NULL; /* Make certain future references will be caught */ - - /* Advance current location in queue */ - prev = cur; - cur = cur->next; - } /* end for */ - - /* Free all entries from queue */ - while(head) { - tmp = head->next; - H5MM_xfree(head); - head = tmp; - } /* end while */ - -done: - FUNC_LEAVE_NOAPI(ret_value) -} -#endif /* H5B_DEBUG */ +} /* end H5B_valid() */ |