source: trunk/libtransmission/request-list.c @ 7609

Last change on this file since 7609 was 7609, checked in by charles, 12 years ago

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

File size: 4.0 KB
Line 
1/*
2 * This file Copyright (C) 2007-2009 Charles Kerr <charles@transmissionbt.com>
3 *
4 * This file is licensed by the GPL version 2.  Works owned by the
5 * Transmission project are granted a special exemption to clause 2(b)
6 * so that the bulk of its code can remain under the MIT license.
7 * This exemption does not extend to derived works not owned by
8 * the Transmission project.
9 *
10 * $Id:$
11 */
12
13#include <assert.h>
14#include "transmission.h"
15#include "request-list.h"
16#include "utils.h"
17
18static int
19compareRequests( const void * va, const void * vb )
20{
21    const struct peer_request * a = va;
22    const struct peer_request * b = vb;
23
24    if( a->index != b->index )
25        return a->index < b->index ? -1 : 1;
26
27    if( a->offset != b->offset )
28        return a->offset < b->offset ? -1 : 1;
29
30    if( a->length != b->length )
31        return a->length < b->length ? -1 : 1;
32
33    return 0;
34}
35
36const struct request_list REQUEST_LIST_INIT = { 0, 0, NULL, NULL };
37
38static void
39reqListReserve( struct request_list * list, size_t max )
40{
41    if( list->max < max )
42    {
43        list->max = max;
44        list->fifo = tr_renew( struct peer_request, list->fifo, list->max );
45        list->sort = tr_renew( struct peer_request, list->sort, list->max );
46    }
47}
48
49void
50reqListClear( struct request_list * list )
51{
52    tr_free( list->fifo );
53    tr_free( list->sort );
54    *list = REQUEST_LIST_INIT;
55}
56
57void
58reqListCopy( struct request_list * dest, const struct request_list * src )
59{
60    dest->len = dest->max = src->len;
61    dest->fifo = tr_memdup( src->fifo, dest->len * sizeof( struct peer_request ) );
62    dest->sort = tr_memdup( src->sort, dest->len * sizeof( struct peer_request ) );
63}
64
65static int
66reqListSortPos( const struct request_list * list,
67                const struct peer_request * req,
68                tr_bool                   * exactMatch )
69{
70    return tr_lowerBound( req,
71                          list->sort,
72                          list->len,
73                          sizeof( struct peer_request ), 
74                          compareRequests,
75                          exactMatch );
76}
77
78void
79reqListAppend( struct request_list *       list,
80               const struct peer_request * req )
81{
82    int low;
83
84    reqListReserve( list, list->len + 8 );
85
86    /* append into list->fifo */
87    list->fifo[list->len] = *req;
88
89    /* insert into list->sort */
90    low = reqListSortPos( list, req, NULL );
91    memmove( &list->sort[low+1], &list->sort[low], (list->len-low)*sizeof(struct peer_request) );
92    list->sort[low] = *req;
93
94    ++list->len;
95}
96
97static tr_bool
98reqListRemoveFromSorted( struct request_list * list, const struct peer_request * key )
99{
100    tr_bool found;
101    const int low = reqListSortPos( list, key, &found );
102    if( found )
103        memmove( &list->sort[low], &list->sort[low+1], (list->len-low-1)*sizeof(struct peer_request));
104    return found;
105}
106
107static void
108reqListRemoveNthFromFifo( struct request_list * list, int n )
109{
110    memmove( &list->fifo[n], &list->fifo[n+1], (list->len-1)*sizeof(struct peer_request));
111}
112
113tr_bool
114reqListPop( struct request_list * list,
115            struct peer_request * setme )
116{
117    tr_bool success;
118
119    if( !list->len )
120    {
121        success = FALSE;
122    }
123    else
124    {
125        *setme = list->fifo[0];
126        reqListRemoveNthFromFifo( list, 0 );
127        reqListRemoveFromSorted( list, setme );
128        --list->len;
129        success = TRUE;
130    }
131
132    return success;
133}
134
135tr_bool
136reqListHas( const struct request_list * list,
137            const struct peer_request * key )
138{
139    tr_bool exactMatch;
140    reqListSortPos( list, key, &exactMatch );
141    return exactMatch;
142}
143
144tr_bool
145reqListRemove( struct request_list       * list,
146               const struct peer_request * key )
147{
148    tr_bool found = reqListRemoveFromSorted( list, key );
149
150    if( found )
151    {
152        size_t i;
153        for( i=0; i<list->len; ++i )
154            if( !compareRequests( &list->fifo[i], key ) )
155                break;
156        assert( i < list->len );
157        reqListRemoveNthFromFifo( list, i );
158        --list->len;
159    }
160
161    return found;
162}
Note: See TracBrowser for help on using the repository browser.