[svn-r26191] Description:

    Track the min & max keys for a v2 B-tree, so it can more efficiently
determine if a key is present in the B-tree.

Tested on:
    Mac OSX/64 10.10.2 (amazon) w/parallel & serial
    Linux/32 2.6.x (jam) w/serial

1 files changed, 134 insertions, 26 deletions

diff --git a/src/H5B2int.c b/src/H5B2int.c
index 630ff98..ef83e93 100644
--- a/src/H5B2int.c
+++ b/src/H5B2int.c
@@ -172,9 +172,9 @@ H5B2_locate_record(const H5B2_class_t *type, unsigned nrec, size_t *rec_off,
  *-------------------------------------------------------------------------
  */
 static herr_t
-H5B2_split1(H5B2_hdr_t *hdr, hid_t dxpl_id, unsigned depth, H5B2_node_ptr_t *curr_node_ptr,
-    unsigned *parent_cache_info_flags_ptr, H5B2_internal_t *internal,
-    unsigned *internal_flags_ptr, unsigned idx)
+H5B2_split1(H5B2_hdr_t *hdr, hid_t dxpl_id, unsigned 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, right_addr;      /* Addresses of left & right child nodes */
@@ -214,7 +214,7 @@ H5B2_split1(H5B2_hdr_t *hdr, hid_t dxpl_id, unsigned depth, H5B2_node_ptr_t *cur
         left_addr = internal->node_ptrs[idx].addr;
         right_addr = internal->node_ptrs[idx + 1].addr;
 
-        /* Protect both leafs */
+        /* Protect both leaves */
         if(NULL == (left_int = H5B2_protect_internal(hdr, dxpl_id, left_addr, internal->node_ptrs[idx].node_nrec, (depth - 1), H5AC_WRITE)))
             HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to protect B-tree internal node")
         if(NULL == (right_int = H5B2_protect_internal(hdr, dxpl_id, right_addr, internal->node_ptrs[idx + 1].node_nrec, (depth - 1), H5AC_WRITE)))
@@ -243,7 +243,7 @@ H5B2_split1(H5B2_hdr_t *hdr, hid_t dxpl_id, unsigned depth, H5B2_node_ptr_t *cur
         left_addr = internal->node_ptrs[idx].addr;
         right_addr = internal->node_ptrs[idx + 1].addr;
 
-        /* Protect both leafs */
+        /* Protect both leaves */
         if(NULL == (left_leaf = H5B2_protect_leaf(hdr, dxpl_id, left_addr, internal->node_ptrs[idx].node_nrec, H5AC_WRITE)))
             HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to protect B-tree leaf node")
         if(NULL == (right_leaf = H5B2_protect_leaf(hdr, dxpl_id, right_addr, internal->node_ptrs[idx + 1].node_nrec, H5AC_WRITE)))
@@ -341,7 +341,7 @@ done:
         HDONE_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release B-tree leaf node")
 
     FUNC_LEAVE_NOAPI(ret_value)
-} /* end H5B2_split1 */
+} /* end H5B2_split1() */
 
 
 /*-------------------------------------------------------------------------
@@ -646,7 +646,7 @@ done:
         HDONE_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release B-tree child node")
 
     FUNC_LEAVE_NOAPI(ret_value)
-} /* end H5B2_redistribute2 */
+} /* end H5B2_redistribute2() */
 
 
 /*-------------------------------------------------------------------------
@@ -1033,7 +1033,7 @@ done:
         HDONE_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release B-tree child node")
 
     FUNC_LEAVE_NOAPI(ret_value)
-} /* end H5B2_redistribute3 */
+} /* end H5B2_redistribute3() */
 
 
 /*-------------------------------------------------------------------------
@@ -1505,7 +1505,7 @@ done:
         HDONE_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release B-tree child node")
 
     FUNC_LEAVE_NOAPI(ret_value)
-} /* end H5B2_swap_leaf */
+} /* end H5B2_swap_leaf() */
 
 
 /*-------------------------------------------------------------------------
@@ -1523,7 +1523,7 @@ done:
  */
 herr_t
 H5B2_insert_leaf(H5B2_hdr_t *hdr, hid_t dxpl_id, H5B2_node_ptr_t *curr_node_ptr,
-    void *udata)
+    H5B2_nodepos_t curr_pos, void *udata)
 {
     H5B2_leaf_t *leaf;                  /* Pointer to leaf node */
     int         cmp;                    /* Comparison value of records */
@@ -1574,6 +1574,27 @@ H5B2_insert_leaf(H5B2_hdr_t *hdr, hid_t dxpl_id, H5B2_node_ptr_t *curr_node_ptr,
     /* Update record count for current node */
     leaf->nrec++;
 
+    /* Check for new record being the min or max for the tree */
+    /* (Don't use 'else' for the idx check, to allow for root leaf node) */
+    if(H5B2_POS_MIDDLE != curr_pos) {
+        if(idx == 0) {
+            if(H5B2_POS_LEFT == curr_pos || H5B2_POS_ROOT == curr_pos) {
+                if(hdr->min_native_rec == NULL)
+                    if(NULL == (hdr->min_native_rec = (uint8_t *)HDmalloc(hdr->cls->nrec_size)))
+                        HGOTO_ERROR(H5E_BTREE, H5E_CANTALLOC, FAIL, "memory allocation failed for v2 B-tree min record info")
+                HDmemcpy(hdr->min_native_rec, H5B2_LEAF_NREC(leaf, hdr, idx), hdr->cls->nrec_size);
+            } /* end if */
+        } /* end if */
+        if(idx == (unsigned)(leaf->nrec - 1)) {
+            if(H5B2_POS_RIGHT == curr_pos || H5B2_POS_ROOT == curr_pos) {
+                if(hdr->max_native_rec == NULL)
+                    if(NULL == (hdr->max_native_rec = (uint8_t *)HDmalloc(hdr->cls->nrec_size)))
+                        HGOTO_ERROR(H5E_BTREE, H5E_CANTALLOC, FAIL, "memory allocation failed for v2 B-tree max record info")
+                HDmemcpy(hdr->max_native_rec, H5B2_LEAF_NREC(leaf, hdr, idx), hdr->cls->nrec_size);
+            } /* end if */
+        } /* end if */
+    } /* end if */
+
 done:
     /* Release the B-tree leaf node (marked as dirty) */
     if(leaf && H5AC_unprotect(hdr->f, dxpl_id, H5AC_BT2_LEAF, curr_node_ptr->addr, leaf, H5AC__DIRTIED_FLAG) < 0)
@@ -1599,11 +1620,12 @@ done:
 herr_t
 H5B2_insert_internal(H5B2_hdr_t *hdr, hid_t dxpl_id, unsigned depth,
     unsigned *parent_cache_info_flags_ptr, H5B2_node_ptr_t *curr_node_ptr,
-    void *udata)
+    H5B2_nodepos_t curr_pos, void *udata)
 {
-    H5B2_internal_t *internal;          /* Pointer to internal node */
+    H5B2_internal_t *internal = NULL;   /* Pointer to internal node */
     unsigned internal_flags = H5AC__NO_FLAGS_SET;
     unsigned    idx;                    /* Location of record which matches key */
+    H5B2_nodepos_t next_pos = H5B2_POS_MIDDLE;    /* Position of node */
     herr_t	ret_value = SUCCEED;    /* Return value */
 
     FUNC_ENTER_NOAPI_NOINIT
@@ -1618,7 +1640,7 @@ H5B2_insert_internal(H5B2_hdr_t *hdr, hid_t dxpl_id, unsigned depth,
     if(NULL == (internal = H5B2_protect_internal(hdr, dxpl_id, curr_node_ptr->addr, curr_node_ptr->node_nrec, depth, H5AC_WRITE)))
         HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to protect B-tree internal node")
 
-/* Split or redistribute child node pointers, if necessary */
+    /* Split or redistribute child node pointers, if necessary */
     {
         int         cmp;        /* Comparison value of records */
         unsigned retries;       /* Number of times to attempt redistribution */
@@ -1691,13 +1713,25 @@ H5B2_insert_internal(H5B2_hdr_t *hdr, hid_t dxpl_id, unsigned depth,
         } /* end while */
     } /* end block */
 
+    /* Check if this node is left/right-most */
+    if(H5B2_POS_MIDDLE != curr_pos) {
+        if(idx == 0) {
+            if(H5B2_POS_LEFT == curr_pos || H5B2_POS_ROOT == curr_pos)
+                next_pos = H5B2_POS_LEFT;
+        } /* end if */
+        else if(idx == internal->nrec) {
+            if(H5B2_POS_RIGHT == curr_pos || H5B2_POS_ROOT == curr_pos)
+                next_pos = H5B2_POS_RIGHT;
+        } /* end else */
+    } /* end if */
+
     /* Attempt to insert node */
     if(depth > 1) {
-        if(H5B2_insert_internal(hdr, dxpl_id, (depth - 1), &internal_flags, &internal->node_ptrs[idx], udata) < 0)
+        if(H5B2_insert_internal(hdr, dxpl_id, (depth - 1), &internal_flags, &internal->node_ptrs[idx], next_pos, udata) < 0)
             HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, FAIL, "unable to insert record into B-tree internal node")
     } /* end if */
     else {
-        if(H5B2_insert_leaf(hdr, dxpl_id, &internal->node_ptrs[idx], udata) < 0)
+        if(H5B2_insert_leaf(hdr, dxpl_id, &internal->node_ptrs[idx], next_pos, udata) < 0)
             HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, FAIL, "unable to insert record into B-tree leaf node")
     } /* end else */
 
@@ -2074,7 +2108,7 @@ done:
  */
 herr_t
 H5B2_remove_leaf(H5B2_hdr_t *hdr, hid_t dxpl_id, H5B2_node_ptr_t *curr_node_ptr,
-    void *udata, H5B2_remove_t op, void *op_data)
+    H5B2_nodepos_t curr_pos, void *udata, H5B2_remove_t op, void *op_data)
 {
     H5B2_leaf_t *leaf;                  /* Pointer to leaf node */
     haddr_t     leaf_addr = HADDR_UNDEF;  /* Leaf address on disk */
@@ -2102,6 +2136,27 @@ H5B2_remove_leaf(H5B2_hdr_t *hdr, hid_t dxpl_id, H5B2_node_ptr_t *curr_node_ptr,
     if(H5B2_locate_record(hdr->cls, leaf->nrec, hdr->nat_off, leaf->leaf_native, udata, &idx) != 0)
         HGOTO_ERROR(H5E_BTREE, H5E_NOTFOUND, FAIL, "record is not in B-tree")
 
+    /* Check for invalidating the min/max record for the tree */
+    if(H5B2_POS_MIDDLE != curr_pos) {
+        /* (Don't use 'else' for the idx check, to allow for root leaf node) */
+        if(idx == 0) {
+            if(H5B2_POS_LEFT == curr_pos || H5B2_POS_ROOT == curr_pos) {
+                if(hdr->min_native_rec) {
+                    HDfree(hdr->min_native_rec);
+                    hdr->min_native_rec = NULL;
+                } /* end if */
+            } /* end if */
+        } /* end if */
+        if(idx == (unsigned)(leaf->nrec - 1)) {
+            if(H5B2_POS_RIGHT == curr_pos || H5B2_POS_ROOT == curr_pos) {
+                if(hdr->max_native_rec) {
+                    HDfree(hdr->max_native_rec);
+                    hdr->max_native_rec = NULL;
+                } /* end if */
+            } /* end if */
+        } /* end if */
+    } /* end if */
+
     /* Make 'remove' callback if there is one */
     if(op)
         if((op)(H5B2_LEAF_NREC(leaf, hdr, idx), op_data) < 0)
@@ -2154,13 +2209,14 @@ done:
 herr_t
 H5B2_remove_internal(H5B2_hdr_t *hdr, hid_t dxpl_id, hbool_t *depth_decreased,
     void *swap_loc, unsigned depth, H5AC_info_t *parent_cache_info,
-    unsigned *parent_cache_info_flags_ptr, H5B2_node_ptr_t *curr_node_ptr,
-    void *udata, H5B2_remove_t op, void *op_data)
+    unsigned *parent_cache_info_flags_ptr, H5B2_nodepos_t curr_pos,
+    H5B2_node_ptr_t *curr_node_ptr, void *udata, H5B2_remove_t op, void *op_data)
 {
     H5AC_info_t *new_cache_info;        /* Pointer to new cache info */
     unsigned *new_cache_info_flags_ptr = NULL;
     H5B2_node_ptr_t *new_node_ptr;      /* Pointer to new node pointer */
     H5B2_internal_t *internal;          /* Pointer to internal node */
+    H5B2_nodepos_t next_pos = H5B2_POS_MIDDLE;  /* Position of next node */
     unsigned internal_flags = H5AC__NO_FLAGS_SET;
     haddr_t internal_addr;              /* Address of internal node */
     size_t      merge_nrec;             /* Number of records to merge node at */
@@ -2211,6 +2267,9 @@ H5B2_remove_internal(H5B2_hdr_t *hdr, hid_t dxpl_id, hbool_t *depth_decreased,
 
         /* Set flag to indicate root was collapsed */
         collapsed_root = TRUE;
+
+        /* Indicate position of next node */
+        next_pos = H5B2_POS_ROOT;
     } /* end if */
     /* Merge or redistribute child node pointers, if necessary */
     else {
@@ -2306,16 +2365,28 @@ H5B2_remove_internal(H5B2_hdr_t *hdr, hid_t dxpl_id, hbool_t *depth_decreased,
         new_cache_info_flags_ptr = &internal_flags;
         new_cache_info = &internal->cache_info;
         new_node_ptr = &internal->node_ptrs[idx];
+
+        /* Indicate position of next node */
+        if(H5B2_POS_MIDDLE != curr_pos) {
+            if(idx == 0) {
+                if(H5B2_POS_LEFT == curr_pos || H5B2_POS_ROOT == curr_pos)
+                    next_pos = H5B2_POS_LEFT;
+            } /* end if */
+            else if(idx == internal->nrec) {
+                if(H5B2_POS_RIGHT == curr_pos || H5B2_POS_ROOT == curr_pos)
+                    next_pos = H5B2_POS_RIGHT;
+            } /* end if */
+        } /* end if */
     } /* end else */
 
     /* Attempt to remove record from child node */
     if(depth > 1) {
         if(H5B2_remove_internal(hdr, dxpl_id, depth_decreased, swap_loc, depth - 1,
-                new_cache_info, new_cache_info_flags_ptr, new_node_ptr, udata, op, op_data) < 0)
+                new_cache_info, new_cache_info_flags_ptr, next_pos, new_node_ptr, udata, op, op_data) < 0)
             HGOTO_ERROR(H5E_BTREE, H5E_CANTDELETE, FAIL, "unable to remove record from B-tree internal node")
     } /* end if */
     else {
-        if(H5B2_remove_leaf(hdr, dxpl_id, new_node_ptr, udata, op, op_data) < 0)
+        if(H5B2_remove_leaf(hdr, dxpl_id, new_node_ptr, next_pos, udata, op, op_data) < 0)
             HGOTO_ERROR(H5E_BTREE, H5E_CANTDELETE, FAIL, "unable to remove record from B-tree leaf node")
     } /* end else */
 
@@ -2355,8 +2426,8 @@ done:
  */
 herr_t
 H5B2_remove_leaf_by_idx(H5B2_hdr_t *hdr, hid_t dxpl_id,
-    H5B2_node_ptr_t *curr_node_ptr, unsigned idx, H5B2_remove_t op,
-    void *op_data)
+    H5B2_node_ptr_t *curr_node_ptr, H5B2_nodepos_t curr_pos,
+    unsigned idx, H5B2_remove_t op, void *op_data)
 {
     H5B2_leaf_t *leaf;                  /* Pointer to leaf node */
     haddr_t     leaf_addr = HADDR_UNDEF;  /* Leaf address on disk */
@@ -2380,6 +2451,27 @@ H5B2_remove_leaf_by_idx(H5B2_hdr_t *hdr, hid_t dxpl_id,
     HDassert(leaf->nrec == curr_node_ptr->node_nrec);
     HDassert(idx < leaf->nrec);
 
+    /* Check for invalidating the min/max record for the tree */
+    if(H5B2_POS_MIDDLE != curr_pos) {
+        /* (Don't use 'else' for the idx check, to allow for root leaf node) */
+        if(idx == 0) {
+            if(H5B2_POS_LEFT == curr_pos || H5B2_POS_ROOT == curr_pos) {
+                if(hdr->min_native_rec) {
+                    HDfree(hdr->min_native_rec);
+                    hdr->min_native_rec = NULL;
+                } /* end if */
+            } /* end if */
+        } /* end if */
+        if(idx == (unsigned)(leaf->nrec - 1)) {
+            if(H5B2_POS_RIGHT == curr_pos || H5B2_POS_ROOT == curr_pos) {
+                if(hdr->max_native_rec) {
+                    HDfree(hdr->max_native_rec);
+                    hdr->max_native_rec = NULL;
+                } /* end if */
+            } /* end if */
+        } /* end if */
+    } /* end if */
+
     /* Make 'remove' callback if there is one */
     if(op)
         if((op)(H5B2_LEAF_NREC(leaf, hdr, idx), op_data) < 0)
@@ -2434,13 +2526,14 @@ herr_t
 H5B2_remove_internal_by_idx(H5B2_hdr_t *hdr, hid_t dxpl_id,
     hbool_t *depth_decreased, void *swap_loc, unsigned depth,
     H5AC_info_t *parent_cache_info, unsigned *parent_cache_info_flags_ptr,
-    H5B2_node_ptr_t *curr_node_ptr, hsize_t n, H5B2_remove_t op,
-    void *op_data)
+    H5B2_node_ptr_t *curr_node_ptr, H5B2_nodepos_t curr_pos, hsize_t n,
+    H5B2_remove_t op, void *op_data)
 {
     H5AC_info_t *new_cache_info;        /* Pointer to new cache info */
     unsigned *new_cache_info_flags_ptr = NULL;
     H5B2_node_ptr_t *new_node_ptr;      /* Pointer to new node pointer */
     H5B2_internal_t *internal;          /* Pointer to internal node */
+    H5B2_nodepos_t next_pos = H5B2_POS_MIDDLE;  /* Position of next node */
     unsigned internal_flags = H5AC__NO_FLAGS_SET;
     haddr_t internal_addr;              /* Address of internal node */
     size_t      merge_nrec;             /* Number of records to merge node at */
@@ -2494,6 +2587,9 @@ H5B2_remove_internal_by_idx(H5B2_hdr_t *hdr, hid_t dxpl_id,
 
         /* Set flag to indicate root was collapsed */
         collapsed_root = TRUE;
+
+        /* Indicate position of next node */
+        next_pos = H5B2_POS_ROOT;
     } /* end if */
     /* Merge or redistribute child node pointers, if necessary */
     else {
@@ -2641,16 +2737,28 @@ H5B2_remove_internal_by_idx(H5B2_hdr_t *hdr, hid_t dxpl_id,
         new_cache_info_flags_ptr = &internal_flags;
         new_cache_info = &internal->cache_info;
         new_node_ptr = &internal->node_ptrs[idx];
+
+        /* Indicate position of next node */
+        if(H5B2_POS_MIDDLE != curr_pos) {
+            if(idx == 0) {
+                if(H5B2_POS_LEFT == curr_pos || H5B2_POS_ROOT == curr_pos)
+                    next_pos = H5B2_POS_LEFT;
+            } /* end if */
+            else if(idx == internal->nrec) {
+                if(H5B2_POS_RIGHT == curr_pos || H5B2_POS_ROOT == curr_pos)
+                    next_pos = H5B2_POS_RIGHT;
+            } /* end if */
+        } /* end if */
     } /* end else */
 
     /* Attempt to remove record from child node */
     if(depth > 1) {
         if(H5B2_remove_internal_by_idx(hdr, dxpl_id, depth_decreased, swap_loc, depth - 1,
-                new_cache_info, new_cache_info_flags_ptr, new_node_ptr, n, op, op_data) < 0)
+                new_cache_info, new_cache_info_flags_ptr, new_node_ptr, next_pos, n, op, op_data) < 0)
             HGOTO_ERROR(H5E_BTREE, H5E_CANTDELETE, FAIL, "unable to remove record from B-tree internal node")
     } /* end if */
     else {
-        if(H5B2_remove_leaf_by_idx(hdr, dxpl_id, new_node_ptr, (unsigned)n, op, op_data) < 0)
+        if(H5B2_remove_leaf_by_idx(hdr, dxpl_id, new_node_ptr, next_pos, (unsigned)n, op, op_data) < 0)
             HGOTO_ERROR(H5E_BTREE, H5E_CANTDELETE, FAIL, "unable to remove record from B-tree leaf node")
     } /* end else */