Changeset 9463


Ignore:
Timestamp:
Oct 31, 2009, 10:16:06 PM (13 years ago)
Author:
charles
Message:

(trunk libT) #2547: fix tr_lowerBound()

Location:
trunk/libtransmission
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • trunk/libtransmission/utils-test.c

    r8809 r9463  
    229229
    230230static int
     231compareInts( const void * va, const void * vb )
     232{
     233    const int a = *(const int *)va;
     234    const int b = *(const int*)vb;
     235    return a - b;
     236}
     237
     238static int
     239test_lowerbound( void )
     240{
     241    int i;
     242    const int A[] = { 1, 2, 3, 3, 3, 5, 8 };
     243    const int expected_pos[] = { 0, 1, 2, 5, 5, 6, 6, 6, 7, 7 };
     244    const int expected_exact[] = { TRUE, TRUE, TRUE, FALSE, TRUE, FALSE, FALSE, TRUE, FALSE, FALSE };
     245    const int N = sizeof(A) / sizeof(A[0]);
     246
     247    for( i=1; i<=10; ++i )
     248    {
     249        tr_bool exact;
     250        const int pos = tr_lowerBound( &i, A, N, sizeof(int), compareInts, &exact );
     251
     252#if 0
     253        fprintf( stderr, "searching for %d.  ", i );
     254        fprintf( stderr, "result: index = %d, ", pos );
     255        if( pos != N )
     256            fprintf( stderr, "A[%d] == %d\n", pos, A[pos] );
     257        else
     258            fprintf( stderr, "which is off the end.\n" );
     259#endif
     260        check( pos == expected_pos[i-1] )
     261        check( exact == expected_exact[i-1] )
     262     
     263    }
     264
     265    return 0;
     266}
     267
     268static int
    231269test_memmem( void )
    232270{
     
    271309    tr_free( out );
    272310
     311    if( ( i = test_lowerbound( ) ) )
     312        return i;
    273313    if( ( i = test_strstrip( ) ) )
    274314        return i;
  • trunk/libtransmission/utils.c

    r9444 r9463  
    11091109    size_t first = 0;
    11101110    const char * cbase = base;
     1111    tr_bool exact = FALSE;
     1112    int c;
    11111113
    11121114    while( nmemb )
     
    11141116        const size_t half = nmemb / 2;
    11151117        const size_t middle = first + half;
    1116         const int c = compar( key, cbase + size*middle );
    1117 
    1118         if( c < 0 )
    1119         {
     1118        c = compar( key, cbase + size*middle );
     1119
     1120        if( c <= 0 ) {
     1121            if( c == 0 )
     1122                exact = TRUE;
     1123            nmemb = half;
     1124        } else {
    11201125            first = middle + 1;
    11211126            nmemb = nmemb - half - 1;
    11221127        }
    1123         else if( !c )
    1124         {
    1125             if( exact_match )
    1126                 *exact_match = TRUE;
    1127             return middle;
    1128         }
    1129         else
    1130         {
    1131             nmemb = half;
    1132         }
    11331128    }
    11341129
    11351130    if( exact_match )
    1136         *exact_match = FALSE;
     1131        *exact_match = exact;
    11371132
    11381133    return first;
Note: See TracChangeset for help on using the changeset viewer.