Changeset 13709


Ignore:
Timestamp:
Dec 28, 2012, 8:10:03 PM (8 years ago)
Author:
jordan
Message:

(trunk, libT) #5199 'tr_sessionGetNextQueuedTorrent() can be faster' -- modify session.c's tr_sessionGetNextQueuedTorrents() and peer-mgr.c's getPeerCandidates() functions use the new tr_quickfindFirstK() utility"

Location:
trunk/libtransmission
Files:
3 edited

Legend:

Unmodified
Added
Removed
  • trunk/libtransmission/peer-mgr.c

    r13707 r13709  
    35913591}
    35923592
     3593
     3594static void
     3595queuePulseForeach (void * vtor)
     3596{
     3597  tr_torrent * tor = vtor;
     3598
     3599  tr_torrentStartNow (tor);
     3600
     3601  if (tor->queue_started_callback != NULL)
     3602    (*tor->queue_started_callback)(tor, tor->queue_started_user_data);
     3603}
     3604
    35933605static void
    35943606queuePulse (tr_session * session, tr_direction dir)
    35953607{
    3596     assert (tr_isSession (session));
    3597     assert (tr_isDirection (dir));
    3598 
    3599     if (tr_sessionGetQueueEnabled (session, dir))
    3600     {
    3601         int i;
    3602         const int n = tr_sessionCountQueueFreeSlots (session, dir);
    3603         for (i=0; i<n; i++) {
    3604             tr_torrent * tor = tr_sessionGetNextQueuedTorrent (session, dir);
    3605             if (tor != NULL) {
    3606                 tr_torrentStartNow (tor);
    3607                 if (tor->queue_started_callback != NULL)
    3608                   (*tor->queue_started_callback)(tor, tor->queue_started_user_data);
    3609             }
    3610         }
     3608  assert (tr_isSession (session));
     3609  assert (tr_isDirection (dir));
     3610
     3611  if (tr_sessionGetQueueEnabled (session, dir))
     3612    {
     3613      tr_ptrArray torrents = TR_PTR_ARRAY_INIT;
     3614
     3615      tr_sessionGetNextQueuedTorrents (session,
     3616                                       dir,
     3617                                       tr_sessionCountQueueFreeSlots (session, dir),
     3618                                       &torrents);
     3619
     3620      tr_ptrArrayForeach (&torrents, queuePulseForeach);
     3621
     3622      tr_ptrArrayDestruct (&torrents, NULL);
    36113623    }
    36123624}
     
    38783890}
    38793891
    3880 #ifndef NDEBUG
    38813892static int
    3882 checkPartition (const struct peer_candidate * candidates, int left, int right, uint64_t pivotScore, int storeIndex)
    3883 {
    3884     int i;
    3885 
    3886     assert (storeIndex >= left);
    3887     assert (storeIndex <= right);
    3888     assert (candidates[storeIndex].score == pivotScore);
    3889 
    3890     for (i=left; i<storeIndex; ++i)
    3891         assert (candidates[i].score < pivotScore);
    3892     for (i=storeIndex+1; i<=right; ++i)
    3893         assert (candidates[i].score >= pivotScore);
    3894 
    3895     return true;
    3896 }
    3897 #endif
    3898 
    3899 /* Helper to selectPeerCandidates().
    3900  * Adapted from http://en.wikipedia.org/wiki/Selection_algorithm */
    3901 static int
    3902 partitionPeerCandidates (struct peer_candidate * candidates, int left, int right, int pivotIndex)
    3903 {
    3904     int i;
    3905     int storeIndex;
    3906     struct peer_candidate tmp;
    3907     const struct peer_candidate pivotValue = candidates[pivotIndex];
    3908 
    3909     /* move pivot to end */
    3910     tmp = candidates[right];
    3911     candidates[right] = pivotValue;
    3912     candidates[pivotIndex] = tmp;
    3913 
    3914     storeIndex = left;
    3915     for (i=left; i<=right; ++i)
    3916     {
    3917         if (candidates[i].score < pivotValue.score)
    3918         {
    3919             tmp = candidates[storeIndex];
    3920             candidates[storeIndex] = candidates[i];
    3921             candidates[i] = tmp;
    3922             storeIndex++;
    3923         }
    3924     }
    3925 
    3926     /* move pivot to its final place */
    3927     tmp = candidates[right];
    3928     candidates[right] = candidates[storeIndex];
    3929     candidates[storeIndex] = tmp;
    3930 
    3931     /* sanity check */
    3932     assert (checkPartition (candidates, left, right, pivotValue.score, storeIndex));
    3933 
    3934     return storeIndex;
     3893comparePeerCandidates (const void * va, const void * vb)
     3894{
     3895  int ret;
     3896  const struct peer_candidate * a = va;
     3897  const struct peer_candidate * b = vb;
     3898
     3899  if (a->score < b->score)
     3900    ret = -1;
     3901  else if (a->score > b->score)
     3902    ret = 1;
     3903  else
     3904    ret = 0;
     3905
     3906  return ret;
    39353907}
    39363908
     
    39383910   Adapted from http://en.wikipedia.org/wiki/Selection_algorithm */
    39393911static void
    3940 selectPeerCandidates (struct peer_candidate * candidates, int left, int right, int k)
    3941 {
    3942     if (right > left)
    3943     {
    3944         const int pivotIndex = left + (right-left)/2;
    3945 
    3946         int pivotNewIndex = partitionPeerCandidates (candidates, left, right, pivotIndex);
    3947 
    3948         if (pivotNewIndex > left + k) /* new condition */
    3949             selectPeerCandidates (candidates, left, pivotNewIndex-1, k);
    3950         else if (pivotNewIndex < left + k)
    3951             selectPeerCandidates (candidates, pivotNewIndex+1, right, k+left-pivotNewIndex-1);
    3952     }
     3912selectPeerCandidates (struct peer_candidate * candidates, int candidate_count, int select_count)
     3913{
     3914  tr_quickfindFirstK (candidates,
     3915                      candidate_count,
     3916                      sizeof(struct peer_candidate),
     3917                      comparePeerCandidates,
     3918                      select_count);
    39533919}
    39543920
     
    40434009    *candidateCount = walk - candidates;
    40444010    if (walk != candidates)
    4045         selectPeerCandidates (candidates, 0, (walk-candidates)-1, max);
     4011        selectPeerCandidates (candidates, walk-candidates, max);
    40464012
    40474013    assert (checkBestScoresComeFirst (candidates, *candidateCount, max));
  • trunk/libtransmission/session.c

    r13703 r13709  
    27142714}
    27152715
    2716 tr_torrent *
    2717 tr_sessionGetNextQueuedTorrent (tr_session * session, tr_direction direction)
    2718 {
    2719     tr_torrent * tor = NULL;
    2720     tr_torrent * best_tor = NULL;
    2721     int best_position = INT_MAX;
    2722 
    2723     assert (tr_isSession (session));
    2724     assert (tr_isDirection (direction));
    2725 
    2726     while ((tor = tr_torrentNext (session, tor)))
     2716struct TorrentAndPosition
     2717{
     2718  tr_torrent * tor;
     2719  int position;
     2720};
     2721
     2722/* higher positions come first */
     2723static int
     2724compareTorrentAndPositions (const void * va, const void * vb)
     2725{
     2726  int ret;
     2727  const struct TorrentAndPosition * a = va;
     2728  const struct TorrentAndPosition * b = vb;
     2729
     2730  if (a->position > b->position)
     2731    ret = -1;
     2732  else if (a->position < b->position)
     2733    ret = 1;
     2734  else
     2735    ret = 0;
     2736
     2737  return ret;
     2738}
     2739
     2740
     2741void
     2742tr_sessionGetNextQueuedTorrents (tr_session   * session,
     2743                                 tr_direction   direction,
     2744                                 size_t         num_wanted,
     2745                                 tr_ptrArray  * setme)
     2746{
     2747  size_t i;
     2748  tr_torrent * tor;
     2749  struct TorrentAndPosition * candidates;
     2750
     2751  assert (tr_isSession (session));
     2752  assert (tr_isDirection (direction));
     2753
     2754  /* build an array of the candidates */
     2755  candidates = tr_new (struct TorrentAndPosition, session->torrentCount);
     2756  tor = NULL;
     2757  while ((tor = tr_torrentNext (session, tor)))
    27272758    {
    2728         int position;
    2729 
    2730         if (!tr_torrentIsQueued (tor))
    2731             continue;
    2732         if (direction != tr_torrentGetQueueDirection (tor))
    2733             continue;
    2734 
    2735         position = tr_torrentGetQueuePosition (tor);
    2736         if (best_position > position) {
    2737             best_position = position;
    2738             best_tor = tor;
    2739         }
    2740     }
    2741 
    2742     return best_tor;
     2759      if (!tr_torrentIsQueued (tor))
     2760        continue;
     2761
     2762      if (direction != tr_torrentGetQueueDirection (tor))
     2763        continue;
     2764
     2765      candidates[i].tor = tor;
     2766      candidates[i].position = tr_torrentGetQueuePosition (tor);
     2767      ++i;
     2768    }
     2769
     2770  /* find the best n candidates */
     2771  if (num_wanted > i)
     2772    num_wanted = i;
     2773  else if (num_wanted < i)
     2774    tr_quickfindFirstK (candidates, i,
     2775                        sizeof(struct TorrentAndPosition),
     2776                        compareTorrentAndPositions, num_wanted);
     2777
     2778  /* add them to the return array */
     2779  for (i=0; i<num_wanted; ++i)
     2780    tr_ptrArrayAppend (setme, candidates[i].tor);
     2781
     2782  /* cleanup */
     2783  tr_free (candidates);
    27432784}
    27442785
  • trunk/libtransmission/session.h

    r13704 r13709  
    330330
    331331tr_torrent * tr_sessionGetNextQueuedSeed (tr_session * session);
    332 tr_torrent * tr_sessionGetNextQueuedTorrent (tr_session * session, tr_direction);
     332void tr_sessionGetNextQueuedTorrents (tr_session * session, tr_direction, size_t n, tr_ptrArray * steme);
    333333
    334334int tr_sessionCountQueueFreeSlots (tr_session * session, tr_direction);
Note: See TracChangeset for help on using the changeset viewer.