Changeset 13708


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

Location:
trunk/libtransmission
Files:
3 edited

Legend:

Unmodified
Added
Removed
  • trunk/libtransmission/utils-test.c

    r13667 r13708  
    219219
    220220static int
     221test_quickFindFirst_Iteration (const size_t k, const size_t n, int * buf, int range)
     222{
     223  size_t i;
     224  int highest_low;
     225  int lowest_high;
     226
     227  /* populate buf with random ints */
     228  for (i=0; i<n; ++i)
     229    buf[i] = tr_cryptoWeakRandInt (range);
     230
     231  /* find the best k */
     232  tr_quickfindFirstK (buf, n, sizeof(int), compareInts, k);
     233
     234  /* confirm that the smallest K ints are in the first slots K slots in buf */
     235
     236  highest_low = INT_MIN;
     237  for (i=0; i<k; ++i)
     238    if (highest_low < buf[i])
     239      highest_low = buf[i];
     240
     241  lowest_high = INT_MAX;
     242  for (i=k; i<n; ++i)
     243    if (lowest_high > buf[i])
     244      lowest_high = buf[i];
     245
     246  check (highest_low <= lowest_high);
     247
     248  return 0;
     249}
     250
     251static int
     252test_quickfindFirst (void)
     253{
     254  size_t i;
     255  const size_t k = 10;
     256  const size_t n = 100;
     257  const size_t n_trials = 1000;
     258  int * buf = tr_new (int, n);
     259
     260  for (i=0; i<n_trials; ++i)
     261    check_int_eq (0, test_quickFindFirst_Iteration (k, n, buf, 100));
     262
     263  tr_free (buf);
     264  return 0;
     265}
     266
     267static int
    221268test_memmem (void)
    222269{
     
    374421                             test_hex,
    375422                             test_lowerbound,
     423                             test_quickfindFirst,
    376424                             test_memmem,
    377425                             test_numbers,
  • 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
  • trunk/libtransmission/utils.h

    r13667 r13708  
    344344                   bool       * exact_match) TR_GNUC_HOT TR_GNUC_NONNULL (1,5,6);
    345345
     346/** @brief moves the best k items to the first slots in the array. O(n) */
     347void tr_quickfindFirstK (void * base, size_t nmemb, size_t size,
     348                         int (*compar)(const void *, const void *), size_t k);
    346349
    347350/**
Note: See TracChangeset for help on using the changeset viewer.