src/GapList.cpp

   1 //
   2 // This file is part of the aMule Project.
   3 //
   4 // Copyright (c) 2008-2011 aMule Team ( admin@amule.org / http://www.amule.org )
   5 //
   6 // Any parts of this program derived from the xMule, lMule or eMule project,
   7 // or contributed by third-party developers are copyrighted by their
   8 // respective authors.
   9 //
  10 // This program is free software; you can redistribute it and/or modify
  11 // it under the terms of the GNU General Public License as published by
  12 // the Free Software Foundation; either version 2 of the License, or
  13 // (at your option) any later version.
  14 //
  15 // This program is distributed in the hope that it will be useful,
  16 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  17 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  18 // GNU General Public License for more details.
  19 //
  20 // You should have received a copy of the GNU General Public License
  21 // along with this program; if not, write to the Free Software
  22 // Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301, USA
  23 //
  24
  25
  26 #include "Types.h"
  27 #include <protocol/ed2k/Constants.h>    // for PARTSIZE
  28 #include "GapList.h"
  29
  30 #include "Logger.h"
  31 #include <common/Format.h>
  32
  33 #if defined(_MSC_VER) && (_MSC_VER >= 1800)
  34 #include <algorithm> // for std::min and std::max
  35 #endif
  36
  37 void CGapList::Init(uint64 fileSize, bool isEmpty)
  38 {
  39         m_filesize = fileSize;
  40         m_iPartCount = fileSize / PARTSIZE + 1;
  41         m_sizeLastPart = fileSize % PARTSIZE;
  42         // file with size of n * PARTSIZE
  43         if (m_sizeLastPart == 0
  44                 && fileSize) {  // that's only for pre-init in ctor
  45                 m_sizeLastPart = PARTSIZE;
  46                 m_iPartCount--;
  47         }
  48         m_gaplist.clear();
  49         m_partsComplete.clear();
  50         if (isEmpty) {
  51                 m_partsComplete.resize(m_iPartCount, incomplete);
  52                 AddGap(0, fileSize - 1);
  53                 m_totalGapSize = fileSize;
  54         } else {
  55                 m_partsComplete.resize(m_iPartCount, complete);
  56                 m_totalGapSize = 0;
  57         }
  58         m_totalGapSizeValid = true;
  59 }
  60
  61
  62 void CGapList::AddGap(uint64 gapstart, uint64 gapend)
  63 {
  64         if (!ArgCheck(gapstart, gapend)) {
  65                 return;
  66         }
  67
  68 //      AddDebugLogLineN(logPartFile, CFormat(wxT("  AddGap: %5d - %5d")) % gapstart % gapend);
  69
  70         // mark involved part(s) as incomplete
  71         uint16 partlast = gapend / PARTSIZE;
  72         for (uint16 part = gapstart / PARTSIZE; part <= partlast; part++) {
  73                 m_partsComplete[part] = incomplete;
  74         }
  75         // total gap size has to be recalculated
  76         m_totalGapSizeValid = false;
  77
  78         // find a place to start:
  79         // first gap which ends >= our gap start - 1
  80         // (-1 so we can join adjacent gaps)
  81         iterator it = m_gaplist.lower_bound(gapstart > 0 ? gapstart - 1 : 0);
  82         while (it != m_gaplist.end()) {
  83                 iterator it2 = it++;
  84                 uint64 curGapStart = it2->second;
  85                 uint64 curGapEnd   = it2->first;
  86
  87                 if (curGapStart >= gapstart && curGapEnd <= gapend) {
  88                         // this gap is inside the new gap - delete
  89                         m_gaplist.erase(it2);
  90                 } else if (curGapStart >= gapstart && curGapStart <= gapend + 1) {
  91                         // head of this gap is in the new gap, or this gap is
  92                         // directly behind the new gap - extend limit and delete
  93                         gapend = curGapEnd;
  94                         m_gaplist.erase(it2);
  95                 } else if (curGapEnd <= gapend && curGapEnd >= gapstart - 1) {
  96                         // tail of this gap is in the new gap, or this gap is
  97                         // directly before the new gap - extend limit and delete
  98                         gapstart = curGapStart;
  99                         m_gaplist.erase(it2);
 100                 } else if (curGapStart <= gapstart && curGapEnd >= gapend) {
 101                         // new gap is already inside this gap - return
 102                         return;
 103                 // now all cases of overlap are ruled out
 104                 } else if (curGapStart > gapstart) {
 105                         // this gap is the first behind the new gap -> insert before it
 106                         it = it2;
 107                         break;
 108                 }
 109         }
 110         // for fastest insertion point to the element AFTER which we want to insert
 111         if (it != m_gaplist.begin()) {
 112                 --it;
 113         }
 114         m_gaplist.insert(it, std::pair<uint64,uint64>(gapend, gapstart));
 115 }
 116
 117 void CGapList::AddGap(uint16 part)
 118 {
 119         if (part >= m_iPartCount) {
 120                 wxFAIL;
 121                 return;
 122         }
 123         uint64 gapstart = part * PARTSIZE;
 124         uint64 gapend = gapstart + GetPartSize(part) - 1;
 125         AddGap(gapstart, gapend);
 126         m_partsComplete[part] = incomplete;
 127 }
 128
 129 void CGapList::FillGap(uint64 partstart, uint64 partend)
 130 {
 131         if (!ArgCheck(partstart, partend)) {
 132                 return;
 133         }
 134
 135 //      AddDebugLogLineN(logPartFile, CFormat(wxT("  FillGap: %5d - %5d")) % partstart % partend);
 136
 137         // mark involved part(s) to be reexamined for completeness
 138         uint16 partlast = partend / PARTSIZE;
 139         for (uint16 part = partstart / PARTSIZE; part <= partlast; part++) {
 140                 m_partsComplete[part] = unknown;
 141         }
 142         // also total gap size
 143         m_totalGapSizeValid = false;
 144
 145         // find a place to start:
 146         // first gap which ends >= our part start
 147         iterator it = m_gaplist.lower_bound(partstart);
 148         while (it != m_gaplist.end()) {
 149                 iterator it2 = it++;
 150                 uint64 curGapStart = it2->second;
 151                 uint64 curGapEnd   = it2->first;
 152
 153                 if (curGapStart >= partstart) {
 154                         if (curGapEnd <= partend) {
 155                                 // our part fills this gap completly
 156                                 m_gaplist.erase(it2);
 157                         } else if (curGapStart <= partend) {
 158                                 // lower part of this gap is in the part - shrink gap:
 159                                 //   (this is the most common case: curGapStart == partstart && curGapEnd > partend)
 160                                 it2->second = partend + 1;
 161                                 // end of our part was in the gap: we're done
 162                                 break;
 163                         } else {
 164                                 // gap starts behind our part end: we're done
 165                                 break;
 166                         }
 167                 } else {
 168                         // curGapStart < partstart
 169                         if (curGapEnd > partend) {
 170                                 // our part is completely enclosed by the gap
 171                                 // cut it in two, leaving our part out:
 172                                 // shrink the gap so it becomes the second gap
 173                                 it2->second = partend + 1;
 174                                 // insert new first gap
 175                                 iterator it3(it2);
 176                                 if (it3 != m_gaplist.begin()) {
 177                                         --it3;
 178                                 }
 179                                 m_gaplist.insert(it3, std::pair<uint64,uint64>(partstart - 1, curGapStart));
 180                                 // we're done
 181                                 break;
 182                         } else if (curGapEnd >= partstart) {
 183                                 // upper part of this gap is in the part - shrink gap:
 184                                 // insert shorter gap
 185                                 iterator it3(it2);
 186                                 if (it3 != m_gaplist.begin()) {
 187                                         --it3;
 188                                 }
 189                                 m_gaplist.insert(it3, std::pair<uint64,uint64>(partstart - 1, curGapStart));
 190                                 // and delete the old one
 191                                 m_gaplist.erase(it2);
 192                         }
 193                         // else: gap is before our part start (should not happen)
 194                 }
 195         }
 196 }
 197
 198 void CGapList::FillGap(uint16 part)
 199 {
 200         if (part >= m_iPartCount) {
 201                 wxFAIL;
 202                 return;
 203         }
 204         uint64 gapstart = part * PARTSIZE;
 205         uint64 gapend = gapstart + GetPartSize(part) - 1;
 206         FillGap(gapstart, gapend);
 207         m_partsComplete[part] = complete;
 208 }
 209
 210 uint64 CGapList::GetGapSize()
 211 {
 212         if (!m_totalGapSizeValid) {
 213                 m_totalGapSizeValid = true;
 214                 m_totalGapSize = 0;
 215
 216                 ListType::const_iterator it = m_gaplist.begin();
 217                 for (; it != m_gaplist.end(); ++it) {
 218                         m_totalGapSize += it->first - it->second + 1;
 219                 }
 220         }
 221         return m_totalGapSize;
 222 }
 223
 224 uint32 CGapList::GetGapSize(uint16 part) const
 225 {
 226         uint64 uRangeStart = part * PARTSIZE;
 227         uint64 uRangeEnd = uRangeStart + GetPartSize(part) - 1;
 228         uint64 uTotalGapSize = 0;
 229
 230         // find a place to start:
 231         // first gap which ends >= our gap start
 232         ListType::const_iterator it = m_gaplist.lower_bound(uRangeStart);
 233         for (; it != m_gaplist.end(); ++it) {
 234                 uint64 curGapStart = it->second;
 235                 uint64 curGapEnd   = it->first;
 236
 237                 if (curGapStart <= uRangeStart && curGapEnd >= uRangeEnd) {
 238                         // total range is in this gap
 239                         uTotalGapSize += uRangeEnd - uRangeStart + 1;
 240                         break;
 241                 } else if (curGapStart >= uRangeStart) {
 242                         if (curGapStart <= uRangeEnd) {
 243                                 // start of this gap is in our range
 244                                 uTotalGapSize += std::min(curGapEnd, uRangeEnd) - curGapStart + 1;
 245                         } else {
 246                                 // this gap starts behind our range
 247                                 break;
 248                         }
 249                 } else if (curGapEnd >= uRangeStart && curGapEnd <= uRangeEnd) {
 250                         // end of this gap is in our range
 251                         uTotalGapSize += curGapEnd - uRangeStart + 1;
 252                 }
 253         }
 254
 255         wxASSERT( uTotalGapSize <= uRangeEnd - uRangeStart + 1 );
 256         return uTotalGapSize;
 257 }
 258
 259 bool CGapList::IsComplete(uint64 gapstart, uint64 gapend) const
 260 {
 261         if (!ArgCheck(gapstart, gapend)) {
 262                 return false;
 263         }
 264
 265         // find a place to start:
 266         // first gap which ends >= our gap start
 267         ListType::const_iterator it = m_gaplist.lower_bound(gapstart);
 268         for (; it != m_gaplist.end(); ++it) {
 269                 uint64 curGapStart = it->second;
 270                 uint64 curGapEnd   = it->first;
 271
 272                 if (  (curGapStart >= gapstart    && curGapEnd   <= gapend)
 273                         ||(curGapStart >= gapstart    && curGapStart <= gapend)
 274                         ||(curGapEnd   <= gapend      && curGapEnd   >= gapstart)
 275                         ||(gapstart    >= curGapStart && gapend      <= curGapEnd)) {
 276                         return false;
 277                 }
 278                 if (curGapStart > gapend) {
 279                         break;
 280                 }
 281         }
 282         return true;
 283 }
 284
 285 bool CGapList::IsComplete(uint16 part)
 286 {
 287 // There is a bug in the ED2K protocol:
 288 // For files of size n * PARTSIZE one part too much is transmitted in the availability bitfield.
 289 // Allow completion detection of this dummy part, and always report it as complete
 290 // (so it doesn't get asked for).
 291         if (part == m_iPartCount && m_sizeLastPart == PARTSIZE) {
 292                 return true;
 293         }
 294 // Remaining error check
 295         if (part >= m_iPartCount) {
 296                 wxFAIL;
 297                 return false;
 298         }
 299         ePartComplete status = (ePartComplete) m_partsComplete[part];
 300         if (status == unknown) {
 301                 uint64 partstart = part * PARTSIZE;
 302                 uint64 partend = partstart + GetPartSize(part) - 1;
 303                 status = IsComplete(partstart, partend) ? complete : incomplete;
 304                 m_partsComplete[part] = status;
 305         }
 306         return status == complete;
 307 }
 308
 309 inline bool CGapList::ArgCheck(uint64 gapstart, uint64 &gapend) const
 310 {
 311         // end < start: serious error
 312         if (gapend < gapstart) {
 313                 wxFAIL;
 314                 return false;
 315         }
 316
 317         // gaps shouldn't go past file anymore either
 318         if (gapend >= m_filesize) {
 319                 wxFAIL;
 320                 gapend = m_filesize - 1;        // fix it
 321         }
 322         return true;
 323 }