src/GapList.cpp

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