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 void CGapList::Init(uint64 fileSize, bool isEmpty)
  34 {
  35         m_filesize = fileSize;
  36         m_iPartCount = fileSize / PARTSIZE + 1;
  37         m_sizeLastPart = fileSize % PARTSIZE;
  38         // file with size of n * PARTSIZE
  39         if (m_sizeLastPart == 0
  40                 && fileSize) {  // that's only for pre-init in ctor
  41                 m_sizeLastPart = PARTSIZE;
  42                 m_iPartCount--;
  43         }
  44         m_gaplist.clear();
  45         m_partsComplete.clear();
  46         if (isEmpty) {
  47                 m_partsComplete.resize(m_iPartCount, incomplete);
  48                 AddGap(0, fileSize - 1);
  49                 m_totalGapSize = fileSize;
  50         } else {
  51                 m_partsComplete.resize(m_iPartCount, complete);
  52                 m_totalGapSize = 0;
  53         }
  54         m_totalGapSizeValid = true;
  55 }
  56
  57
  58 void CGapList::AddGap(uint64 gapstart, uint64 gapend)
  59 {
  60         if (!ArgCheck(gapstart, gapend)) {
  61                 return;
  62         }
  63
  64 //      AddDebugLogLineN(logPartFile, CFormat(wxT("  AddGap: %5d - %5d")) % gapstart % gapend);
  65
  66         // mark involved part(s) as incomplete
  67         uint16 partlast = gapend / PARTSIZE;
  68         for (uint16 part = gapstart / PARTSIZE; part <= partlast; part++) {
  69                 m_partsComplete[part] = incomplete;
  70         }
  71         // total gap size has to be recalculated
  72         m_totalGapSizeValid = false;
  73
  74         // find a place to start:
  75         // first gap which ends >= our gap start - 1
  76         // (-1 so we can join adjacent gaps)
  77         iterator it = m_gaplist.lower_bound(gapstart > 0 ? gapstart - 1 : 0);
  78         while (it != m_gaplist.end()) {
  79                 iterator it2 = it++;
  80                 uint64 curGapStart = it2->second;
  81                 uint64 curGapEnd   = it2->first;
  82
  83                 if (curGapStart >= gapstart && curGapEnd <= gapend) {
  84                         // this gap is inside the new gap - delete
  85                         m_gaplist.erase(it2);
  86                 } else if (curGapStart >= gapstart && curGapStart <= gapend + 1) {
  87                         // head of this gap is in the new gap, or this gap is
  88                         // directly behind the new gap - extend limit and delete
  89                         gapend = curGapEnd;
  90                         m_gaplist.erase(it2);
  91                 } else if (curGapEnd <= gapend && curGapEnd >= gapstart - 1) {
  92                         // tail of this gap is in the new gap, or this gap is
  93                         // directly before the new gap - extend limit and delete
  94                         gapstart = curGapStart;
  95                         m_gaplist.erase(it2);
  96                 } else if (curGapStart <= gapstart && curGapEnd >= gapend) {
  97                         // new gap is already inside this gap - return
  98                         return;
  99                 // now all cases of overlap are ruled out
 100                 } else if (curGapStart > gapstart) {
 101                         // this gap is the first behind the new gap -> insert before it
 102                         it = it2;
 103                         break;
 104                 }
 105         }
 106         // for fastest insertion point to the element AFTER which we want to insert
 107         if (it != m_gaplist.begin()) {
 108                 --it;
 109         }
 110         m_gaplist.insert(it, std::pair<uint64,uint64>(gapend, gapstart));
 111 }
 112
 113 void CGapList::AddGap(uint16 part)
 114 {
 115         if (part >= m_iPartCount) {
 116                 wxFAIL;
 117                 return;
 118         }
 119         uint64 gapstart = part * PARTSIZE;
 120         uint64 gapend = gapstart + GetPartSize(part) - 1;
 121         AddGap(gapstart, gapend);
 122         m_partsComplete[part] = incomplete;
 123 }
 124
 125 void CGapList::FillGap(uint64 partstart, uint64 partend)
 126 {
 127         if (!ArgCheck(partstart, partend)) {
 128                 return;
 129         }
 130
 131 //      AddDebugLogLineN(logPartFile, CFormat(wxT("  FillGap: %5d - %5d")) % partstart % partend);
 132
 133         // mark involved part(s) to be reexamined for completeness
 134         uint16 partlast = partend / PARTSIZE;
 135         for (uint16 part = partstart / PARTSIZE; part <= partlast; part++) {
 136                 m_partsComplete[part] = unknown;
 137         }
 138         // also total gap size
 139         m_totalGapSizeValid = false;
 140
 141         // find a place to start:
 142         // first gap which ends >= our part start
 143         iterator it = m_gaplist.lower_bound(partstart);
 144         while (it != m_gaplist.end()) {
 145                 iterator it2 = it++;
 146                 uint64 curGapStart = it2->second;
 147                 uint64 curGapEnd   = it2->first;
 148
 149                 if (curGapStart >= partstart) {
 150                         if (curGapEnd <= partend) {
 151                                 // our part fills this gap completly
 152                                 m_gaplist.erase(it2);
 153                         } else if (curGapStart <= partend) {
 154                                 // lower part of this gap is in the part - shrink gap:
 155                                 //   (this is the most common case: curGapStart == partstart && curGapEnd > partend)
 156                                 it2->second = partend + 1;
 157                                 // end of our part was in the gap: we're done
 158                                 break;
 159                         } else {
 160                                 // gap starts behind our part end: we're done
 161                                 break;
 162                         }
 163                 } else {
 164                         // curGapStart < partstart
 165                         if (curGapEnd > partend) {
 166                                 // our part is completely enclosed by the gap
 167                                 // cut it in two, leaving our part out:
 168                                 // shrink the gap so it becomes the second gap
 169                                 it2->second = partend + 1;
 170                                 // insert new first gap
 171                                 iterator it3(it2);
 172                                 if (it3 != m_gaplist.begin()) {
 173                                         --it3;
 174                                 }
 175                                 m_gaplist.insert(it3, std::pair<uint64,uint64>(partstart - 1, curGapStart));
 176                                 // we're done
 177                                 break;
 178                         } else if (curGapEnd >= partstart) {
 179                                 // upper part of this gap is in the part - shrink gap:
 180                                 // insert shorter gap
 181                                 iterator it3(it2);
 182                                 if (it3 != m_gaplist.begin()) {
 183                                         --it3;
 184                                 }
 185                                 m_gaplist.insert(it3, std::pair<uint64,uint64>(partstart - 1, curGapStart));
 186                                 // and delete the old one
 187                                 m_gaplist.erase(it2);
 188                         }
 189                         // else: gap is before our part start (should not happen)
 190                 }
 191         }
 192 }
 193
 194 void CGapList::FillGap(uint16 part)
 195 {
 196         if (part >= m_iPartCount) {
 197                 wxFAIL;
 198                 return;
 199         }
 200         uint64 gapstart = part * PARTSIZE;
 201         uint64 gapend = gapstart + GetPartSize(part) - 1;
 202         FillGap(gapstart, gapend);
 203         m_partsComplete[part] = complete;
 204 }
 205
 206 uint64 CGapList::GetGapSize()
 207 {
 208         if (!m_totalGapSizeValid) {
 209                 m_totalGapSizeValid = true;
 210                 m_totalGapSize = 0;
 211
 212                 ListType::const_iterator it = m_gaplist.begin();
 213                 for (; it != m_gaplist.end(); ++it) {
 214                         m_totalGapSize += it->first - it->second + 1;
 215                 }
 216         }
 217         return m_totalGapSize;
 218 }
 219
 220 uint32 CGapList::GetGapSize(uint16 part) const
 221 {
 222         uint64 uRangeStart = part * PARTSIZE;
 223         uint64 uRangeEnd = uRangeStart + GetPartSize(part) - 1;
 224         uint64 uTotalGapSize = 0;
 225
 226         // find a place to start:
 227         // first gap which ends >= our gap start
 228         ListType::const_iterator it = m_gaplist.lower_bound(uRangeStart);
 229         for (; it != m_gaplist.end(); ++it) {
 230                 uint64 curGapStart = it->second;
 231                 uint64 curGapEnd   = it->first;
 232
 233                 if (curGapStart <= uRangeStart && curGapEnd >= uRangeEnd) {
 234                         // total range is in this gap
 235                         uTotalGapSize += uRangeEnd - uRangeStart + 1;
 236                         break;
 237                 } else if (curGapStart >= uRangeStart) {
 238                         if (curGapStart <= uRangeEnd) {
 239                                 // start of this gap is in our range
 240                                 uTotalGapSize += std::min(curGapEnd, uRangeEnd) - curGapStart + 1;
 241                         } else {
 242                                 // this gap starts behind our range
 243                                 break;
 244                         }
 245                 } else if (curGapEnd >= uRangeStart && curGapEnd <= uRangeEnd) {
 246                         // end of this gap is in our range
 247                         uTotalGapSize += curGapEnd - uRangeStart + 1;
 248                 }
 249         }
 250
 251         wxASSERT( uTotalGapSize <= uRangeEnd - uRangeStart + 1 );
 252         return uTotalGapSize;
 253 }
 254
 255 bool CGapList::IsComplete(uint64 gapstart, uint64 gapend) const
 256 {
 257         if (!ArgCheck(gapstart, gapend)) {
 258                 return false;
 259         }
 260
 261         // find a place to start:
 262         // first gap which ends >= our gap start
 263         ListType::const_iterator it = m_gaplist.lower_bound(gapstart);
 264         for (; it != m_gaplist.end(); ++it) {
 265                 uint64 curGapStart = it->second;
 266                 uint64 curGapEnd   = it->first;
 267
 268                 if (  (curGapStart >= gapstart    && curGapEnd   <= gapend)
 269                         ||(curGapStart >= gapstart    && curGapStart <= gapend)
 270                         ||(curGapEnd   <= gapend      && curGapEnd   >= gapstart)
 271                         ||(gapstart    >= curGapStart && gapend      <= curGapEnd)) {
 272                         return false;
 273                 }
 274                 if (curGapStart > gapend) {
 275                         break;
 276                 }
 277         }
 278         return true;
 279 }
 280
 281 bool CGapList::IsComplete(uint16 part)
 282 {
 283 // There is a bug in the ED2K protocol:
 284 // For files of size n * PARTSIZE one part too much is transmitted in the availability bitfield.
 285 // Allow completion detection of this dummy part, and always report it as complete
 286 // (so it doesn't get asked for).
 287         if (part == m_iPartCount && m_sizeLastPart == PARTSIZE) {
 288                 return true;
 289         }
 290 // Remaining error check
 291         if (part >= m_iPartCount) {
 292                 wxFAIL;
 293                 return false;
 294         }
 295         ePartComplete status = (ePartComplete) m_partsComplete[part];
 296         if (status == unknown) {
 297                 uint64 partstart = part * PARTSIZE;
 298                 uint64 partend = partstart + GetPartSize(part) - 1;
 299                 status = IsComplete(partstart, partend) ? complete : incomplete;
 300                 m_partsComplete[part] = status;
 301         }
 302         return status == complete;
 303 }
 304
 305 inline bool CGapList::ArgCheck(uint64 gapstart, uint64 &gapend) const
 306 {
 307         // end < start: serious error
 308         if (gapend < gapstart) {
 309                 wxFAIL;
 310                 return false;
 311         }
 312
 313         // gaps shouldn't go past file anymore either
 314         if (gapend >= m_filesize) {
 315                 wxFAIL;
 316                 gapend = m_filesize - 1;        // fix it
 317         }
 318         return true;
 319 }