summaryrefslogtreecommitdiffstats
path: root/src/H5B.c
diff options
context:
space:
mode:
authorAllen Byrne <byrn@hdfgroup.org>2019-08-23 19:09:20 (GMT)
committerAllen Byrne <byrn@hdfgroup.org>2019-08-23 19:09:20 (GMT)
commitd20d355b79bf25d2685dc9e3967951b1532951bb (patch)
treec862028f2d6c7ea540c6ffd2ca34d6ac9b715686 /src/H5B.c
parentc951ee8eded3cd63adfeaa87dcdd966ceb3e58c1 (diff)
downloadhdf5-d20d355b79bf25d2685dc9e3967951b1532951bb.zip
hdf5-d20d355b79bf25d2685dc9e3967951b1532951bb.tar.gz
hdf5-d20d355b79bf25d2685dc9e3967951b1532951bb.tar.bz2
OESS-29 Update HD prefix and compare against develop
Diffstat (limited to 'src/H5B.c')
-rw-r--r--src/H5B.c834
1 files changed, 417 insertions, 417 deletions
diff --git a/src/H5B.c b/src/H5B.c
index 53d5529..16772a8 100644
--- a/src/H5B.c
+++ b/src/H5B.c
@@ -13,79 +13,79 @@
/*-------------------------------------------------------------------------
*
- * Created: H5B.c
- * Jul 10 1997
- * Robb Matzke <matzke@llnl.gov>
+ * Created: H5B.c
+ * Jul 10 1997
+ * Robb Matzke <matzke@llnl.gov>
*
- * Purpose: Implements balanced, sibling-linked, N-ary trees
- * capable of storing any type of data with unique key
- * values.
+ * Purpose: Implements balanced, sibling-linked, N-ary trees
+ * capable of storing any type of data with unique key
+ * values.
*
- * A B-link-tree is a balanced tree where each node has
- * a pointer to its left and right siblings. A
- * B-link-tree is a rooted tree having the following
- * properties:
+ * A B-link-tree is a balanced tree where each node has
+ * a pointer to its left and right siblings. A
+ * B-link-tree is a rooted tree having the following
+ * properties:
*
- * 1. Every node, x, has the following fields:
+ * 1. Every node, x, has the following fields:
*
- * a. level[x], the level in the tree at which node
- * x appears. Leaf nodes are at level zero.
+ * a. level[x], the level in the tree at which node
+ * x appears. Leaf nodes are at level zero.
*
- * b. n[x], the number of children pointed to by the
- * node. Internal nodes point to subtrees while
- * leaf nodes point to arbitrary data.
+ * b. n[x], the number of children pointed to by the
+ * node. Internal nodes point to subtrees while
+ * leaf nodes point to arbitrary data.
*
- * c. The child pointers themselves, child[x,i] such
- * that 0 <= i < n[x].
+ * c. The child pointers themselves, child[x,i] such
+ * that 0 <= i < n[x].
*
- * d. n[x]+1 key values stored in increasing
- * order:
+ * d. n[x]+1 key values stored in increasing
+ * order:
*
- * key[x,0] < key[x,1] < ... < key[x,n[x]].
+ * key[x,0] < key[x,1] < ... < key[x,n[x]].
*
- * e. left[x] is a pointer to the node's left sibling
- * or the null pointer if this is the left-most
- * node at this level in the tree.
+ * e. left[x] is a pointer to the node's left sibling
+ * or the null pointer if this is the left-most
+ * node at this level in the tree.
*
- * f. right[x] is a pointer to the node's right
- * sibling or the null pointer if this is the
- * right-most node at this level in the tree.
+ * f. right[x] is a pointer to the node's right
+ * sibling or the null pointer if this is the
+ * right-most node at this level in the tree.
*
- * 3. The keys key[x,i] partition the key spaces of the
- * children of x:
+ * 3. The keys key[x,i] partition the key spaces of the
+ * children of x:
*
- * key[x,i] <= key[child[x,i],j] <= key[x,i+1]
+ * key[x,i] <= key[child[x,i],j] <= key[x,i+1]
*
- * for any valid combination of i and j.
+ * for any valid combination of i and j.
*
- * 4. There are lower and upper bounds on the number of
- * child pointers a node can contain. These bounds
- * can be expressed in terms of a fixed integer k>=2
- * called the `minimum degree' of the B-tree.
+ * 4. There are lower and upper bounds on the number of
+ * child pointers a node can contain. These bounds
+ * can be expressed in terms of a fixed integer k>=2
+ * called the `minimum degree' of the B-tree.
*
- * a. Every node other than the root must have at least
- * k child pointers and k+1 keys. If the tree is
- * nonempty, the root must have at least one child
- * pointer and two keys.
+ * a. Every node other than the root must have at least
+ * k child pointers and k+1 keys. If the tree is
+ * nonempty, the root must have at least one child
+ * pointer and two keys.
*
- * b. Every node can contain at most 2k child pointers
- * and 2k+1 keys. A node is `full' if it contains
- * exactly 2k child pointers and 2k+1 keys.
+ * b. Every node can contain at most 2k child pointers
+ * and 2k+1 keys. A node is `full' if it contains
+ * exactly 2k child pointers and 2k+1 keys.
*
- * 5. When searching for a particular value, V, and
- * key[V] = key[x,i] for some node x and entry i,
- * then:
+ * 5. When searching for a particular value, V, and
+ * key[V] = key[x,i] for some node x and entry i,
+ * then:
*
- * a. If i=0 the child[0] is followed.
+ * a. If i=0 the child[0] is followed.
*
- * b. If i=n[x] the child[n[x]-1] is followed.
+ * b. If i=n[x] the child[n[x]-1] is followed.
*
- * c. Otherwise, the child that is followed
- * (either child[x,i-1] or child[x,i]) is
- * determined by the type of object to which the
- * leaf nodes of the tree point and is controlled
- * by the key comparison function registered for
- * that type of B-tree.
+ * c. Otherwise, the child that is followed
+ * (either child[x,i-1] or child[x,i]) is
+ * determined by the type of object to which the
+ * leaf nodes of the tree point and is controlled
+ * by the key comparison function registered for
+ * that type of B-tree.
*
*
*-------------------------------------------------------------------------
@@ -101,22 +101,22 @@
/***********/
/* Headers */
/***********/
-#include "H5private.h" /* Generic Functions */
-#include "H5Bpkg.h" /* B-link trees */
+#include "H5private.h" /* Generic Functions */
+#include "H5Bpkg.h" /* B-link trees */
#include "H5CXprivate.h" /* API Contexts */
-#include "H5Eprivate.h" /* Error handling */
-#include "H5Iprivate.h" /* IDs */
-#include "H5MFprivate.h" /* File memory management */
+#include "H5Eprivate.h" /* Error handling */
+#include "H5Iprivate.h" /* IDs */
+#include "H5MFprivate.h" /* File memory management */
#include "H5Pprivate.h" /* Property lists */
/****************/
/* Local Macros */
/****************/
-#define H5B_SIZEOF_HDR(F) \
- (H5_SIZEOF_MAGIC + /*magic number */ \
- 4 + /*type, level, num entries */ \
- 2*H5F_SIZEOF_ADDR(F)) /*left and right sibling addresses */
+#define H5B_SIZEOF_HDR(F) \
+ (H5_SIZEOF_MAGIC + /*magic number */ \
+ 4 + /*type, level, num entries */ \
+ 2*H5F_SIZEOF_ADDR(F)) /*left and right sibling addresses */
/* Default initializer for H5B_ins_ud_t */
#define H5B_INS_UD_T_NULL {NULL, HADDR_UNDEF, H5AC__NO_FLAGS_SET}
@@ -149,7 +149,7 @@ static H5B_ins_t H5B__insert_helper(H5F_t *f, H5B_ins_ud_t *bt_ud,
H5B_ins_ud_t *split_bt_ud/*out*/);
static herr_t H5B__insert_child(H5B_t *bt, unsigned *bt_flags,
unsigned idx, haddr_t child,
- H5B_ins_t anchor, const void *md_key);
+ H5B_ins_t anchor, const void *md_key);
static herr_t H5B__split(H5F_t *f, H5B_ins_ud_t *bt_ud, unsigned idx,
void *udata, H5B_ins_ud_t *split_bt_ud/*out*/);
static H5B_t * H5B__copy(const H5B_t *old_bt);
@@ -191,31 +191,31 @@ H5FL_BLK_DEFINE_STATIC(page);
H5FL_SEQ_DEFINE_STATIC(size_t);
-
+
/*-------------------------------------------------------------------------
- * Function: H5B_create
+ * Function: H5B_create
*
- * Purpose: Creates a new empty B-tree leaf node. The UDATA pointer is
- * passed as an argument to the sizeof_rkey() method for the
- * B-tree.
+ * Purpose: Creates a new empty B-tree leaf node. The UDATA pointer is
+ * passed as an argument to the sizeof_rkey() method for the
+ * B-tree.
*
- * Return: Success: Non-negative, and the address of new node is
- * returned through the ADDR_P argument.
+ * Return: Success: Non-negative, and the address of new node is
+ * returned through the ADDR_P argument.
*
- * Failure: Negative
+ * Failure: Negative
*
- * Programmer: Robb Matzke
- * matzke@llnl.gov
- * Jun 23 1997
+ * Programmer: Robb Matzke
+ * matzke@llnl.gov
+ * Jun 23 1997
*
*-------------------------------------------------------------------------
*/
herr_t
H5B_create(H5F_t *f, const H5B_class_t *type, void *udata, haddr_t *addr_p/*out*/)
{
- H5B_t *bt = NULL;
+ H5B_t *bt = NULL;
H5B_shared_t *shared=NULL; /* Pointer to shared B-tree info */
- herr_t ret_value = SUCCEED;
+ herr_t ret_value = SUCCEED;
FUNC_ENTER_NOAPI(FAIL)
@@ -230,20 +230,20 @@ H5B_create(H5F_t *f, const H5B_class_t *type, void *udata, haddr_t *addr_p/*out*
* Allocate file and memory data structures.
*/
if(NULL == (bt = H5FL_MALLOC(H5B_t)))
- HGOTO_ERROR(H5E_BTREE, H5E_CANTALLOC, FAIL, "memory allocation failed for B-tree root node")
+ HGOTO_ERROR(H5E_BTREE, H5E_CANTALLOC, FAIL, "memory allocation failed for B-tree root node")
HDmemset(&bt->cache_info, 0, sizeof(H5AC_info_t));
bt->level = 0;
bt->left = HADDR_UNDEF;
bt->right = HADDR_UNDEF;
bt->nchildren = 0;
if(NULL == (bt->rc_shared = (type->get_shared)(f, udata)))
- HGOTO_ERROR(H5E_BTREE, H5E_CANTGET, FAIL, "can't retrieve B-tree node buffer")
+ HGOTO_ERROR(H5E_BTREE, H5E_CANTGET, FAIL, "can't retrieve B-tree node buffer")
H5UC_INC(bt->rc_shared);
shared=(H5B_shared_t *)H5UC_GET_OBJ(bt->rc_shared);
HDassert(shared);
if(NULL == (bt->native = H5FL_BLK_MALLOC(native_block, shared->sizeof_keys)) ||
NULL == (bt->child = H5FL_SEQ_MALLOC(haddr_t, (size_t)shared->two_k)))
- HGOTO_ERROR(H5E_BTREE, H5E_CANTALLOC, FAIL, "memory allocation failed for B-tree root node")
+ HGOTO_ERROR(H5E_BTREE, H5E_CANTALLOC, FAIL, "memory allocation failed for B-tree root node")
if(HADDR_UNDEF == (*addr_p = H5MF_alloc(f, H5FD_MEM_BTREE, (hsize_t)shared->sizeof_rnode)))
HGOTO_ERROR(H5E_BTREE, H5E_CANTALLOC, FAIL, "file allocation failed for B-tree root node")
@@ -251,7 +251,7 @@ H5B_create(H5F_t *f, const H5B_class_t *type, void *udata, haddr_t *addr_p/*out*
* Cache the new B-tree node.
*/
if(H5AC_insert_entry(f, H5AC_BT, *addr_p, bt, H5AC__NO_FLAGS_SET) < 0)
- HGOTO_ERROR(H5E_BTREE, H5E_CANTINIT, FAIL, "can't add B-tree root node to cache")
+ HGOTO_ERROR(H5E_BTREE, H5E_CANTINIT, FAIL, "can't add B-tree root node to cache")
#ifdef H5B_DEBUG
H5B__assert(f, *addr_p, shared->type, udata);
#endif
@@ -262,7 +262,7 @@ done:
H5_CHECK_OVERFLOW(shared->sizeof_rnode,size_t,hsize_t);
(void)H5MF_xfree(f, H5FD_MEM_BTREE, *addr_p, (hsize_t)shared->sizeof_rnode);
} /* end if */
- if(bt)
+ if(bt)
/* Destroy B-tree node */
if(H5B__node_dest(bt) < 0)
HDONE_ERROR(H5E_BTREE, H5E_CANTFREE, FAIL, "unable to destroy B-tree node")
@@ -271,40 +271,40 @@ done:
FUNC_LEAVE_NOAPI(ret_value)
} /* end H5B_create() */ /*lint !e818 Can't make udata a pointer to const */
-
+
/*-------------------------------------------------------------------------
- * Function: H5B_find
+ * Function: H5B_find
*
- * Purpose: Locate the specified information in a B-tree and return
- * that information by filling in fields of the caller-supplied
- * UDATA pointer depending on the type of leaf node
- * requested. The UDATA can point to additional data passed
- * to the key comparison function.
+ * Purpose: Locate the specified information in a B-tree and return
+ * that information by filling in fields of the caller-supplied
+ * UDATA pointer depending on the type of leaf node
+ * requested. The UDATA can point to additional data passed
+ * to the key comparison function.
*
- * Note: This function does not follow the left/right sibling
- * pointers since it assumes that all nodes can be reached
- * from the parent node.
+ * Note: This function does not follow the left/right sibling
+ * pointers since it assumes that all nodes can be reached
+ * from the parent node.
*
- * Return: Non-negative (TRUE/FALSE) on success (if found, values returned
+ * 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
- * Jun 23 1997
+ * Programmer: Robb Matzke
+ * matzke@llnl.gov
+ * Jun 23 1997
*
*-------------------------------------------------------------------------
*/
htri_t
H5B_find(H5F_t *f, const H5B_class_t *type, haddr_t addr, void *udata)
{
- H5B_t *bt = NULL;
- H5UC_t *rc_shared; /* Ref-counted shared info */
+ H5B_t *bt = NULL;
+ H5UC_t *rc_shared; /* Ref-counted shared info */
H5B_shared_t *shared; /* Pointer to shared B-tree info */
H5B_cache_ud_t cache_udata; /* User-data for metadata cache callback */
unsigned idx = 0, lt = 0, rt; /* Final, left & right key indices */
- int cmp = 1; /* Key comparison value */
- htri_t ret_value = FAIL; /* Return value */
+ int cmp = 1; /* Key comparison value */
+ htri_t ret_value = FAIL; /* Return value */
FUNC_ENTER_NOAPI(FAIL)
@@ -336,16 +336,16 @@ H5B_find(H5F_t *f, const H5B_class_t *type, haddr_t addr, void *udata)
rt = bt->nchildren;
while(lt < rt && cmp) {
- idx = (lt + rt) / 2;
- /* compare */
- if((cmp = (type->cmp3)(H5B_NKEY(bt, shared, idx), udata, H5B_NKEY(bt, shared, (idx + 1)))) < 0)
- rt = idx;
- else
- lt = idx + 1;
+ idx = (lt + rt) / 2;
+ /* compare */
+ if((cmp = (type->cmp3)(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)
- HGOTO_DONE(FALSE)
+ HGOTO_DONE(FALSE)
/*
* Follow the link to the subtree or to the data node.
@@ -353,41 +353,41 @@ H5B_find(H5F_t *f, const H5B_class_t *type, haddr_t addr, void *udata)
HDassert(idx < bt->nchildren);
if(bt->level > 0) {
- if((ret_value = H5B_find(f, type, bt->child[idx], udata)) < 0)
- HGOTO_ERROR(H5E_BTREE, H5E_NOTFOUND, FAIL, "can't lookup key in subtree")
+ if((ret_value = H5B_find(f, 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, bt->child[idx], H5B_NKEY(bt, shared, idx), udata)) < 0)
+ if((ret_value = (type->found)(f, 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, H5AC_BT, addr, bt, H5AC__NO_FLAGS_SET) < 0)
- HDONE_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release node")
+ HDONE_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release node")
FUNC_LEAVE_NOAPI(ret_value)
} /* end H5B_find() */
-
+
/*-------------------------------------------------------------------------
- * Function: H5B__split
+ * Function: H5B__split
*
- * Purpose: Split a single node into two nodes. The old node will
- * contain the left children and the new node will contain the
- * right children.
+ * Purpose: Split a single node into two nodes. The old node will
+ * contain the left children and the new node will contain the
+ * right children.
*
- * The UDATA pointer is passed to the sizeof_rkey() method but is
- * otherwise unused.
+ * The UDATA pointer is passed to the sizeof_rkey() method but is
+ * otherwise unused.
*
- * The BT_UD argument is a pointer to a protected B-tree
- * node.
+ * The BT_UD argument is a pointer to a protected B-tree
+ * node.
*
- * Return: Non-negative on success (The address of the new node is
+ * Return: Non-negative on success (The address of the new node is
* returned through the NEW_ADDR argument). Negative on failure.
*
- * Programmer: Robb Matzke
- * matzke@llnl.gov
- * Jul 3 1997
+ * Programmer: Robb Matzke
+ * matzke@llnl.gov
+ * Jul 3 1997
*
*-------------------------------------------------------------------------
*/
@@ -397,9 +397,9 @@ H5B__split(H5F_t *f, H5B_ins_ud_t *bt_ud, unsigned idx,
{
H5B_shared_t *shared; /* Pointer to shared B-tree info */
H5B_cache_ud_t cache_udata; /* User-data for metadata cache callback */
- unsigned nleft, nright; /* Number of keys in left & right halves */
+ unsigned nleft, nright; /* Number of keys in left & right halves */
double split_ratios[3]; /* B-tree split ratios */
- herr_t ret_value = SUCCEED; /* Return value */
+ herr_t ret_value = SUCCEED; /* Return value */
FUNC_ENTER_STATIC
@@ -426,18 +426,18 @@ H5B__split(H5F_t *f, H5B_ins_ud_t *bt_ud, unsigned idx,
#ifdef H5B_DEBUG
if(H5DEBUG(B)) {
- const char *side;
-
- if(!H5F_addr_defined(bt_ud->bt->left) && !H5F_addr_defined(bt_ud->bt->right))
- side = "ONLY";
- else if(!H5F_addr_defined(bt_ud->bt->right))
- side = "RIGHT";
- else if(!H5F_addr_defined(bt_ud->bt->left))
- side = "LEFT";
- else
- side = "MIDDLE";
- fprintf(H5DEBUG(B), "H5B__split: %3u {%5.3f,%5.3f,%5.3f} %6s",
- shared->two_k, split_ratios[0], split_ratios[1], split_ratios[2], side);
+ const char *side;
+
+ if(!H5F_addr_defined(bt_ud->bt->left) && !H5F_addr_defined(bt_ud->bt->right))
+ side = "ONLY";
+ else if(!H5F_addr_defined(bt_ud->bt->right))
+ side = "RIGHT";
+ else if(!H5F_addr_defined(bt_ud->bt->left))
+ side = "LEFT";
+ else
+ side = "MIDDLE";
+ HDfprintf(H5DEBUG(B), "H5B__split: %3u {%5.3f,%5.3f,%5.3f} %6s",
+ shared->two_k, split_ratios[0], split_ratios[1], split_ratios[2], side);
}
#endif
@@ -446,11 +446,11 @@ H5B__split(H5F_t *f, H5B_ins_ud_t *bt_ud, unsigned idx,
* and the new node.
*/
if(!H5F_addr_defined(bt_ud->bt->right))
- nleft = (unsigned)((double)shared->two_k * split_ratios[2]); /*right*/
+ nleft = (unsigned)((double)shared->two_k * split_ratios[2]); /*right*/
else if(!H5F_addr_defined(bt_ud->bt->left))
- nleft = (unsigned)((double)shared->two_k * split_ratios[0]); /*left*/
+ nleft = (unsigned)((double)shared->two_k * split_ratios[0]); /*left*/
else
- nleft = (unsigned)((double)shared->two_k * split_ratios[1]); /*middle*/
+ nleft = (unsigned)((double)shared->two_k * split_ratios[1]); /*middle*/
/*
* Keep the new child in the same node as the child that split. This can
@@ -458,25 +458,25 @@ H5B__split(H5F_t *f, H5B_ins_ud_t *bt_ud, unsigned idx,
* sequentially, but it simplifies stuff below.
*/
if(idx < nleft && nleft == shared->two_k)
- --nleft;
+ --nleft;
else if(idx >= nleft && 0 == nleft)
- nleft++;
+ nleft++;
nright = shared->two_k - nleft;
#ifdef H5B_DEBUG
if(H5DEBUG(B))
- fprintf(H5DEBUG(B), " split %3d/%-3d\n", nleft, nright);
+ HDfprintf(H5DEBUG(B), " split %3d/%-3d\n", nleft, nright);
#endif
/*
* Create the new B-tree node.
*/
if(H5B_create(f, shared->type, udata, &split_bt_ud->addr/*out*/) < 0)
- HGOTO_ERROR(H5E_BTREE, H5E_CANTINIT, FAIL, "unable to create B-tree")
+ HGOTO_ERROR(H5E_BTREE, H5E_CANTINIT, FAIL, "unable to create B-tree")
cache_udata.f = f;
cache_udata.type = shared->type;
cache_udata.rc_shared = bt_ud->bt->rc_shared;
if(NULL == (split_bt_ud->bt = (H5B_t *)H5AC_protect(f, H5AC_BT, split_bt_ud->addr, &cache_udata, H5AC__NO_FLAGS_SET)))
- HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to protect B-tree")
+ HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to protect B-tree")
split_bt_ud->bt->level = bt_ud->bt->level;
/*
@@ -485,8 +485,8 @@ H5B__split(H5F_t *f, H5B_ins_ud_t *bt_ud, unsigned idx,
split_bt_ud->cache_flags = H5AC__DIRTIED_FLAG;
HDmemcpy(split_bt_ud->bt->native,
- bt_ud->bt->native + nleft * shared->type->sizeof_nkey,
- (nright + 1) * shared->type->sizeof_nkey);
+ bt_ud->bt->native + nleft * shared->type->sizeof_nkey,
+ (nright + 1) * shared->type->sizeof_nkey);
HDmemcpy(split_bt_ud->bt->child,
&bt_ud->bt->child[nleft],
nright * sizeof(haddr_t));
@@ -532,17 +532,17 @@ done:
FUNC_LEAVE_NOAPI(ret_value)
} /* end H5B__split() */
-
+
/*-------------------------------------------------------------------------
- * Function: H5B_insert
+ * Function: H5B_insert
*
- * Purpose: Adds a new item to the B-tree.
+ * Purpose: Adds a new item to the B-tree.
*
- * Return: Non-negative on success/Negative on failure
+ * Return: Non-negative on success/Negative on failure
*
- * Programmer: Robb Matzke
- * matzke@llnl.gov
- * Jun 23 1997
+ * Programmer: Robb Matzke
+ * matzke@llnl.gov
+ * Jun 23 1997
*
*-------------------------------------------------------------------------
*/
@@ -552,22 +552,22 @@ H5B_insert(H5F_t *f, const H5B_class_t *type, haddr_t addr, void *udata)
/*
* These are defined this way to satisfy alignment constraints.
*/
- uint64_t _lt_key[128], _md_key[128], _rt_key[128];
- uint8_t *lt_key=(uint8_t*)_lt_key;
- uint8_t *md_key=(uint8_t*)_md_key;
- uint8_t *rt_key=(uint8_t*)_rt_key;
+ uint64_t _lt_key[128], _md_key[128], _rt_key[128];
+ uint8_t *lt_key=(uint8_t*)_lt_key;
+ uint8_t *md_key=(uint8_t*)_md_key;
+ uint8_t *rt_key=(uint8_t*)_rt_key;
- hbool_t lt_key_changed = FALSE, rt_key_changed = FALSE;
+ hbool_t lt_key_changed = FALSE, rt_key_changed = FALSE;
haddr_t old_root_addr = HADDR_UNDEF;
- unsigned level;
+ unsigned level;
H5B_ins_ud_t bt_ud = H5B_INS_UD_T_NULL; /* (Old) root node */
H5B_ins_ud_t split_bt_ud = H5B_INS_UD_T_NULL; /* Split B-tree node */
H5B_t *new_root_bt = NULL; /* New root node */
- H5UC_t *rc_shared; /* Ref-counted shared info */
+ H5UC_t *rc_shared; /* Ref-counted shared info */
H5B_shared_t *shared; /* Pointer to shared B-tree info */
H5B_cache_ud_t cache_udata; /* User-data for metadata cache callback */
- H5B_ins_t my_ins = H5B_INS_ERROR;
- herr_t ret_value = SUCCEED;
+ H5B_ins_t my_ins = H5B_INS_ERROR;
+ herr_t ret_value = SUCCEED;
FUNC_ENTER_NOAPI(FAIL)
@@ -595,7 +595,7 @@ H5B_insert(H5F_t *f, const H5B_class_t *type, haddr_t addr, void *udata)
if((int)(my_ins = H5B__insert_helper(f, &bt_ud, type, lt_key,
&lt_key_changed, md_key, udata, rt_key, &rt_key_changed,
&split_bt_ud/*out*/)) < 0)
- HGOTO_ERROR(H5E_BTREE, H5E_CANTINIT, FAIL, "unable to insert key")
+ HGOTO_ERROR(H5E_BTREE, H5E_CANTINIT, FAIL, "unable to insert key")
/* Check if the root node split */
if(H5B_INS_NOOP == my_ins) {
@@ -612,9 +612,9 @@ H5B_insert(H5F_t *f, const H5B_class_t *type, haddr_t addr, void *udata)
/* update left and right keys */
if(!lt_key_changed)
- HDmemcpy(lt_key, H5B_NKEY(bt_ud.bt,shared,0), type->sizeof_nkey);
+ HDmemcpy(lt_key, H5B_NKEY(bt_ud.bt,shared,0), type->sizeof_nkey);
if(!rt_key_changed)
- HDmemcpy(rt_key, H5B_NKEY(split_bt_ud.bt,shared,split_bt_ud.bt->nchildren), type->sizeof_nkey);
+ HDmemcpy(rt_key, H5B_NKEY(split_bt_ud.bt,shared,split_bt_ud.bt->nchildren), type->sizeof_nkey);
/*
* Copy the old root node to some other file location and make the new root
@@ -623,7 +623,7 @@ H5B_insert(H5F_t *f, const H5B_class_t *type, haddr_t addr, void *udata)
*/
H5_CHECK_OVERFLOW(shared->sizeof_rnode,size_t,hsize_t);
if(HADDR_UNDEF == (old_root_addr = H5MF_alloc(f, H5FD_MEM_BTREE, (hsize_t)shared->sizeof_rnode)))
- HGOTO_ERROR(H5E_BTREE, H5E_CANTALLOC, FAIL, "unable to allocate file space to move root")
+ HGOTO_ERROR(H5E_BTREE, H5E_CANTALLOC, FAIL, "unable to allocate file space to move root")
/*
* Move the node to the new location
@@ -636,12 +636,12 @@ H5B_insert(H5F_t *f, const H5B_class_t *type, haddr_t addr, void *udata)
/* Unprotect the old root so we can move it. Also force it to be marked
* dirty so it is written to the new location. */
if(H5AC_unprotect(f, H5AC_BT, bt_ud.addr, bt_ud.bt, H5AC__DIRTIED_FLAG) < 0)
- HGOTO_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release old root")
+ HGOTO_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release old root")
bt_ud.bt = NULL; /* Make certain future references will be caught */
/* Move the location of the old root on the disk */
if(H5AC_move_entry(f, H5AC_BT, bt_ud.addr, old_root_addr) < 0)
- HGOTO_ERROR(H5E_BTREE, H5E_CANTSPLIT, FAIL, "unable to move B-tree root node")
+ HGOTO_ERROR(H5E_BTREE, H5E_CANTSPLIT, FAIL, "unable to move B-tree root node")
bt_ud.addr = old_root_addr;
/* Update the split b-tree's left pointer to point to the new location */
@@ -688,19 +688,19 @@ done:
FUNC_LEAVE_NOAPI(ret_value)
} /* end H5B_insert() */
-
+
/*-------------------------------------------------------------------------
- * Function: H5B__insert_child
+ * Function: H5B__insert_child
*
- * Purpose: Insert a child to the left or right of child[IDX] depending
- * on whether ANCHOR is H5B_INS_LEFT or H5B_INS_RIGHT. The BT
- * argument is a pointer to a protected B-tree node.
+ * Purpose: Insert a child to the left or right of child[IDX] depending
+ * on whether ANCHOR is H5B_INS_LEFT or H5B_INS_RIGHT. The BT
+ * argument is a pointer to a protected 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
- * Jul 8 1997
+ * Programmer: Robb Matzke
+ * matzke@llnl.gov
+ * Jul 8 1997
*
*-------------------------------------------------------------------------
*/
@@ -761,35 +761,35 @@ H5B__insert_child(H5B_t *bt, unsigned *bt_flags, unsigned idx,
FUNC_LEAVE_NOAPI(SUCCEED)
} /* end H5B_insert_child() */
-
+
/*-------------------------------------------------------------------------
- * Function: H5B__insert_helper
+ * Function: H5B__insert_helper
*
- * Purpose: Inserts the item UDATA into the tree rooted at ADDR and having
- * the specified type.
+ * Purpose: Inserts the item UDATA into the tree rooted at ADDR and having
+ * the specified type.
*
- * On return, if LT_KEY_CHANGED is non-zero, then LT_KEY is
- * the new native left key. Similarly for RT_KEY_CHANGED
- * and RT_KEY.
+ * On return, if LT_KEY_CHANGED is non-zero, then LT_KEY is
+ * the new native left key. Similarly for RT_KEY_CHANGED
+ * and RT_KEY.
*
- * If the node splits, then MD_KEY contains the key that
- * was split between the two nodes (that is, the key that
- * appears as the max key in the left node and the min key
- * in the right node).
+ * If the node splits, then MD_KEY contains the key that
+ * was split between the two nodes (that is, the key that
+ * appears as the max key in the left node and the min key
+ * in the right node).
*
- * Return: Success: A B-tree operation. The address of the new
- * node, if the node splits, is returned through
- * the NEW_NODE_P argument. The new node is always
- * to the right of the previous node. This
- * function is called recursively and the return
- * value influences the behavior of the caller.
- * See also, declaration of H5B_ins_t.
+ * Return: Success: A B-tree operation. The address of the new
+ * node, if the node splits, is returned through
+ * the NEW_NODE_P argument. The new node is always
+ * to the right of the previous node. This
+ * function is called recursively and the return
+ * value influences the behavior of the caller.
+ * See also, declaration of H5B_ins_t.
*
- * Failure: H5B_INS_ERROR
+ * Failure: H5B_INS_ERROR
*
- * Programmer: Robb Matzke
- * matzke@llnl.gov
- * Jul 9 1997
+ * Programmer: Robb Matzke
+ * matzke@llnl.gov
+ * Jul 9 1997
*
*-------------------------------------------------------------------------
*/
@@ -799,15 +799,15 @@ H5B__insert_helper(H5F_t *f, H5B_ins_ud_t *bt_ud, const H5B_class_t *type,
uint8_t *rt_key, hbool_t *rt_key_changed, H5B_ins_ud_t *split_bt_ud/*out*/)
{
H5B_t *bt; /* Convenience pointer to B-tree */
- H5UC_t *rc_shared; /* Ref-counted shared info */
+ H5UC_t *rc_shared; /* Ref-counted shared info */
H5B_shared_t *shared; /* Pointer to shared B-tree info */
H5B_cache_ud_t cache_udata; /* User-data for metadata cache callback */
- unsigned lt = 0, idx = 0, rt; /* Left, final & right index values */
+ unsigned lt = 0, idx = 0, rt; /* Left, final & right index values */
int cmp = -1; /* Key comparison value */
H5B_ins_ud_t child_bt_ud = H5B_INS_UD_T_NULL; /* Child B-tree */
H5B_ins_ud_t new_child_bt_ud = H5B_INS_UD_T_NULL; /* Newly split child B-tree */
- H5B_ins_t my_ins = H5B_INS_ERROR;
- H5B_ins_t ret_value = H5B_INS_ERROR; /* Return value */
+ H5B_ins_t my_ins = H5B_INS_ERROR;
+ H5B_ins_t ret_value = H5B_INS_ERROR; /* Return value */
FUNC_ENTER_STATIC
@@ -838,7 +838,7 @@ H5B__insert_helper(H5F_t *f, H5B_ins_ud_t *bt_ud, const H5B_class_t *type,
/* Get shared info for B-tree */
if(NULL == (rc_shared = (type->get_shared)(f, udata)))
- HGOTO_ERROR(H5E_BTREE, H5E_CANTGET, H5B_INS_ERROR, "can't retrieve B-tree's shared ref. count object")
+ HGOTO_ERROR(H5E_BTREE, H5E_CANTGET, H5B_INS_ERROR, "can't retrieve B-tree's shared ref. count object")
shared = (H5B_shared_t *)H5UC_GET_OBJ(rc_shared);
HDassert(shared);
@@ -850,11 +850,11 @@ H5B__insert_helper(H5F_t *f, H5B_ins_ud_t *bt_ud, const H5B_class_t *type,
rt = bt->nchildren;
while(lt < rt && cmp) {
- idx = (lt + rt) / 2;
- if((cmp = (type->cmp3)(H5B_NKEY(bt, shared, idx), udata, H5B_NKEY(bt, shared, idx + 1))) < 0)
- rt = idx;
- else
- lt = idx + 1;
+ idx = (lt + rt) / 2;
+ if((cmp = (type->cmp3)(H5B_NKEY(bt, shared, idx), udata, H5B_NKEY(bt, shared, idx + 1))) < 0)
+ rt = idx;
+ else
+ lt = idx + 1;
} /* end while */
/* Set up user data for cache callbacks */
@@ -863,26 +863,26 @@ H5B__insert_helper(H5F_t *f, H5B_ins_ud_t *bt_ud, const H5B_class_t *type,
cache_udata.rc_shared = rc_shared;
if(0 == bt->nchildren) {
- /*
- * The value being inserted will be the only value in this tree. We
- * must necessarily be at level zero.
- */
- HDassert(0 == bt->level);
- if((type->new_node)(f, H5B_INS_FIRST, H5B_NKEY(bt, shared, 0), udata,
- H5B_NKEY(bt, shared, 1), bt->child + 0/*out*/) < 0)
- HGOTO_ERROR(H5E_BTREE, H5E_CANTINIT, H5B_INS_ERROR, "unable to create leaf node")
- bt->nchildren = 1;
+ /*
+ * The value being inserted will be the only value in this tree. We
+ * must necessarily be at level zero.
+ */
+ HDassert(0 == bt->level);
+ if((type->new_node)(f, H5B_INS_FIRST, H5B_NKEY(bt, shared, 0), udata,
+ H5B_NKEY(bt, shared, 1), bt->child + 0/*out*/) < 0)
+ HGOTO_ERROR(H5E_BTREE, H5E_CANTINIT, H5B_INS_ERROR, "unable to create leaf node")
+ bt->nchildren = 1;
bt_ud->cache_flags |= H5AC__DIRTIED_FLAG;
- idx = 0;
+ idx = 0;
- if(type->follow_min) {
- if((int)(my_ins = (type->insert)(f, bt->child[idx], H5B_NKEY(bt, shared, idx),
+ if(type->follow_min) {
+ if((int)(my_ins = (type->insert)(f, bt->child[idx], H5B_NKEY(bt, shared, idx),
lt_key_changed, md_key, udata, H5B_NKEY(bt, shared, idx + 1),
rt_key_changed, &new_child_bt_ud.addr/*out*/)) < 0)
- HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, H5B_INS_ERROR, "unable to insert first leaf node")
- } /* end if */
+ HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, H5B_INS_ERROR, "unable to insert first leaf node")
+ } /* end if */
else
- my_ins = H5B_INS_NOOP;
+ my_ins = H5B_INS_NOOP;
} else if(cmp < 0 && idx == 0) {
if(bt->level > 0) {
/*
@@ -977,36 +977,36 @@ H5B__insert_helper(H5F_t *f, H5B_ins_ud_t *bt_ud, const H5B_class_t *type,
HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, H5B_INS_ERROR, "internal error: likely corrupt key values")
#endif /* H5_STRICT_FORMAT_CHECKS */
} else if(cmp) {
- /*
- * We couldn't figure out which branch to follow out of this node. THIS
- * IS A MAJOR PROBLEM THAT NEEDS TO BE FIXED --rpm.
- */
- HDassert("INTERNAL HDF5 ERROR (contact rpm)" && 0);
+ /*
+ * We couldn't figure out which branch to follow out of this node. THIS
+ * IS A MAJOR PROBLEM THAT NEEDS TO BE FIXED --rpm.
+ */
+ HDassert("INTERNAL HDF5 ERROR (contact rpm)" && 0);
#ifdef NDEBUG
- HDabort();
+ HDabort();
#endif /* NDEBUG */
} else if(bt->level > 0) {
- /*
- * Follow a branch out of this node to another subtree.
- */
- HDassert(idx < bt->nchildren);
- child_bt_ud.addr = bt->child[idx];
+ /*
+ * Follow a branch out of this node to another subtree.
+ */
+ HDassert(idx < bt->nchildren);
+ child_bt_ud.addr = bt->child[idx];
if(NULL == (child_bt_ud.bt = (H5B_t *)H5AC_protect(f, H5AC_BT, child_bt_ud.addr, &cache_udata, H5AC__NO_FLAGS_SET)))
HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, H5B_INS_ERROR, "unable to load node")
- if((int)(my_ins = H5B__insert_helper(f, &child_bt_ud, type,
+ if((int)(my_ins = H5B__insert_helper(f, &child_bt_ud, type,
H5B_NKEY(bt, shared, idx), lt_key_changed, md_key, udata,
H5B_NKEY(bt, shared, idx + 1), rt_key_changed, &new_child_bt_ud/*out*/)) < 0)
- HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, H5B_INS_ERROR, "can't insert subtree")
+ HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, H5B_INS_ERROR, "can't insert subtree")
} else {
- /*
- * Follow a branch out of this node to a leaf node of some other type.
- */
- HDassert(idx < bt->nchildren);
- if((int)(my_ins = (type->insert)(f, bt->child[idx], H5B_NKEY(bt, shared, idx),
+ /*
+ * Follow a branch out of this node to a leaf node of some other type.
+ */
+ HDassert(idx < bt->nchildren);
+ if((int)(my_ins = (type->insert)(f, bt->child[idx], H5B_NKEY(bt, shared, idx),
lt_key_changed, md_key, udata, H5B_NKEY(bt, shared, idx + 1),
rt_key_changed, &new_child_bt_ud.addr/*out*/)) < 0)
- HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, H5B_INS_ERROR, "can't insert leaf node")
+ HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, H5B_INS_ERROR, "can't insert leaf node")
}
HDassert((int)my_ins >= 0);
@@ -1039,40 +1039,40 @@ H5B__insert_helper(H5F_t *f, H5B_ins_ud_t *bt_ud, const H5B_class_t *type,
*/
HDassert(!(bt->level == 0) != !(child_bt_ud.bt));
if(H5B_INS_CHANGE == my_ins) {
- /*
- * The insertion simply changed the address for the child.
- */
- HDassert(!child_bt_ud.bt);
- HDassert(bt->level == 0);
- bt->child[idx] = new_child_bt_ud.addr;
+ /*
+ * The insertion simply changed the address for the child.
+ */
+ HDassert(!child_bt_ud.bt);
+ HDassert(bt->level == 0);
+ bt->child[idx] = new_child_bt_ud.addr;
bt_ud->cache_flags |= H5AC__DIRTIED_FLAG;
} else if(H5B_INS_LEFT == my_ins || H5B_INS_RIGHT == my_ins) {
unsigned *tmp_bt_flags_ptr = NULL;
- H5B_t *tmp_bt;
-
- /*
- * If this node is full then split it before inserting the new child.
- */
- if(bt->nchildren == shared->two_k) {
- if(H5B__split(f, bt_ud, idx, udata, split_bt_ud/*out*/) < 0)
- HGOTO_ERROR(H5E_BTREE, H5E_CANTSPLIT, H5B_INS_ERROR, "unable to split node")
- if(idx < bt->nchildren) {
- tmp_bt = bt;
+ H5B_t *tmp_bt;
+
+ /*
+ * If this node is full then split it before inserting the new child.
+ */
+ if(bt->nchildren == shared->two_k) {
+ if(H5B__split(f, bt_ud, idx, udata, split_bt_ud/*out*/) < 0)
+ HGOTO_ERROR(H5E_BTREE, H5E_CANTSPLIT, H5B_INS_ERROR, "unable to split node")
+ if(idx < bt->nchildren) {
+ tmp_bt = bt;
tmp_bt_flags_ptr = &bt_ud->cache_flags;
- } else {
- idx -= bt->nchildren;
- tmp_bt = split_bt_ud->bt;
+ } else {
+ idx -= bt->nchildren;
+ tmp_bt = split_bt_ud->bt;
tmp_bt_flags_ptr = &split_bt_ud->cache_flags;
- }
- } /* end if */
+ }
+ } /* end if */
else {
- tmp_bt = bt;
+ tmp_bt = bt;
tmp_bt_flags_ptr = &bt_ud->cache_flags;
- } /* end else */
+ } /* end else */
- /* Insert the child */
- if(H5B__insert_child(tmp_bt, tmp_bt_flags_ptr, idx, new_child_bt_ud.addr, my_ins, md_key) < 0)
- HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, H5B_INS_ERROR, "can't insert child")
+ /* Insert the child */
+ if(H5B__insert_child(tmp_bt, tmp_bt_flags_ptr, idx, new_child_bt_ud.addr, my_ins, md_key) < 0)
+ HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, H5B_INS_ERROR, "can't insert child")
} /* end else-if */
/*
@@ -1080,20 +1080,20 @@ H5B__insert_helper(H5F_t *f, H5B_ins_ud_t *bt_ud, const H5B_class_t *type,
* by the left and right node).
*/
if(split_bt_ud->bt) {
- HDmemcpy(md_key, H5B_NKEY(split_bt_ud->bt, shared, 0), type->sizeof_nkey);
- ret_value = H5B_INS_RIGHT;
+ HDmemcpy(md_key, H5B_NKEY(split_bt_ud->bt, shared, 0), type->sizeof_nkey);
+ ret_value = H5B_INS_RIGHT;
#ifdef H5B_DEBUG
- /*
- * The max key in the original left node must be equal to the min key
- * in the new node.
- */
- cmp = (type->cmp2)(H5B_NKEY(bt, shared, bt->nchildren), udata,
- H5B_NKEY(split_bt_ud->bt, shared, 0));
- HDassert(0 == cmp);
+ /*
+ * The max key in the original left node must be equal to the min key
+ * in the new node.
+ */
+ cmp = (type->cmp2)(H5B_NKEY(bt, shared, bt->nchildren), udata,
+ H5B_NKEY(split_bt_ud->bt, shared, 0));
+ HDassert(0 == cmp);
#endif
} /* end if */
else
- ret_value = H5B_INS_NOOP;
+ ret_value = H5B_INS_NOOP;
done:
if(child_bt_ud.bt)
@@ -1107,18 +1107,18 @@ done:
FUNC_LEAVE_NOAPI(ret_value)
} /* end H5B_insert_helper() */
-
+
/*-------------------------------------------------------------------------
- * Function: H5B__iterate_helper
+ * Function: H5B__iterate_helper
*
- * Purpose: Calls the list callback for each leaf node of the
- * B-tree, passing it the caller's UDATA structure.
+ * Purpose: Calls the list callback for each leaf node of the
+ * B-tree, passing it the caller's UDATA structure.
*
- * Return: Non-negative on success/Negative on failure
+ * Return: Non-negative on success/Negative on failure
*
- * Programmer: Robb Matzke
- * matzke@llnl.gov
- * Jun 23 1997
+ * Programmer: Robb Matzke
+ * matzke@llnl.gov
+ * Jun 23 1997
*
*-------------------------------------------------------------------------
*/
@@ -1127,7 +1127,7 @@ H5B__iterate_helper(H5F_t *f, const H5B_class_t *type, haddr_t addr,
H5B_operator_t op, void *udata)
{
H5B_t *bt = NULL; /* Pointer to current B-tree node */
- H5UC_t *rc_shared; /* Ref-counted shared info */
+ H5UC_t *rc_shared; /* Ref-counted shared info */
H5B_shared_t *shared; /* Pointer to shared B-tree info */
H5B_cache_ud_t cache_udata; /* User-data for metadata cache callback */
unsigned u; /* Local index variable */
@@ -1174,18 +1174,18 @@ done:
FUNC_LEAVE_NOAPI(ret_value)
} /* end H5B__iterate_helper() */
-
+
/*-------------------------------------------------------------------------
- * Function: H5B_iterate
+ * Function: H5B_iterate
*
- * Purpose: Calls the list callback for each leaf node of the
- * B-tree, passing it the UDATA structure.
+ * Purpose: Calls the list callback for each leaf node of the
+ * B-tree, passing it the UDATA structure.
*
- * Return: Non-negative on success/Negative on failure
+ * Return: Non-negative on success/Negative on failure
*
- * Programmer: Robb Matzke
- * matzke@llnl.gov
- * Jun 23 1997
+ * Programmer: Robb Matzke
+ * matzke@llnl.gov
+ * Jun 23 1997
*
*-------------------------------------------------------------------------
*/
@@ -1213,27 +1213,27 @@ H5B_iterate(H5F_t *f, const H5B_class_t *type, haddr_t addr,
FUNC_LEAVE_NOAPI(ret_value)
} /* end H5B_iterate() */
-
+
/*-------------------------------------------------------------------------
- * Function: H5B__remove_helper
+ * Function: H5B__remove_helper
*
- * Purpose: The recursive part of removing an item from a B-tree. The
- * sub B-tree that is being considered is located at ADDR and
- * the item to remove is described by UDATA. If the removed
- * item falls at the left or right end of the current level then
- * it might be necessary to adjust the left and/or right keys
- * (LT_KEY and/or RT_KEY) to to indicate that they changed by
- * setting LT_KEY_CHANGED and/or RT_KEY_CHANGED.
+ * Purpose: The recursive part of removing an item from a B-tree. The
+ * sub B-tree that is being considered is located at ADDR and
+ * the item to remove is described by UDATA. If the removed
+ * item falls at the left or right end of the current level then
+ * it might be necessary to adjust the left and/or right keys
+ * (LT_KEY and/or RT_KEY) to to indicate that they changed by
+ * setting LT_KEY_CHANGED and/or RT_KEY_CHANGED.
*
- * Return: Success: A B-tree operation, see comments for
- * H5B_ins_t declaration. This function is
- * called recursively and the return value
- * influences the actions of the caller. It is
- * also called by H5B_remove().
+ * Return: Success: A B-tree operation, see comments for
+ * H5B_ins_t declaration. This function is
+ * called recursively and the return value
+ * influences the actions of the caller. It is
+ * also called by H5B_remove().
*
- * Failure: H5B_INS_ERROR, a negative value.
+ * Failure: H5B_INS_ERROR, a negative value.
*
- * Programmer: Robb Matzke
+ * Programmer: Robb Matzke
* Wednesday, September 16, 1998
*
*-------------------------------------------------------------------------
@@ -1243,14 +1243,14 @@ H5B__remove_helper(H5F_t *f, haddr_t addr, const H5B_class_t *type, int level,
uint8_t *lt_key/*out*/, hbool_t *lt_key_changed/*out*/, void *udata,
uint8_t *rt_key/*out*/, hbool_t *rt_key_changed/*out*/)
{
- H5B_t *bt = NULL, *sibling = NULL;
- unsigned bt_flags = H5AC__NO_FLAGS_SET;
- H5UC_t *rc_shared; /* Ref-counted shared info */
+ H5B_t *bt = NULL, *sibling = NULL;
+ unsigned bt_flags = H5AC__NO_FLAGS_SET;
+ H5UC_t *rc_shared; /* Ref-counted shared info */
H5B_shared_t *shared; /* Pointer to shared B-tree info */
H5B_cache_ud_t cache_udata; /* User-data for metadata cache callback */
unsigned idx = 0, lt = 0, rt; /* Final, left & right indices */
int cmp = 1; /* Key comparison value */
- H5B_ins_t ret_value = H5B_INS_ERROR;
+ H5B_ins_t ret_value = H5B_INS_ERROR;
FUNC_ENTER_STATIC
@@ -1265,7 +1265,7 @@ H5B__remove_helper(H5F_t *f, haddr_t addr, const H5B_class_t *type, int level,
/* Get shared info for B-tree */
if(NULL == (rc_shared = (type->get_shared)(f, udata)))
- HGOTO_ERROR(H5E_BTREE, H5E_CANTGET, H5B_INS_ERROR, "can't retrieve B-tree's shared ref. count object")
+ HGOTO_ERROR(H5E_BTREE, H5E_CANTGET, H5B_INS_ERROR, "can't retrieve B-tree's shared ref. count object")
shared = (H5B_shared_t *)H5UC_GET_OBJ(rc_shared);
HDassert(shared);
@@ -1277,18 +1277,18 @@ H5B__remove_helper(H5F_t *f, haddr_t addr, const H5B_class_t *type, int level,
cache_udata.type = type;
cache_udata.rc_shared = rc_shared;
if(NULL == (bt = (H5B_t *)H5AC_protect(f, H5AC_BT, addr, &cache_udata, H5AC__NO_FLAGS_SET)))
- HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, H5B_INS_ERROR, "unable to load B-tree node")
+ HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, H5B_INS_ERROR, "unable to load B-tree node")
rt = bt->nchildren;
while(lt < rt && cmp) {
- idx = (lt + rt) / 2;
- if((cmp = (type->cmp3)(H5B_NKEY(bt, shared, idx), udata, H5B_NKEY(bt, shared, idx + 1))) < 0)
- rt = idx;
- else
- lt = idx + 1;
+ idx = (lt + rt) / 2;
+ if((cmp = (type->cmp3)(H5B_NKEY(bt, shared, idx), udata, H5B_NKEY(bt, shared, idx + 1))) < 0)
+ rt = idx;
+ else
+ lt = idx + 1;
} /* end while */
if(cmp)
- HGOTO_ERROR(H5E_BTREE, H5E_NOTFOUND, H5B_INS_ERROR, "B-tree key not found")
+ HGOTO_ERROR(H5E_BTREE, H5E_NOTFOUND, H5B_INS_ERROR, "B-tree key not found")
/*
* Follow the link to the subtree or to the data node. The return value
@@ -1296,31 +1296,31 @@ H5B__remove_helper(H5F_t *f, haddr_t addr, const H5B_class_t *type, int level,
*/
HDassert(idx < bt->nchildren);
if(bt->level > 0) {
- /* We're at an internal node -- call recursively */
- if((int)(ret_value = H5B__remove_helper(f, bt->child[idx], type,
+ /* We're at an internal node -- call recursively */
+ if((int)(ret_value = H5B__remove_helper(f, bt->child[idx], type,
level + 1, H5B_NKEY(bt, shared, idx)/*out*/,
lt_key_changed/*out*/, udata, H5B_NKEY(bt, shared, idx + 1)/*out*/,
rt_key_changed/*out*/)) < 0)
- HGOTO_ERROR(H5E_BTREE, H5E_NOTFOUND, H5B_INS_ERROR, "key not found in subtree")
+ HGOTO_ERROR(H5E_BTREE, H5E_NOTFOUND, H5B_INS_ERROR, "key not found in subtree")
} else if(type->remove) {
- /*
- * We're at a leaf node but the leaf node points to an object that
- * has a removal method. Pass the removal request to the pointed-to
- * object and let it decide how to progress.
- */
- if((int)(ret_value = (type->remove)(f, bt->child[idx],
+ /*
+ * We're at a leaf node but the leaf node points to an object that
+ * has a removal method. Pass the removal request to the pointed-to
+ * object and let it decide how to progress.
+ */
+ if((int)(ret_value = (type->remove)(f, bt->child[idx],
H5B_NKEY(bt, shared, idx), lt_key_changed, udata,
H5B_NKEY(bt, shared, idx + 1), rt_key_changed)) < 0)
- HGOTO_ERROR(H5E_BTREE, H5E_NOTFOUND, H5B_INS_ERROR, "key not found in leaf node")
+ HGOTO_ERROR(H5E_BTREE, H5E_NOTFOUND, H5B_INS_ERROR, "key not found in leaf node")
} else {
- /*
- * We're at a leaf node which points to an object that has no removal
- * method. The best we can do is to leave the object alone but
- * remove the B-tree reference to the object.
- */
- *lt_key_changed = FALSE;
- *rt_key_changed = FALSE;
- ret_value = H5B_INS_REMOVE;
+ /*
+ * We're at a leaf node which points to an object that has no removal
+ * method. The best we can do is to leave the object alone but
+ * remove the B-tree reference to the object.
+ */
+ *lt_key_changed = FALSE;
+ *rt_key_changed = FALSE;
+ ret_value = H5B_INS_REMOVE;
}
/*
@@ -1416,7 +1416,7 @@ H5B__remove_helper(H5F_t *f, haddr_t addr, const H5B_class_t *type, int level,
bt->nchildren = 0;
/* Delete the node from disk (via the metadata cache) */
- bt_flags |= H5AC__DIRTIED_FLAG | H5AC__FREE_FILE_SPACE_FLAG;
+ bt_flags |= H5AC__DIRTIED_FLAG | H5AC__FREE_FILE_SPACE_FLAG;
H5_CHECK_OVERFLOW(shared->sizeof_rnode, size_t, hsize_t);
if(H5AC_unprotect(f, H5AC_BT, addr, bt, bt_flags | H5AC__DELETED_FLAG) < 0) {
bt = NULL;
@@ -1541,24 +1541,24 @@ H5B__remove_helper(H5F_t *f, haddr_t addr, const H5B_class_t *type, int level,
done:
if(bt && H5AC_unprotect(f, H5AC_BT, addr, bt, bt_flags) < 0)
- HDONE_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, H5B_INS_ERROR, "unable to release node")
+ HDONE_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, H5B_INS_ERROR, "unable to release node")
FUNC_LEAVE_NOAPI(ret_value)
} /* end H5B__remove_helper() */
-
+
/*-------------------------------------------------------------------------
- * Function: H5B_remove
+ * Function: H5B_remove
*
- * Purpose: Removes an item from a B-tree.
+ * Purpose: Removes an item from a B-tree.
*
- * Note: The current version does not attempt to rebalance the tree.
+ * Note: The current version does not attempt to rebalance the tree.
* (Read the paper Yao & Lehman paper for details on why)
*
- * Return: Non-negative on success/Negative on failure (failure includes
- * not being able to find the object which is to be removed).
+ * Return: Non-negative on success/Negative on failure (failure includes
+ * not being able to find the object which is to be removed).
*
- * Programmer: Robb Matzke
+ * Programmer: Robb Matzke
* Wednesday, September 16, 1998
*
*-------------------------------------------------------------------------
@@ -1567,11 +1567,11 @@ herr_t
H5B_remove(H5F_t *f, const H5B_class_t *type, haddr_t addr, void *udata)
{
/* These are defined this way to satisfy alignment constraints */
- uint64_t _lt_key[128], _rt_key[128];
- uint8_t *lt_key = (uint8_t*)_lt_key; /*left key*/
- uint8_t *rt_key = (uint8_t*)_rt_key; /*right key*/
- hbool_t lt_key_changed = FALSE; /*left key changed?*/
- hbool_t rt_key_changed = FALSE; /*right key changed?*/
+ uint64_t _lt_key[128], _rt_key[128];
+ uint8_t *lt_key = (uint8_t*)_lt_key; /*left key*/
+ uint8_t *rt_key = (uint8_t*)_rt_key; /*right key*/
+ hbool_t lt_key_changed = FALSE; /*left key changed?*/
+ hbool_t rt_key_changed = FALSE; /*right key changed?*/
herr_t ret_value = SUCCEED; /* Return value */
FUNC_ENTER_NOAPI(FAIL)
@@ -1584,7 +1584,7 @@ H5B_remove(H5F_t *f, const H5B_class_t *type, haddr_t addr, void *udata)
/* The actual removal */
if(H5B_INS_ERROR == H5B__remove_helper(f, addr, type, 0, lt_key, &lt_key_changed, udata, rt_key, &rt_key_changed))
- HGOTO_ERROR(H5E_BTREE, H5E_CANTINIT, FAIL, "unable to remove entry from B-tree")
+ HGOTO_ERROR(H5E_BTREE, H5E_CANTINIT, FAIL, "unable to remove entry from B-tree")
#ifdef H5B_DEBUG
H5B__assert(f, addr, type, udata);
@@ -1593,16 +1593,16 @@ done:
FUNC_LEAVE_NOAPI(ret_value)
} /* end H5B_remove() */
-
+
/*-------------------------------------------------------------------------
- * Function: H5B_delete
+ * Function: H5B_delete
*
- * Purpose: Deletes an entire B-tree from the file, calling the 'remove'
+ * Purpose: Deletes an entire B-tree from the file, calling the 'remove'
* callbacks for each node.
*
- * Return: Non-negative on success/Negative on failure
+ * Return: Non-negative on success/Negative on failure
*
- * Programmer: Quincey Koziol
+ * Programmer: Quincey Koziol
* Thursday, March 20, 2003
*
*-------------------------------------------------------------------------
@@ -1610,8 +1610,8 @@ done:
herr_t
H5B_delete(H5F_t *f, const H5B_class_t *type, haddr_t addr, void *udata)
{
- H5B_t *bt = NULL; /* B-tree node being operated on */
- H5UC_t *rc_shared; /* Ref-counted shared info */
+ H5B_t *bt = NULL; /* B-tree node being operated on */
+ H5UC_t *rc_shared; /* Ref-counted shared info */
H5B_shared_t *shared; /* Pointer to shared B-tree info */
H5B_cache_ud_t cache_udata; /* User-data for metadata cache callback */
unsigned u; /* Local index variable */
@@ -1668,18 +1668,18 @@ done:
FUNC_LEAVE_NOAPI(ret_value)
} /* end H5B_delete() */
-
+
/*-------------------------------------------------------------------------
- * Function: H5B_shared_new
+ * Function: H5B_shared_new
*
- * Purpose: Allocates & constructs a shared v1 B-tree struct for client.
+ * Purpose: Allocates & constructs a shared v1 B-tree struct for client.
*
- * Return: Success: non-NULL pointer to struct allocated
- * Failure: NULL
+ * Return: Success: non-NULL pointer to struct allocated
+ * Failure: NULL
*
- * Programmer: Quincey Koziol
- * koziol@hdfgroup.org
- * May 27 2008
+ * Programmer: Quincey Koziol
+ * koziol@hdfgroup.org
+ * May 27 2008
*
*-------------------------------------------------------------------------
*/
@@ -1687,7 +1687,7 @@ H5B_shared_t *
H5B_shared_new(const H5F_t *f, const H5B_class_t *type, size_t sizeof_rkey)
{
H5B_shared_t *shared = NULL; /* New shared B-tree struct */
- size_t u; /* Local index variable */
+ size_t u; /* Local index variable */
H5B_shared_t *ret_value = NULL; /* Return value */
FUNC_ENTER_NOAPI(NULL)
@@ -1699,7 +1699,7 @@ H5B_shared_new(const H5F_t *f, const H5B_class_t *type, size_t sizeof_rkey)
/* Allocate space for the shared structure */
if(NULL == (shared = H5FL_CALLOC(H5B_shared_t)))
- HGOTO_ERROR(H5E_BTREE, H5E_CANTALLOC, NULL, "memory allocation failed for shared B-tree info")
+ 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 */
shared->type = type;
@@ -1709,9 +1709,9 @@ H5B_shared_new(const H5F_t *f, const H5B_class_t *type, size_t sizeof_rkey)
shared->sizeof_rkey = sizeof_rkey;
HDassert(shared->sizeof_rkey);
shared->sizeof_keys = (shared->two_k + 1) * type->sizeof_nkey;
- shared->sizeof_rnode = ((size_t)H5B_SIZEOF_HDR(f) + /*node header */
- shared->two_k * H5F_SIZEOF_ADDR(f) + /*child pointers */
- (shared->two_k + 1) * shared->sizeof_rkey); /*keys */
+ shared->sizeof_rnode = ((size_t)H5B_SIZEOF_HDR(f) + /*node header */
+ shared->two_k * H5F_SIZEOF_ADDR(f) + /*child pointers */
+ (shared->two_k + 1) * shared->sizeof_rkey); /*keys */
HDassert(shared->sizeof_rnode);
/* Allocate and clear shared buffers */
@@ -1742,15 +1742,15 @@ done:
FUNC_LEAVE_NOAPI(ret_value)
} /* end H5B_shared_new() */
-
+
/*-------------------------------------------------------------------------
- * Function: H5B_shared_free
+ * Function: H5B_shared_free
*
- * Purpose: Free B-tree shared info
+ * Purpose: Free B-tree shared info
*
- * Return: Non-negative on success/Negative on failure
+ * Return: Non-negative on success/Negative on failure
*
- * Programmer: Quincey Koziol
+ * Programmer: Quincey Koziol
* Tuesday, May 27, 2008
*
*-------------------------------------------------------------------------
@@ -1774,28 +1774,28 @@ H5B_shared_free(void *_shared)
FUNC_LEAVE_NOAPI(SUCCEED)
} /* end H5B_shared_free() */
-
+
/*-------------------------------------------------------------------------
- * Function: H5B__copy
+ * Function: H5B__copy
*
- * Purpose: Deep copies an existing H5B_t node.
+ * Purpose: Deep copies an existing H5B_t node.
*
- * Return: Success: Pointer to H5B_t object.
+ * Return: Success: Pointer to H5B_t object.
*
- * Failure: NULL
+ * Failure: NULL
*
- * Programmer: Quincey Koziol
- * koziol@ncsa.uiuc.edu
- * Apr 18 2000
+ * Programmer: Quincey Koziol
+ * koziol@ncsa.uiuc.edu
+ * Apr 18 2000
*
*-------------------------------------------------------------------------
*/
static H5B_t *
H5B__copy(const H5B_t *old_bt)
{
- H5B_t *new_node = NULL;
+ H5B_t *new_node = NULL;
H5B_shared_t *shared; /* Pointer to shared B-tree info */
- H5B_t *ret_value = NULL; /* Return value */
+ H5B_t *ret_value = NULL; /* Return value */
FUNC_ENTER_STATIC
@@ -1833,26 +1833,26 @@ H5B__copy(const H5B_t *old_bt)
done:
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);
- new_node = H5FL_FREE(H5B_t, new_node);
+ new_node->native = H5FL_BLK_FREE(native_block, new_node->native);
+ new_node->child = H5FL_SEQ_FREE(haddr_t, new_node->child);
+ new_node = H5FL_FREE(H5B_t, new_node);
} /* end if */
} /* end if */
FUNC_LEAVE_NOAPI(ret_value)
} /* end H5B__copy() */
-
+
/*-------------------------------------------------------------------------
- * Function: H5B__get_info_helper
+ * Function: H5B__get_info_helper
*
- * Purpose: Walks the B-tree nodes, getting information for all of them.
+ * Purpose: Walks the B-tree nodes, getting information for all of them.
*
- * Return: Non-negative on success/Negative on failure
+ * Return: Non-negative on success/Negative on failure
*
- * Programmer: Quincey Koziol
- * koziol@hdfgroup.org
- * Jun 3 2008
+ * Programmer: Quincey Koziol
+ * koziol@hdfgroup.org
+ * Jun 3 2008
*
*-------------------------------------------------------------------------
*/
@@ -1864,8 +1864,8 @@ H5B__get_info_helper(H5F_t *f, const H5B_class_t *type, haddr_t addr,
H5UC_t *rc_shared; /* Ref-counted shared info */
H5B_shared_t *shared; /* Pointer to shared B-tree info */
H5B_cache_ud_t cache_udata; /* User-data for metadata cache callback */
- unsigned level; /* Node level */
- size_t sizeof_rnode; /* Size of raw (disk) node */
+ unsigned level; /* Node level */
+ size_t sizeof_rnode; /* Size of raw (disk) node */
haddr_t next_addr; /* Address of next node to the right */
haddr_t left_child; /* Address of left-most child in node */
herr_t ret_value = SUCCEED; /* Return value */
@@ -1884,7 +1884,7 @@ H5B__get_info_helper(H5F_t *f, const H5B_class_t *type, haddr_t addr,
/* Get shared info for B-tree */
if(NULL == (rc_shared = (type->get_shared)(f, info_udata->udata)))
- HGOTO_ERROR(H5E_BTREE, H5E_CANTGET, FAIL, "can't retrieve B-tree's shared ref. count object")
+ HGOTO_ERROR(H5E_BTREE, H5E_CANTGET, FAIL, "can't retrieve B-tree's shared ref. count object")
shared = (H5B_shared_t *)H5UC_GET_OBJ(rc_shared);
HDassert(shared);
@@ -1896,7 +1896,7 @@ H5B__get_info_helper(H5F_t *f, const H5B_class_t *type, haddr_t addr,
cache_udata.type = type;
cache_udata.rc_shared = rc_shared;
if(NULL == (bt = (H5B_t *)H5AC_protect(f, H5AC_BT, addr, &cache_udata, H5AC__READ_ONLY_FLAG)))
- HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to load B-tree node")
+ HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to load B-tree node")
/* Cache information from this node */
left_child = bt->child[0];
@@ -1937,9 +1937,9 @@ H5B__get_info_helper(H5F_t *f, const H5B_class_t *type, haddr_t addr,
/* Check for another "row" of B-tree nodes to iterate over */
if(level > 0) {
- /* Keep following the left-most child until we reach a leaf node. */
- if(H5B__get_info_helper(f, type, left_child, info_udata) < 0)
- HGOTO_ERROR(H5E_BTREE, H5E_CANTLIST, FAIL, "unable to list B-tree node")
+ /* Keep following the left-most child until we reach a leaf node. */
+ if(H5B__get_info_helper(f, type, left_child, info_udata) < 0)
+ HGOTO_ERROR(H5E_BTREE, H5E_CANTLIST, FAIL, "unable to list B-tree node")
} /* end if */
done:
@@ -1949,7 +1949,7 @@ done:
FUNC_LEAVE_NOAPI(ret_value)
} /* end H5B__get_info_helper() */
-
+
/*-------------------------------------------------------------------------
* Function: H5B_get_info
*
@@ -1967,7 +1967,7 @@ H5B_get_info(H5F_t *f, const H5B_class_t *type, haddr_t addr,
H5B_info_t *bt_info, H5B_operator_t op, void *udata)
{
H5B_info_ud_t info_udata; /* User-data for B-tree size iteration */
- herr_t ret_value = SUCCEED; /* Return value */
+ herr_t ret_value = SUCCEED; /* Return value */
FUNC_ENTER_NOAPI(FAIL)
@@ -2001,7 +2001,7 @@ done:
FUNC_LEAVE_NOAPI(ret_value)
} /* end H5B_get_info() */
-
+
/*-------------------------------------------------------------------------
* Function: H5B_valid
*
@@ -2021,7 +2021,7 @@ H5B_valid(H5F_t *f, const H5B_class_t *type, haddr_t addr)
H5UC_t *rc_shared; /* Ref-counted shared info */
H5B_shared_t *shared; /* Pointer to shared B-tree info */
H5B_cache_ud_t cache_udata; /* User-data for metadata cache callback */
- htri_t ret_value = SUCCEED; /* Return value */
+ htri_t ret_value = SUCCEED; /* Return value */
FUNC_ENTER_NOAPI(FAIL)
@@ -2036,7 +2036,7 @@ H5B_valid(H5F_t *f, const H5B_class_t *type, haddr_t addr)
/* Get shared info for B-tree */
if(NULL == (rc_shared = (type->get_shared)(f, NULL)))
- HGOTO_ERROR(H5E_BTREE, H5E_CANTGET, FAIL, "can't retrieve B-tree's shared ref. count object")
+ HGOTO_ERROR(H5E_BTREE, H5E_CANTGET, FAIL, "can't retrieve B-tree's shared ref. count object")
shared = (H5B_shared_t *)H5UC_GET_OBJ(rc_shared);
HDassert(shared);
@@ -2047,7 +2047,7 @@ H5B_valid(H5F_t *f, const H5B_class_t *type, haddr_t addr)
cache_udata.type = type;
cache_udata.rc_shared = rc_shared;
if(NULL == (bt = (H5B_t *)H5AC_protect(f, H5AC_BT, addr, &cache_udata, H5AC__READ_ONLY_FLAG)))
- HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to protect B-tree node")
+ HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to protect B-tree node")
done:
/* Release the node */
@@ -2057,7 +2057,7 @@ done:
FUNC_LEAVE_NOAPI(ret_value)
} /* end H5B_valid() */
-
+
/*-------------------------------------------------------------------------
* Function: H5B__node_dest
*