/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

 * Copyright by The HDF Group.                                               *

 * All rights reserved.                                                      *

 *                                                                           *

 * This file is part of HDF5.  The full HDF5 copyright notice, including     *

 * terms governing use, modification, and redistribution, is contained in    *

 * the COPYING file, which can be found at the root of the source code       *

 * distribution tree, or in https://www.hdfgroup.org/licenses.               *

 * If you do not have access to either file, you may request a copy from     *

 * help@hdfgroup.org.                                                        *

 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */

/*-------------------------------------------------------------------------

 *

 * Created:   H5B2int.c

 *

 * Purpose:   Internal routines for managing v2 B-trees.

 *

 *-------------------------------------------------------------------------

 */

/****************/

/* Module Setup */

/****************/

#include "H5B2module.h" /* This source code file is part of the H5B2 module */

/***********/

/* Headers */

/***********/

#include "H5private.h"   /* Generic Functions     */

#include "H5B2pkg.h"     /* v2 B-trees        */

#include "H5Eprivate.h"  /* Error handling        */

#include "H5FLprivate.h" /* Free Lists                               */

#include "H5MMprivate.h" /* Memory management     */

#include "H5VMprivate.h" /* Vectors and arrays      */

/****************/

/* Local Macros */

/****************/

/******************/

/* Local Typedefs */

/******************/

/********************/

/* Package Typedefs */

/********************/

/********************/

/* Local Prototypes */

/********************/

static herr_t H5B2__update_child_flush_depends(H5B2_hdr_t *hdr, unsigned depth, H5B2_node_ptr_t *node_ptrs,

                                               unsigned start_idx, unsigned end_idx, void *old_parent,

                                               void *new_parent);

/*********************/

/* Package Variables */

/*********************/

/*****************************/

/* Library Private Variables */

/*****************************/

/*******************/

/* Local Variables */

/*******************/

/* Declare a free list to manage the 'H5B2_node_info_t' sequence information */

H5FL_SEQ_EXTERN(H5B2_node_info_t);

/*-------------------------------------------------------------------------

 * Function:  H5B2__locate_record

 *

 * Purpose: Performs a binary search to locate a record in a sorted

 *              array of records.

 *

 *              Sets *IDX to location of record greater than or equal to

 *              record to locate.

 *

 * Return:  Comparison value for insertion location.  Negative for record

 *              to locate being less than value in *IDX.  Zero for record to

 *              locate equal to value in *IDX.  Positive for record to locate

 *              being greater than value in *IDX (which should only happen when

 *              record to locate is greater than all records to search).

 *

 *-------------------------------------------------------------------------

 */

herr_t

H5B2__locate_record(const H5B2_class_t *type, unsigned nrec, size_t *rec_off, const uint8_t *native,

                    const void *udata, unsigned *idx, int *cmp)

{

    unsigned lo        = 0, hi; /* Low & high index values */

    unsigned my_idx    = 0;     /* Final index value */

    herr_t   ret_value = SUCCEED;

    FUNC_ENTER_PACKAGE

    *cmp = -1;

    hi = nrec;

    while (lo < hi && *cmp) {

        my_idx = (lo + hi) / 2;

        if ((type->compare)(udata, native + rec_off[my_idx], cmp) < 0)

            HGOTO_ERROR(H5E_BTREE, H5E_CANTCOMPARE, FAIL, "can't compare btree2 records");

        if (*cmp < 0)

            hi = my_idx;

        else

            lo = my_idx + 1;

    } /* end while */

    *idx = my_idx;

done:

    FUNC_LEAVE_NOAPI(ret_value)

} /* end H5B2__locate_record */

/*-------------------------------------------------------------------------

 * Function:  H5B2__split1

 *

 * Purpose: Perform a 1->2 node split

 *

 * Return:  Success:  Non-negative

 *    Failure:  Negative

 *

 *-------------------------------------------------------------------------

 */

herr_t

H5B2__split1(H5B2_hdr_t *hdr, uint16_t depth, H5B2_node_ptr_t *curr_node_ptr,

             unsigned *parent_cache_info_flags_ptr, H5B2_internal_t *internal, unsigned *internal_flags_ptr,

             unsigned idx)

