TMMBRHelp::FindBoundingSet function cleaned

webrtc/modules/rtp_rtcp/source/tmmbr_help.cc

 /*
  *  Copyright (c) 2012 The WebRTC project authors. All Rights Reserved.
  *
  *  Use of this source code is governed by a BSD-style license
  *  that can be found in the LICENSE file in the root of the source
  *  tree. An additional intellectual property rights grant can be found
  *  in the file PATENTS.  All contributing project authors may
  *  be found in the AUTHORS file in the root of the source tree.
  */
 
 #include "webrtc/modules/rtp_rtcp/source/tmmbr_help.h"
 
-#include <assert.h>
-#include <string.h>
-
+#include <algorithm>
 #include <limits>
+#include <memory>
 
 #include "webrtc/base/checks.h"
 #include "webrtc/modules/rtp_rtcp/source/rtp_rtcp_config.h"
 
 namespace webrtc {
 void
 TMMBRSet::VerifyAndAllocateSet(uint32_t minimumSize)
 {
   clear();
   reserve(minimumSize);
@@ skipping 23 matching lines @@
                         uint32_t ssrcSet) {
   RTC_DCHECK_LT(size(), capacity());
   SetEntry(size(), tmmbrSet, packetOHSet, ssrcSet);
 }
 
 void TMMBRSet::RemoveEntry(uint32_t sourceIdx) {
   RTC_DCHECK_LT(sourceIdx, size());
   erase(begin() + sourceIdx);
 }
 
-void TMMBRSet::SwapEntries(uint32_t i, uint32_t j) {
-  using std::swap;
-  swap((*this)[i], (*this)[j]);
-}
-
-void TMMBRSet::ClearEntry(uint32_t idx) {
-  SetEntry(idx, 0, 0, 0);
-}
-
-TMMBRHelp::TMMBRHelp()
-    : _candidateSet(),
-      _boundingSet(),
-      _ptrIntersectionBoundingSet(NULL),
-      _ptrMaxPRBoundingSet(NULL) {
-}
-
-TMMBRHelp::~TMMBRHelp() {
-  delete [] _ptrIntersectionBoundingSet;
-  delete [] _ptrMaxPRBoundingSet;
-  _ptrIntersectionBoundingSet = 0;
-  _ptrMaxPRBoundingSet = 0;
-}
-
-TMMBRSet*
-TMMBRHelp::VerifyAndAllocateBoundingSet(uint32_t minimumSize)
-{
-    rtc::CritScope lock(&_criticalSection);
-
-    if(minimumSize > _boundingSet.capacity())
-    {
-        // make sure that our buffers are big enough
-        if(_ptrIntersectionBoundingSet)
-        {
-            delete [] _ptrIntersectionBoundingSet;
-            delete [] _ptrMaxPRBoundingSet;
-        }
-        _ptrIntersectionBoundingSet = new float[minimumSize];
-        _ptrMaxPRBoundingSet = new float[minimumSize];
-    }
-    _boundingSet.VerifyAndAllocateSet(minimumSize);
-    return &_boundingSet;
-}
-
-TMMBRSet* TMMBRHelp::BoundingSet() {
-  return &_boundingSet;
-}
-
 TMMBRSet*
 TMMBRHelp::VerifyAndAllocateCandidateSet(uint32_t minimumSize)
 {
     rtc::CritScope lock(&_criticalSection);
 
     _candidateSet.VerifyAndAllocateSet(minimumSize);
     return &_candidateSet;
 }
 
 TMMBRSet*
@@ skipping 15 matching lines @@
     {
         if(_candidateSet.Tmmbr(i))
         {
             candidateSet.AddEntry(_candidateSet.Tmmbr(i),
                                   _candidateSet.PacketOH(i),
                                   _candidateSet.Ssrc(i));
         }
         else
         {
             // make sure this is zero if tmmbr = 0
-            assert(_candidateSet.PacketOH(i) == 0);
+            RTC_DCHECK_EQ(_candidateSet.PacketOH(i), 0u);
             // Old code:
             // _candidateSet.ptrPacketOHSet[i] = 0;
         }
     }
 
     // Number of set candidates
     int32_t numSetCandidates = candidateSet.lengthOfSet();
     // Find bounding set
     uint32_t numBoundingSet = 0;
     if (numSetCandidates > 0)
     {
-        numBoundingSet =  FindTMMBRBoundingSet(numSetCandidates, candidateSet);
+        FindBoundingSet(std::move(candidateSet), &_boundingSet);
+        numBoundingSet = _boundingSet.size();
         if(numBoundingSet < 1 || (numBoundingSet > _candidateSet.size()))
         {
             return -1;
         }
         boundingSet = &_boundingSet;
     }
     return numBoundingSet;
 }
 
 
