RE: (ITS#6985) sssvlv / greaterThanOrEqual problem

[ctcard@hotmail.com]

> >
> >>>>>> Looking at the code in sssvlv.c, it uses tavl_find3() to search the values, but the
> >>>>>> code in tavl_find3() looks to me that it only works properly with an exact match
> >>>>>> type of matching rule:
> >>>>>>
> >>>>>> Avlnode *
> >>>>>> tavl_find3( Avlnode *root, const void *data, AVL_CMP fcmp, int *ret )
> >>>>>> {
> >>>>>> int cmp = -1, dir;
> >>>>>> Avlnode *prev = root;
> >>>>>>
> >>>>>> while ( root != 0&& (cmp = (*fcmp)( data, root->avl_data )) != 0 ) {
> >>>>>> prev = root;
> >>>>>> dir = cmp> 0;
> >>>>>> root = avl_child( root, dir );
> >>>>>> }
> >>>>>> *ret = cmp;
> >>>>>> return root ? root : prev;
> >>>>>> }
> >>>>>>
> >>>>>> since the while loop terminates when the fcmp function returns 0 (i.e. exact match).
> >>>>>>
> >>>>>
> >>>>> I think I've worked out where the problem is.
> >>>>> Firstly, there's a comment before tavl_find3() saying
> >>>>> /*
> >>>>> * tavl_find2 - returns Avlnode instead of data pointer.
> >>>>> * tavl_find3 - as above, but returns Avlnode even if no match is found.
> >>>>> * also set *ret = last comparison result, or -1 if root == NULL.
> >>>>> */
> >>>>>
> >>>>> but the "or -1 if root == NULL" is not done.
> >>
> >> Not true; since cmp is initialized to -1, it will return -1 when the function
> >> is entered with root == NULL. There is no bug in this part.It depends how you read the comment.
>
> I wrote the code and the comment; it does what I intended it to do. There is
> no "depends" about it.
The comment is ambiguous, but in any case the code as it stands doesn't work with the way tavl_find3() is called in sssvlv.c.For example:if cmp > 0 when the while loop terminates, the sssvlv code treats that as if the search failed, whereas the search oughtto return the closest node > search node.
My suggested patch does work with the way tavl_find3() is called in sssvlv.c, but I'd be happy with adding a new function, tavl_find4() say, to implement this functionality. In that case I'd suggest it look like this:
Avlnode *tavl_find4( Avlnode *root, const void *data, AVL_CMP fcmp){    int cmp, dir;    Avlnode *prev = root;    Avlnode *prev_gt = 0;
    while ( root != 0 && (cmp = (*fcmp)( data, root->avl_data )) != 0 ) {        prev = root;        dir = cmp > 0;        prev_gt = (dir ? prev_gt : root);        root = avl_child( root, dir );    }    return (root ? root : (prev_gt ? prev_gt : prev));}
tavl_find4() always returns the first node >= the search node, unless the search node is > all the nodes in the tree, in which case the last node is returned (or null if the tree is empty).
Then replace 
        cur_node = tavl_find3( so->so_tree, sn, node_cmp, &j );        /* didn't find >= match */        if ( j > 0 )            cur_node = NULL;by        cur_node = tavl_find4( so->so_tree, sn, node_cmp); in sssvlv.c.

Chris