{

    const H5AC_class_t *child_class;                             /* Pointer to child node's class info */

    haddr_t   left_addr = HADDR_UNDEF, right_addr = HADDR_UNDEF; /* Addresses of left & right child nodes */

    void     *left_child = NULL, *right_child = NULL;            /* Pointers to child nodes */

    uint16_t *left_nrec, *right_nrec;                            /* Pointers to child # of records */

    uint8_t  *left_native, *right_native;                        /* Pointers to childs' native records */

    H5B2_node_ptr_t *left_node_ptrs  = NULL,

                    *right_node_ptrs = NULL; /* Pointers to childs' node pointer info */

    uint16_t mid_record;                     /* Index of "middle" record in current node */

    uint16_t old_node_nrec;                  /* Number of records in internal node split */

    unsigned left_child_flags  = H5AC__NO_FLAGS_SET,

             right_child_flags = H5AC__NO_FLAGS_SET; /* Flags for unprotecting child nodes */

    herr_t ret_value           = SUCCEED;            /* Return value */

    FUNC_ENTER_PACKAGE

    /* Check arguments. */

    assert(hdr);

    assert(internal);

    assert(internal_flags_ptr);

    /* Slide records in parent node up one space, to make room for promoted record */

    if (idx < internal->nrec) {

        memmove(H5B2_INT_NREC(internal, hdr, idx + 1), H5B2_INT_NREC(internal, hdr, idx),

                hdr->cls->nrec_size * (internal->nrec - idx));

        memmove(&(internal->node_ptrs[idx + 2]), &(internal->node_ptrs[idx + 1]),

                sizeof(H5B2_node_ptr_t) * (internal->nrec - idx));

    } /* end if */

    /* Check for the kind of B-tree node to split */

    if (depth > 1) {

        H5B2_internal_t *left_int = NULL, *right_int = NULL; /* Pointers to old & new internal nodes */

        /* Create new internal node */

        internal->node_ptrs[idx + 1].all_nrec = internal->node_ptrs[idx + 1].node_nrec = 0;

        if (H5B2__create_internal(hdr, internal, &(internal->node_ptrs[idx + 1]), (uint16_t)(depth - 1)) < 0)

            HGOTO_ERROR(H5E_BTREE, H5E_CANTINIT, FAIL, "unable to create new internal node");

        /* Setup information for unlocking child nodes */

        child_class = H5AC_BT2_INT;

        /* Protect both leaves */

        /* (Shadow left node if doing SWMR writes) */

        if (NULL ==

            (left_int = H5B2__protect_internal(hdr, internal, &internal->node_ptrs[idx],

                                               (uint16_t)(depth - 1), hdr->swmr_write, H5AC__NO_FLAGS_SET)))

            HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to protect B-tree internal node");

        left_addr = internal->node_ptrs[idx].addr;

        if (NULL == (right_int = H5B2__protect_internal(hdr, internal, &internal->node_ptrs[idx + 1],

                                                        (uint16_t)(depth - 1), false, H5AC__NO_FLAGS_SET)))

            HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to protect B-tree internal node");

        right_addr = internal->node_ptrs[idx + 1].addr;

        /* More setup for child nodes */

        left_child      = left_int;

        right_child     = right_int;

        left_nrec       = &(left_int->nrec);

        right_nrec      = &(right_int->nrec);

        left_native     = left_int->int_native;

        right_native    = right_int->int_native;

        left_node_ptrs  = left_int->node_ptrs;

        right_node_ptrs = right_int->node_ptrs;

    } /* end if */

    else {

        H5B2_leaf_t *left_leaf = NULL, *right_leaf = NULL; /* Pointers to old & new leaf nodes */

        /* Create new leaf node */

        internal->node_ptrs[idx + 1].all_nrec = internal->node_ptrs[idx + 1].node_nrec = 0;

        if (H5B2__create_leaf(hdr, internal, &(internal->node_ptrs[idx + 1])) < 0)

            HGOTO_ERROR(H5E_BTREE, H5E_CANTINIT, FAIL, "unable to create new leaf node");

        /* Setup information for unlocking child nodes */

        child_class = H5AC_BT2_LEAF;

        /* Protect both leaves */

        /* (Shadow the left node if doing SWMR writes) */

        if (NULL == (left_leaf = H5B2__protect_leaf(hdr, internal, &internal->node_ptrs[idx], hdr->swmr_write,

                                                    H5AC__NO_FLAGS_SET)))

            HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to protect B-tree leaf node");

        left_addr = internal->node_ptrs[idx].addr;

        if (NULL == (right_leaf = H5B2__protect_leaf(hdr, internal, &internal->node_ptrs[idx + 1], false,

                                                     H5AC__NO_FLAGS_SET)))

            HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to protect B-tree leaf node");

        right_addr = internal->node_ptrs[idx + 1].addr;

        /* More setup for child nodes */

        left_child   = left_leaf;

        right_child  = right_leaf;

        left_nrec    = &(left_leaf->nrec);

        right_nrec   = &(right_leaf->nrec);

        left_native  = left_leaf->leaf_native;

        right_native = right_leaf->leaf_native;

    } /* end if */

    /* Get the number of records in node to split */

    old_node_nrec = internal->node_ptrs[idx].node_nrec;

    /* Determine "middle" record to promote to internal node */

    mid_record = (uint16_t)(old_node_nrec / 2);

    /* Copy "upper half" of records to new child */

    H5MM_memcpy(H5B2_NAT_NREC(right_native, hdr, 0),

                H5B2_NAT_NREC(left_native, hdr, mid_record + (unsigned)1),

                hdr->cls->nrec_size * (old_node_nrec - (mid_record + (unsigned)1)));

    /* Copy "upper half" of node pointers, if the node is an internal node */

    if (depth > 1)

        H5MM_memcpy(&(right_node_ptrs[0]), &(left_node_ptrs[mid_record + (unsigned)1]),

                    sizeof(H5B2_node_ptr_t) * (size_t)(old_node_nrec - mid_record));

    /* Copy "middle" record to internal node */

    H5MM_memcpy(H5B2_INT_NREC(internal, hdr, idx), H5B2_NAT_NREC(left_native, hdr, mid_record),

                hdr->cls->nrec_size);

    /* Mark nodes as dirty */

    left_child_flags |= H5AC__DIRTIED_FLAG;

    right_child_flags |= H5AC__DIRTIED_FLAG;

    /* Update record counts in child nodes */

    internal->node_ptrs[idx].node_nrec = *left_nrec = mid_record;

    internal->node_ptrs[idx + 1].node_nrec = *right_nrec = (uint16_t)(old_node_nrec - (mid_record + 1));

    /* Determine total number of records in new child nodes */

    if (depth > 1) {

        unsigned u;                  /* Local index variable */

        hsize_t  new_left_all_nrec;  /* New total number of records in left child */

        hsize_t  new_right_all_nrec; /* New total number of records in right child */

        /* Compute total of all records in each child node */

        new_left_all_nrec = internal->node_ptrs[idx].node_nrec;

        for (u = 0; u < (*left_nrec + (unsigned)1); u++)

            new_left_all_nrec += left_node_ptrs[u].all_nrec;

        new_right_all_nrec = internal->node_ptrs[idx + 1].node_nrec;

        for (u = 0; u < (*right_nrec + (unsigned)1); u++)

            new_right_all_nrec += right_node_ptrs[u].all_nrec;

        internal->node_ptrs[idx].all_nrec     = new_left_all_nrec;

        internal->node_ptrs[idx + 1].all_nrec = new_right_all_nrec;

    } /* end if */

    else {

        internal->node_ptrs[idx].all_nrec     = internal->node_ptrs[idx].node_nrec;

        internal->node_ptrs[idx + 1].all_nrec = internal->node_ptrs[idx + 1].node_nrec;

    } /* end else */

    /* Update # of records in parent node */

    internal->nrec++;

    /* Mark parent as dirty */

    *internal_flags_ptr |= H5AC__DIRTIED_FLAG;

    /* Update grandparent info */

    curr_node_ptr->node_nrec++;

    /* Mark grandparent as dirty, if given */

    if (parent_cache_info_flags_ptr)

        *parent_cache_info_flags_ptr |= H5AC__DIRTIED_FLAG;

    /* Update flush dependencies for grandchildren, if using SWMR */

    if (hdr->swmr_write && depth > 1)

        if (H5B2__update_child_flush_depends(hdr, depth, right_node_ptrs, 0, (unsigned)(*right_nrec + 1),

                                             left_child, right_child) < 0)

            HGOTO_ERROR(H5E_BTREE, H5E_CANTUPDATE, FAIL, "unable to update child nodes to new parent");

#ifdef H5B2_DEBUG

    H5B2__assert_internal((hsize_t)0, hdr, internal);

    if (depth > 1) {

        H5B2__assert_internal2(internal->node_ptrs[idx].all_nrec, hdr, (H5B2_internal_t *)left_child,

                               (H5B2_internal_t *)right_child);

        H5B2__assert_internal2(internal->node_ptrs[idx + 1].all_nrec, hdr, (H5B2_internal_t *)right_child,

                               (H5B2_internal_t *)left_child);

    } /* end if */

    else {

        H5B2__assert_leaf2(hdr, (H5B2_leaf_t *)left_child, (H5B2_leaf_t *)right_child);

        H5B2__assert_leaf(hdr, (H5B2_leaf_t *)right_child);

    }  /* end else */

#endif /* H5B2_DEBUG */

done:

    /* Release child nodes (marked as dirty) */

    if (left_child && H5AC_unprotect(hdr->f, child_class, left_addr, left_child, left_child_flags) < 0)

        HDONE_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release B-tree leaf node");

    if (right_child && H5AC_unprotect(hdr->f, child_class, right_addr, right_child, right_child_flags) < 0)

        HDONE_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release B-tree leaf node");

    FUNC_LEAVE_NOAPI(ret_value)

} /* end H5B2__split1() */

