p2pfragmenttracker.cpp

/***************************************************************************
                          p2pfragmenttracker.cpp -  description
                             -------------------
    begin                : Wed Dec 5 2007
    copyright            : (C) 2007 by Diederik van der Boor
    email                : "vdboor" --at-- "codingdomain.com"
 ***************************************************************************/

/***************************************************************************
 *                                                                         *
 *   This program is free software; you can redistribute it and/or modify  *
 *   it under the terms of the GNU General Public License as published by  *
 *   the Free Software Foundation; either version 2 of the License, or     *
 *   (at your option) any later version.                                   *
 *                                                                         *
 ***************************************************************************/

#include "p2pfragmenttracker.h"

#include "../../kmessdebug.h"

#define ADDDIFF(orig, new) ( (new) > (orig) ? (new) - (orig) : 0 )



/**
 * Constructor
 */
00029 P2PFragmentTracker::P2PFragmentTracker()
: messageID_(0)
, totalSize_(0)
, transferredBytes_(0)
{
}



/**
 * Destructor
 */
00041 P2PFragmentTracker::~P2PFragmentTracker()
{
}


/**
 * @brief Return a string with the various received parts.
 * @returns  String with 1..100 120..200 to indicate the received parts.
 */
00050 QString P2PFragmentTracker::getDebugMap() const
{
  // Add header
  QString result( "id=" + QString::number( messageID_ ) +
                  ", got " + QString::number( transferredBytes_ ) +
                  " bytes of " + QString::number( totalSize_ ) );
  if( ! ranges_.isEmpty() )
  {
    result += ", ranges:";
  }

  // Add range details
  unsigned long realCount = 0;
  foreach( Range *range, ranges_ )
  {
    // Update string and counter
    result    += " " + QString::number( range->start ) + ".." + QString::number( range->end );
    realCount += ( range->end - range->start );
  }

  // Test if counters are correct
#ifdef KMESSTEST
  KMESS_ASSERT( realCount == transferredBytes_ );
#endif
  if( realCount != transferredBytes_ )
  {
    result += " ERROR realCount=" + QString::number( realCount );
  }

  return "fragmentedMessage[ " + result + " ]";
}


/**
 * @brief  Return the identifier of the tracked message.
 * @return  The message identifier.
 */
00087 quint32 P2PFragmentTracker::getMessageID() const
{
  return messageID_;
}



/**
 * @brief  Return the number of bytes transferred.
 * @returns Number of bytes transferred.
 */
00098 quint32 P2PFragmentTracker::getTransferredBytes() const
{
  // TODO: for KMess 1.6, remove this
  // Just soo close before release don't assume transferredBytes_ will always be correct

  quint32 realCount = 0;
  foreach( Range *range, ranges_ )
  {
    realCount += ( range->end - range->start );
  }

  if( transferredBytes_ != realCount )
  {
    kWarning() << "P2PFragmentTracker: Invalid byte count for " << getDebugMap();
    return realCount;
  }

  return transferredBytes_;
}



/**
 * @brief  Initialize the tracker with a new message.
 * @param  messageID  Unique identifier of the message.
 * @param  totalSize  The total size of the message.
 *
 * Resets the current state.
 */
00127 void P2PFragmentTracker::initialize( quint32 messageID, quint32 totalSize )
{
  // Reset fields
  messageID_        = messageID;
  transferredBytes_ = 0;
  totalSize_        = totalSize;

  // Clear collection
  qDeleteAll( ranges_ );
  ranges_.clear();
}



/**
 * @brief  Return whether the fragment tracker is complete.
 * @return  Returns true if all fragments are transferred.
 */
00145 bool P2PFragmentTracker::isComplete() const
{
  // Check the preconditions, otherwise don't even check the ranges.
  if( totalSize_== 0 || ranges_.count() != 1 || getTransferredBytes() < totalSize_ )
  {
    return false;
  }

  // Check the last remaining range.
  const Range *range = ranges_.first();
  return range->start == 0 && range->end >= totalSize_;
}



/**
 * @brief Return whether the tracker is empty, no data added yet.
 * @return  Returns true if there is no data in the tracker.
 */
00164 bool P2PFragmentTracker::isEmpty() const
{
  return ranges_.isEmpty();
}



