Ignore:
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:
1 edited

Legend:

Unmodified
Added
Removed
  • trunk/libtransmission/utils.c

    r7594 r7609  
    12881288    tr_lockUnlock( l );
    12891289}
     1290
     1291/***
     1292****
     1293***/
     1294
     1295int
     1296tr_lowerBound( const void * key,
     1297               const void * base,
     1298               size_t       nmemb,
     1299               size_t       size,
     1300               int       (* compar)(const void* key, const void* arrayMember),
     1301               tr_bool    * exact_match )
     1302{
     1303    size_t first = 0;
     1304
     1305    while( nmemb > 0 )
     1306    {
     1307        const size_t half = nmemb / 2;
     1308        const size_t middle = first + half;
     1309        const int c = compar( key, ((const char*)base) + size*middle );
     1310
     1311        if( c < 0 )
     1312        {
     1313            first = middle + 1;
     1314            nmemb = nmemb - half - 1;
     1315        }
     1316        else if( !c )
     1317        {
     1318            if( exact_match )
     1319                *exact_match = TRUE;
     1320            return middle;
     1321        }
     1322        else
     1323        {
     1324            nmemb = half;
     1325        }
     1326    }
     1327
     1328    if( exact_match )
     1329        *exact_match = FALSE;
     1330
     1331    return first;
     1332}
Note: See TracChangeset for help on using the changeset viewer.