/*-------------------------------------------------------------------------

 * Function:  H5B2__split_root

 *

 * Purpose: Split the root node

 *

 * Return:  Success:  Non-negative

 *    Failure:  Negative

 *

 *-------------------------------------------------------------------------

 */

herr_t

H5B2__split_root(H5B2_hdr_t *hdr)

{

    H5B2_internal_t *new_root       = NULL;               /* Pointer to new root node */

    unsigned         new_root_flags = H5AC__NO_FLAGS_SET; /* Cache flags for new root node */

    H5B2_node_ptr_t  old_root_ptr;                        /* Old node pointer to root node in B-tree */

    size_t           sz_max_nrec;                         /* Temporary variable for range checking */

    unsigned         u_max_nrec_size;                     /* Temporary variable for range checking */

    herr_t           ret_value = SUCCEED;                 /* Return value */

    FUNC_ENTER_PACKAGE

    /* Check arguments. */

    assert(hdr);

    /* Update depth of B-tree */

    hdr->depth++;

    /* Re-allocate array of node info structs */

    if (NULL ==

        (hdr->node_info = H5FL_SEQ_REALLOC(H5B2_node_info_t, hdr->node_info, (size_t)(hdr->depth + 1))))

        HGOTO_ERROR(H5E_RESOURCE, H5E_NOSPACE, FAIL, "memory allocation failed");

    /* Update node info for new depth of tree */

    sz_max_nrec = H5B2_NUM_INT_REC(hdr, hdr->depth);

    H5_CHECKED_ASSIGN(hdr->node_info[hdr->depth].max_nrec, unsigned, sz_max_nrec, size_t);

    hdr->node_info[hdr->depth].split_nrec = (hdr->node_info[hdr->depth].max_nrec * hdr->split_percent) / 100;

    hdr->node_info[hdr->depth].merge_nrec = (hdr->node_info[hdr->depth].max_nrec * hdr->merge_percent) / 100;

    hdr->node_info[hdr->depth].cum_max_nrec =

        ((hdr->node_info[hdr->depth].max_nrec + 1) * hdr->node_info[hdr->depth - 1].cum_max_nrec) +

        hdr->node_info[hdr->depth].max_nrec;

    u_max_nrec_size = H5VM_limit_enc_size((uint64_t)hdr->node_info[hdr->depth].cum_max_nrec);

    H5_CHECKED_ASSIGN(hdr->node_info[hdr->depth].cum_max_nrec_size, uint8_t, u_max_nrec_size, unsigned);

    if (NULL == (hdr->node_info[hdr->depth].nat_rec_fac =

                     H5FL_fac_init(hdr->cls->nrec_size * hdr->node_info[hdr->depth].max_nrec)))

        HGOTO_ERROR(H5E_RESOURCE, H5E_CANTINIT, FAIL, "can't create node native key block factory");

    if (NULL == (hdr->node_info[hdr->depth].node_ptr_fac =

                     H5FL_fac_init(sizeof(H5B2_node_ptr_t) * (hdr->node_info[hdr->depth].max_nrec + 1))))

        HGOTO_ERROR(H5E_RESOURCE, H5E_CANTINIT, FAIL,

                    "can't create internal 'branch' node node pointer block factory");

    /* Keep old root node pointer info */

    old_root_ptr = hdr->root;

    /* Create new internal node to use as root */

    hdr->root.node_nrec = 0;

    if (H5B2__create_internal(hdr, hdr, &(hdr->root), hdr->depth) < 0)

        HGOTO_ERROR(H5E_BTREE, H5E_CANTINIT, FAIL, "unable to create new internal node");

    /* Protect new root node */

    if (NULL ==

        (new_root = H5B2__protect_internal(hdr, hdr, &hdr->root, hdr->depth, false, H5AC__NO_FLAGS_SET)))

        HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to protect B-tree internal node");

    /* Set first node pointer in root node to old root node pointer info */

    new_root->node_ptrs[0] = old_root_ptr;

    /* Split original root node */

    if (H5B2__split1(hdr, hdr->depth, &(hdr->root), NULL, new_root, &new_root_flags, 0) < 0)

        HGOTO_ERROR(H5E_BTREE, H5E_CANTSPLIT, FAIL, "unable to split old root node");

done:

    /* Release new root node (marked as dirty) */

    if (new_root && H5AC_unprotect(hdr->f, H5AC_BT2_INT, hdr->root.addr, new_root, new_root_flags) < 0)

        HDONE_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release B-tree internal node");

    FUNC_LEAVE_NOAPI(ret_value)

} /* end H5B2__split_root() */