/**
 * @brief Return whether the tracker is initialized to receive a part for the given message ID.
 * @param  messageID  Message identifier to verify.
 * @return  Returns true if the tracker is initialized to receive parts of the given message ID.
 */
00176 bool P2PFragmentTracker::isInitialized( quint32 messageID ) const
{
  return ( messageID_ == messageID );
}



/**
 * @brief  // Register the arrival of a new fragment, updates the counters.
 * @param  offset  The starting point of the fragment.
 * @param  size    The length of the fragment.
 */
00188 void P2PFragmentTracker::registerFragment( quint32 offset, quint32 size )
{
  // Calculate end, check unsafe values.
  quint32 newEnd  = offset + size;
  if( newEnd > totalSize_ )
  {
    newEnd = totalSize_;
  }

  if( offset > totalSize_ )
  {
    return;
  }


  // This algorithm also allows overlapping parts
  // just to be on the safe side.

  // Example ranges:
  // --------------------------------
  //    __A__       ___B___                __C__
  //   |     |     |       |              |     |
  //
  //
  //         |__4__|         |__3__|   |__2__|       |__1__|
  //
  //
  //         |___________5_________|
  //
  //              |____________6____________|
  //
  //
  // Posibilities for new range:
  // 1: after last one
  // 2: after current, but overlap next one.
  // 3: after previous, but before next
  // 4: append current
  // 4b: even fill the gap with the previous element.
  // 5: append current but span over next
  // 6: after current, span over next, but C contains the real new end.
  //
  // Unhandled option: fragment overlapping an existing one completely.

  Range *nextRange = 0; // as in "after current"
  Range *range     = 0;

  // Initialize with first range.
  if( ranges_.isEmpty() )
  {
    range = new Range;
    range->start = offset;
    range->end   = newEnd;
    ranges_.append( range );
    transferredBytes_ = size;
  }
  else
  {
    // More items, see where to add.
    int last   = ranges_.count() - 1;
    bool merge = false;
    int i;
    for( i = last; i >= 0; i-- )
    {
      nextRange = range;
      range     = ranges_.at( i );

      if( offset > range->end )
      {
        // new range starts after current item.

        // See it does not touche/overlap the next item, otherwise update that one instead.
        if( nextRange == 0 || newEnd < nextRange->start )
        {
          // No overlap, insert between current and next element.
          // Option 1 or 3
          i++;
          range = new Range;
          range->start = offset;
          range->end   = newEnd;
          ranges_.insert( i, range );
          transferredBytes_ += size;
          return;
        }
        else
        {
          // Option 2.
          range = nextRange;  // had to update this one after all.
          transferredBytes_ += ADDDIFF( offset, range->start );
          transferredBytes_ += ADDDIFF( range->end, newEnd );
          range->start = offset;
          range->end   = qMax( nextRange->end, newEnd );

          // Fix next item, for next test
          i++;
          nextRange = ( i < last ) ? ranges_.at( i + 1 ) : 0;
          merge = true;
          break;
        }
      }
      else if( offset >= range->start )
      {
        // New range appends current item.
        // Option 4
        transferredBytes_ += ADDDIFF( range->end, newEnd );
        range->end         = qMax( range->end, newEnd );

        // See if the item can be merged.
        // Option 4b and 5
        merge = true;
        break;
      }
      else if( i == 0 && offset < range->start )
      {
        // See if the item should be added before all elements.
        range = new Range;
        range->start = offset;
        range->end   = newEnd;
        ranges_.insert( i, range );
        transferredBytes_ += size;
        merge = true;
        break;
      }
    }


    // Found an item.
    // See if item can be merged with next ones.
    if( merge )
    {
      while( nextRange != 0 && nextRange->start <= range->end )
      {
        quint32 rangeSize = ( nextRange->end - nextRange->start );
        transferredBytes_ -= rangeSize;
        if( nextRange->end > range->end ) // last item has highest range
        {
          transferredBytes_ += ( nextRange->end - range->end );
        }

        range->end = qMax( range->end, nextRange->end );

        delete ranges_.takeAt( i + 1 );
        last--;
        nextRange = ( i < last ) ? ranges_.at( i + 1 ) : 0;
      }
    }
  }
}