-int32_t
-TMMBRHelp::FindTMMBRBoundingSet(int32_t numCandidates, TMMBRSet& candidateSet)
+void
+TMMBRHelp::FindBoundingSet(std::vector<rtcp::TmmbItem> candidateSet,
+                           std::vector<rtcp::TmmbItem>* boundingSet)
 {
-    rtc::CritScope lock(&_criticalSection);
+    RTC_DCHECK(boundingSet);
+    RTC_DCHECK(!candidateSet.empty());
+    size_t numCandidates = candidateSet.size();
 
     uint32_t numBoundingSet = 0;
-    VerifyAndAllocateBoundingSet(candidateSet.capacity());
+    boundingSet->clear();
+    boundingSet->reserve(candidateSet.size());
 
     if (numCandidates == 1)
     {
-        for (uint32_t i = 0; i < candidateSet.size(); i++)
-        {
-            if (candidateSet.Tmmbr(i) > 0)
-            {
-                _boundingSet.AddEntry(candidateSet.Tmmbr(i),
-                                    candidateSet.PacketOH(i),
-                                    candidateSet.Ssrc(i));
-                numBoundingSet++;
-            }
-        }
-        return (numBoundingSet == 1) ? 1 : -1;
+        RTC_DCHECK(candidateSet[0].bitrate_bps());
+        *boundingSet = std::move(candidateSet);
+        return;
     }
 
     // 1. Sort by increasing packetOH
-    for (int i = candidateSet.size() - 1; i >= 0; i--)
-    {
-        for (int j = 1; j <= i; j++)
-        {
-            if (candidateSet.PacketOH(j-1) > candidateSet.PacketOH(j))
-            {
-                candidateSet.SwapEntries(j-1, j);
-            }
-        }
-    }
+    std::sort(candidateSet.begin(), candidateSet.end(),
+              [](const rtcp::TmmbItem& lhs, const rtcp::TmmbItem& rhs) {
+      return lhs.packet_overhead() < rhs.packet_overhead();
+    });
     // 2. For tuples with same OH, keep the one w/ the lowest bitrate
     for (uint32_t i = 0; i < candidateSet.size(); i++)
     {
-        if (candidateSet.Tmmbr(i) > 0)
+        if (candidateSet[i].bitrate_bps())
         {
             // get min bitrate for packets w/ same OH
-            uint32_t currentPacketOH = candidateSet.PacketOH(i);
-            uint32_t currentMinTMMBR = candidateSet.Tmmbr(i);
+            uint32_t currentPacketOH = candidateSet[i].packet_overhead();
+            uint32_t currentMinTMMBR = candidateSet[i].bitrate_bps();
             uint32_t currentMinIndexTMMBR = i;
             for (uint32_t j = i+1; j < candidateSet.size(); j++)
             {
-                if(candidateSet.PacketOH(j) == currentPacketOH)
+                if(candidateSet[j].packet_overhead() == currentPacketOH)
                 {
-                    if(candidateSet.Tmmbr(j) < currentMinTMMBR)
+                    if(candidateSet[j].bitrate_bps() < currentMinTMMBR)
                     {
-                        currentMinTMMBR = candidateSet.Tmmbr(j);
+                        currentMinTMMBR = candidateSet[j].bitrate_bps();
                         currentMinIndexTMMBR = j;
                     }
                 }
             }
             // keep lowest bitrate
             for (uint32_t j = 0; j < candidateSet.size(); j++)
             {
-              if(candidateSet.PacketOH(j) == currentPacketOH
+              if(candidateSet[j].packet_overhead() == currentPacketOH
                   && j != currentMinIndexTMMBR)
                 {
-                    candidateSet.ClearEntry(j);
+                    candidateSet[j].set_bitrate_bps(0);
                     numCandidates--;
                 }
             }
         }
     }
     // 3. Select and remove tuple w/ lowest tmmbr.
     // (If more than 1, choose the one w/ highest OH).
     uint32_t minTMMBR = 0;
     uint32_t minIndexTMMBR = 0;
     for (uint32_t i = 0; i < candidateSet.size(); i++)
     {
-        if (candidateSet.Tmmbr(i) > 0)
+        if (candidateSet[i].bitrate_bps())
         {
-            minTMMBR = candidateSet.Tmmbr(i);
+            minTMMBR = candidateSet[i].bitrate_bps();
             minIndexTMMBR = i;
             break;
         }
     }
 
     for (uint32_t i = 0; i < candidateSet.size(); i++)
     {
-        if (candidateSet.Tmmbr(i) > 0 && candidateSet.Tmmbr(i) <= minTMMBR)
+        if (candidateSet[i].bitrate_bps() &&
+            candidateSet[i].bitrate_bps() <= minTMMBR)
         {
             // get min bitrate
-            minTMMBR = candidateSet.Tmmbr(i);
+            minTMMBR = candidateSet[i].bitrate_bps();
             minIndexTMMBR = i;
         }
     }
     // first member of selected list
-    _boundingSet.SetEntry(numBoundingSet,
-                          candidateSet.Tmmbr(minIndexTMMBR),
-                          candidateSet.PacketOH(minIndexTMMBR),
-                          candidateSet.Ssrc(minIndexTMMBR));
+    boundingSet->push_back(candidateSet[minIndexTMMBR]);
 
+    std::unique_ptr<float[]> _ptrIntersectionBoundingSet(new float[numCandidates]);
+    std::unique_ptr<float[]> _ptrMaxPRBoundingSet(new float[numCandidates]);
     // set intersection value
     _ptrIntersectionBoundingSet[numBoundingSet] = 0;
     // calculate its maximum packet rate (where its line crosses x-axis)
-    uint32_t packet_overhead_bits = 8 * _boundingSet.PacketOH(numBoundingSet);
+    uint32_t packet_overhead_bits = 8 * boundingSet->back().packet_overhead();
     if (packet_overhead_bits == 0) {
       // Avoid division by zero.
       _ptrMaxPRBoundingSet[numBoundingSet] = std::numeric_limits<float>::max();
     } else {
       _ptrMaxPRBoundingSet[numBoundingSet] =
-          _boundingSet.Tmmbr(numBoundingSet) * 1000 /
+          boundingSet->back().bitrate_bps() /
           static_cast<float>(packet_overhead_bits);
     }
     numBoundingSet++;
     // remove from candidate list
-    candidateSet.ClearEntry(minIndexTMMBR);
+    candidateSet[minIndexTMMBR].set_bitrate_bps(0);
     numCandidates--;
 
     // 4. Discard from candidate list all tuple w/ lower OH
     // (next tuple must be steeper)
     for (uint32_t i = 0; i < candidateSet.size(); i++)
     {
-        if(candidateSet.Tmmbr(i) > 0
-            && candidateSet.PacketOH(i) < _boundingSet.PacketOH(0))
+        if(candidateSet[i].bitrate_bps()
+            && candidateSet[i].packet_overhead() < boundingSet->front().packet_overhead())
         {
-            candidateSet.ClearEntry(i);
+            candidateSet[i].set_bitrate_bps(0);
             numCandidates--;
         }
     }
 
     if (numCandidates == 0)
     {
         // Should be true already:_boundingSet.lengthOfSet = numBoundingSet;
-        assert(_boundingSet.lengthOfSet() == numBoundingSet);
-        return numBoundingSet;
+        RTC_DCHECK_EQ(boundingSet->size(), numBoundingSet);
+        return;
     }
 
     bool getNewCandidate = true;
-    uint32_t curCandidateTMMBR = 0;
-    size_t curCandidateIndex = 0;
-    uint32_t curCandidatePacketOH = 0;
-    uint32_t curCandidateSSRC = 0;
+    rtcp::TmmbItem curCandidate;
     do
     {
         if (getNewCandidate)
         {
             // 5. Remove first remaining tuple from candidate list
             for (uint32_t i = 0; i < candidateSet.size(); i++)
             {
-                if (candidateSet.Tmmbr(i) > 0)
+                if (candidateSet[i].bitrate_bps())
                 {
-                    curCandidateTMMBR    = candidateSet.Tmmbr(i);
-                    curCandidatePacketOH = candidateSet.PacketOH(i);
-                    curCandidateSSRC     = candidateSet.Ssrc(i);
-                    curCandidateIndex    = i;
-                    candidateSet.ClearEntry(curCandidateIndex);
+                    curCandidate = candidateSet[i];
+                    candidateSet[i].set_bitrate_bps(0);
                     break;
                 }
             }
         }
 
         // 6. Calculate packet rate and intersection of the current
         // line with line of last tuple in selected list
-        RTC_DCHECK_NE(curCandidatePacketOH,
-                      _boundingSet.PacketOH(numBoundingSet - 1));
+        RTC_DCHECK_NE(curCandidate.packet_overhead(),
+                      boundingSet->back().packet_overhead());
         float packetRate
-            = float(curCandidateTMMBR
-                    - _boundingSet.Tmmbr(numBoundingSet-1))*1000
-            / (8*(curCandidatePacketOH
-                  - _boundingSet.PacketOH(numBoundingSet-1)));
+            = float(curCandidate.bitrate_bps()
+                    - boundingSet->back().bitrate_bps())
+            / (8*(curCandidate.packet_overhead()
+                  - boundingSet->back().packet_overhead()));
 
         // 7. If the packet rate is equal or lower than intersection of
         //    last tuple in selected list,
         //    remove last tuple in selected list & go back to step 6
         if(packetRate <= _ptrIntersectionBoundingSet[numBoundingSet-1])
         {
             // remove last tuple and goto step 6
             numBoundingSet--;
-            _boundingSet.ClearEntry(numBoundingSet);
-            _ptrIntersectionBoundingSet[numBoundingSet] = 0;
-            _ptrMaxPRBoundingSet[numBoundingSet]        = 0;
+            boundingSet->pop_back();
             getNewCandidate = false;
         } else
         {
             // 8. If packet rate is lower than maximum packet rate of
             // last tuple in selected list, add current tuple to selected
             // list
             if (packetRate < _ptrMaxPRBoundingSet[numBoundingSet-1])
             {
-                _boundingSet.SetEntry(numBoundingSet,
-                                      curCandidateTMMBR,
-                                      curCandidatePacketOH,
-                                      curCandidateSSRC);
+                boundingSet->push_back(curCandidate);
                 _ptrIntersectionBoundingSet[numBoundingSet] = packetRate;
                 float packet_overhead_bits =
-                    8 * _boundingSet.PacketOH(numBoundingSet);
+                    8 * boundingSet->back().packet_overhead();
                 RTC_DCHECK_NE(packet_overhead_bits, 0.0f);
                 _ptrMaxPRBoundingSet[numBoundingSet] =
-                    _boundingSet.Tmmbr(numBoundingSet) * 1000 /
+                    boundingSet->back().bitrate_bps() * 1000 /

[danilchap, 2016/05/20 13:38:53]

overlooked removing *1000 here, removed in patchset#7

                     packet_overhead_bits;
                 numBoundingSet++;
             }
             numCandidates--;
             getNewCandidate = true;
         }
 
         // 9. Go back to step 5 if any tuple remains in candidate list
     } while (numCandidates > 0);
 
-    return numBoundingSet;
+    RTC_DCHECK_EQ(boundingSet->size(), numBoundingSet);
 }
 
 bool TMMBRHelp::IsOwner(const uint32_t ssrc,
                         const uint32_t length) const {
   rtc::CritScope lock(&_criticalSection);
 
   if (length == 0) {
     // Empty bounding set.
     return false;
   }
@@ skipping 19 matching lines @@
     uint32_t curNetBitRateKbit = _candidateSet.Tmmbr(i);
     if (curNetBitRateKbit < MIN_VIDEO_BW_MANAGEMENT_BITRATE) {
       curNetBitRateKbit = MIN_VIDEO_BW_MANAGEMENT_BITRATE;
     }
     *minBitrateKbit = curNetBitRateKbit < *minBitrateKbit ?
         curNetBitRateKbit : *minBitrateKbit;
   }
   return true;
 }
 }  // namespace webrtc