/*-------------------------------------------------------------------------

 * Function:  H5B2__redistribute2

 *

 * Purpose: Redistribute records between two nodes

 *

 * Return:  Success:  Non-negative

 *    Failure:  Negative

 *

 *-------------------------------------------------------------------------

 */

herr_t

H5B2__redistribute2(H5B2_hdr_t *hdr, uint16_t depth, H5B2_internal_t *internal, unsigned idx)

{

    const H5AC_class_t *child_class;                             /* Pointer to child node's class info */

    haddr_t   left_addr = HADDR_UNDEF, right_addr = HADDR_UNDEF; /* Addresses of left & right child nodes */

    void     *left_child = NULL, *right_child = NULL;            /* Pointers to child nodes */

    uint16_t *left_nrec, *right_nrec;                            /* Pointers to child # of records */

    uint8_t  *left_native, *right_native;                        /* Pointers to childs' native records */

    H5B2_node_ptr_t *left_node_ptrs  = NULL,

                    *right_node_ptrs = NULL;            /* Pointers to childs' node pointer info */

    hssize_t left_moved_nrec = 0, right_moved_nrec = 0; /* Number of records moved, for internal redistrib */

    unsigned left_child_flags  = H5AC__NO_FLAGS_SET,

             right_child_flags = H5AC__NO_FLAGS_SET; /* Flags for unprotecting child nodes */

    herr_t ret_value           = SUCCEED;            /* Return value */

    FUNC_ENTER_PACKAGE

    /* Check arguments. */

    assert(hdr);

    assert(internal);

    /* Check for the kind of B-tree node to redistribute */

    if (depth > 1) {

        H5B2_internal_t *left_internal;  /* Pointer to left internal node */

        H5B2_internal_t *right_internal; /* Pointer to right internal node */

        /* Setup information for unlocking child nodes */

        child_class = H5AC_BT2_INT;

        /* Lock left & right B-tree child nodes */

        /* (Shadow both nodes if doing SWMR writes) */

        if (NULL == (left_internal =

                         H5B2__protect_internal(hdr, internal, &internal->node_ptrs[idx],

                                                (uint16_t)(depth - 1), hdr->swmr_write, H5AC__NO_FLAGS_SET)))

            HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to protect B-tree leaf node");

        left_addr = internal->node_ptrs[idx].addr;

        if (NULL == (right_internal =

                         H5B2__protect_internal(hdr, internal, &internal->node_ptrs[idx + 1],

                                                (uint16_t)(depth - 1), hdr->swmr_write, H5AC__NO_FLAGS_SET)))

            HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to protect B-tree leaf node");

        right_addr = internal->node_ptrs[idx + 1].addr;

        /* More setup for child nodes */

        left_child      = left_internal;

        right_child     = right_internal;

        left_nrec       = &(left_internal->nrec);

        right_nrec      = &(right_internal->nrec);

        left_native     = left_internal->int_native;

        right_native    = right_internal->int_native;

        left_node_ptrs  = left_internal->node_ptrs;

        right_node_ptrs = right_internal->node_ptrs;

    } /* end if */

    else {

        H5B2_leaf_t *left_leaf;  /* Pointer to left leaf node */

        H5B2_leaf_t *right_leaf; /* Pointer to right leaf node */

        /* Setup information for unlocking child nodes */

        child_class = H5AC_BT2_LEAF;

        /* Lock left & right B-tree child nodes */

        /* (Shadow both nodes if doing SWMR writes) */

        if (NULL == (left_leaf = H5B2__protect_leaf(hdr, internal, &internal->node_ptrs[idx], hdr->swmr_write,

                                                    H5AC__NO_FLAGS_SET)))

            HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to protect B-tree leaf node");

        left_addr = internal->node_ptrs[idx].addr;

        if (NULL == (right_leaf = H5B2__protect_leaf(hdr, internal, &internal->node_ptrs[idx + 1],

                                                     hdr->swmr_write, H5AC__NO_FLAGS_SET)))

            HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to protect B-tree leaf node");

        right_addr = internal->node_ptrs[idx + 1].addr;

        /* More setup for child nodes */

        left_child   = left_leaf;

        right_child  = right_leaf;

        left_nrec    = &(left_leaf->nrec);

        right_nrec   = &(right_leaf->nrec);

        left_native  = left_leaf->leaf_native;

        right_native = right_leaf->leaf_native;

    } /* end else */

#ifdef H5B2_DEBUG

    H5B2__assert_internal((hsize_t)0, hdr, internal);

    if (depth > 1) {

        H5B2__assert_internal2(internal->node_ptrs[idx].all_nrec, hdr, (H5B2_internal_t *)left_child,

                               (H5B2_internal_t *)right_child);

        H5B2__assert_internal2(internal->node_ptrs[idx + 1].all_nrec, hdr, (H5B2_internal_t *)right_child,

                               (H5B2_internal_t *)left_child);

    } /* end if */

    else {

        H5B2__assert_leaf2(hdr, (H5B2_leaf_t *)left_child, (H5B2_leaf_t *)right_child);

        H5B2__assert_leaf(hdr, (H5B2_leaf_t *)right_child);

    }  /* end else */

#endif /* H5B2_DEBUG */

    /* Determine whether to shuffle records left or right */

    if (*left_nrec < *right_nrec) {

        /* Moving record from right node to left */

        uint16_t new_right_nrec =

            (uint16_t)((*left_nrec + *right_nrec) / 2); /* New number of records for right child */

        uint16_t move_nrec =

            (uint16_t)(*right_nrec - new_right_nrec); /* Number of records to move from right node to left */

        /* Copy record from parent node down into left child */

        H5MM_memcpy(H5B2_NAT_NREC(left_native, hdr, *left_nrec), H5B2_INT_NREC(internal, hdr, idx),

                    hdr->cls->nrec_size);

        /* See if we need to move records from right node */

        if (move_nrec > 1)

            H5MM_memcpy(H5B2_NAT_NREC(left_native, hdr, (*left_nrec + 1)),

                        H5B2_NAT_NREC(right_native, hdr, 0), hdr->cls->nrec_size * (size_t)(move_nrec - 1));

        /* Move record from right node into parent node */

        H5MM_memcpy(H5B2_INT_NREC(internal, hdr, idx), H5B2_NAT_NREC(right_native, hdr, (move_nrec - 1)),

                    hdr->cls->nrec_size);

        /* Slide records in right node down */

        memmove(H5B2_NAT_NREC(right_native, hdr, 0), H5B2_NAT_NREC(right_native, hdr, move_nrec),

                hdr->cls->nrec_size * new_right_nrec);

        /* Handle node pointers, if we have an internal node */

        if (depth > 1) {

            hsize_t  moved_nrec = move_nrec; /* Total number of records moved, for internal redistrib */

            unsigned u;                      /* Local index variable */

            /* Count the number of records being moved */

            for (u = 0; u < move_nrec; u++)

                moved_nrec += right_node_ptrs[u].all_nrec;

            H5_CHECKED_ASSIGN(left_moved_nrec, hssize_t, moved_nrec, hsize_t);

            right_moved_nrec -= (hssize_t)moved_nrec;

            /* Copy node pointers from right node to left */

            H5MM_memcpy(&(left_node_ptrs[*left_nrec + 1]), &(right_node_ptrs[0]),

                        sizeof(H5B2_node_ptr_t) * move_nrec);

            /* Slide node pointers in right node down */

            memmove(&(right_node_ptrs[0]), &(right_node_ptrs[move_nrec]),

                    sizeof(H5B2_node_ptr_t) * (new_right_nrec + (unsigned)1));

        } /* end if */

        /* Update flush dependencies for grandchildren, if using SWMR */

        if (hdr->swmr_write && depth > 1)

            if (H5B2__update_child_flush_depends(hdr, depth, left_node_ptrs, (unsigned)(*left_nrec + 1),

                                                 (unsigned)(*left_nrec + move_nrec + 1), right_child,

                                                 left_child) < 0)

                HGOTO_ERROR(H5E_BTREE, H5E_CANTUPDATE, FAIL, "unable to update child nodes to new parent");

        /* Update number of records in child nodes */

        *left_nrec  = (uint16_t)(*left_nrec + move_nrec);

        *right_nrec = new_right_nrec;

        /* Mark nodes as dirty */

        left_child_flags |= H5AC__DIRTIED_FLAG;

        right_child_flags |= H5AC__DIRTIED_FLAG;

    } /* end if */

    else {

        /* Moving record from left node to right */

        uint16_t new_left_nrec =

            (uint16_t)((*left_nrec + *right_nrec) / 2); /* New number of records for left child */

        uint16_t move_nrec =

            (uint16_t)(*left_nrec - new_left_nrec); /* Number of records to move from left node to right */

        /* Sanity check */

        assert(*left_nrec > *right_nrec);

        /* Slide records in right node up */

        memmove(H5B2_NAT_NREC(right_native, hdr, move_nrec), H5B2_NAT_NREC(right_native, hdr, 0),

                hdr->cls->nrec_size * (*right_nrec));

        /* Copy record from parent node down into right child */

        H5MM_memcpy(H5B2_NAT_NREC(right_native, hdr, (move_nrec - 1)), H5B2_INT_NREC(internal, hdr, idx),

                    hdr->cls->nrec_size);

        /* See if we need to move records from left node */

        if (move_nrec > 1)

            H5MM_memcpy(H5B2_NAT_NREC(right_native, hdr, 0),

                        H5B2_NAT_NREC(left_native, hdr, ((*left_nrec - move_nrec) + 1)),

                        hdr->cls->nrec_size * (size_t)(move_nrec - 1));

        /* Move record from left node into parent node */

        H5MM_memcpy(H5B2_INT_NREC(internal, hdr, idx),

                    H5B2_NAT_NREC(left_native, hdr, (*left_nrec - move_nrec)), hdr->cls->nrec_size);

        /* Handle node pointers, if we have an internal node */

        if (depth > 1) {

            hsize_t  moved_nrec = move_nrec; /* Total number of records moved, for internal redistrib */

            unsigned u;                      /* Local index variable */

            /* Slide node pointers in right node up */

            memmove(&(right_node_ptrs[move_nrec]), &(right_node_ptrs[0]),

                    sizeof(H5B2_node_ptr_t) * (size_t)(*right_nrec + 1));

            /* Copy node pointers from left node to right */

            H5MM_memcpy(&(right_node_ptrs[0]), &(left_node_ptrs[new_left_nrec + 1]),

                        sizeof(H5B2_node_ptr_t) * move_nrec);

            /* Count the number of records being moved */

            for (u = 0; u < move_nrec; u++)

                moved_nrec += right_node_ptrs[u].all_nrec;

            left_moved_nrec -= (hssize_t)moved_nrec;

            H5_CHECKED_ASSIGN(right_moved_nrec, hssize_t, moved_nrec, hsize_t);

        } /* end if */

        /* Update flush dependencies for grandchildren, if using SWMR */

        if (hdr->swmr_write && depth > 1)

            if (H5B2__update_child_flush_depends(hdr, depth, right_node_ptrs, 0, (unsigned)move_nrec,

                                                 left_child, right_child) < 0)

                HGOTO_ERROR(H5E_BTREE, H5E_CANTUPDATE, FAIL, "unable to update child nodes to new parent");

        /* Update number of records in child nodes */

        *left_nrec  = new_left_nrec;

        *right_nrec = (uint16_t)(*right_nrec + move_nrec);

        /* Mark nodes as dirty */

        left_child_flags |= H5AC__DIRTIED_FLAG;

        right_child_flags |= H5AC__DIRTIED_FLAG;

    } /* end else */

    /* Update # of records in child nodes */

    internal->node_ptrs[idx].node_nrec     = *left_nrec;

    internal->node_ptrs[idx + 1].node_nrec = *right_nrec;

    /* Update total # of records in child B-trees */

    if (depth > 1) {

        internal->node_ptrs[idx].all_nrec =

            (hsize_t)((hssize_t)internal->node_ptrs[idx].all_nrec + left_moved_nrec);

        internal->node_ptrs[idx + 1].all_nrec =

            (hsize_t)((hssize_t)internal->node_ptrs[idx + 1].all_nrec + right_moved_nrec);

    } /* end if */

    else {

        internal->node_ptrs[idx].all_nrec     = internal->node_ptrs[idx].node_nrec;

        internal->node_ptrs[idx + 1].all_nrec = internal->node_ptrs[idx + 1].node_nrec;

    } /* end else */

#ifdef H5B2_DEBUG

    H5B2__assert_internal((hsize_t)0, hdr, internal);

    if (depth > 1) {

        H5B2__assert_internal2(internal->node_ptrs[idx].all_nrec, hdr, (H5B2_internal_t *)left_child,

                               (H5B2_internal_t *)right_child);

        H5B2__assert_internal2(internal->node_ptrs[idx + 1].all_nrec, hdr, (H5B2_internal_t *)right_child,

                               (H5B2_internal_t *)left_child);

    } /* end if */

    else {

        H5B2__assert_leaf2(hdr, (H5B2_leaf_t *)left_child, (H5B2_leaf_t *)right_child);

        H5B2__assert_leaf(hdr, (H5B2_leaf_t *)right_child);

    }  /* end else */

#endif /* H5B2_DEBUG */

done:

    /* Release child nodes (marked as dirty) */

    if (left_child && H5AC_unprotect(hdr->f, child_class, left_addr, left_child, left_child_flags) < 0)

        HDONE_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release B-tree child node");

    if (right_child && H5AC_unprotect(hdr->f, child_class, right_addr, right_child, right_child_flags) < 0)

        HDONE_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release B-tree child node");

    FUNC_LEAVE_NOAPI(ret_value)

} /* end H5B2__redistribute2() */

