diff options
author | Allen Byrne <byrn@hdfgroup.org> | 2019-08-23 19:09:20 (GMT) |
---|---|---|
committer | Allen Byrne <byrn@hdfgroup.org> | 2019-08-23 19:09:20 (GMT) |
commit | d20d355b79bf25d2685dc9e3967951b1532951bb (patch) | |
tree | c862028f2d6c7ea540c6ffd2ca34d6ac9b715686 /src/H5B.c | |
parent | c951ee8eded3cd63adfeaa87dcdd966ceb3e58c1 (diff) | |
download | hdf5-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.c | 834 |
1 files changed, 417 insertions, 417 deletions
@@ -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, <_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, <_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 * |