Changeset 9463

Timestamp:

Oct 31, 2009, 10:16:06 PM (13 years ago)

Author:

charles

Message:

(trunk libT) #2547: fix tr_lowerBound()

Location:

trunk/libtransmission

Files:

• utils-test.c (modified) (2 diffs)
• utils.c (modified) (2 diffs)

trunk/libtransmission/utils-test.c

@@ -229 +229 @@
 
 static int
+compareInts( const void * va, const void * vb )
+{
+    const int a = *(const int *)va;
+    const int b = *(const int*)vb;
+    return a - b;
+}
+
+static int
+test_lowerbound( void )
+{
+    int i;
+    const int A[] = { 1, 2, 3, 3, 3, 5, 8 };
+    const int expected_pos[] = { 0, 1, 2, 5, 5, 6, 6, 6, 7, 7 };
+    const int expected_exact[] = { TRUE, TRUE, TRUE, FALSE, TRUE, FALSE, FALSE, TRUE, FALSE, FALSE };
+    const int N = sizeof(A) / sizeof(A[0]);
+
+    for( i=1; i<=10; ++i )
+    {
+        tr_bool exact;
+        const int pos = tr_lowerBound( &i, A, N, sizeof(int), compareInts, &exact );
+
+#if 0
+        fprintf( stderr, "searching for %d.  ", i );
+        fprintf( stderr, "result: index = %d, ", pos );
+        if( pos != N )
+            fprintf( stderr, "A[%d] == %d\n", pos, A[pos] );
+        else
+            fprintf( stderr, "which is off the end.\n" );
+#endif
+        check( pos == expected_pos[i-1] )
+        check( exact == expected_exact[i-1] )
+     
+    }
+
+    return 0;
+}
+
+static int
 test_memmem( void )
 {
@@ -271 +309 @@
     tr_free( out );
 
+    if( ( i = test_lowerbound( ) ) )
+        return i;
     if( ( i = test_strstrip( ) ) )
         return i;

trunk/libtransmission/utils.c

@@ -1109 +1109 @@
     size_t first = 0;
     const char * cbase = base;
+    tr_bool exact = FALSE;
+    int c;
 
     while( nmemb )
@@ -1114 +1116 @@
         const size_t half = nmemb / 2;
         const size_t middle = first + half;
-        const int c = compar( key, cbase + size*middle );
-
-        if( c < 0 )
-        {
+        c = compar( key, cbase + size*middle );
+
+        if( c <= 0 ) {
+            if( c == 0 )
+                exact = TRUE;
+            nmemb = half;
+        } else {
             first = middle + 1;
             nmemb = nmemb - half - 1;
         }
-        else if( !c )
-        {
-            if( exact_match )
-                *exact_match = TRUE;
-            return middle;
-        }
-        else
-        {
-            nmemb = half;
-        }
     }
 
     if( exact_match )
-        *exact_match = FALSE;
+        *exact_match = exact;
 
     return first;