Ignore:
Timestamp:
Dec 28, 2012, 8:07:50 PM (9 years ago)
Author:
jordan
Message:

(trunk, libT) #5199 'tr_sessionGetNextQueuedTorrent() can be faster' -- copy peer-mgr.c's partial-sorting peer candidate code to a reusable function in utils.c, tr_quickfindFirstK()"

File:
1 edited

Legend:

Unmodified
Added
Removed
  • trunk/libtransmission/utils.c

    r13683 r13708  
    12541254/***
    12551255****
     1256****
     1257***/
     1258
     1259/* Byte-wise swap two items of size SIZE.
     1260   From glibc, written by Douglas C. Schmidt, LGPL 2.1 or higher */
     1261#define SWAP(a, b, size) \
     1262  do { \
     1263    register size_t __size = (size); \
     1264    register char *__a = (a), *__b = (b); \
     1265    if (__a != __b) do { \
     1266      char __tmp = *__a; \
     1267      *__a++ = *__b; \
     1268      *__b++ = __tmp; \
     1269    } while (--__size > 0); \
     1270  } while (0)
     1271
     1272
     1273static size_t
     1274quickfindPartition (char * base, size_t left, size_t right, size_t size,
     1275                    int (*compar)(const void *, const void *), size_t pivotIndex)
     1276{
     1277  size_t i;
     1278  size_t storeIndex;
     1279
     1280  /* move pivot to the end */
     1281  SWAP (base+(size*pivotIndex), base+(size*right), size);
     1282
     1283  storeIndex = left;
     1284  for (i=left; i<=right-1; ++i)
     1285    {
     1286      if (compar (base+(size*i), base+(size*right)) <= 0)
     1287        {
     1288          SWAP (base+(size*storeIndex), base+(size*i), size);
     1289          ++storeIndex;
     1290        }
     1291    }
     1292
     1293  /* move pivot to its final place */
     1294  SWAP (base+(size*right), base+(size*storeIndex), size);
     1295
     1296  /* sanity check the partition */
     1297#ifndef NDEBUG
     1298  assert (storeIndex >= left);
     1299  assert (storeIndex <= right);
     1300
     1301  for (i=left; i<storeIndex; ++i)
     1302    assert (compar (base+(size*i), base+(size*storeIndex)) <= 0);
     1303  for (i=storeIndex+1; i<=right; ++i)
     1304    assert (compar (base+(size*i), base+(size*storeIndex)) >= 0);
     1305#endif
     1306
     1307  return storeIndex;
     1308}
     1309
     1310static void
     1311quickfindFirstK (char * base, size_t left, size_t right, size_t size,
     1312                 int (*compar)(const void *, const void *), size_t k)
     1313{
     1314  if (right > left)
     1315    {
     1316      const size_t pivotIndex = left + (right-left)/2u;
     1317
     1318      const size_t pivotNewIndex = quickfindPartition (base, left, right, size, compar, pivotIndex);
     1319
     1320      if (pivotNewIndex > left + k) /* new condition */
     1321        quickfindFirstK (base, left, pivotNewIndex-1, size, compar, k);
     1322      else if (pivotNewIndex < left + k)
     1323        quickfindFirstK (base, pivotNewIndex+1, right, size, compar, k+left-pivotNewIndex-1);
     1324    }
     1325}
     1326
     1327#ifndef NDEBUG
     1328static void
     1329checkBestScoresComeFirst (char * base, size_t nmemb, size_t size,
     1330                          int (*compar)(const void *, const void *), size_t k)
     1331{
     1332  size_t i;
     1333  size_t worstFirstPos = 0;
     1334
     1335  for (i=1; i<k; ++i)
     1336    if (compar (base+(size*worstFirstPos), base+(size*i)) < 0)
     1337      worstFirstPos = i;
     1338
     1339  for (i=0; i<k; ++i)
     1340    assert (compar (base+(size*i), base+(size*worstFirstPos)) <= 0);
     1341  for (i=k; i<nmemb; ++i)
     1342    assert (compar (base+(size*i), base+(size*worstFirstPos)) >= 0);
     1343}
     1344#endif
     1345
     1346void
     1347tr_quickfindFirstK (void * base, size_t nmemb, size_t size,
     1348                    int (*compar)(const void *, const void *), size_t k)
     1349{
     1350  if (k < nmemb)
     1351    {
     1352      quickfindFirstK (base, 0, nmemb-1, size, compar, k);
     1353
     1354#ifndef NDEBUG
     1355      checkBestScoresComeFirst (base, nmemb, size, compar, k);
     1356#endif
     1357    }
     1358}
     1359
     1360/***
     1361****
    12561362***/
    12571363
Note: See TracChangeset for help on using the changeset viewer.