Changeset 7609


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()

Location:
trunk/libtransmission
Files:
2 added
4 edited

Legend:

Unmodified
Added
Removed
  • trunk/libtransmission/Makefile.am

    r7419 r7609  
    4040    publish.c \
    4141    ratecontrol.c \
     42    request-list.c \
    4243    resume.c \
    4344    rpcimpl.c \
     
    8788    publish.h \
    8889    ratecontrol.h \
     90    request-list.h \
    8991    resume.h \
    9092    rpcimpl.h \
     
    109111    json-test \
    110112    peer-msgs-test \
     113    request-list-test \
    111114    rpc-test \
    112115    test-peer-id \
     
    154157test_peer_id_LDFLAGS = ${apps_ldflags}
    155158
     159request_list_test_SOURCES = request-list-test.c
     160request_list_test_LDADD = ${apps_ldadd}
     161request_list_test_LDFLAGS = ${apps_ldflags}
     162
    156163peer_msgs_test_SOURCES = peer-msgs-test.c
    157164peer_msgs_test_LDADD = ${apps_ldadd}
  • trunk/libtransmission/peer-msgs.c

    r7606 r7609  
    3535#include "platform.h" /* MAX_STACK_ARRAY_SIZE */
    3636#include "ratecontrol.h"
     37#include "request-list.h"
    3738#include "stats.h"
    3839#include "torrent.h"
     
    103104};
    104105
    105 /**
    106 ***  REQUEST MANAGEMENT
    107 **/
    108 
    109106enum
    110107{
     
    114111    AWAITING_BT_PIECE
    115112};
    116 
    117 struct peer_request
    118 {
    119     uint32_t    index;
    120     uint32_t    offset;
    121     uint32_t    length;
    122     time_t      time_requested;
    123 };
    124 
    125 static inline tr_bool
    126 requestsMatch( const struct peer_request * a, const struct peer_request * b )
    127 {
    128     return (a->index==b->index) && (a->offset==b->offset) && (a->length==b->length);
    129 }
    130 
    131 struct request_list
    132 {
    133     uint16_t               count;
    134     uint16_t               max;
    135     struct peer_request *  requests;
    136 };
    137 
    138 static const struct request_list REQUEST_LIST_INIT = { 0, 0, NULL };
    139 
    140 static void
    141 reqListReserve( struct request_list * list,
    142                 uint16_t              max )
    143 {
    144     if( list->max < max )
    145     {
    146         list->max = max;
    147         list->requests = tr_renew( struct peer_request,
    148                                    list->requests,
    149                                    list->max );
    150     }
    151 }
    152 
    153 static void
    154 reqListClear( struct request_list * list )
    155 {
    156     tr_free( list->requests );
    157     *list = REQUEST_LIST_INIT;
    158 }
    159 
    160 static void
    161 reqListCopy( struct request_list * dest, const struct request_list * src )
    162 {
    163     dest->count = dest->max = src->count;
    164     dest->requests = tr_memdup( src->requests, dest->count * sizeof( struct peer_request ) );
    165 }
    166 
    167 static void
    168 reqListRemoveOne( struct request_list * list,
    169                   int                   i )
    170 {
    171     assert( 0 <= i && i < list->count );
    172 
    173     memmove( &list->requests[i],
    174              &list->requests[i + 1],
    175              sizeof( struct peer_request ) * ( --list->count - i ) );
    176 }
    177 
    178 static void
    179 reqListAppend( struct request_list *       list,
    180                const struct peer_request * req )
    181 {
    182     if( ++list->count >= list->max )
    183         reqListReserve( list, list->max + 8 );
    184 
    185     list->requests[list->count - 1] = *req;
    186 }
    187 
    188 static int
    189 reqListPop( struct request_list * list,
    190             struct peer_request * setme )
    191 {
    192     int success;
    193 
    194     if( !list->count )
    195         success = FALSE;
    196     else {
    197         *setme = list->requests[0];
    198         reqListRemoveOne( list, 0 );
    199         success = TRUE;
    200     }
    201 
    202     return success;
    203 }
    204 
    205 static int
    206 reqListFind( struct request_list *       list,
    207              const struct peer_request * key )
    208 {
    209     uint16_t i;
    210 
    211     for( i = 0; i < list->count; ++i )
    212         if( requestsMatch( key, list->requests + i ) )
    213             return i;
    214 
    215     return -1;
    216 }
    217 
    218 static int
    219 reqListRemove( struct request_list *       list,
    220                const struct peer_request * key )
    221 {
    222     int success;
    223     const int i = reqListFind( list, key );
    224 
    225     if( i < 0 )
    226         success = FALSE;
    227     else {
    228         reqListRemoveOne( list, i );
    229         success = TRUE;
    230     }
    231 
    232     return success;
    233 }
    234113
    235114/**
     
    861740                const time_t           oldestAllowed )
    862741{
    863     int i;
    864 
    865     /* walk through the list, looking for the first req that's too old */
    866     for( i=0; i<list->count; ++i ) {
    867         const struct peer_request * req = &list->requests[i];
    868         if( req->time_requested < oldestAllowed )
     742    size_t i;
     743    struct request_list tmp = REQUEST_LIST_INIT;
     744
     745    /* since the fifo list is sorted by time, the oldest will be first */
     746    if( list->fifo[0].time_requested >= oldestAllowed )
     747        return;
     748
     749    /* if we found one too old, start pruning them */
     750    reqListCopy( &tmp, list );
     751    for( i=0; i<tmp.len; ++i ) {
     752        const struct peer_request * req = &tmp.fifo[i];
     753        if( req->time_requested >= oldestAllowed )
    869754            break;
    870     }
    871 
    872     /* if we found one too old, start pruning them */
    873     if( i < list->count ) {
    874         struct request_list tmp = REQUEST_LIST_INIT;
    875         reqListCopy( &tmp, list );
    876         for( ; i<tmp.count; ++i ) {
    877             const struct peer_request * req = &tmp.requests[i];
    878             if( req->time_requested < oldestAllowed )
    879                 tr_peerMsgsCancel( msgs, req->index, req->offset, req->length );
    880         }
    881         reqListClear( &tmp );
    882     }
     755        tr_peerMsgsCancel( msgs, req->index, req->offset, req->length );
     756    }
     757    reqListClear( &tmp );
    883758}
    884759
     
    909784    const int           max = msgs->maxActiveRequests;
    910785    int                 sent = 0;
    911     int                 count = msgs->clientAskedFor.count;
     786    int                 len = msgs->clientAskedFor.len;
    912787    struct peer_request req;
    913788
     
    917792        return;
    918793
    919     while( ( count < max ) && reqListPop( &msgs->clientWillAskFor, &req ) )
     794    while( ( len < max ) && reqListPop( &msgs->clientWillAskFor, &req ) )
    920795    {
    921796        const tr_block_index_t block = _tr_block( msgs->torrent, req.index, req.offset );
     
    932807            reqListAppend( &msgs->clientAskedFor, &req );
    933808
    934             ++count;
     809            ++len;
    935810            ++sent;
    936811        }
     
    939814    if( sent )
    940815        dbgmsg( msgs, "pump sent %d requests, now have %d active and %d queued",
    941                 sent, msgs->clientAskedFor.count, msgs->clientWillAskFor.count );
    942 
    943     if( count < max )
     816                sent, msgs->clientAskedFor.len, msgs->clientWillAskFor.len );
     817
     818    if( len < max )
    944819        fireNeedReq( msgs );
    945820}
     
    949824{
    950825    const int req_max = msgs->maxActiveRequests;
    951     return msgs->clientWillAskFor.count >= req_max;
     826    return msgs->clientWillAskFor.len >= (size_t)req_max;
    952827}
    953828
     
    988863    req.offset = offset;
    989864    req.length = length;
    990     if( reqListFind( &msgs->clientAskedFor, &req ) != -1 ) {
     865    if( reqListHas( &msgs->clientAskedFor, &req ) ) {
    991866        dbgmsg( msgs, "declining because it's a duplicate" );
    992867        return TR_ADDREQ_DUPLICATE;
    993868    }
    994     if( reqListFind( &msgs->clientWillAskFor, &req ) != -1 ) {
     869    if( reqListHas( &msgs->clientWillAskFor, &req ) ) {
    995870        dbgmsg( msgs, "declining because it's a duplicate" );
    996871        return TR_ADDREQ_DUPLICATE;
     
    1011886cancelAllRequestsToPeer( tr_peermsgs * msgs, tr_bool sendCancel )
    1012887{
    1013     int i;
     888    size_t i;
    1014889    struct request_list a = msgs->clientWillAskFor;
    1015890    struct request_list b = msgs->clientAskedFor;
     
    1019894    msgs->clientWillAskFor = REQUEST_LIST_INIT;
    1020895
    1021     for( i=0; i<a.count; ++i )
    1022         fireCancelledReq( msgs, &a.requests[i] );
    1023 
    1024     for( i = 0; i < b.count; ++i ) {
    1025         fireCancelledReq( msgs, &b.requests[i] );
     896    for( i=0; i<a.len; ++i )
     897        fireCancelledReq( msgs, &a.fifo[i] );
     898
     899    for( i = 0; i < b.len; ++i ) {
     900        fireCancelledReq( msgs, &b.fifo[i] );
    1026901        if( sendCancel )
    1027             protocolSendCancel( msgs, &b.requests[i] );
     902            protocolSendCancel( msgs, &b.fifo[i] );
    1028903    }
    1029904
     
    16871562
    16881563    dbgmsg( msgs, "peer has %d more blocks we've asked for",
    1689             msgs->clientAskedFor.count );
     1564            msgs->clientAskedFor.len );
    16901565
    16911566    /**
  • 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}
  • trunk/libtransmission/utils.h

    r7592 r7609  
    315315    return tr_strndup( in, in ? strlen( (const char*)in ) : 0 );
    316316}
     317
     318/* @brief same argument list as bsearch() */
     319int tr_lowerBound( const void * key,
     320                   const void * base,
     321                   size_t       nmemb,
     322                   size_t       size,
     323                   int       (* compar)(const void* key, const void* arrayMember),
     324                   tr_bool    * exact_match );
     325
    317326
    318327char*       tr_strdup_printf( const char * fmt,
Note: See TracChangeset for help on using the changeset viewer.