[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, 129 insertions, 25 deletions

diff --git a/src/H5B2.c b/src/H5B2.c
index a2b218d..7d7345e 100644
--- a/src/H5B2.c
+++ b/src/H5B2.c
@@ -128,11 +128,11 @@ H5FL_DEFINE_STATIC(H5B2_t);
 H5B2_t *
 H5B2_create(H5F_t *f, hid_t dxpl_id, const H5B2_create_t *cparam, void *ctx_udata)
 {
-    H5B2_t	*bt2 = NULL;            /* Pointer to the B-tree */
-    H5B2_hdr_t	*hdr = NULL;            /* Pointer to the B-tree header */
+    H5B2_t      *bt2 = NULL;            /* Pointer to the B-tree */
+    H5B2_hdr_t  *hdr = NULL;            /* Pointer to the B-tree header */
     H5B2_hdr_cache_ud_t cache_udata;    /* User-data for callback */
     haddr_t     hdr_addr;               /* B-tree header address */
-    H5B2_t	*ret_value;             /* Return value */
+    H5B2_t      *ret_value;             /* Return value */
 
     FUNC_ENTER_NOAPI(NULL)
 
@@ -147,7 +147,7 @@ H5B2_create(H5F_t *f, hid_t dxpl_id, const H5B2_create_t *cparam, void *ctx_udat
 
     /* Create shared v2 B-tree header */
     if(HADDR_UNDEF == (hdr_addr = H5B2_hdr_create(f, dxpl_id, cparam, ctx_udata)))
-	HGOTO_ERROR(H5E_BTREE, H5E_CANTINIT, NULL, "can't create v2 B-tree header")
+        HGOTO_ERROR(H5E_BTREE, H5E_CANTINIT, NULL, "can't create v2 B-tree header")
 
     /* Create v2 B-tree wrapper */
     if(NULL == (bt2 = H5FL_MALLOC(H5B2_t)))
@@ -157,7 +157,7 @@ H5B2_create(H5F_t *f, hid_t dxpl_id, const H5B2_create_t *cparam, void *ctx_udat
     cache_udata.f = f;
     cache_udata.ctx_udata = ctx_udata;
     if(NULL == (hdr = (H5B2_hdr_t *)H5AC_protect(f, dxpl_id, H5AC_BT2_HDR, hdr_addr, &cache_udata, H5AC_WRITE)))
-	HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, NULL, "unable to load B-tree header")
+        HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, NULL, "unable to load B-tree header")
 
     /* Point v2 B-tree wrapper at header and bump it's ref count */
     bt2->hdr = hdr;
@@ -166,7 +166,7 @@ H5B2_create(H5F_t *f, hid_t dxpl_id, const H5B2_create_t *cparam, void *ctx_udat
 
     /* Increment # of files using this v2 B-tree header */
     if(H5B2_hdr_fuse_incr(bt2->hdr) < 0)
-	HGOTO_ERROR(H5E_BTREE, H5E_CANTINC, NULL, "can't increment file reference count on shared v2 B-tree header")
+        HGOTO_ERROR(H5E_BTREE, H5E_CANTINC, NULL, "can't increment file reference count on shared v2 B-tree header")
 
     /* Set file pointer for this v2 B-tree open context */
     bt2->f = f;
@@ -299,11 +299,11 @@ H5B2_insert(H5B2_t *bt2, hid_t dxpl_id, void *udata)
 
     /* Attempt to insert record into B-tree */
     if(hdr->depth > 0) {
-        if(H5B2_insert_internal(hdr, dxpl_id, hdr->depth, NULL, &hdr->root, udata) < 0)
+        if(H5B2_insert_internal(hdr, dxpl_id, hdr->depth, NULL, &hdr->root, H5B2_POS_ROOT, 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, &hdr->root, udata) < 0)
+        if(H5B2_insert_leaf(hdr, dxpl_id, &hdr->root, H5B2_POS_ROOT, udata) < 0)
             HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, FAIL, "unable to insert record into B-tree leaf node")
     } /* end else */
 
@@ -420,12 +420,13 @@ htri_t
 H5B2_find(H5B2_t *bt2, hid_t dxpl_id, void *udata, H5B2_found_t op,
     void *op_data)
 {
-    H5B2_hdr_t	*hdr;                   /* Pointer to the B-tree header */
+    H5B2_hdr_t  *hdr;                   /* Pointer to the B-tree header */
     H5B2_node_ptr_t curr_node_ptr;      /* Node pointer info for current node */
     unsigned    depth;                  /* Current depth of the tree */
     int         cmp;                    /* Comparison value of records */
     unsigned    idx;                    /* Location of record which matches key */
-    htri_t	ret_value = TRUE;       /* Return value */
+    H5B2_nodepos_t curr_pos;            /* Position of the current node */
+    htri_t      ret_value = TRUE;       /* Return value */
 
     FUNC_ENTER_NOAPI(FAIL)
 
@@ -441,16 +442,39 @@ H5B2_find(H5B2_t *bt2, hid_t dxpl_id, void *udata, H5B2_found_t op,
     /* Make copy of the root node pointer to start search with */
     curr_node_ptr = hdr->root;
 
-    /* Current depth of the tree */
-    depth = hdr->depth;
-
     /* Check for empty tree */
     if(curr_node_ptr.node_nrec == 0)
         HGOTO_DONE(FALSE)
 
+    /* Check record against min & max records in tree, to attempt to quickly
+     *  find candidates or avoid further searching.
+     */
+    if(hdr->min_native_rec != NULL) {
+	if((cmp = (hdr->cls->compare)(udata, hdr->min_native_rec)) < 0)
+	    HGOTO_DONE(FALSE) 	/* Less than the least record--not found */ 
+	else if(cmp == 0) { /* Record is found */
+	    if(op && (op)(hdr->min_native_rec, op_data) < 0)
+                HGOTO_ERROR(H5E_BTREE, H5E_NOTFOUND, FAIL, "'found' callback failed for B-tree find operation")
+	    HGOTO_DONE(TRUE)
+	} /* end if */
+    } /* end if */
+    if(hdr->max_native_rec != NULL) {
+	if((cmp = (hdr->cls->compare)(udata, hdr->max_native_rec)) > 0)
+	    HGOTO_DONE(FALSE) 	/* Greater than the greatest record--not found */
+	else if(cmp == 0) { /* Record is found */
+	    if(op && (op)(hdr->max_native_rec, op_data) < 0)
+                HGOTO_ERROR(H5E_BTREE, H5E_NOTFOUND, FAIL, "'found' callback failed for B-tree find operation")
+	    HGOTO_DONE(TRUE)
+	} /* end if */
+    } /* end if */
+
+    /* Current depth of the tree */
+    depth = hdr->depth;
+
     /* Walk down B-tree to find record or leaf node where record is located */
     cmp = -1;
-    while(depth > 0 && cmp != 0) {
+    curr_pos = H5B2_POS_ROOT;
+    while(depth > 0) {
         H5B2_internal_t *internal;          /* Pointer to internal node in B-tree */
         H5B2_node_ptr_t next_node_ptr;      /* Node pointer info for next node */
 
@@ -467,6 +491,24 @@ H5B2_find(H5B2_t *bt2, hid_t dxpl_id, void *udata, H5B2_found_t op,
             /* Get node pointer for next node to search */
             next_node_ptr=internal->node_ptrs[idx];
 
+            /* Set the position of the next node */
+            if(H5B2_POS_MIDDLE != curr_pos) {
+                if(idx == 0) {
+                    if(H5B2_POS_LEFT == curr_pos || H5B2_POS_ROOT == curr_pos)
+                        curr_pos = H5B2_POS_LEFT;
+                    else
+                        curr_pos = H5B2_POS_MIDDLE;
+                } /* end if */
+                else if(idx == internal->nrec) {
+                    if(H5B2_POS_RIGHT == curr_pos || H5B2_POS_ROOT == curr_pos)
+                        curr_pos = H5B2_POS_RIGHT;
+                    else
+                        curr_pos = H5B2_POS_MIDDLE;
+                } /* end if */
+                else
+                    curr_pos = H5B2_POS_MIDDLE;
+            } /* end if */
+
             /* Unlock current node */
             if(H5AC_unprotect(hdr->f, dxpl_id, H5AC_BT2_INT, curr_node_ptr.addr, internal, H5AC__NO_FLAGS_SET) < 0)
                 HGOTO_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release B-tree node")
@@ -523,6 +565,27 @@ H5B2_find(H5B2_t *bt2, hid_t dxpl_id, void *udata, H5B2_found_t op,
 
                 HGOTO_ERROR(H5E_BTREE, H5E_NOTFOUND, FAIL, "'found' callback failed for B-tree find operation")
             } /* end if */
+
+            /* Check for 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 */
         } /* end else */
 
         /* Unlock current node */
@@ -577,9 +640,6 @@ H5B2_index(H5B2_t *bt2, hid_t dxpl_id, H5_iter_order_t order, hsize_t idx,
     /* Make copy of the root node pointer to start search with */
     curr_node_ptr = hdr->root;
 
-    /* Current depth of the tree */
-    depth = hdr->depth;
-
     /* Check for empty tree */
     if(curr_node_ptr.node_nrec == 0)
         HGOTO_ERROR(H5E_BTREE, H5E_NOTFOUND, FAIL, "B-tree has no records")
@@ -588,6 +648,9 @@ H5B2_index(H5B2_t *bt2, hid_t dxpl_id, H5_iter_order_t order, hsize_t idx,
     if(idx >= curr_node_ptr.all_nrec)
         HGOTO_ERROR(H5E_BTREE, H5E_NOTFOUND, FAIL, "B-tree doesn't have that many records")
 
+    /* Current depth of the tree */
+    depth = hdr->depth;
+
     /* Check for reverse indexing and map requested index to appropriate forward index */
     if(order == H5_ITER_DEC)
         idx = curr_node_ptr.all_nrec - (idx + 1);
@@ -736,7 +799,7 @@ H5B2_remove(H5B2_t *bt2, hid_t dxpl_id, void *udata, H5B2_remove_t op,
         hbool_t depth_decreased = FALSE;  /* Flag to indicate whether the depth of the B-tree decreased */
 
         if(H5B2_remove_internal(hdr, dxpl_id, &depth_decreased, NULL, hdr->depth,
-                &(hdr->cache_info), NULL, &hdr->root, udata, op, op_data) < 0)
+                &(hdr->cache_info), NULL, H5B2_POS_ROOT, &hdr->root, udata, op, op_data) < 0)
             HGOTO_ERROR(H5E_BTREE, H5E_CANTDELETE, FAIL, "unable to remove record from B-tree internal node")
 
         /* Check for decreasing the depth of the B-tree */
@@ -754,7 +817,7 @@ H5B2_remove(H5B2_t *bt2, hid_t dxpl_id, void *udata, H5B2_remove_t op,
         } /* end for */
     } /* end if */
     else {
-        if(H5B2_remove_leaf(hdr, dxpl_id, &hdr->root, udata, op, op_data) < 0)
+        if(H5B2_remove_leaf(hdr, dxpl_id, &hdr->root, H5B2_POS_ROOT, udata, op, op_data) < 0)
             HGOTO_ERROR(H5E_BTREE, H5E_CANTDELETE, FAIL, "unable to remove record from B-tree leaf node")
     } /* end else */
 
@@ -818,7 +881,7 @@ H5B2_remove_by_idx(H5B2_t *bt2, hid_t dxpl_id, H5_iter_order_t order,
         hbool_t depth_decreased = FALSE;  /* Flag to indicate whether the depth of the B-tree decreased */
 
         if(H5B2_remove_internal_by_idx(hdr, dxpl_id, &depth_decreased, NULL, hdr->depth,
-                &(hdr->cache_info), NULL, &hdr->root, idx, op, op_data) < 0)
+                &(hdr->cache_info), NULL, &hdr->root, H5B2_POS_ROOT, idx, op, op_data) < 0)
             HGOTO_ERROR(H5E_BTREE, H5E_CANTDELETE, FAIL, "unable to remove record from B-tree internal node")
 
         /* Check for decreasing the depth of the B-tree */
@@ -836,7 +899,7 @@ H5B2_remove_by_idx(H5B2_t *bt2, hid_t dxpl_id, H5_iter_order_t order,
         } /* end for */
     } /* end if */
     else {
-        if(H5B2_remove_leaf_by_idx(hdr, dxpl_id, &hdr->root, (unsigned)idx, op, op_data) < 0)
+        if(H5B2_remove_leaf_by_idx(hdr, dxpl_id, &hdr->root, H5B2_POS_ROOT, (unsigned)idx, op, op_data) < 0)
             HGOTO_ERROR(H5E_BTREE, H5E_CANTDELETE, FAIL, "unable to remove record from B-tree leaf node")
     } /* end else */
 
@@ -970,6 +1033,7 @@ H5B2_modify(H5B2_t *bt2, hid_t dxpl_id, void *udata, H5B2_modify_t op,
 {
     H5B2_hdr_t	*hdr;                   /* Pointer to the B-tree header */
     H5B2_node_ptr_t curr_node_ptr;      /* Node pointer info for current node */
+    H5B2_nodepos_t curr_pos;            /* Position of current node */
     unsigned    depth;                  /* Current depth of the tree */
     int         cmp;                    /* Comparison value of records */
     unsigned    idx;                    /* Location of record which matches key */
@@ -990,16 +1054,17 @@ H5B2_modify(H5B2_t *bt2, hid_t dxpl_id, void *udata, H5B2_modify_t op,
     /* Make copy of the root node pointer to start search with */
     curr_node_ptr = hdr->root;
 
-    /* Current depth of the tree */
-    depth = hdr->depth;
-
     /* Check for empty tree */
     if(0 == curr_node_ptr.node_nrec)
         HGOTO_ERROR(H5E_BTREE, H5E_NOTFOUND, FAIL, "B-tree has no records")
 
+    /* Current depth of the tree */
+    depth = hdr->depth;
+
     /* Walk down B-tree to find record or leaf node where record is located */
     cmp = -1;
-    while(depth > 0 && cmp != 0) {
+    curr_pos = H5B2_POS_ROOT;
+    while(depth > 0) {
         unsigned internal_flags = H5AC__NO_FLAGS_SET;
         H5B2_internal_t *internal;          /* Pointer to internal node in B-tree */
         H5B2_node_ptr_t next_node_ptr;      /* Node pointer info for next node */
@@ -1017,6 +1082,24 @@ H5B2_modify(H5B2_t *bt2, hid_t dxpl_id, void *udata, H5B2_modify_t op,
             /* Get node pointer for next node to search */
             next_node_ptr = internal->node_ptrs[idx];
 
+            /* Set the position of the next node */
+            if(H5B2_POS_MIDDLE != curr_pos) {
+                if(idx == 0) {
+                    if(H5B2_POS_LEFT == curr_pos || H5B2_POS_ROOT == curr_pos)
+                        curr_pos = H5B2_POS_LEFT;
+                    else
+                        curr_pos = H5B2_POS_MIDDLE;
+                } /* end if */
+                else if(idx == internal->nrec) {
+                    if(H5B2_POS_RIGHT == curr_pos || H5B2_POS_ROOT == curr_pos)
+                        curr_pos = H5B2_POS_RIGHT;
+                    else
+                        curr_pos = H5B2_POS_MIDDLE;
+                } /* end if */
+                else
+                    curr_pos = H5B2_POS_MIDDLE;
+            } /* end if */
+
             /* Unlock current node */
             if(H5AC_unprotect(hdr->f, dxpl_id, H5AC_BT2_INT, curr_node_ptr.addr, internal, H5AC__NO_FLAGS_SET) < 0)
                 HGOTO_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release B-tree node")
@@ -1092,6 +1175,27 @@ H5B2_modify(H5B2_t *bt2, hid_t dxpl_id, void *udata, H5B2_modify_t op,
 
                 HGOTO_ERROR(H5E_BTREE, H5E_CANTMODIFY, FAIL, "'modify' callback failed for B-tree find operation")
             } /* end if */
+
+            /* Check for modified 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 */
         } /* end else */
 
         /* Mark the node as dirty if it changed */