/*-------------------------------------------------------------------------

 * Function:  H5B2__redistribute3

 *

 * Purpose: Redistribute records between three nodes

 *

 * Return:  Success:  Non-negative

 *    Failure:  Negative

 *

 *-------------------------------------------------------------------------

 */

herr_t

H5B2__redistribute3(H5B2_hdr_t *hdr, uint16_t depth, H5B2_internal_t *internal, unsigned *internal_flags_ptr,

                    unsigned idx)

{

    H5B2_node_ptr_t *left_node_ptrs      = NULL,

                    *right_node_ptrs     = NULL;                 /* Pointers to childs' node pointer info */

    H5B2_node_ptr_t    *middle_node_ptrs = NULL;                 /* Pointers to childs' node pointer info */

    const H5AC_class_t *child_class;                             /* Pointer to child node's class info */

    haddr_t   left_addr = HADDR_UNDEF, right_addr = HADDR_UNDEF; /* Addresses of left & right child nodes */

    haddr_t   middle_addr = HADDR_UNDEF;                         /* Address of middle child node */

    void     *left_child = NULL, *right_child = NULL;            /* Pointers to child nodes */

    void     *middle_child = NULL;                               /* Pointers to middle child node */

    uint16_t *left_nrec, *right_nrec;                            /* Pointers to child # of records */

    uint16_t *middle_nrec;                                       /* Pointers to middle child # of records */

    uint8_t  *left_native, *right_native;                        /* Pointers to childs' native records */

    uint8_t  *middle_native;                             /* Pointers to middle child's native records */

    hssize_t  left_moved_nrec = 0, right_moved_nrec = 0; /* Number of records moved, for internal split */

    hssize_t  middle_moved_nrec = 0;                     /* Number of records moved, for internal split */

    unsigned  left_child_flags  = H5AC__NO_FLAGS_SET,

             right_child_flags  = H5AC__NO_FLAGS_SET; /* Flags for unprotecting child nodes */

    unsigned middle_child_flags = H5AC__NO_FLAGS_SET; /* Flags for unprotecting child nodes */

    herr_t   ret_value          = SUCCEED;            /* Return value */

    FUNC_ENTER_PACKAGE

    /* Check arguments. */

    assert(hdr);

    assert(internal);

    assert(internal_flags_ptr);

    /* Check for the kind of B-tree node to redistribute */

    if (depth > 1) {

        H5B2_internal_t *left_internal;   /* Pointer to left internal node */

        H5B2_internal_t *middle_internal; /* Pointer to middle internal node */

        H5B2_internal_t *right_internal;  /* Pointer to right internal node */

        /* Setup information for unlocking child nodes */

        child_class = H5AC_BT2_INT;

        /* Lock B-tree child nodes */

        /* (Shadow all nodes if doing SWMR writes) */

        if (NULL == (left_internal =

                         H5B2__protect_internal(hdr, internal, &internal->node_ptrs[idx - 1],

                                                (uint16_t)(depth - 1), hdr->swmr_write, H5AC__NO_FLAGS_SET)))

            HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to protect B-tree internal node");

        left_addr = internal->node_ptrs[idx - 1].addr;

        if (NULL == (middle_internal =

                         H5B2__protect_internal(hdr, internal, &internal->node_ptrs[idx],

                                                (uint16_t)(depth - 1), hdr->swmr_write, H5AC__NO_FLAGS_SET)))

            HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to protect B-tree internal node");

        middle_addr = internal->node_ptrs[idx].addr;

        if (NULL == (right_internal =

                         H5B2__protect_internal(hdr, internal, &internal->node_ptrs[idx + 1],

                                                (uint16_t)(depth - 1), hdr->swmr_write, H5AC__NO_FLAGS_SET)))

            HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to protect B-tree internal node");

        right_addr = internal->node_ptrs[idx + 1].addr;

        /* More setup for child nodes */

        left_child       = left_internal;

        middle_child     = middle_internal;

        right_child      = right_internal;

        left_nrec        = &(left_internal->nrec);

        middle_nrec      = &(middle_internal->nrec);

        right_nrec       = &(right_internal->nrec);

        left_native      = left_internal->int_native;

        middle_native    = middle_internal->int_native;

        right_native     = right_internal->int_native;

        left_node_ptrs   = left_internal->node_ptrs;

        middle_node_ptrs = middle_internal->node_ptrs;

        right_node_ptrs  = right_internal->node_ptrs;

    } /* end if */

    else {

        H5B2_leaf_t *left_leaf;   /* Pointer to left leaf node */

        H5B2_leaf_t *middle_leaf; /* Pointer to middle leaf node */

        H5B2_leaf_t *right_leaf;  /* Pointer to right leaf node */

        /* Setup information for unlocking child nodes */

        child_class = H5AC_BT2_LEAF;

        /* Lock B-tree child nodes */

        /* (Shadow all nodes if doing SWMR writes) */

        if (NULL == (left_leaf = H5B2__protect_leaf(hdr, internal, &internal->node_ptrs[idx - 1],

                                                    hdr->swmr_write, H5AC__NO_FLAGS_SET)))

            HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to protect B-tree leaf node");

        left_addr = internal->node_ptrs[idx - 1].addr;

        if (NULL == (middle_leaf = H5B2__protect_leaf(hdr, internal, &internal->node_ptrs[idx],

                                                      hdr->swmr_write, H5AC__NO_FLAGS_SET)))

            HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to protect B-tree leaf node");

        middle_addr = internal->node_ptrs[idx].addr;

        if (NULL == (right_leaf = H5B2__protect_leaf(hdr, internal, &internal->node_ptrs[idx + 1],

                                                     hdr->swmr_write, H5AC__NO_FLAGS_SET)))

            HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to protect B-tree leaf node");

        right_addr = internal->node_ptrs[idx + 1].addr;

        /* More setup for child nodes */

        left_child    = left_leaf;

        middle_child  = middle_leaf;

        right_child   = right_leaf;

        left_nrec     = &(left_leaf->nrec);

        middle_nrec   = &(middle_leaf->nrec);

        right_nrec    = &(right_leaf->nrec);

        left_native   = left_leaf->leaf_native;

        middle_native = middle_leaf->leaf_native;

        right_native  = right_leaf->leaf_native;

    } /* end else */

    /* Redistribute records */

    {

        /* Compute new # of records in each node */

        unsigned total_nrec      = (unsigned)(*left_nrec + *middle_nrec + *right_nrec + 2);

        uint16_t new_middle_nrec = (uint16_t)((total_nrec - 2) / 3);

        uint16_t new_left_nrec   = (uint16_t)(((total_nrec - 2) - new_middle_nrec) / 2);

        uint16_t new_right_nrec  = (uint16_t)((total_nrec - 2) - (unsigned)(new_left_nrec + new_middle_nrec));

        uint16_t curr_middle_nrec = *middle_nrec;

        /* Sanity check rounding */

        assert(new_middle_nrec <= new_left_nrec);

        assert(new_middle_nrec <= new_right_nrec);

        /* Move records into left node */

        if (new_left_nrec > *left_nrec) {

            uint16_t moved_middle_nrec = 0; /* Number of records moved into left node */

            /* Move left parent record down to left node */

            H5MM_memcpy(H5B2_NAT_NREC(left_native, hdr, *left_nrec), H5B2_INT_NREC(internal, hdr, idx - 1),

                        hdr->cls->nrec_size);

            /* Move records from middle node into left node */

            if ((new_left_nrec - 1) > *left_nrec) {

                moved_middle_nrec = (uint16_t)(new_left_nrec - (*left_nrec + 1));

                H5MM_memcpy(H5B2_NAT_NREC(left_native, hdr, *left_nrec + 1),

                            H5B2_NAT_NREC(middle_native, hdr, 0), hdr->cls->nrec_size * moved_middle_nrec);

            } /* end if */

            /* Move record from middle node up to parent node */

            H5MM_memcpy(H5B2_INT_NREC(internal, hdr, idx - 1),

                        H5B2_NAT_NREC(middle_native, hdr, moved_middle_nrec), hdr->cls->nrec_size);

            moved_middle_nrec++;

            /* Slide records in middle node down */

            memmove(H5B2_NAT_NREC(middle_native, hdr, 0),

                    H5B2_NAT_NREC(middle_native, hdr, moved_middle_nrec),

                    hdr->cls->nrec_size * (size_t)(*middle_nrec - moved_middle_nrec));

            /* Move node pointers also if this is an internal node */

            if (depth > 1) {

                hsize_t  moved_nrec; /* Total number of records moved, for internal redistrib */

                unsigned move_nptrs; /* Number of node pointers to move */

                unsigned u;          /* Local index variable */

                /* Move middle node pointers into left node */

                move_nptrs = (unsigned)(new_left_nrec - *left_nrec);

                H5MM_memcpy(&(left_node_ptrs[*left_nrec + 1]), &(middle_node_ptrs[0]),

                            sizeof(H5B2_node_ptr_t) * move_nptrs);

                /* Count the number of records being moved into the left node */

                for (u = 0, moved_nrec = 0; u < move_nptrs; u++)

                    moved_nrec += middle_node_ptrs[u].all_nrec;

                left_moved_nrec = (hssize_t)(moved_nrec + move_nptrs);

                middle_moved_nrec -= (hssize_t)(moved_nrec + move_nptrs);

                /* Slide the node pointers in middle node down */

                memmove(&(middle_node_ptrs[0]), &(middle_node_ptrs[move_nptrs]),

                        sizeof(H5B2_node_ptr_t) * ((*middle_nrec - move_nptrs) + 1));

            } /* end if */

            /* Update flush dependencies for grandchildren, if using SWMR */

            if (hdr->swmr_write && depth > 1)

                if (H5B2__update_child_flush_depends(hdr, depth, left_node_ptrs, (unsigned)(*left_nrec + 1),

                                                     (unsigned)(*left_nrec + moved_middle_nrec + 1),

                                                     middle_child, left_child) < 0)

                    HGOTO_ERROR(H5E_BTREE, H5E_CANTUPDATE, FAIL,

                                "unable to update child nodes to new parent");

            /* Update the current number of records in middle node */

            curr_middle_nrec = (uint16_t)(curr_middle_nrec - moved_middle_nrec);

            /* Mark nodes as dirty */

            left_child_flags |= H5AC__DIRTIED_FLAG;

            middle_child_flags |= H5AC__DIRTIED_FLAG;

        } /* end if */

        /* Move records into right node */

        if (new_right_nrec > *right_nrec) {

            unsigned right_nrec_move =

                (unsigned)(new_right_nrec - *right_nrec); /* Number of records to move out of right node */

            /* Slide records in right node up */

            memmove(H5B2_NAT_NREC(right_native, hdr, right_nrec_move), H5B2_NAT_NREC(right_native, hdr, 0),

                    hdr->cls->nrec_size * (*right_nrec));

            /* Move right parent record down to right node */

            H5MM_memcpy(H5B2_NAT_NREC(right_native, hdr, right_nrec_move - 1),

                        H5B2_INT_NREC(internal, hdr, idx), hdr->cls->nrec_size);

            /* Move records from middle node into right node */

            if (right_nrec_move > 1)

                H5MM_memcpy(H5B2_NAT_NREC(right_native, hdr, 0),

                            H5B2_NAT_NREC(middle_native, hdr, ((curr_middle_nrec - right_nrec_move) + 1)),

                            hdr->cls->nrec_size * (right_nrec_move - 1));

            /* Move record from middle node up to parent node */

            H5MM_memcpy(H5B2_INT_NREC(internal, hdr, idx),

                        H5B2_NAT_NREC(middle_native, hdr, (curr_middle_nrec - right_nrec_move)),

                        hdr->cls->nrec_size);

            /* Move node pointers also if this is an internal node */

            if (depth > 1) {

                hsize_t  moved_nrec; /* Total number of records moved, for internal redistrib */

                unsigned u;          /* Local index variable */

                /* Slide the node pointers in right node up */

                memmove(&(right_node_ptrs[right_nrec_move]), &(right_node_ptrs[0]),

                        sizeof(H5B2_node_ptr_t) * (size_t)(*right_nrec + 1));

                /* Move middle node pointers into right node */

                H5MM_memcpy(&(right_node_ptrs[0]),

                            &(middle_node_ptrs[(curr_middle_nrec - right_nrec_move) + 1]),

                            sizeof(H5B2_node_ptr_t) * right_nrec_move);

                /* Count the number of records being moved into the right node */

                for (u = 0, moved_nrec = 0; u < right_nrec_move; u++)

                    moved_nrec += right_node_ptrs[u].all_nrec;

                right_moved_nrec = (hssize_t)(moved_nrec + right_nrec_move);

                middle_moved_nrec -= (hssize_t)(moved_nrec + right_nrec_move);

            } /* end if */

            /* Update flush dependencies for grandchildren, if using SWMR */

            if (hdr->swmr_write && depth > 1)

                if (H5B2__update_child_flush_depends(hdr, depth, right_node_ptrs, 0,

                                                     (unsigned)right_nrec_move, middle_child,

                                                     right_child) < 0)

                    HGOTO_ERROR(H5E_BTREE, H5E_CANTUPDATE, FAIL,

                                "unable to update child nodes to new parent");

            /* Update the current number of records in middle node */

            curr_middle_nrec = (uint16_t)(curr_middle_nrec - right_nrec_move);

            /* Mark nodes as dirty */

            middle_child_flags |= H5AC__DIRTIED_FLAG;

            right_child_flags |= H5AC__DIRTIED_FLAG;

        } /* end if */