Changeset 7609 for trunk/libtransmission/utils.c

Timestamp:

Jan 4, 2009, 4:29:44 PM (12 years ago)

Author:

charles

Message:

(trunk libT) new peer request fifo queue with log(N) search time. new unit tests for the queue. new utility tr_lowerBound()

File:

• trunk/libtransmission/utils.c (modified) (1 diff)

trunk/libtransmission/utils.c

@@ -1288 +1288 @@
     tr_lockUnlock( l );
 }
+
+/***
+****
+***/
+
+int
+tr_lowerBound( const void * key,
+               const void * base,
+               size_t       nmemb,
+               size_t       size,
+               int       (* compar)(const void* key, const void* arrayMember),
+               tr_bool    * exact_match )
+{
+    size_t first = 0;
+
+    while( nmemb > 0 )
+    {
+        const size_t half = nmemb / 2;
+        const size_t middle = first + half;
+        const int c = compar( key, ((const char*)base) + size*middle );
+
+        if( c < 0 )
+        {
+            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;
+
+    return first;
+}