summaryrefslogtreecommitdiffstats
path: root/src
diff options
context:
space:
mode:
authorQuincey Koziol <koziol@hdfgroup.org>2004-07-05 17:08:47 (GMT)
committerQuincey Koziol <koziol@hdfgroup.org>2004-07-05 17:08:47 (GMT)
commitfc512bc7716ff9b90eef10eb313fafb2fe12ba0b (patch)
tree02bd7ba6cc58fff72c91ccba17cf6527abe0ab70 /src
parent3fa118a4b18ba3444e06079eda0dc359fdfe66fb (diff)
downloadhdf5-fc512bc7716ff9b90eef10eb313fafb2fe12ba0b.zip
hdf5-fc512bc7716ff9b90eef10eb313fafb2fe12ba0b.tar.gz
hdf5-fc512bc7716ff9b90eef10eb313fafb2fe12ba0b.tar.bz2
[svn-r8805] Purpose:
Code optimization & bug fix Description: Speed up "fast comparison" lookups in trees by a factor of 2-3x Correctly handle "fast comparisons" for unsigned values (esp. hsize_t). Solution: Mostly removing if statements and redundant assigns, etc. Platforms tested: Solaris 2.7 (arabica) FreeBSD 4.10 (sleipnir) w/parallel Too minor to require h5committest
Diffstat (limited to 'src')
-rw-r--r--src/H5TB.c206
1 files changed, 120 insertions, 86 deletions
diff --git a/src/H5TB.c b/src/H5TB.c
index 526acaf..f55400a 100644
--- a/src/H5TB.c
+++ b/src/H5TB.c
@@ -468,14 +468,11 @@ H5TB_dfind(H5TB_TREE * tree, const void * key, H5TB_NODE ** pp)
*-------------------------------------------------------------------------
*/
H5TB_NODE *
-H5TB_find(H5TB_NODE * root, const void * key,
+H5TB_find(H5TB_NODE * ptr, const void * key,
H5TB_cmp_t compar, int arg, H5TB_NODE ** pp)
{
- H5TB_NODE *ptr = root;
H5TB_NODE *parent = NULL;
int cmp = 1;
- int side;
- H5TB_NODE *ret_value; /* Return value */
FUNC_ENTER_NOAPI_NOFUNC(H5TB_find);
@@ -483,20 +480,27 @@ H5TB_find(H5TB_NODE * root, const void * key,
if(ptr) {
while (0 != (cmp = KEYcmp(key, ptr->key, arg))) {
parent = ptr;
- side = (cmp < 0) ? LEFT : RIGHT;
- if (!HasChild(ptr, side))
- break;
- ptr = ptr->link[side];
- } /* end while */
+ if(cmp<0) {
+ if(!LeftCnt(ptr)) {
+ ptr=NULL;
+ break;
+ } /* end if */
+ ptr = ptr->link[LEFT];
+ } /* end if */
+ else {
+ if(!RightCnt(ptr)) {
+ ptr=NULL;
+ break;
+ } /* end if */
+ ptr = ptr->link[RIGHT];
+ } /* end else */
+ } /* end while */
} /* end if */
if (NULL != pp)
*pp = parent;
- /* Set return value */
- ret_value= (0 == cmp) ? ptr : NULL;
-
- FUNC_LEAVE_NOAPI(ret_value);
+ FUNC_LEAVE_NOAPI(ptr);
} /* end H5TB_find() */
@@ -1317,90 +1321,120 @@ done:
/* This routine is based on tbbtfind (fix bugs in both places!) */
/* Returns a pointer to the found node (or NULL) */
static H5TB_NODE *
-H5TB_ffind(H5TB_NODE * root, const void * key, unsigned fast_compare, H5TB_NODE ** pp)
+H5TB_ffind(H5TB_NODE * ptr, const void * key, unsigned fast_compare, H5TB_NODE ** pp)
{
- H5TB_NODE *ptr = root;
H5TB_NODE *parent = NULL;
- int side;
- int cmp = 1;
- H5TB_NODE *ret_value = NULL;
FUNC_ENTER_NOAPI_NOINIT_NOFUNC(H5TB_ffind);
- switch(fast_compare) {
- case H5TB_FAST_HADDR_COMPARE:
- if (ptr) {
- while (0 != (cmp = H5F_addr_cmp(*(const haddr_t *)key,*(haddr_t *)ptr->key))) {
- parent = ptr;
- side = (cmp < 0) ? LEFT : RIGHT;
- if (!HasChild(ptr, side))
- break;
- ptr = ptr->link[side];
- } /* end while */
- } /* end if */
- if (NULL != pp)
- *pp = parent;
-
- /* Set return value */
- ret_value= (0 == cmp) ? ptr : NULL;
- break;
-
- case H5TB_FAST_INTN_COMPARE:
- if (ptr) {
- while (0 != (cmp = (*(const int *)key - *(int *)ptr->key))) {
- parent = ptr;
- side = (cmp < 0) ? LEFT : RIGHT;
- if (!HasChild(ptr, side))
- break;
- ptr = ptr->link[side];
- } /* end while */
- } /* end if */
- if (NULL != pp)
- *pp = parent;
-
- /* Set return value */
- ret_value= (0 == cmp) ? ptr : NULL;
- break;
+ if(ptr) {
+ switch(fast_compare) {
+ case H5TB_FAST_HADDR_COMPARE:
+ {
+ haddr_t key_val=*(const haddr_t *)key;
+
+ while (key_val != *(haddr_t *)ptr->key) {
+ parent = ptr;
+ if(key_val < *(haddr_t *)ptr->key) {
+ if(!LeftCnt(ptr)) {
+ ptr=NULL;
+ break;
+ } /* end if */
+ ptr = ptr->link[LEFT];
+ } /* end if */
+ else {
+ if(!RightCnt(ptr)) {
+ ptr=NULL;
+ break;
+ } /* end if */
+ ptr = ptr->link[RIGHT];
+ } /* end else */
+ } /* end while */
+ } /* end case */
+ break;
- case H5TB_FAST_STR_COMPARE:
- if (ptr) {
- while (0 != (cmp = HDstrcmp(key,ptr->key))) {
- parent = ptr;
- side = (cmp < 0) ? LEFT : RIGHT;
- if (!HasChild(ptr, side))
- break;
- ptr = ptr->link[side];
- } /* end while */
- } /* end if */
- if (NULL != pp)
- *pp = parent;
+ case H5TB_FAST_INTN_COMPARE:
+ {
+ int key_val=*(const int *)key;
+
+ while (key_val != *(int *)ptr->key) {
+ parent = ptr;
+ if(key_val < *(int *)ptr->key) {
+ if(!LeftCnt(ptr)) {
+ ptr=NULL;
+ break;
+ } /* end if */
+ ptr = ptr->link[LEFT];
+ } /* end if */
+ else {
+ if(!RightCnt(ptr)) {
+ ptr=NULL;
+ break;
+ } /* end if */
+ ptr = ptr->link[RIGHT];
+ } /* end else */
+ } /* end while */
+ } /* end case */
+ break;
- /* Set return value */
- ret_value= (0 == cmp) ? ptr : NULL;
- break;
+ case H5TB_FAST_STR_COMPARE:
+ {
+ int cmp;
+
+ while (0 != (cmp = HDstrcmp(key,ptr->key))) {
+ parent = ptr;
+ if(cmp<0) {
+ if(!LeftCnt(ptr)) {
+ ptr=NULL;
+ break;
+ } /* end if */
+ ptr = ptr->link[LEFT];
+ } /* end if */
+ else {
+ if(!RightCnt(ptr)) {
+ ptr=NULL;
+ break;
+ } /* end if */
+ ptr = ptr->link[RIGHT];
+ } /* end else */
+ } /* end while */
+ } /* end case */
+ break;
- case H5TB_FAST_HSIZE_COMPARE:
- if (ptr) {
- while (0 != (cmp = (int)(*(const hsize_t *)key - *(hsize_t *)ptr->key))) {
- parent = ptr;
- side = (cmp < 0) ? LEFT : RIGHT;
- if (!HasChild(ptr, side))
- break;
- ptr = ptr->link[side];
- } /* end while */
- } /* end if */
- if (NULL != pp)
- *pp = parent;
+ case H5TB_FAST_HSIZE_COMPARE:
+ {
+ hsize_t key_val=*(const hsize_t *)key;
+
+ while (key_val != *(hsize_t *)ptr->key) {
+ parent = ptr;
+ if(key_val < *(hsize_t *)ptr->key) {
+ if(!LeftCnt(ptr)) {
+ ptr=NULL;
+ break;
+ } /* end if */
+ ptr = ptr->link[LEFT];
+ } /* end if */
+ else {
+ if(!RightCnt(ptr)) {
+ ptr=NULL;
+ break;
+ } /* end if */
+ ptr = ptr->link[RIGHT];
+ } /* end else */
+ } /* end while */
+ } /* end case */
+ break;
- /* Set return value */
- ret_value= (0 == cmp) ? ptr : NULL;
- break;
+ default:
+ assert("invalid fast compare type" && 0);
+ break;
+ } /* end switch */
+ } /* end if */
- default:
- break;
- } /* end switch */
+ if (NULL != pp)
+ *pp = parent;
- FUNC_LEAVE_NOAPI(ret_value);
+ FUNC_LEAVE_NOAPI(ptr);
} /* H5TB_ffind() */
/* swapkid -- Often refered to as "rotating" nodes. ptr and ptr's `side'