1 // ========================================================================== 2 // SeqAn - The Library for Sequence Analysis 3 // ========================================================================== 4 // Copyright (c) 2006-2015, Knut Reinert, FU Berlin 5 // All rights reserved. 6 // 7 // Redistribution and use in source and binary forms, with or without 8 // modification, are permitted provided that the following conditions are met: 9 // 10 // * Redistributions of source code must retain the above copyright 11 // notice, this list of conditions and the following disclaimer. 12 // * Redistributions in binary form must reproduce the above copyright 13 // notice, this list of conditions and the following disclaimer in the 14 // documentation and/or other materials provided with the distribution. 15 // * Neither the name of Knut Reinert or the FU Berlin nor the names of 16 // its contributors may be used to endorse or promote products derived 17 // from this software without specific prior written permission. 18 // 19 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 20 // AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 21 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 22 // ARE DISCLAIMED. IN NO EVENT SHALL KNUT REINERT OR THE FU BERLIN BE LIABLE 23 // FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 24 // DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR 25 // SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER 26 // CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 27 // LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 28 // OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH 29 // DAMAGE. 30 // 31 // ========================================================================== 32 // Author: David Weese <david.weese@fu-berlin.de> 33 // ========================================================================== 34 // Access a file like a string by implementing a custom paging/lru mechanism. 35 // ========================================================================== 36 37 #ifndef SEQAN_HEADER_STRING_EXTERNAL_H 38 #define SEQAN_HEADER_STRING_EXTERNAL_H 39 40 /* IOREV 41 * _nottested_ 42 * _doc_ 43 * 44 * 45 * mostly documented (doc for some functions missing) 46 * not tested in any test case nor used in any app right now 47 * -> needs testing, especially different iterators 48 */ 49 50 51 52 ////////////////////////////////////////////////////////////////////////////// 53 54 namespace SEQAN_NAMESPACE_MAIN 55 { 56 57 /*! 58 * @class ExternalConfig 59 * @headerfile <seqan/file.h> 60 * @brief Standard configuration for the @link ExternalString @endlink. 61 * 62 * @signature template <[typename TFile[, unsigned PAGESIZE[, unsigned FRAMES]]> 63 * struct ExternalConfig; 64 * 65 * @tparam TFile The @link File @endlink type to use. Default: <tt>File<></tt>. 66 * @tparam PAGESIZE The number of values in one page. This should be a power of 2 to speed up transfer and 67 * calculations. Default: 2<sup>20</sup>. 68 * @tparam FRAMES The number of pages that should reside in internal memory. To enable prefetching and automatic 69 * swap-out, <tt>frames</tt> should be greater than 1. Default: 2. 70 * 71 * When using this configuration, the Size type of the ExternalString is <tt>unsigned</tt>. Thus, with this configuration at 72 * most 4.294.967.296 values can be stored in an ExternalString on a 32 bit system. 73 * 74 * For a larger size type use @link ExternalConfigLarge @endlink. 75 * 76 * @see ExternalConfigLarge 77 */ 78 79 /*! 80 * @class ExternalConfigLarge 81 * @headerfile <seqan/file.h> 82 * @brief Large size type configuration for the @link ExternalString @endlink. 83 * 84 * @signature template <[typename TFile[, unsigned PAGESIZE[, unsigned FRAMES]]> 85 * struct ExternalConfigLarge; 86 * 87 * @tparam TFile The @link File @endlink type to use. Default: <tt>File<></tt>. 88 * @tparam PAGESIZE The number of values in one page. This should be a power of 2 to speed up transfer and 89 * calculations. Default: 2<sup>20</sup>. 90 * @tparam FRAMES The number of pages that should reside in internal memory. To enable prefetching and automatic 91 * swap-out, <tt>frames</tt> should be greater than 1. Default: 2. 92 * 93 * @see ExternalConfig 94 * 95 * @section Remarks 96 * 97 * When using this configuration ,th eSize type o fthe ExternalString is Size type of <tt>TFile</tt>. Normally, this is 98 * a 64 bit integer. For a smaller size type use ExternalConfig. 99 * 100 * Some data structures store size types values (e.g. suffix arrays in indices). To save memory, you should think o 101 * fusing ExternalConfig. 102 */ 103 104 /*! 105 * @class ExternalConfigSize 106 * @headerfile <seqan/file.h> 107 * @brief Arbitrary size type configuration for @link ExternalString @endlink. 108 * 109 * @signature template <typename TSize[, typename TFile[, unsigned PAGESIZE[, unsigned FRAMEs]]]> 110 * class ExternalConfigSize; 111 * 112 * @tparam TSize The size type of the ExternalString. 113 * @tparam TFile Type of file the ExternalString will be based on. Defaults to <tt>File<></tt>. 114 * @tparam PAGESIZE The number of values in one page. This should be a power of 2 to speed up transfer and 115 * calculations. Default: 2<sup>20</sup>. 116 * @tparam FRAMES The number of pages that should reside in internal memory. To enable prefetching and automatic 117 * swap-out, <tt>frames</tt> should be greater than 1. Default: 2. 118 */ 119 120 /*! 121 * @class ExternalString External String 122 * @extends String 123 * @headerfile <seqan/file.h> 124 * @brief String that is stored in external memory. 125 * 126 * @signature template <typename TValue[, typename TConfig]> 127 * class String<TValue, External<TConfig> >; 128 * 129 * @tparam TValue The type that is used for the items/characters stored in the string. 130 * @tparam TConfig A structure to confgure the external string. Defaults to <tt>ExternalConfigLarge<>. See 131 * ExternalConfig, ExternalConfigLarge, and ExternalConfigSize. 132 * 133 * The External String enables to access sequences larger than the available internal memory (RAM) by using external 134 * memory (e.g. Hard disk, Network storage, ...) via a File object. Sequences of nearly arbitrary size can be accessed 135 * even larger than the logically addressable memory, i.e. they can in particular contain more than 2^32 elements on a 136 * 32bit system (see Tag.ExternalConfigLarge). See the String constructor for more details. 137 * 138 * This String also supports fast appending and removing of values at the end (see Block String, appendValue) 139 * 140 * The External String implements a LRU mechanism to swap out pages. The External String's Iterator detects a forward or 141 * backward iteration and asynchronously prefetches pages that certainly will be accessed and automatically swaps out 142 * pages that certainly won't be accessed any more in the iteration process. 143 * 144 * The String is implemented like a virtual memory manager. It divides its character sequence into pages of a fixed 145 * length (e.g. 1MB) and maintains a page table with information for each page (e.g. resides in memory or was swapped 146 * out, is dirty and needs to be saved, ...). Besides the page table the String also contains a size-limited list of 147 * page frames. A page frame is reserved internal memory for a page. When accessing values of a page that is stored in 148 * external memory, the page is loaded to a page frame first. In case that there is no page frame free, another page is 149 * swapped out before to free a page frame. 150 */ 151 152 // standard external string 153 // size is uint32 154 template < typename TFile_ = File<>, // default file type 155 unsigned PAGESIZE_ = 4 * 1024 * 1024, // 1MTypes per default 156 unsigned FRAMES_ = 2 > // simultanous frames 157 struct ExternalConfig { 158 //IOREV _bug_ doc says default page size is 2^20, but it is 2^22 159 typedef TFile_ TFile; 160 typedef unsigned TSize; 161 enum { PAGESIZE = PAGESIZE_ }; 162 enum { FRAMES = FRAMES_ }; 163 }; 164 165 // the same as ExternalConfig 166 // but size type is size type of TFile_ (i.e. uint64) 167 // 168 // ATTENTION: 169 // pipes use the size type 170 // uint64 blows up your suffix arrays, lcp-tables, ... 171 template < typename TFile_ = File<>, // default file type 172 unsigned PAGESIZE_ = 4 * 1024 * 1024, // 1MTypes per default 173 unsigned FRAMES_ = 2 > // simultanous frames 174 struct ExternalConfigLarge { 175 //IOREV contains warning in code comments, need to investigate 176 typedef TFile_ TFile; 177 typedef typename MakeUnsigned<typename Size<TFile_>::Type>::Type TSize; 178 enum { PAGESIZE = PAGESIZE_ }; 179 enum { FRAMES = FRAMES_ }; 180 }; 181 182 // custom size type 183 template < typename TSize_, 184 typename TFile_ = File<>, // default file type 185 unsigned PAGESIZE_ = 1 * 1024 * 1024, // 1MTypes per default 186 unsigned FRAMES_ = 2 > // simultanous frames 187 struct ExternalConfigSize { 188 //IOREV 189 typedef TSize_ TSize; 190 typedef TFile_ TFile; 191 enum { PAGESIZE = PAGESIZE_ }; 192 enum { FRAMES = FRAMES_ }; 193 }; 194 195 template < typename TConfig = ExternalConfigLarge<> > 196 struct External {}; 197 //IOREV 198 199 200 ////////////////////////////////////////////////////////////////////////////// 201 // random External String iterator 202 template < typename TExtString > 203 struct ExtStringIterator 204 { 205 //IOREV 206 typedef ExtStringIterator TIterator; 207 typedef ExtStringIterator TStdIterator; 208 209 typedef typename Value<TExtString>::Type TValue; 210 typedef typename Size<TExtString>::Type TSize; 211 typedef typename Difference<TExtString>::Type TDifference; 212 typedef typename TExtString::TVolatilePtr TVolatilePtr; 213 214 enum { PAGESIZE = TExtString::PAGESIZE }; 215 216 TSize offset; 217 TExtString *extString; 218 219 ExtStringIteratorExtStringIterator220 ExtStringIterator(): 221 offset(0), 222 extString(NULL) {} 223 ExtStringIteratorExtStringIterator224 explicit ExtStringIterator(TExtString *_extString, TSize _offset): 225 extString(_extString), 226 offset(_offset) {} 227 228 ////////////////////////////////////////////////////////////////////////////// 229 // iterator conversion interface 230 ExtStringIteratorExtStringIterator231 ExtStringIterator(const TStdIterator &I): 232 offset(I.offset), 233 extString(I.extString) {} 234 235 ////////////////////////////////////////////////////////////////////////////// 236 // iterator arithmetic 237 238 inline TDifference operator- (const TIterator &I) const { 239 return offset - I.offset; 240 } 241 242 inline TIterator operator- (TDifference delta) const { 243 return TIterator(extString, offset - delta); 244 } 245 246 inline TIterator& operator-= (TDifference delta) const { 247 offset -= delta; 248 return *this; 249 } 250 251 inline TIterator operator+ (TDifference delta) const { 252 return TIterator(extString, offset + delta); 253 } 254 255 inline TIterator& operator+= (TDifference delta) const { 256 offset += delta; 257 return *this; 258 } 259 260 inline TValue & operator* () const { 261 return (*extString)[offset]; 262 } 263 264 /* inline TValue const & operator* () const { 265 return (*extString)[offset]; 266 } 267 */ 268 inline TIterator& operator++ () { 269 ++offset; return *this; 270 } 271 272 inline TIterator operator++ (int) { 273 TIterator before = *this; 274 ++offset; return before; 275 } 276 277 inline TIterator& operator-- () { 278 --offset; return *this; 279 } 280 281 inline TIterator operator-- (int) { 282 TIterator before = *this; 283 --offset; return before; 284 } 285 286 inline bool operator== (const TIterator &I) const { 287 SEQAN_ASSERT_EQ(extString, I.extString); 288 return offset == I.offset; 289 } 290 291 inline bool operator!= (const TIterator &I) const { 292 SEQAN_ASSERT_EQ(extString, I.extString); 293 return offset != I.offset; 294 } 295 296 inline bool operator< (const TIterator &I) const { 297 SEQAN_ASSERT_EQ(extString, I.extString); 298 return offset < I.offset; 299 } 300 }; 301 302 303 ////////////////////////////////////////////////////////////////////////////// 304 // const random External String iterator 305 template < typename TExtString > 306 struct ExtStringConstIterator 307 { 308 //IOREV 309 typedef ExtStringConstIterator TIterator; 310 typedef ExtStringIterator<TExtString> TStdIterator; 311 typedef ExtStringConstIterator TStdConstIterator; 312 313 typedef typename Value<TExtString>::Type TValue; 314 typedef typename Size<TExtString>::Type TSize; 315 typedef typename Difference<TExtString>::Type TDifference; 316 typedef typename TExtString::TVolatilePtr TVolatilePtr; 317 318 enum { PAGESIZE = TExtString::PAGESIZE }; 319 320 TSize offset; 321 TExtString *extString; 322 323 ExtStringConstIteratorExtStringConstIterator324 ExtStringConstIterator(): 325 offset(0), 326 extString(NULL) {} 327 ExtStringConstIteratorExtStringConstIterator328 explicit ExtStringConstIterator(TExtString *_extString, TSize _offset): 329 extString(_extString), 330 offset(_offset) {} 331 332 ////////////////////////////////////////////////////////////////////////////// 333 // iterator conversion interface 334 ExtStringConstIteratorExtStringConstIterator335 ExtStringConstIterator(const TStdIterator &I): 336 offset(I.offset), 337 extString(I.extString) {} 338 ExtStringConstIteratorExtStringConstIterator339 ExtStringConstIterator(const TStdConstIterator &I): 340 offset(I.offset), 341 extString(I.extString) {} 342 343 ////////////////////////////////////////////////////////////////////////////// 344 // iterator arithmetic 345 346 inline TDifference operator- (const TIterator &I) const { 347 return offset - I.offset; 348 } 349 350 inline TIterator operator- (TDifference delta) const { 351 return TIterator(extString, offset - delta); 352 } 353 354 inline TIterator& operator-= (TDifference delta) const { 355 offset -= delta; 356 return *this; 357 } 358 359 inline TIterator operator+ (TDifference delta) const { 360 return TIterator(extString, offset + delta); 361 } 362 363 inline TIterator& operator+= (TDifference delta) const { 364 offset += delta; 365 return *this; 366 } 367 368 inline TValue const & operator* () const { 369 return (*extString)[offset]; 370 } 371 372 inline TIterator& operator++ () { 373 ++offset; return *this; 374 } 375 376 inline TIterator operator++ (int) { 377 TIterator before = *this; 378 ++offset; return before; 379 } 380 381 inline TIterator& operator-- () { 382 --offset; return *this; 383 } 384 385 inline TIterator operator-- (int) { 386 TIterator before = *this; 387 --offset; return before; 388 } 389 390 inline bool operator== (const TIterator &I) const { 391 SEQAN_ASSERT_EQ(extString, I.extString); 392 return offset == I.offset; 393 } 394 395 inline bool operator!= (const TIterator &I) const { 396 SEQAN_ASSERT_EQ(extString, I.extString); 397 return offset != I.offset; 398 } 399 400 inline bool operator< (const TIterator &I) const { 401 SEQAN_ASSERT_EQ(extString, I.extString); 402 return offset < I.offset; 403 } 404 }; 405 406 407 ////////////////////////////////////////////////////////////////////////////// 408 // forward External String iterator 409 template < typename TExtString > 410 struct ExtStringFwdIterator 411 { 412 //IOREV 413 typedef ExtStringFwdIterator TIterator; 414 typedef ExtStringIterator<TExtString> TStdIterator; 415 typedef ExtStringConstIterator<TExtString> TStdConstIterator; 416 417 typedef typename Value<TExtString>::Type TValue; 418 typedef typename Size<TExtString>::Type TSize; 419 typedef typename Difference<TExtString>::Type TDifference; 420 typedef typename TExtString::TVolatilePtr TVolatilePtr; 421 422 enum { PAGESIZE = TExtString::PAGESIZE }; 423 424 425 TExtString *extString; 426 427 bool dirty; 428 int pageNo; 429 unsigned pageOfs; 430 int prefetch; // -n .. prefetch n pages downwards, n .. prefetch n pages upwards, 0 .. disabled 431 TVolatilePtr begin; 432 ExtStringFwdIteratorExtStringFwdIterator433 ExtStringFwdIterator(): 434 extString(NULL), 435 dirty(true), 436 pageNo(0), 437 pageOfs(0), 438 prefetch(0), 439 begin(NULL) {} 440 ExtStringFwdIteratorExtStringFwdIterator441 ExtStringFwdIterator(const TIterator &I): 442 extString(I.extString), 443 dirty(true), 444 pageNo(I.pageNo), 445 pageOfs(I.pageOfs), 446 prefetch(I.prefetch), 447 begin(NULL) {} 448 ExtStringFwdIteratorExtStringFwdIterator449 explicit ExtStringFwdIterator(TExtString *_extString, TSize _offset): 450 extString(_extString), 451 dirty(true), 452 pageNo(_offset / PAGESIZE), 453 pageOfs(_offset % PAGESIZE), 454 prefetch(0), 455 begin(NULL) {} 456 ExtStringFwdIteratorExtStringFwdIterator457 explicit ExtStringFwdIterator(TExtString *_extString, TSize _pageNo, TSize _pageOfs): 458 extString(_extString), 459 dirty(true), 460 pageNo(_pageNo), 461 pageOfs(_pageOfs), 462 prefetch(0), 463 begin(NULL) {} 464 ~ExtStringFwdIteratorExtStringFwdIterator465 ~ExtStringFwdIterator() 466 { 467 invalidate(); 468 } 469 470 ////////////////////////////////////////////////////////////////////////////// 471 // iterator conversion interface 472 ExtStringFwdIteratorExtStringFwdIterator473 ExtStringFwdIterator(const TStdIterator &I): 474 extString(I.extString), 475 pageNo(I.offset / PAGESIZE), 476 pageOfs(I.offset % PAGESIZE), 477 prefetch(0), 478 begin(NULL) {} 479 480 inline TIterator& operator=(TStdIterator const & Right_) { 481 invalidate(); 482 pageNo = Right_.offset / PAGESIZE; 483 pageOfs = Right_.offset % PAGESIZE; 484 extString = Right_.extString; 485 return *this; 486 } 487 positionExtStringFwdIterator488 inline TSize position() const 489 { 490 return (TSize)pageNo * (TSize)PAGESIZE + pageOfs; 491 } 492 TStdIteratorExtStringFwdIterator493 inline operator TStdIterator() const { 494 return TStdIterator(extString, position()); 495 } 496 TStdConstIteratorExtStringFwdIterator497 inline operator TStdConstIterator() const { 498 return TStdConstIterator(extString, position()); 499 } 500 501 inline TIterator& operator=(TIterator const & Right_) { 502 invalidate(); 503 extString = Right_.extString; 504 pageNo = Right_.pageNo; 505 pageOfs = Right_.pageOfs; 506 prefetch = Right_.prefetch; 507 return *this; 508 } 509 510 ////////////////////////////////////////////////////////////////////////////// 511 // iterator arithmetic 512 513 inline TDifference operator- (const TIterator &I) const 514 { 515 return position() - I.position(); 516 } 517 518 inline TIterator operator- (TDifference delta) const { 519 TDifference dPNo = delta / PAGESIZE; 520 TDifference dPOfs = delta % PAGESIZE; 521 if (pageOfs >= dPOfs) 522 return TIterator(extString, pageNo - dPNo, pageOfs - dPOfs); 523 else 524 return TIterator(extString, pageNo - dPNo - 1, PAGESIZE + pageOfs - dPOfs); 525 } 526 527 inline TIterator& operator-= (TDifference delta) { 528 TDifference dPNo = delta / PAGESIZE; 529 TDifference dPOfs = delta % PAGESIZE; 530 if (pageOfs < dPOfs) { 531 ++dPNo; 532 pageOfs = PAGESIZE + pageOfs - dPOfs; 533 } else 534 pageOfs -= dPOfs; 535 if (dPNo) invalidate(0); 536 pageNo -= dPNo; 537 return *this; 538 } 539 540 inline TIterator operator+ (TDifference delta) const { 541 TDifference dPNo = delta / PAGESIZE; 542 TDifference nPOfs = pageOfs + delta % PAGESIZE; 543 if (nPOfs < PAGESIZE) 544 return TIterator(extString, pageNo + dPNo, nPOfs); 545 else 546 return TIterator(extString, pageNo + dPNo + 1, nPOfs - PAGESIZE); 547 } 548 549 inline TIterator& operator+= (TDifference delta) { 550 TDifference dPNo = delta / PAGESIZE; 551 TDifference nPOfs = pageOfs + delta % PAGESIZE; 552 if (nPOfs >= PAGESIZE) { 553 ++dPNo; 554 nPOfs -= PAGESIZE; 555 } 556 if (dPNo) invalidate(0); 557 pageNo += dPNo; 558 pageOfs = nPOfs; 559 return *this; 560 } 561 validateExtStringFwdIterator562 inline void validate() const 563 { 564 typename TExtString::TPageFrame &pf = extString->getSharedPage(pageNo, prefetch); 565 const_cast<TIterator*>(this)->dirty = pf.dirty; 566 const_cast<TIterator*>(this)->begin = pf.begin; 567 } 568 569 inline void invalidate(int _prefetch = 0) const 570 { 571 if (begin) 572 { 573 const_cast<TIterator*>(this)->begin = NULL; 574 extString->releasePage(pageNo, (prefetch != 0) || (_prefetch != 0)); 575 const_cast<TIterator*>(this)->prefetch = _prefetch; 576 } 577 } 578 579 inline TValue & operator* () const 580 { 581 if (!begin) validate(); 582 // synchronize PageFrame dirty flag on dirty false->true change 583 if (!dirty) { 584 const_cast<TIterator*>(this)->dirty = true; 585 extString->getPage(pageNo).dirty = true; 586 } 587 return const_cast<TIterator*>(this)->begin[pageOfs]; 588 } 589 /* 590 inline TValue const & operator* () const { 591 if (!begin) validate(); 592 return begin[pageOfs]; 593 } 594 */ 595 inline TIterator& operator++ () { 596 if (++pageOfs == PAGESIZE) { 597 invalidate(1); 598 pageOfs = 0; 599 ++pageNo; 600 } 601 return *this; 602 } 603 604 inline TIterator operator++ (int) { 605 TIterator before = *this; 606 if (++pageOfs == PAGESIZE) { 607 invalidate(1); 608 pageOfs = 0; 609 ++pageNo; 610 } 611 return before; 612 } 613 614 inline TIterator& operator-- () { 615 if (pageOfs) 616 --pageOfs; 617 else { 618 invalidate(-1); 619 pageOfs = PAGESIZE - 1; 620 --pageNo; 621 } 622 return *this; 623 } 624 625 inline TIterator operator-- (int) { 626 TIterator before = *this; 627 if (pageOfs) 628 --pageOfs; 629 else { 630 invalidate(-1); 631 pageOfs = PAGESIZE - 1; 632 --pageNo; 633 } 634 return before; 635 } 636 637 inline bool operator== (const TIterator &I) const { 638 SEQAN_ASSERT_EQ(extString, I.extString); 639 return pageNo == I.pageNo && pageOfs == I.pageOfs; 640 } 641 642 inline bool operator!= (const TIterator &I) const { 643 SEQAN_ASSERT_EQ(extString, I.extString); 644 return pageNo != I.pageNo || pageOfs != I.pageOfs; 645 } 646 647 inline bool operator< (const TIterator &I) const { 648 SEQAN_ASSERT_EQ(extString, I.extString); 649 return pageNo < I.pageNo || (pageNo == I.pageNo && pageOfs < I.pageOfs); 650 } 651 }; 652 653 654 ////////////////////////////////////////////////////////////////////////////// 655 // const forward External String iterator 656 template < typename TExtString > 657 struct ExtStringFwdConstIterator 658 { 659 //IOREV _nottested_ 660 typedef ExtStringFwdConstIterator TIterator; 661 typedef ExtStringIterator<TExtString> TStdIterator; 662 typedef ExtStringConstIterator<TExtString> TStdConstIterator; 663 typedef ExtStringFwdIterator<TExtString> TFwdIterator; 664 665 typedef typename Value<TExtString>::Type TValue; 666 typedef typename Size<TExtString>::Type TSize; 667 typedef typename Difference<TExtString>::Type TDifference; 668 typedef typename TExtString::TVolatilePtr TVolatilePtr; 669 670 enum { PAGESIZE = TExtString::PAGESIZE }; 671 672 673 TExtString *extString; 674 675 int pageNo; 676 unsigned pageOfs; 677 int prefetch; // -n .. prefetch n pages downwards, n .. prefetch n pages upwards, 0 .. disabled 678 TVolatilePtr begin; 679 680 ExtStringFwdConstIteratorExtStringFwdConstIterator681 ExtStringFwdConstIterator(): 682 extString(NULL), 683 pageNo(0), 684 pageOfs(0), 685 prefetch(0), 686 begin(NULL) {} 687 ExtStringFwdConstIteratorExtStringFwdConstIterator688 ExtStringFwdConstIterator(const TIterator &I): 689 extString(I.extString), 690 pageNo(I.pageNo), 691 pageOfs(I.pageOfs), 692 prefetch(I.prefetch), 693 begin(NULL) {} 694 ExtStringFwdConstIteratorExtStringFwdConstIterator695 ExtStringFwdConstIterator(const TFwdIterator &I): 696 extString(I.extString), 697 pageNo(I.pageNo), 698 pageOfs(I.pageOfs), 699 prefetch(I.prefetch), 700 begin(NULL) {} 701 ~ExtStringFwdConstIteratorExtStringFwdConstIterator702 ~ExtStringFwdConstIterator() { 703 invalidate(); 704 } 705 ExtStringFwdConstIteratorExtStringFwdConstIterator706 ExtStringFwdConstIterator(TExtString *_extString, TSize _offset): 707 extString(_extString), 708 pageNo(_offset / PAGESIZE), 709 pageOfs(_offset % PAGESIZE), 710 prefetch(0), 711 begin(NULL) {} 712 ExtStringFwdConstIteratorExtStringFwdConstIterator713 ExtStringFwdConstIterator(TExtString *_extString, TSize _pageNo, TSize _pageOfs): 714 extString(_extString), 715 pageNo(_pageNo), 716 pageOfs(_pageOfs), 717 prefetch(0), 718 begin(NULL) {} 719 720 ////////////////////////////////////////////////////////////////////////////// 721 // iterator conversion interface 722 ExtStringFwdConstIteratorExtStringFwdConstIterator723 ExtStringFwdConstIterator(TStdIterator &I): 724 extString(I.extString), 725 pageNo(I.offset / PAGESIZE), 726 pageOfs(I.offset % PAGESIZE), 727 prefetch(0), 728 begin(NULL) {} 729 ExtStringFwdConstIteratorExtStringFwdConstIterator730 ExtStringFwdConstIterator(TStdConstIterator const &I): 731 extString(I.extString), 732 pageNo(I.offset / PAGESIZE), 733 pageOfs(I.offset % PAGESIZE), 734 prefetch(0), 735 begin(NULL) {} 736 737 inline TIterator& operator=(TStdIterator const & Right_) { 738 invalidate(); 739 pageNo = Right_.offset / PAGESIZE; 740 pageOfs = Right_.offset % PAGESIZE; 741 extString = Right_.extString; 742 return *this; 743 } 744 745 inline TIterator& operator=(TStdConstIterator const & Right_) { 746 invalidate(); 747 pageNo = Right_.offset / PAGESIZE; 748 pageOfs = Right_.offset % PAGESIZE; 749 extString = Right_.extString; 750 return *this; 751 } 752 positionExtStringFwdConstIterator753 inline TSize position() const 754 { 755 return (TSize)pageNo * (TSize)PAGESIZE + pageOfs; 756 } 757 TStdConstIteratorExtStringFwdConstIterator758 inline operator TStdConstIterator() const { 759 return TStdConstIterator(extString, position()); 760 } 761 762 inline TIterator& operator=(TIterator const & Right_) { 763 invalidate(); 764 extString = Right_.extString; 765 pageNo = Right_.pageNo; 766 pageOfs = Right_.pageOfs; 767 prefetch = Right_.prefetch; 768 return *this; 769 } 770 771 inline TIterator& operator=(TFwdIterator const & Right_) { 772 invalidate(); 773 extString = Right_.extString; 774 pageNo = Right_.pageNo; 775 pageOfs = Right_.pageOfs; 776 prefetch = Right_.prefetch; 777 return *this; 778 } 779 780 ////////////////////////////////////////////////////////////////////////////// 781 // iterator arithmetic 782 783 inline TDifference operator- (const TIterator &I) const 784 { 785 return position() - I.position(); 786 } 787 788 inline TIterator operator- (TDifference delta) const { 789 TDifference dPNo = delta / PAGESIZE; 790 TDifference dPOfs = delta % PAGESIZE; 791 if (pageOfs >= dPOfs) 792 return TIterator(extString, pageNo - dPNo, pageOfs - dPOfs); 793 else 794 return TIterator(extString, pageNo - dPNo - 1, PAGESIZE + pageOfs - dPOfs); 795 } 796 797 inline TIterator& operator-= (TDifference delta) { 798 TDifference dPNo = delta / PAGESIZE; 799 TDifference dPOfs = delta % PAGESIZE; 800 if (pageOfs < dPOfs) { 801 ++dPNo; 802 pageOfs = PAGESIZE + pageOfs - dPOfs; 803 } else 804 pageOfs -= dPOfs; 805 if (dPNo) invalidate(0); 806 pageNo -= dPNo; 807 return *this; 808 } 809 810 inline TIterator operator+ (TDifference delta) const { 811 TDifference dPNo = delta / PAGESIZE; 812 TDifference nPOfs = pageOfs + delta % PAGESIZE; 813 if (nPOfs < PAGESIZE) 814 return TIterator(extString, pageNo + dPNo, nPOfs); 815 else 816 return TIterator(extString, pageNo + dPNo + 1, nPOfs - PAGESIZE); 817 } 818 819 inline TIterator& operator+= (TDifference delta) { 820 TDifference dPNo = delta / PAGESIZE; 821 TDifference nPOfs = pageOfs + delta % PAGESIZE; 822 if (nPOfs >= PAGESIZE) { 823 ++dPNo; 824 nPOfs -= PAGESIZE; 825 } 826 if (dPNo) invalidate(0); 827 pageNo += dPNo; 828 pageOfs = nPOfs; 829 return *this; 830 } 831 validateExtStringFwdConstIterator832 inline void validate() const { 833 typename TExtString::TPageFrame &pf = extString->getSharedPage(pageNo, prefetch); 834 const_cast<TIterator*>(this)->begin = pf.begin; 835 } 836 837 inline void invalidate(int _prefetch = 0) const { 838 if (begin) { 839 const_cast<TIterator*>(this)->begin = NULL; 840 extString->releasePage(pageNo, (prefetch != 0) || (_prefetch != 0)); 841 const_cast<TIterator*>(this)->prefetch = _prefetch; 842 } 843 } 844 845 inline TValue const & operator* () const { 846 if (!begin) validate(); 847 return begin[pageOfs]; 848 } 849 850 inline TIterator& operator++ () { 851 if (++pageOfs == PAGESIZE) { 852 invalidate(1); 853 pageOfs = 0; 854 ++pageNo; 855 } 856 return *this; 857 } 858 859 inline TIterator operator++ (int) { 860 TIterator before = *this; 861 if (++pageOfs == PAGESIZE) { 862 invalidate(1); 863 pageOfs = 0; 864 ++pageNo; 865 } 866 return before; 867 } 868 869 inline TIterator& operator-- () { 870 if (pageOfs) 871 --pageOfs; 872 else { 873 invalidate(-1); 874 pageOfs = PAGESIZE - 1; 875 --pageNo; 876 } 877 return *this; 878 } 879 880 inline TIterator operator-- (int) { 881 TIterator before = *this; 882 if (pageOfs) 883 --pageOfs; 884 else { 885 invalidate(-1); 886 pageOfs = PAGESIZE - 1; 887 --pageNo; 888 } 889 return before; 890 } 891 892 inline bool operator== (const TIterator &I) const { 893 SEQAN_ASSERT_EQ(extString, I.extString); 894 return pageNo == I.pageNo && pageOfs == I.pageOfs; 895 } 896 897 inline bool operator!= (const TIterator &I) const { 898 SEQAN_ASSERT_EQ(extString, I.extString); 899 return pageNo != I.pageNo || pageOfs != I.pageOfs; 900 } 901 902 inline bool operator< (const TIterator &I) const { 903 SEQAN_ASSERT_EQ(extString, I.extString); 904 return pageNo < I.pageNo || (pageNo == I.pageNo && pageOfs < I.pageOfs); 905 } 906 907 }; 908 909 910 911 ////////////////////////////////////////////////////////////////////////////// 912 // iterator metafunctions 913 914 template < typename TString > 915 struct Container< ExtStringIterator<TString> > { typedef TString Type; }; 916 //IOREV 917 template < typename TString > 918 struct Container< ExtStringConstIterator<TString> > { typedef TString Type; }; 919 //IOREV 920 template < typename TString > 921 struct Container< ExtStringFwdIterator<TString> > { typedef TString Type; }; 922 //IOREV 923 template < typename TString > 924 struct Container< ExtStringFwdConstIterator<TString> > { typedef TString Type; }; 925 //IOREV 926 927 template < typename TString > 928 struct Value< ExtStringIterator<TString> > { typedef typename Value<TString>::Type Type; }; 929 //IOREV 930 template < typename TString > 931 struct Value< ExtStringConstIterator<TString> > { typedef typename Value<TString>::Type Type; }; 932 //IOREV 933 template < typename TString > 934 struct Value< ExtStringFwdIterator<TString> > { typedef typename Value<TString>::Type Type; }; 935 //IOREV 936 template < typename TString > 937 struct Value< ExtStringFwdConstIterator<TString> > { typedef typename Value<TString>::Type Type; }; 938 //IOREV 939 940 template < typename TString > 941 struct Reference< ExtStringConstIterator<TString> >: 942 public Reference<TString const> {}; 943 //IOREV 944 945 template < typename TString > 946 struct Reference< ExtStringFwdConstIterator<TString> >: 947 public Reference<TString const> {}; 948 //IOREV 949 950 template < typename TString > 951 struct Size< ExtStringIterator<TString> > { typedef typename Size<TString>::Type Type; }; 952 //IOREV 953 template < typename TString > 954 struct Size< ExtStringConstIterator<TString> > { typedef typename Size<TString>::Type Type; }; 955 //IOREV 956 template < typename TString > 957 struct Size< ExtStringFwdIterator<TString> > { typedef typename Size<TString>::Type Type; }; 958 //IOREV 959 template < typename TString > 960 struct Size< ExtStringFwdConstIterator<TString> > { typedef typename Size<TString>::Type Type; }; 961 //IOREV 962 963 template < typename TString > 964 struct Position< ExtStringIterator<TString> > { typedef typename Position<TString>::Type Type; }; 965 //IOREV 966 template < typename TString > 967 struct Position< ExtStringConstIterator<TString> > { typedef typename Position<TString>::Type Type; }; 968 //IOREV 969 template < typename TString > 970 struct Position< ExtStringFwdIterator<TString> > { typedef typename Position<TString>::Type Type; }; 971 //IOREV 972 template < typename TString > 973 struct Position< ExtStringFwdConstIterator<TString> > { typedef typename Position<TString>::Type Type; }; 974 //IOREV 975 976 template < typename TString > 977 struct Difference< ExtStringIterator<TString> > { typedef typename Difference<TString>::Type Type; }; 978 //IOREV 979 template < typename TString > 980 struct Difference< ExtStringConstIterator<TString> > { typedef typename Difference<TString>::Type Type; }; 981 //IOREV 982 template < typename TString > 983 struct Difference< ExtStringFwdIterator<TString> > { typedef typename Difference<TString>::Type Type; }; 984 //IOREV 985 template < typename TString > 986 struct Difference< ExtStringFwdConstIterator<TString> > { typedef typename Difference<TString>::Type Type; }; 987 //IOREV 988 989 990 ////////////////////////////////////////////////////////////////////////////// 991 // global interface 992 993 template <typename TExtString> 994 inline TExtString & container(ExtStringIterator<TExtString> &it) { return *(it.extString); } 995 //IOREV 996 template <typename TExtString> 997 inline TExtString & container(ExtStringIterator<TExtString> const &it) { return *(it.extString); } 998 //IOREV 999 1000 template <typename TExtString> 1001 inline TExtString & container(ExtStringConstIterator<TExtString> &it) { return *(it.extString); } 1002 //IOREV 1003 template <typename TExtString> 1004 inline TExtString & container(ExtStringConstIterator<TExtString> const &it) { return *(it.extString); } 1005 //IOREV 1006 1007 template <typename TExtString> 1008 inline TExtString & container(ExtStringFwdIterator<TExtString> &it) { return *(it.extString); } 1009 //IOREV 1010 template <typename TExtString> 1011 inline TExtString & container(ExtStringFwdIterator<TExtString> const &it) { return *(it.extString); } 1012 //IOREV 1013 1014 template <typename TExtString> 1015 inline TExtString & container(ExtStringFwdConstIterator<TExtString> &it) { return *(it.extString); } 1016 //IOREV 1017 template <typename TExtString> 1018 inline TExtString & container(ExtStringFwdConstIterator<TExtString> const &it) { return *(it.extString); } 1019 //IOREV 1020 //____________________________________________________________________________ 1021 1022 template <typename TExtString> 1023 inline bool atBegin(ExtStringIterator<TExtString> &it) { return it.offset == 0; } 1024 //IOREV 1025 template <typename TExtString> 1026 inline bool atBegin(ExtStringIterator<TExtString> const &it) { return it.offset == 0; } 1027 //IOREV 1028 1029 template <typename TExtString> 1030 inline bool atBegin(ExtStringConstIterator<TExtString> &it) { return it.offset == 0; } 1031 //IOREV 1032 template <typename TExtString> 1033 inline bool atBegin(ExtStringConstIterator<TExtString> const &it) { return it.offset == 0; } 1034 //IOREV 1035 1036 template <typename TExtString> 1037 inline bool atBegin(ExtStringFwdIterator<TExtString> &it) { 1038 //IOREV 1039 return it.pageNo == 0 && it.pageOfs == 0; 1040 } 1041 template <typename TExtString> 1042 inline bool atBegin(ExtStringFwdIterator<TExtString> const &it) { 1043 //IOREV 1044 return it.pageNo == 0 && it.pageOfs == 0; 1045 } 1046 1047 template <typename TExtString> 1048 inline bool atBegin(ExtStringFwdConstIterator<TExtString> &it) { 1049 //IOREV 1050 return it.pageNo == 0 && it.pageOfs == 0; 1051 } 1052 template <typename TExtString> 1053 inline bool atBegin(ExtStringFwdConstIterator<TExtString> const &it) { 1054 //IOREV 1055 return it.pageNo == 0 && it.pageOfs == 0; 1056 } 1057 //____________________________________________________________________________ 1058 1059 template <typename TExtString> 1060 inline bool atEnd(ExtStringIterator<TExtString> &it) { return it.offset == it.extString->data_size; } 1061 //IOREV 1062 template <typename TExtString> 1063 inline bool atEnd(ExtStringIterator<TExtString> const &it) { return it.offset == it.extString->data_size; } 1064 //IOREV 1065 1066 template <typename TExtString> 1067 inline bool atEnd(ExtStringConstIterator<TExtString> &it) { return it.offset == it.extString->data_size; } 1068 //IOREV 1069 template <typename TExtString> 1070 inline bool atEnd(ExtStringConstIterator<TExtString> const &it) { return it.offset == it.extString->data_size; } 1071 //IOREV 1072 1073 template <typename TExtString> 1074 inline bool atEnd(ExtStringFwdIterator<TExtString> &it) { 1075 //IOREV 1076 return TExtString::PAGESIZE * it.pageNo + it.pageOfs == it.extString->data_size; 1077 } 1078 template <typename TExtString> 1079 inline bool atEnd(ExtStringFwdIterator<TExtString> const &it) { 1080 //IOREV 1081 return TExtString::PAGESIZE * it.pageNo + it.pageOfs == it.extString->data_size; 1082 } 1083 1084 template <typename TExtString> 1085 inline bool atEnd(ExtStringFwdConstIterator<TExtString> &it) { 1086 //IOREV 1087 return TExtString::PAGESIZE * it.pageNo + it.pageOfs == it.extString->data_size; 1088 } 1089 template <typename TExtString> 1090 inline bool atEnd(ExtStringFwdConstIterator<TExtString> const &it) { 1091 //IOREV 1092 return TExtString::PAGESIZE * it.pageNo + it.pageOfs == it.extString->data_size; 1093 } 1094 1095 1096 1097 1098 1099 1100 ////////////////////////////////////////////////////////////////////////////// 1101 // External String 1102 ////////////////////////////////////////////////////////////////////////////// 1103 1104 template < typename TValue, 1105 typename TConfig > 1106 class String<TValue, External<TConfig> > 1107 { 1108 //IOREV _doc_ contains TODOs by holtgrew 1109 public: 1110 enum { FRAMES = TConfig::FRAMES, 1111 PAGESIZE = TConfig::PAGESIZE }; 1112 1113 typedef typename TConfig::TFile TFile; 1114 typedef typename TConfig::TSize TSize; 1115 1116 typedef String<int> TPageTable; 1117 typedef Buffer<TValue, PageFrame<TFile, Fixed<PAGESIZE> > > TPageFrame; 1118 typedef PageContainer<TPageFrame, FRAMES> TCache; 1119 typedef VolatilePtr<TValue> TVolatilePtr; 1120 1121 TPageTable pager; 1122 TCache cache; 1123 TFile file; 1124 bool _temporary, _ownFile; 1125 TSize data_size; 1126 int lastDiskPage; // the last page on disk and in mem 1127 unsigned lastDiskPageSize; // can be smaller than PAGESIZE 1128 1129 String(TSize size = 0) : 1130 file(NULL), _temporary(true), _ownFile(false), data_size(0), 1131 lastDiskPage(0), // the last two values need not to be initialized here 1132 lastDiskPageSize(0) // because of "write before read" 1133 { 1134 resize(*this, size); 1135 } 1136 1137 /*! 1138 * @fn ExternalString::String 1139 * @brief Constructor 1140 * 1141 * @signature String::String(); 1142 * @signature String::String(file); 1143 * @signature String::String(fileName[, openMode]); 1144 * 1145 * @param[in] file The @link File @endlink to use for reading and writing. You must ensture that 1146 * <tt>file</tt> is open as the string will not call <tt>open</tt> and <tt>close</tt> 1147 * on the file. 1148 * @param[in] fileName The path to open. Type: <tt>char const *</tt> 1149 * @param[in,out] openMode The open mode. 1150 * 1151 * @section Remarks 1152 * 1153 * When a file or file name is given, this file will be used for the ExternalString. If the file exists, this file will 1154 * be used and determines the strings length and content. If the file doesn't exist, a new and empty file will be 1155 * created and used for the string. In both cases, the string won't delete the file in the destructor. 1156 * 1157 * When no file is given (default c'tor) the string will be empty and no file is used until the string needs to swap out 1158 * page frames. Then a temporary file will be used which will be deleted when the string is destroyed. 1159 * 1160 * Instead of giving file or fileName to the constructor, you could also use the default constructor and call open or 1161 * openTemp afterwards to reach the same behaviour. 1162 */ 1163 1164 explicit 1165 String(TFile &_file) : 1166 file(NULL), _temporary(true), _ownFile(false), data_size(0), lastDiskPage(0), lastDiskPageSize(0) 1167 { 1168 open(*this, _file); 1169 } 1170 1171 explicit 1172 String(const char *fileName, int openMode = DefaultOpenMode<TFile>::VALUE) : 1173 file(NULL), _temporary(true), _ownFile(false), data_size(0), lastDiskPage(0), lastDiskPageSize(0) 1174 { 1175 open(*this, fileName, openMode); 1176 } 1177 1178 // copy the contents from another string 1179 String(String const & source): 1180 file(NULL), _temporary(true), _ownFile(false), data_size(0), lastDiskPage(0), lastDiskPageSize(0) 1181 { 1182 assign(*this, source); 1183 } 1184 1185 template <typename TSource> 1186 String(TSource const & source) : 1187 file(NULL), _temporary(true), _ownFile(false), data_size(0), lastDiskPage(0), lastDiskPageSize(0) 1188 { 1189 assign(*this, source); 1190 } 1191 1192 ~String() 1193 { 1194 close(*this); 1195 } 1196 1197 inline TValue & operator[] (TSize offset) { 1198 TPageFrame &pf = getPage(offset / PAGESIZE); 1199 pf.dirty = true; 1200 return pf[offset % PAGESIZE]; 1201 } 1202 1203 inline TValue const & operator[] (TSize offset) const { 1204 return const_cast<String*>(this)->getPage(offset / PAGESIZE)[offset % PAGESIZE]; 1205 } 1206 1207 template <typename TSource> 1208 inline String & operator= (TSource const & source) 1209 { 1210 assign(*this, source); 1211 return *this; 1212 } 1213 1214 inline String & operator= (String const & source) 1215 { 1216 assign(*this, source); 1217 return *this; 1218 } 1219 1220 inline operator bool() 1221 { 1222 return file; 1223 } 1224 1225 ////////////////////////////////////////////////////////////////////////////// 1226 // swapping interface 1227 1228 // when a page has to be swapped out and file is not open, open a temporary file 1229 inline void _ensureFileIsOpen() 1230 { 1231 if (!file) 1232 { 1233 _temporary = true; 1234 if (!(_ownFile = openTemp(file))) 1235 std::cerr << "External String couldn't open temporary file" << std::endl; 1236 } 1237 } 1238 1239 // for debugging 1240 void _dumpCache() 1241 { 1242 for(int i = 0; i < length(cache); ++i) 1243 { 1244 TPageFrame &pf = cache[i]; 1245 std::cerr << "[" << pf.pageNo << "]"; 1246 if (pf.dirty) 1247 std::cerr << "*"; 1248 else 1249 std::cerr << " "; 1250 1251 if (pf.status == READY) 1252 std::cerr << " "; 1253 else 1254 std::cerr << ". "; 1255 } 1256 std::cerr << std::endl; 1257 } 1258 1259 // return a priority for a page frame (the higher is more persistent) 1260 inline typename TPageFrame::Priority getPriority(int /*pageNo*/) const 1261 { 1262 /* if (keepFirst && pageNo < (int)(length(cache)) - 10) // save 1 for random access 1263 return TPageFrame::PERMANENT_LEVEL; 1264 else*/ 1265 return TPageFrame::NORMAL_LEVEL; 1266 } 1267 1268 // write page to disk if dirty and remove from page table now or after finishing IO 1269 inline void flush(TPageFrame &pf) 1270 { 1271 if (pf.status == READY && pf.dirty) { // write if dirty and not i/o transferring 1272 nukeCopies(pf.begin); // proceeding writes should wait and set dirty bit 1273 1274 if (pf.priority > TPageFrame::NORMAL_LEVEL && pf.priority <= TPageFrame::ITERATOR_LEVEL) 1275 cache.upgrade(pf, TPageFrame::PREFETCH_LEVEL); 1276 1277 _ensureFileIsOpen(); 1278 if (pf.pageNo != (int)(data_size / (TSize)PAGESIZE)) 1279 writePage(pf, pf.pageNo, file); 1280 else { 1281 lastDiskPage = data_size / PAGESIZE; 1282 lastDiskPageSize = data_size % PAGESIZE; 1283 writeLastPage(pf, pf.pageNo, file, lastDiskPageSize); 1284 } 1285 pf.dataStatus = TPageFrame::ON_DISK; 1286 } 1287 } 1288 1289 // write page synchronously to disk if dirty and remove from page table 1290 inline void swapOutAndWait(TPageFrame &pf) 1291 { 1292 nukeCopies(pf.begin); // proceeding writes should wait and set dirty bit 1293 1294 if (pf.status != READY) 1295 { 1296 pager[pf.pageNo] = TPageFrame::ON_DISK; // page is not dirty and on disk 1297 bool waitResult = waitFor(pf); // after finishing I/O transfer 1298 1299 // TODO(weese): Throw an I/O exception 1300 if (!waitResult) 1301 SEQAN_FAIL("%s operation could not be completed: \"%s\"", 1302 _pageFrameStatusString(pf.status), 1303 strerror(errno)); 1304 1305 pf.pageNo = -1; // cut back link 1306 return; 1307 } 1308 1309 if (pf.dirty) { // write if dirty 1310 _ensureFileIsOpen(); 1311 if (pf.pageNo != (int)(data_size / (TSize)PAGESIZE)) { 1312 writePage(pf, pf.pageNo, file); 1313 if (pf.pageNo >= lastDiskPage) 1314 lastDiskPage = -1; // make lastDiskPage(Size) invalid because file size is aligned 1315 } else { 1316 writeLastPage(pf, pf.pageNo, file, data_size % PAGESIZE); 1317 lastDiskPage = data_size / PAGESIZE; 1318 lastDiskPageSize = data_size % PAGESIZE; 1319 } 1320 pager[pf.pageNo] = TPageFrame::ON_DISK; // page is marked to be on disk 1321 bool waitResult = waitFor(pf); // after finishing I/O transfer 1322 1323 // TODO(weese): Throw an I/O exception 1324 if (!waitResult) 1325 SEQAN_FAIL("%s operation could not be completed: \"%s\"", 1326 _pageFrameStatusString(pf.status), 1327 strerror(errno)); 1328 } else 1329 pager[pf.pageNo] = pf.dataStatus; // restore original data status 1330 1331 pf.pageNo = -1; // cut back link 1332 } 1333 1334 struct testIODone : public std::unary_function<TPageFrame&,bool> 1335 { 1336 String &me; 1337 testIODone(String &_me): me(_me) {} 1338 1339 inline bool operator() (TPageFrame &pf) 1340 { 1341 PageFrameState oldStatus = pf.status; 1342 bool inProgress; 1343 bool waitResult = waitFor(pf, 0, inProgress); 1344 1345 // TODO(weese): Throw an I/O exception 1346 if (!waitResult) 1347 SEQAN_FAIL("%s operation could not be completed: \"%s\"", 1348 _pageFrameStatusString(pf.status), 1349 strerror(errno)); 1350 1351 if (!inProgress && (oldStatus != READY)) 1352 { 1353 if (pf.pageNo >= me.lastDiskPage) 1354 me.lastDiskPage = -1; // make lastDiskPage(Size) invalid because file size is aligned 1355 } 1356 return !inProgress; 1357 } 1358 }; 1359 1360 inline TPageFrame &getPage( 1361 int pageNo, 1362 typename TPageFrame::Priority maxLevel, 1363 typename TPageFrame::Priority newLevel, 1364 int prefetchPages) 1365 { 1366 int frameNo = pager[pageNo]; 1367 if (frameNo >= 0) // cache hit 1368 { 1369 TPageFrame &pf = cache[frameNo]; 1370 cache.upgrade( 1371 pf, 1372 _max(pf.priority, newLevel)); // update lru order 1373 1374 PageFrameState oldStatus = pf.status; 1375 bool waitResult = waitFor(pf); // wait for I/O transfer to complete 1376 1377 // TODO(weese): Throw an I/O exception 1378 if (!waitResult) 1379 SEQAN_FAIL("%s operation could not be completed: \"%s\"", 1380 _pageFrameStatusString(pf.status), 1381 strerror(errno)); 1382 1383 if (oldStatus != READY) 1384 if (pf.pageNo >= lastDiskPage) 1385 lastDiskPage = -1; // make lastDiskPage(Size) invalid because file size is aligned 1386 1387 if (prefetchPages > 0) prefetch(pageNo + 1, pageNo + 1 + prefetchPages, frameNo); 1388 else if (prefetchPages < 0) prefetch(pageNo + prefetchPages, pageNo, frameNo); 1389 1390 return pf; 1391 1392 } else { // cache miss 1393 1394 typename TPageFrame::DataStatus dataStatus = static_cast<typename TPageFrame::DataStatus>(frameNo); 1395 frameNo = cache.mru(testIODone(*this), maxLevel); // try to get an undirty and READY pageframe 1396 if (frameNo < 0) // if there is none, 1397 frameNo = cache.mruDirty(); // get the most recently used dirty frame 1398 TPageFrame &pf = cache[frameNo]; 1399 1400 // *** frame is choosen *** 1401 1402 if (pf.begin) 1403 swapOutAndWait(pf); // write synchronously to disk, if page is dirty 1404 else 1405 allocPage(pf, file); // allocate memory if page is virgin 1406 1407 // *** frame is free now *** 1408 1409 pf.dataStatus = dataStatus; 1410 if (dataStatus == TPageFrame::ON_DISK) 1411 { 1412 if (pageNo != lastDiskPage) 1413 readPage(pageNo, pf, file); 1414 else 1415 readLastPage(pageNo, pf, file, lastDiskPageSize); 1416 } 1417 pager[pageNo] = frameNo; // assign new page to page table 1418 pf.pageNo = pageNo; // set back link 1419 cache.upgrade( 1420 pf, 1421 _max(getPriority(pageNo), newLevel)); // update lru order 1422 1423 if (prefetchPages > 0) prefetch(pageNo + 1, pageNo + 1 + prefetchPages, frameNo); 1424 else if (prefetchPages < 0) prefetch(pageNo + prefetchPages, pageNo, frameNo); 1425 1426 bool waitResult = waitFor(pf); // wait for I/O transfer to complete 1427 1428 // TODO(weese): Throw an I/O exception 1429 if (!waitResult) 1430 SEQAN_FAIL("%s operation could not be completed: \"%s\"", 1431 _pageFrameStatusString(pf.status), 1432 strerror(errno)); 1433 1434 return pf; 1435 } 1436 } 1437 1438 inline TPageFrame &getPage(int pageNo) 1439 { 1440 return getPage(pageNo, TPageFrame::NORMAL_LEVEL, TPageFrame::NORMAL_LEVEL, 0); 1441 } 1442 1443 // prefetch is non-blocking and should speed up swapping 1444 inline void prefetch(int pageBegin, int pageEnd, int except = -1) 1445 { 1446 if (!file) return; 1447 if (pageBegin < 0) pageBegin = 0; 1448 if (pageEnd >= (int)length(pager)) pageEnd = (int)length(pager) - 1; 1449 for(int pageNo = pageBegin; pageNo < pageEnd; ++pageNo) { 1450 int frameNo = pager[pageNo]; 1451 typename TPageFrame::DataStatus dataStatus = static_cast<typename TPageFrame::DataStatus>(frameNo); 1452 if (dataStatus == TPageFrame::ON_DISK && // prefetch only if page is on disk 1453 pageNo != lastDiskPage) // reading the last page is blocking 1454 { 1455 frameNo = cache.mru( 1456 testIODone(*this), 1457 TPageFrame::NORMAL_LEVEL); // choose undirty and ready page 1458 1459 if (frameNo < 0 || frameNo == except) return; // no lowlevel-page left for prefetching 1460 TPageFrame &pf = cache[frameNo]; 1461 #ifdef SEQAN_VERBOSE 1462 std::cerr << "prefetch: page " << pageNo << std::endl; 1463 #endif 1464 1465 // *** frame is choosen *** 1466 1467 if (pf.begin) 1468 swapOutAndWait(pf); // write synchronously to disk, if page is dirty 1469 else 1470 allocPage(pf, file); // allocate memory if page is virgin 1471 1472 // *** frame is free now *** 1473 1474 pf.dataStatus = dataStatus; 1475 readPage(pageNo, pf, file); 1476 pager[pageNo] = frameNo; // assign new page to page table 1477 pf.pageNo = pageNo; // set back link 1478 cache.upgrade(pf, TPageFrame::PREFETCH_LEVEL); // update lru order 1479 } 1480 } 1481 } 1482 1483 template < typename T > 1484 inline static int _prefetchIffAsync(int /*prefetchPages*/, T const &) { 1485 return 0; 1486 } 1487 1488 template < typename TSpec > 1489 inline static int _prefetchIffAsync(int prefetchPages, File<Async<TSpec> > const &) { 1490 return prefetchPages; 1491 } 1492 1493 inline TPageFrame &getSharedPage(int pageNo, int prefetchPages = 0) 1494 { 1495 return getPage( 1496 pageNo, 1497 TPageFrame::PREFETCH_LEVEL, 1498 TPageFrame::ITERATOR_LEVEL, 1499 _prefetchIffAsync(prefetchPages, file)); 1500 } 1501 1502 inline void releasePage(int pageNo, bool writeThrough = false) 1503 { 1504 int frameNo = pager[pageNo]; 1505 if (frameNo >= 0) // release only cached pages 1506 { 1507 TPageFrame &pf = cache[frameNo]; 1508 if (pf.begin.isLonely() && pf.priority <= TPageFrame::ITERATOR_LEVEL) 1509 { 1510 cache.upgrade(pf, _max(getPriority(pageNo), TPageFrame::NORMAL_LEVEL)); 1511 if (writeThrough) 1512 { 1513 #ifdef SEQAN_VERBOSE 1514 if (pf.dirty) 1515 std::cerr << "writeThrough: page " << pageNo << std::endl; 1516 #endif 1517 flush(pf); // write if dirty 1518 } 1519 } 1520 } 1521 } 1522 1523 inline void rename(unsigned frameNo) 1524 { 1525 TPageFrame &pf = cache[frameNo]; 1526 cache.rename(frameNo); // update lru entry 1527 if (pf.pageNo >= 0) 1528 pager[pf.pageNo] = frameNo; // update back link 1529 } 1530 1531 // change the number of in-mem pageframes 1532 // more pages mean less swapping, 1533 // less pages mean more free mem 1534 inline void resizeCache(unsigned newFrames) 1535 { 1536 unsigned oldFrames = length(cache); 1537 if (data_size) 1538 newFrames = _min(newFrames, (unsigned) enclosingBlocks(data_size, (unsigned)PAGESIZE)); 1539 if (newFrames < oldFrames) { 1540 flush(*this); 1541 for(unsigned i = newFrames; i < oldFrames; ++i) { 1542 int frameNo = cache.mruDirty(); // get the most recently used frame (can be dirty) 1543 if (frameNo < 0) break; 1544 TPageFrame &pf = cache[frameNo]; 1545 1546 // *** frame is choosen *** 1547 1548 if (pf.begin) { 1549 swapOutAndWait(pf); // write synchronously to disk, if page is dirty 1550 freePage(pf, file); // free memory 1551 } 1552 1553 cache.erase(frameNo); // erase page frame from cache 1554 1555 for(unsigned j = frameNo; j < length(cache); ++j) 1556 rename(j); // update remaining pages 1557 } 1558 } else if (oldFrames < newFrames) { 1559 resize(cache, newFrames); 1560 } 1561 } 1562 1563 }; 1564 1565 1566 ////////////////////////////////////////////////////////////////////////////// 1567 // meta-function interface 1568 1569 template < typename TValue, typename TConfig > 1570 struct Size< String<TValue, External<TConfig> > > 1571 { 1572 //IOREV 1573 typedef typename String<TValue, External<TConfig> >::TSize Type; 1574 }; 1575 1576 template < typename TValue, typename TConfig > 1577 struct Difference< String<TValue, External<TConfig> > > 1578 { 1579 //IOREV 1580 typedef typename MakeSigned_<typename String<TValue, External<TConfig> >::TSize>::Type Type; 1581 }; 1582 1583 template < typename TValue, typename TConfig, typename TSpec > 1584 struct Iterator< String<TValue, External<TConfig> > const, Tag<TSpec> const > 1585 { 1586 //IOREV 1587 typedef ExtStringFwdConstIterator< String<TValue, External<TConfig> > > Type; 1588 }; 1589 1590 template < typename TValue, typename TConfig, typename TSpec > 1591 struct Iterator< String<TValue, External<TConfig> >, Tag<TSpec> const > 1592 { 1593 //IOREV 1594 typedef ExtStringFwdIterator< String<TValue, External<TConfig> > > Type; 1595 }; 1596 //____________________________________________________________________________ 1597 1598 template < typename TValue, typename TConfig > 1599 struct DefaultOverflowExplicit<String<TValue, External<TConfig> > > 1600 { 1601 //IOREV 1602 typedef Generous Type; 1603 }; 1604 1605 template < typename TValue, typename TConfig > 1606 struct DefaultOverflowImplicit<String<TValue, External<TConfig> > > 1607 { 1608 //IOREV 1609 typedef Generous Type; 1610 }; 1611 //____________________________________________________________________________ 1612 1613 /* 1614 template < typename TValue, typename TConfig > 1615 struct DefaultIteratorSpec< String<TValue, External<TConfig> > > { 1616 typedef Standard Type; 1617 }; 1618 1619 template < typename TValue, typename TConfig > 1620 struct DefaultIteratorSpec< String<TValue, External<TConfig> > const > { 1621 typedef Standard Type; 1622 }; 1623 */ 1624 1625 template < typename TValue, typename TConfig > 1626 struct AllowsFastRandomAccess< String<TValue, External<TConfig> > > 1627 { 1628 //IOREV 1629 typedef False Type; 1630 enum { VALUE = false }; 1631 }; 1632 1633 1634 ////////////////////////////////////////////////////////////////////////////// 1635 // global interface 1636 1637 //____________________________________________________________________________ 1638 1639 template < typename TValue, typename TConfig > 1640 inline void 1641 clear(String<TValue, External<TConfig> > &me) 1642 { 1643 //IOREV 1644 // clear(me.pager); 1645 resize(me, 0); 1646 } 1647 //____________________________________________________________________________ 1648 1649 // wait until IO of every page is finished 1650 template < typename TValue, typename TConfig > 1651 inline void 1652 waitForAll(String<TValue, External<TConfig> > &me) 1653 { 1654 //IOREV _nodoc_ 1655 typedef typename String<TValue, External<TConfig> >::TCache TCache; 1656 typedef typename Iterator<TCache, Standard>::Type TIter; 1657 1658 TIter f = begin(me.cache, Standard()); 1659 TIter fEnd = end(me.cache, Standard()); 1660 1661 for(; f != fEnd ; ++f) 1662 { 1663 bool waitResult = waitFor(*f); // wait for I/O transfer to complete 1664 1665 if (!waitResult) 1666 SEQAN_FAIL("%s operation could not be completed: \"%s\"", 1667 _pageFrameStatusString(f->status), 1668 strerror(errno)); 1669 } 1670 } 1671 1672 /*! 1673 * @fn ExternalString#flush 1674 * @brief Waits for all open read/write requests to complete. 1675 * 1676 * @signature void flush(str); 1677 * 1678 * @param[in,out] str The ExternalString to flush. 1679 */ 1680 1681 template < typename TValue, typename TConfig > 1682 inline void 1683 flush(String<TValue, External<TConfig> > &me) 1684 { 1685 //IOREV _doc_ 1686 typedef typename String<TValue, External<TConfig> >::TCache TCache; 1687 typedef typename Iterator<TCache, Standard>::Type TIter; 1688 1689 // write all dirty pages to disk 1690 if (me.file) 1691 { 1692 TIter f = begin(me.cache, Standard()); 1693 TIter fEnd = end(me.cache, Standard()); 1694 1695 for(; f != fEnd ; ++f) 1696 if ((*f).begin) me.flush(*f); 1697 waitForAll(me); 1698 } 1699 } 1700 1701 // cancel all transactions 1702 template < typename TValue, typename TConfig > 1703 inline void 1704 cancel(String<TValue, External<TConfig> > &me) 1705 { 1706 //IOREV _nodoc_ 1707 typedef typename String<TValue, External<TConfig> >::TCache TCache; 1708 typedef typename Iterator<TCache, Standard>::Type TIter; 1709 1710 if (me.file) 1711 { 1712 TIter f = begin(me.cache, Standard()); 1713 TIter fEnd = end(me.cache, Standard()); 1714 1715 for(; f != fEnd ; ++f) 1716 if ((*f).begin) cancel(*f, me.file); 1717 } 1718 } 1719 1720 // cancel all transactions and free allocated pages 1721 template < typename TValue, typename TConfig > 1722 inline void 1723 cancelAndFree(String<TValue, External<TConfig> > &me) 1724 { 1725 //IOREV _nodoc_ 1726 typedef String<TValue, External<TConfig> > TExtString; 1727 typedef typename TExtString::TPageFrame TPageFrame; 1728 typedef typename String<TValue, External<TConfig> >::TCache TCache; 1729 typedef typename Iterator<TCache, Standard>::Type TIter; 1730 1731 TIter f = begin(me.cache, Standard()); 1732 TIter fEnd = end(me.cache, Standard()); 1733 1734 for(; f != fEnd ; ++f) 1735 { 1736 if ((me.file) && (*f).begin) cancel(*f, me.file); 1737 if ((*f).pageNo >= 0) 1738 { 1739 me.pager[(*f).pageNo] = (*f).dataStatus; 1740 (*f).pageNo = TPageFrame::UNINITIALIZED; 1741 } 1742 // std::cerr << *f << std::endl; 1743 if ((*f).begin) 1744 freePage(*f, me.file); 1745 } 1746 } 1747 1748 // flush and free all allocated pages 1749 template < typename TValue, typename TConfig > 1750 inline void 1751 flushAndFree(String<TValue, External<TConfig> > &me) 1752 { 1753 //IOREV _nodoc_ 1754 typedef String<TValue, External<TConfig> > TExtString; 1755 typedef typename TExtString::TPageFrame TPageFrame; 1756 typedef typename TExtString::TCache TCache; 1757 typedef typename Iterator<TCache, Standard>::Type TIter; 1758 1759 flush(me); 1760 1761 TIter f = begin(me.cache, Standard()); 1762 TIter fEnd = end(me.cache, Standard()); 1763 1764 for(; f != fEnd ; ++f) 1765 { 1766 if (f->pageNo >= 0) 1767 { 1768 me.pager[f->pageNo] = f->dataStatus; 1769 f->pageNo = TPageFrame::UNINITIALIZED; 1770 } 1771 // std::cerr << *f << std::endl; 1772 if (f->begin) freePage(*f, me.file); 1773 } 1774 } 1775 //____________________________________________________________________________ 1776 1777 /*! 1778 * @fn ExternalString#open 1779 * @brief Open the ExternalString's underlying file from a path. 1780 * 1781 * @signature bool open(str, fileName[, openMode]); 1782 * 1783 * @param[in,out] str The ExternalString to open. 1784 * @param[in] fileName Path to the file to open. Type: <tt>char const *</tt>. 1785 * @param[in] openMode The open mode. Type: <tt>int</tt>. 1786 * 1787 * @return bool <tt>true</tt> if the operation succeeded and <tt>false</tt> otherwise. 1788 */ 1789 1790 template < typename TValue, typename TConfig > 1791 inline bool 1792 open(String<TValue, External<TConfig> > &me, const char *fileName, int openMode) 1793 { 1794 //IOREV _doc_ 1795 typedef String<TValue, External<TConfig> > TExtString; 1796 typedef typename TExtString::TPageFrame TPageFrame; 1797 1798 me._temporary = false; 1799 if ((me._ownFile = open(me.file, fileName, openMode))) 1800 me.data_size = length(me.file) / sizeof(TValue); 1801 else 1802 me.data_size = 0; 1803 1804 resize(me.pager, enclosingBlocks(me.data_size, 1805 (unsigned)me.PAGESIZE), (me.data_size)? 1806 TPageFrame::ON_DISK: 1807 TPageFrame::UNINITIALIZED); 1808 1809 me.lastDiskPage = me.data_size / me.PAGESIZE; 1810 me.lastDiskPageSize = me.data_size % me.PAGESIZE; 1811 return me._ownFile; 1812 } 1813 1814 template < typename TValue, typename TConfig > 1815 inline bool 1816 open(String<TValue, External<TConfig> > &me, const char *fileName) 1817 { 1818 //IOREV _doc_ 1819 typedef String<TValue, External<TConfig> > TExtString; 1820 typedef typename TExtString::TFile TFile; 1821 1822 return open(me, fileName, DefaultOpenMode<TFile>::VALUE); 1823 } 1824 1825 template < typename TValue, typename TConfig > 1826 inline bool 1827 open(String<TValue, External<TConfig> > &me, typename TConfig::TFile file) 1828 { 1829 //IOREV _doc_ 1830 typedef String<TValue, External<TConfig> > TExtString; 1831 typedef typename TExtString::TPageFrame TPageFrame; 1832 1833 me.file = file; 1834 me._temporary = false; 1835 me._ownFile = false; 1836 if (me.file) 1837 me.data_size = length(me.file) / sizeof(TValue); 1838 else 1839 me.data_size = 0; 1840 1841 resize(me.pager, enclosingBlocks(me.data_size, 1842 (unsigned)me.PAGESIZE), (me.data_size)? 1843 TPageFrame::ON_DISK: 1844 TPageFrame::UNINITIALIZED); 1845 1846 me.lastDiskPage = me.data_size / me.PAGESIZE; 1847 me.lastDiskPageSize = me.data_size % me.PAGESIZE; 1848 return me._file; 1849 } 1850 1851 /*! 1852 * @fn ExternalString#openTemp 1853 * @brief Open an ExternalString using an temporary file. 1854 * 1855 * @signature bool openTemp(str); 1856 * 1857 * @param[in,out] str The ExternalString to open using temporary file. 1858 * 1859 * @return bool <tt>true</tt> if opening succeeded, <tt>false</tt> otherwise. 1860 */ 1861 1862 template < typename TValue, typename TConfig > 1863 inline bool 1864 openTemp(String<TValue, External<TConfig> > &me) 1865 { 1866 //IOREV _doc_ 1867 me._temporary = true; 1868 me.lastDiskPage = 0; 1869 me.lastDiskPageSize = 0; 1870 clear(me.pager); 1871 return me._ownFile = openTemp(me.file); 1872 } 1873 //____________________________________________________________________________ 1874 1875 template < typename TValue, typename TConfig > 1876 inline bool 1877 save(String<TValue, External<TConfig> > const &/*me*/, const char * /*fileName*/, int /*openMode*/) { 1878 //IOREV _nodoc_ shouldn't we flush here? in case of abnormal termination... 1879 // External Strings are persistent, thus there is no need to save them 1880 //ExtStringsDontNeedToBeSaved error; 1881 return true; 1882 } 1883 1884 template < typename TValue, typename TConfig > 1885 inline bool 1886 save(String<TValue, External<TConfig> > const &/*me*/, const char * /*fileName*/) { 1887 //IOREV _nodoc_ shouldn't we flush here? in case of abnormal termination... 1888 // External Strings are persistent, thus there is no need to save them 1889 //ExtStringsDontNeedToBeSaved error; 1890 return true; 1891 } 1892 1893 template < typename TValue, typename TConfig > 1894 inline bool 1895 save(String<TValue, External<TConfig> > const &/*me*/, typename TConfig::TFile /*file*/) { 1896 //IOREV _nodoc_ shouldn't we flush here? in case of abnormal termination... 1897 // External Strings are persistent, thus there is no need to save them 1898 //ExtStringsDontNeedToBeSaved error; 1899 return true; 1900 } 1901 //____________________________________________________________________________ 1902 1903 /*! 1904 * @fn ExternalString#close 1905 * @brief Close the external string. 1906 * 1907 * @signature bool close(str); 1908 * 1909 * @param[in] str The ExternalString to close the file of. 1910 * 1911 * @return bool <tt>true</tt> if the closing succeeded, <tt>false</tt> otherwise. 1912 */ 1913 1914 template < typename TValue, typename TConfig > 1915 inline bool 1916 close(String<TValue, External<TConfig> > &me) 1917 { 1918 //IOREV _doc_ 1919 // close associated file 1920 if (me._temporary) 1921 cancelAndFree(me); 1922 else 1923 flushAndFree(me); 1924 clear(me.pager); 1925 1926 if (me._ownFile) 1927 { 1928 me._ownFile = false; 1929 return close(me.file); 1930 } 1931 else 1932 return true; 1933 } 1934 //____________________________________________________________________________ 1935 template < typename TValue, typename TConfig > 1936 inline typename Size< String<TValue, External<TConfig> > >::Type 1937 length(String<TValue, External<TConfig> > const &me) 1938 { 1939 //IOREV 1940 return me.data_size; 1941 } 1942 1943 template < typename TValue, typename TConfig > 1944 inline typename Size< String<TValue, External<TConfig> > >::Type 1945 capacity(String<TValue, External<TConfig> > const &me) 1946 { 1947 //IOREV 1948 typedef typename Size< String<TValue, External<TConfig> > >::Type TSize; 1949 return (TSize)capacity(me.pager) * (TSize)me.PAGESIZE; 1950 } 1951 //____________________________________________________________________________ 1952 1953 template < typename TValue, typename TConfig, typename TNewSize, typename TExpand > 1954 inline typename Size< String<TValue, External<TConfig> > >::Type 1955 resize( 1956 String<TValue, External<TConfig> > &me, 1957 TNewSize new_length, 1958 Tag<TExpand> expand) 1959 { 1960 //IOREV 1961 typedef String<TValue, External<TConfig> > TString; 1962 typedef typename TString::TPageFrame TPageFrame; 1963 typedef typename Size<TString>::Type TSize; 1964 typedef typename TString::TCache TCache; 1965 typedef typename Iterator<TCache, Standard>::Type TIter; 1966 1967 resize(me.pager, enclosingBlocks(new_length, (unsigned)me.PAGESIZE), TPageFrame::UNINITIALIZED, expand); 1968 if ((TSize)new_length < me.data_size) 1969 { 1970 1971 TIter f = begin(me.cache, Standard()); 1972 TIter fEnd = end(me.cache, Standard()); 1973 1974 // remove pages from cache that are behind our new file end 1975 int new_pages = (new_length + me.PAGESIZE - 1) / me.PAGESIZE; 1976 for(; f != fEnd ; ++f) 1977 if (f->begin && f->pageNo >= new_pages) 1978 { 1979 if (f->status != READY) 1980 cancel(*f, me.file); 1981 clear(*f); 1982 } 1983 1984 // before shrinking the file size 1985 me.lastDiskPage = new_length / me.PAGESIZE; 1986 me.lastDiskPageSize = new_length % me.PAGESIZE; 1987 1988 if (me.file) 1989 resize(me.file, (TSize)new_length * (TSize)sizeof(TValue)); 1990 } 1991 me.data_size = new_length; 1992 return length(me); 1993 } 1994 //____________________________________________________________________________ 1995 1996 template < typename TValue, typename TConfig, typename TSize, typename TExpand > 1997 inline typename Size< String<TValue, External<TConfig> > >::Type 1998 reserve( 1999 String<TValue, External<TConfig> > &me, 2000 TSize new_capacity, 2001 Tag<TExpand> expand) 2002 { 2003 //IOREV 2004 reserve(me.pager, enclosingBlocks(new_capacity, (unsigned)me.PAGESIZE), expand); 2005 return capacity(me); 2006 } 2007 //____________________________________________________________________________ 2008 2009 template < typename TValue, typename TConfig, typename TSpec > 2010 inline typename Iterator<String<TValue, External<TConfig> >, Tag<TSpec> const>::Type 2011 begin(String<TValue, External<TConfig> > &me, Tag<TSpec> const) 2012 { 2013 //IOREV 2014 typedef String<TValue, External<TConfig> > TString; 2015 return typename Iterator<TString, Tag<TSpec> const>::Type (&me, 0); 2016 } 2017 2018 template < typename TValue, typename TConfig, typename TSpec > 2019 inline typename Iterator<String<TValue, External<TConfig> > const, Tag<TSpec> const>::Type 2020 begin(String<TValue, External<TConfig> > const &me, Tag<TSpec> const) 2021 { 2022 //IOREV 2023 typedef String<TValue, External<TConfig> > TString; 2024 return typename Iterator<TString const, Tag<TSpec> const>::Type (const_cast<TString*>(&me), 0); 2025 } 2026 2027 template < typename TValue, typename TConfig, typename TSpec > 2028 inline typename Iterator<String<TValue, External<TConfig> >, Tag<TSpec> const>::Type 2029 end(String<TValue, External<TConfig> > &me, Tag<TSpec> const) 2030 { 2031 //IOREV 2032 typedef String<TValue, External<TConfig> > TString; 2033 return typename Iterator<TString, Tag<TSpec> const>::Type (&me, length(me)); 2034 } 2035 2036 template < typename TValue, typename TConfig, typename TSpec > 2037 inline typename Iterator<String<TValue, External<TConfig> > const, Tag<TSpec> const>::Type 2038 end(String<TValue, External<TConfig> > const &me, Tag<TSpec> const) 2039 { 2040 //IOREV 2041 typedef String<TValue, External<TConfig> > TString; 2042 return typename Iterator<TString const, Tag<TSpec> const>::Type (const_cast<TString*>(&me), length(me)); 2043 } 2044 //____________________________________________________________________________ 2045 2046 template < typename TValue, typename TConfig, typename TPos > 2047 inline typename Reference<String<TValue, External<TConfig> > >::Type 2048 value(String<TValue, External<TConfig> > &me, TPos pos) 2049 { 2050 //IOREV 2051 return me[pos]; 2052 } 2053 2054 template < typename TValue, typename TConfig, typename TPos > 2055 inline typename Reference<String<TValue, External<TConfig> > const>::Type 2056 value(String<TValue, External<TConfig> > const &me, TPos pos) 2057 { 2058 //IOREV 2059 return me[pos]; 2060 } 2061 //____________________________________________________________________________ 2062 2063 template < typename TTargetValue, typename TConfig, typename TValue, typename TExpand > 2064 inline void 2065 appendValue(String<TTargetValue, External<TConfig> > &me, 2066 TValue SEQAN_FORWARD_CARG value, 2067 Tag<TExpand> expand) 2068 { 2069 resize(me, me.data_size + 1, expand); 2070 back(me) = SEQAN_FORWARD(TValue, value); 2071 } 2072 2073 //____________________________________________________________________________ 2074 2075 template < typename TValue, typename TConfig, typename TSource, typename TExpand > 2076 inline void 2077 append(String<TValue, External<TConfig> > &target, 2078 TSource const &source, 2079 Tag<TExpand> expand) 2080 { 2081 //IOREV doc says, resize() my invalidate iterators, therefore it_target might be bogus 2082 typedef String<TValue, External<TConfig> > TTarget; 2083 typedef typename Iterator<TSource const, Standard>::Type ISource; 2084 typedef typename Iterator<TTarget, Standard>::Type ITarget; 2085 2086 ITarget it_target = end(target, Standard()); 2087 2088 resize(target, length(target) + length(source), expand); 2089 2090 ISource it_source = begin(source, Standard()); 2091 ISource it_source_end = end(source, Standard()); 2092 2093 for (; it_source != it_source_end; ++it_source, ++it_target) 2094 *it_target = *it_source; 2095 } 2096 2097 template < typename TValue, typename TConfig, typename TSourceValue, typename TExpand > 2098 inline void 2099 append(String<TValue, External<TConfig> > &target, 2100 TSourceValue * source, 2101 Tag<TExpand> expand) 2102 { 2103 //IOREV doc says, resize() my invalidate iterators, therefore it_target might be bogus 2104 typedef String<TValue, External<TConfig> > TTarget; 2105 typedef typename Iterator<TSourceValue *, Standard>::Type ISource; 2106 typedef typename Iterator<TTarget, Standard>::Type ITarget; 2107 2108 ITarget it_target = end(target, Standard()); 2109 2110 resize(target, length(target) + length(source), expand); 2111 2112 ISource it_source = begin(source, Standard()); 2113 ISource it_source_end = end(source, Standard()); 2114 2115 for (; it_source != it_source_end; ++it_source, ++it_target) 2116 *it_target = *it_source; 2117 } 2118 2119 2120 /* 2121 template < typename TSpec > 2122 std::ostream& operator<<(std::ostream &out, String<char, TSpec > &p) { 2123 2124 typename Iterator< String<char, TSpec > >::Type _cur = begin(p), _end = end(p); 2125 while (_cur != _end) { 2126 out << *_cur; 2127 ++_cur; 2128 } 2129 return out; 2130 } 2131 2132 template < typename TValue, typename TSpec > 2133 std::ostream& operator<<(std::ostream &out, String<TValue, TSpec > &p) { 2134 2135 typename Iterator< String<TValue, TSpec > >::Type _cur = begin(p), _end = end(p); 2136 while (_cur != _end) { 2137 out << *_cur << " "; 2138 ++_cur; 2139 } 2140 return out; 2141 } 2142 */ 2143 //____________________________________________________________________________ 2144 // sequence -> external string 2145 2146 template < typename TValue, 2147 typename TConfig, 2148 typename TSource, 2149 typename TExpand > 2150 inline void assign( 2151 String<TValue, External<TConfig> > &target, 2152 TSource const &source, 2153 Tag<TExpand>) 2154 { 2155 //IOREV 2156 typedef String<TValue, External<TConfig> > TTarget; 2157 typedef typename Iterator<TSource const, Standard>::Type ISource; 2158 typedef typename Iterator<TTarget, Standard>::Type ITarget; 2159 2160 resize(target, length(source)); 2161 2162 ISource it_source = begin(source, Standard()); 2163 ISource it_source_end = end(source, Standard()); 2164 ITarget it_target = begin(target, Standard()); 2165 2166 for (; it_source != it_source_end; ++it_source, ++it_target) 2167 *it_target = *it_source; 2168 } 2169 /* 2170 template < typename TValue, 2171 typename TConfig, 2172 typename TSourceValue, 2173 typename TExpand > 2174 inline void assign( 2175 String<TValue, External<TConfig> > &target, 2176 TSourceValue const * source, 2177 Tag<TExpand>) 2178 { 2179 //IOREV 2180 typedef String<TValue, External<TConfig> > TTarget; 2181 typedef typename Iterator<TSourceValue *, Standard>::Type ISource; 2182 typedef typename Iterator<TTarget, Standard>::Type ITarget; 2183 2184 resize(target, length(source)); 2185 2186 ISource it_source = begin(source, Standard()); 2187 ISource it_source_end = end(source, Standard()); 2188 ITarget it_target = begin(target, Standard()); 2189 2190 for (; it_source != it_source_end; ++it_source, ++it_target) 2191 *it_target = *it_source; 2192 } 2193 */ 2194 //____________________________________________________________________________ 2195 2196 template < typename TValue, typename TConfig > 2197 inline void const * 2198 getObjectId(String<TValue, External<TConfig> > const &me) 2199 { 2200 //IOREV 2201 return &(*begin(me.pager)); 2202 } 2203 2204 } 2205 2206 #endif 2207