From fc512bc7716ff9b90eef10eb313fafb2fe12ba0b Mon Sep 17 00:00:00 2001 From: Quincey Koziol Date: Mon, 5 Jul 2004 12:08:47 -0500 Subject: [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 --- src/H5TB.c | 206 +++++++++++++++++++++++++++++++++++-------------------------- 1 file 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' -- cgit v0.12