1 /// Recycler for the blockfile. 2 module tagion.dart.Recycler; 3 4 import std.algorithm; 5 import std.container.rbtree : RedBlackTree; 6 import std.format; 7 import std.range; 8 import std.stdio; 9 import std.traits : PointerTarget, isImplicitlyConvertible; 10 import std.typecons : tuple; 11 import tagion.basic.Types : Buffer; 12 import tagion.dart.BlockFile : BlockFile, Index, check; 13 import tagion.hibon.HiBONFile : fread, fwrite; 14 import tagion.hibon.HiBONRecord : HiBONRecord, exclude, label, recordType; 15 16 /** 17 * The segments used for the recycler. 18 * They contain a next pointer that points to the next recycler segment index. 19 * As well as a index for where it is located. 20 */ 21 @safe @recordType("R") 22 struct RecycleSegment { 23 Index next; 24 ulong size; 25 @exclude Index index; 26 Index end() const pure nothrow @nogc { 27 return Index(index + size); 28 } 29 30 mixin HiBONRecord!(q{ 31 @disable this(); 32 this(const Index index, const ulong size, Index next = Index.init) pure nothrow { 33 this.index = index; 34 this.size = size; 35 this.next = next; 36 } 37 this(BlockFile blockfile, const Index _index) 38 in (_index != Index.init) 39 do 40 { 41 blockfile.seek(_index); 42 const doc = blockfile.file.fread(); 43 check(RecycleSegment.isRecord(doc), "The loaded segment was not of type segment doc"); 44 next = doc[GetLabel!(next).name].get!Index; 45 size = doc[GetLabel!(size).name].get!ulong; 46 index = _index; 47 48 } 49 this(const(Document) doc, const(Index) _index) 50 in (_index != Index.init) 51 do 52 { 53 index = Index(_index); 54 this(doc); 55 56 } 57 }); 58 59 /// We never want to create a segment with a size smaller than zero. 60 invariant { 61 assert(size > 0); 62 } 63 /// We never want to create a index at Index.init. 64 invariant { 65 assert(index != Index.init, "RecycleSegment cannot be inserted at index 0"); 66 } 67 } 68 69 /// Indices in the recycler: sorted by index 70 alias Indices = RedBlackTree!(RecycleSegment*, (a, b) => a.index < b.index); // RecycleSegment: sorted by size. 71 72 /** 73 * Used for disposing and claiming segments from the blockfile. 74 * Therefore responsible for keeping track of unused segments. 75 * and making sure these are used so the file does not continue. 76 * growing. 77 */ 78 @safe 79 struct Recycler { 80 /** 81 * Checks if the recycler has overlapping segments. 82 */ 83 invariant { 84 assert(noOverlaps, "Recycle segments has overlaps"); 85 } 86 /** 87 * Checks if the indicies and segments are the same length; 88 */ 89 invariant { 90 assert(indices.length == segments.length); 91 } 92 93 protected { 94 BlockFile owner; /// The blockfile owner 95 Indices indices; /// Indices that are stored in the blockfile. 96 RecycleSegment*[] segments; /// The other way to sort. Sorted by segment size therefore allowing overlaps. 97 RecycleSegment*[] to_be_recycled; /// RecycleSegments that are disposed and need to be added to the recycler. 98 } 99 @disable this(); 100 this(BlockFile owner) pure nothrow 101 in (owner !is null) 102 103 do { 104 this.owner = owner; 105 indices = new Indices; 106 } 107 /** 108 * Function to sort the segments by their size. It returns a assumeSorted of the segments. 109 */ 110 protected auto sortedRecycleSegments() { 111 // check if the segments are already sorted. If not then sort. 112 if (!segments.isSorted!((a, b) => a.size < b.size)) { 113 segments.sort!((a, b) => a.size < b.size); 114 } 115 return assumeSorted!((a, b) => a.size < b.size)(segments); 116 } 117 /** 118 * Inserts a range of segments into the recycler. 119 * Params: 120 * segment_range = Range of segments. Must be ElementType = RecycleSegment* 121 */ 122 protected void insert(R)(R segment_range) 123 if (isInputRange!R && isImplicitlyConvertible!(ElementType!R, RecycleSegment*)) { 124 indices.stableInsert(segment_range); 125 segments ~= segment_range; 126 } 127 /** 128 * Insert a single segment into the recycler. 129 * Params: 130 * segment = segment to be inserted. 131 */ 132 protected void insert(RecycleSegment* segment) { 133 indices.insert(segment); 134 segments ~= segment; 135 } 136 /** 137 * Removes a segment from the recycler. 138 * Params: 139 * segment = segment to be removed 140 */ 141 protected void remove(RecycleSegment* segment) { 142 auto remove_segment = indices.equalRange(segment).front; 143 144 indices.removeKey(remove_segment); 145 segments = segments.remove(segments.countUntil(remove_segment)); 146 } 147 /** 148 * Recycles the segments. Goes over the list of recycle_segments. 149 * First it takes the lowerbound. If there is a element in the 150 * lowerbound, the index of the current segment is changed to the one 151 * of the lowerbound.back and the `lower_range.back` is removed. 152 * The same step is used for the upperbound using the front of the elements. 153 * We go over all the new segments that needs to be recycled. 154 * First we get `lowerBound` in the `indices`. The `indices` are sorted by 155 * index meaning we get all sgements by indexes as a range 156 * that are smaller or equal to our segment. If the segments connext 157 * we add remove it and create a new one. The same procedure is used for 158 * the upperrange. 159 * 160 * Params: 161 * recycle_segments = newly disposed segments 162 */ 163 void recycle(RecycleSegment*[] recycle_segments) { 164 165 foreach (insert_segment; recycle_segments) { 166 auto lower_range = indices.lowerBound(insert_segment); 167 if (!lower_range.empty && lower_range.back.end == insert_segment.index) { 168 169 insert_segment.index = lower_range.back.index; 170 insert_segment.size = lower_range.back.size + insert_segment.size; 171 // remove the lowerrange segment since we have created a new segment 172 // that incorporates this segment. 173 remove(lower_range.back); 174 } 175 176 auto upper_range = indices.upperBound(insert_segment); 177 if (!upper_range.empty && upper_range.front.index == insert_segment.end) { 178 insert_segment.size = upper_range.front.size + insert_segment.size; 179 remove(upper_range.front); 180 } 181 // lastly we insert the new segment. 182 insert(insert_segment); 183 184 } 185 } 186 187 /** 188 Returns: true if the segments overlaps in the indices 189 */ 190 private bool noOverlaps() const pure nothrow @nogc { 191 import std.algorithm.iteration : map; 192 import std.algorithm.searching : any; 193 import std.range : slide; 194 195 if (indices.length <= 1) { 196 return true; 197 } 198 /// Check a pair of segments overlaps 199 static bool overlaps(R)(ref R pair) pure nothrow @nogc { 200 const prev_end = pair.front.end; 201 pair.popFront; 202 const current_index = pair.front 203 .index; 204 return prev_end > current_index; 205 } 206 207 return !indices[] 208 .slide(2) 209 .map!(slice => overlaps(slice)) 210 .any; 211 } 212 213 const(ulong) length() const pure nothrow @nogc { 214 return indices.length; 215 216 } 217 /** 218 * Dumps the segments in the recycler. 219 */ 220 void dump(File fout = stdout) { 221 222 if (indices.empty) { 223 fout.writefln("indices empty"); 224 return; 225 } 226 227 foreach (segment; indices) { 228 fout.writef("INDEX: %s |", segment 229 .index); 230 fout.writef("END: %s |", segment 231 .end); 232 fout.writefln("NEXT: %s ", segment.next); 233 } 234 } 235 /** 236 * Dumps the segments in the to_be_recycled array. 237 */ 238 void dumpToBeRecycled(File fout = stdout) { 239 import std.stdio; 240 241 if (to_be_recycled.empty) { 242 fout.writefln("indices empty"); 243 return; 244 } 245 246 foreach (segment; to_be_recycled) { 247 fout.writef("INDEX: %s |", segment 248 .index); 249 fout.writef("END: %s |", segment 250 .end); 251 fout.writefln("NEXT: %s ", segment.next); 252 } 253 } 254 255 /** 256 * Reads an element from the blockfile. 257 * Params: 258 * index = 259 */ 260 void read(Index index) { 261 // First we reset the indices and segments 262 indices = new Indices; 263 segments = null; 264 // If the index is Index(0) we return. 265 if (index == Index(0)) { 266 return; 267 } 268 // The last element points to a Index.init. 269 // Therefore we continue until we reach this. 270 while (index != Index.init) { 271 auto add_segment = new RecycleSegment(owner, index); 272 insert(add_segment); 273 index = add_segment.next; 274 } 275 } 276 277 /** 278 * Writes the data to the file. First it calls recycler with the to_be_recycled. 279 * Afterwards it goes through and updates the pointer chain. 280 * Returns: the index of the first recycler index. 281 */ 282 Index write() nothrow { 283 assumeWontThrow(recycle(to_be_recycled[])); 284 to_be_recycled = null; 285 286 if (indices.empty) { 287 return Index.init; 288 } 289 290 Index next; 291 bool first = true; 292 foreach_reverse (segment; indices) { 293 if (segment.next != next || first) { 294 segment.next = next; 295 assumeWontThrow(owner.seek(segment.index)); 296 assumeWontThrow(owner.file.fwrite(*segment)); 297 first = false; 298 } 299 next = segment.index; 300 } 301 302 return indices[].front.index; 303 } 304 305 /** 306 * Claims a free segment. Priority is first to use segments already in the disposed list 307 * from to_be_recycled. Next is to use a element in the recycler indices. 308 * Therefore removing a segment from the recycler. 309 * Secondly if no available segments then it appends a new segment to the blockfile and changes 310 * the owners last block index. 311 * Params: 312 * segment_size = in number of blocks. 313 * Returns: 314 * Index pointer of a free segment 315 */ 316 const(Index) claim(const ulong segment_size) nothrow 317 in (segment_size > 0) 318 319 out (result) { 320 assert(result != Index.init); 321 322 } 323 do { 324 try { 325 // First we check the to_be_recycled. 326 auto seg_index = to_be_recycled.countUntil!(seg => seg.size == segment_size); 327 if (seg_index >= 0) { 328 scope (exit) { 329 to_be_recycled = to_be_recycled.remove(seg_index); 330 } 331 return to_be_recycled[seg_index].index; 332 } 333 334 auto sorted_segments = sortedRecycleSegments(); 335 auto search_segment = new RecycleSegment(Index.max, segment_size); 336 337 auto equal_range = sorted_segments.equalRange(search_segment); 338 339 if (!equal_range.empty) { 340 // there is a element equal. 341 const index = equal_range.front.index; 342 remove(equal_range.front); 343 return index; 344 } 345 346 auto upper_range = sorted_segments.upperBound(search_segment); 347 if (!upper_range.empty) { 348 const index = upper_range.front.index; 349 auto add_segment = new RecycleSegment(Index(index + segment_size), upper_range.front.size - segment_size); 350 351 remove(upper_range.front); 352 353 insert(add_segment); 354 return index; 355 } 356 } 357 catch (Exception e) { 358 assert(0, e.msg); 359 } 360 361 scope (success) { 362 owner._last_block_index = Index(owner._last_block_index + segment_size); 363 } 364 365 return owner._last_block_index; 366 367 } 368 /** 369 * Disposes a used segment. This means adding a NEW segment to the recycler. 370 * Params: 371 * index = index to the block 372 * segment_size = in number of blocks. 373 */ 374 void dispose(const(Index) index, const ulong segment_size) nothrow { 375 // If the index is 0 then it is because we have returned a Leave.init. 376 // This should not be added to the recycler. 377 if (index == 0) { 378 return; 379 } 380 381 auto seg = new RecycleSegment(index, segment_size); 382 // The segment should not already be in the list of the to_be_recycled. 383 assert(!(to_be_recycled.canFind(seg)), assumeWontThrow( 384 format("segment already in dispose list index: %s", index))); 385 to_be_recycled ~= seg; 386 } 387 388 } 389 390 version (unittest) { 391 import std.algorithm.iteration : map; 392 import std.range : iota; 393 import tagion.basic.Types : FileExtension; 394 import tagion.basic.basic : forceRemove; 395 import tagion.dart.BlockFile; 396 397 enum SMALL_BLOCK_SIZE = 0x40; 398 } 399 400 import std.exception; 401 402 @safe 403 unittest { 404 // remove test 405 immutable filename = fileId("recycle").fullpath; 406 BlockFile.create(filename, "recycle.unittest", SMALL_BLOCK_SIZE); 407 auto blockfile = BlockFile(filename); 408 scope (exit) { 409 blockfile.close; 410 } 411 auto recycler = Recycler(blockfile); 412 413 RecycleSegment*[] dispose_segments = [ 414 new RecycleSegment(Index(1UL), 5), 415 new RecycleSegment(Index(6UL), 5), 416 new RecycleSegment(Index(17UL), 5), 417 ]; 418 419 // add the segments with the recycler function. 420 recycler.recycle(dispose_segments); 421 // recycler.dump(); 422 423 // writefln("####"); 424 425 const(Index) claim_index = recycler.claim(5); 426 assert(claim_index == Index(17UL)); 427 assert(recycler.indices.length == 1); 428 assert(recycler.segments.length == 1); 429 430 auto seg = recycler.indices.front; 431 assert(seg.index == Index(1UL)); 432 assert(seg.end == Index(seg.index + seg.size)); 433 434 } 435 436 @safe 437 unittest { 438 // add extra test 439 immutable filename = fileId("recycle").fullpath; 440 filename.forceRemove; 441 BlockFile.create(filename, "recycle.unittest", SMALL_BLOCK_SIZE); 442 auto blockfile = BlockFile( 443 filename); 444 scope (exit) { 445 blockfile.close; 446 } 447 auto recycler = Recycler( 448 blockfile); 449 450 RecycleSegment*[] dispose_segments = [ 451 new RecycleSegment(Index(1UL), 5), 452 new RecycleSegment(Index(10UL), 5), 453 new RecycleSegment(Index(17UL), 5), 454 ]; 455 456 recycler.recycle(dispose_segments); 457 recycler.write(); 458 459 RecycleSegment*[] extra_segments = [ 460 new RecycleSegment(Index(6UL), 2), 461 new RecycleSegment(Index(25UL), 6), 462 new RecycleSegment(Index(22UL), 3), 463 ]; 464 465 recycler.recycle(extra_segments); 466 recycler.write(); 467 468 RecycleSegment*[] expected_segments = [ 469 new RecycleSegment(Index(1UL), 8), 470 new RecycleSegment(Index(10UL), 5), 471 new RecycleSegment(Index(17UL), 31 - 17), 472 ]; 473 Indices expected_indices = new Indices(expected_segments); 474 475 assert(expected_indices.length == recycler.indices.length, "Got other indices than expected"); 476 (() @trusted { assert(expected_indices.opEquals( 477 recycler.indices), "elements should be the same"); }()); 478 } 479 480 @safe 481 unittest { 482 // middle add segment 483 immutable filename = fileId( 484 "recycle").fullpath; 485 filename.forceRemove; 486 BlockFile.create(filename, "recycle.unittest", SMALL_BLOCK_SIZE); 487 auto blockfile = BlockFile( 488 filename); 489 scope (exit) { 490 blockfile.close; 491 } 492 auto recycler = Recycler( 493 blockfile); 494 495 RecycleSegment*[] dispose_segments = [ 496 new RecycleSegment(Index(1UL), 5), 497 new RecycleSegment(Index(10UL), 5), 498 ]; 499 500 recycler.recycle(dispose_segments); 501 // recycler.dump(); 502 503 RecycleSegment*[] remove_segments = [ 504 new RecycleSegment(Index(6UL), 4), 505 ]; 506 507 recycler.recycle(remove_segments); 508 // recycler.dump(); 509 510 assert(recycler.indices.length == 1, "should only be one segment after middle insertion"); 511 assert(recycler.indices.front.index == Index(1UL) && recycler.indices.front 512 .end == Index(15UL), "Middle insertion not valid"); 513 } 514 515 unittest { 516 // empty lowerrange connecting 517 immutable filename = fileId( 518 "recycle").fullpath; 519 filename.forceRemove; 520 521 BlockFile.create(filename, "recycle.unittest", SMALL_BLOCK_SIZE); 522 auto blockfile = BlockFile( 523 filename); 524 scope (exit) { 525 blockfile.close; 526 } 527 auto recycler = Recycler( 528 blockfile); 529 530 RecycleSegment*[] add_indices; 531 add_indices = 532 [ 533 new RecycleSegment(Index(10UL), 5) 534 ]; 535 recycler.recycle(add_indices); 536 // recycler.dump; 537 add_indices = 538 [ 539 new RecycleSegment(Index(2UL), 8) 540 ]; 541 recycler.recycle(add_indices); 542 543 assert(recycler.indices.length == 1, "should have merged segments"); 544 assert(recycler.indices.front.index == Index(2UL), "Index not correct"); 545 assert(recycler.indices.front.end == Index(15UL)); 546 547 // upperrange empty connecting 548 add_indices = 549 [ 550 new RecycleSegment(Index(15UL), 5) 551 ]; 552 recycler.recycle(add_indices); 553 assert(recycler.indices.length == 1, "should have merged segments"); 554 assert(recycler.indices.front.index == Index( 555 2UL)); 556 assert( 557 recycler.indices.front.end == Index( 558 20UL)); 559 // recycler.dump; 560 } 561 562 unittest { 563 // empty lowerrange NOT connecting 564 immutable filename = fileId( 565 "recycle").fullpath; 566 filename.forceRemove; 567 568 BlockFile.create(filename, "recycle.unittest", SMALL_BLOCK_SIZE); 569 auto blockfile = BlockFile( 570 filename); 571 scope (exit) { 572 blockfile.close; 573 } 574 auto recycler = Recycler( 575 blockfile); 576 RecycleSegment*[] add_indices; 577 add_indices = 578 [ 579 new RecycleSegment(Index(10UL), 5) 580 ]; 581 recycler.recycle(add_indices); 582 // recycler.dump; 583 add_indices = 584 [ 585 new RecycleSegment(Index(2UL), 5) 586 ]; 587 recycler.recycle( 588 add_indices); 589 590 assert(recycler.indices.length == 2, "should NOT have merged types"); 591 assert(recycler.indices.front.index == Index( 592 2UL), "Index not correct"); 593 // recycler.dump 594 595 // upper range NOT connecting 596 add_indices = 597 [ 598 new RecycleSegment(Index(25UL), 5) 599 ]; 600 recycler.recycle( 601 add_indices[]); 602 assert(recycler.indices.length == 3, "Should not have merged"); 603 assert(recycler.indices.back.index == Index( 604 25UL), "Should not have merged"); 605 606 } 607 608 unittest { 609 // NOT empty upperrange and lowerrange connecting 610 // empty lowerrange connecting 611 immutable filename = fileId( 612 "recycle").fullpath; 613 filename.forceRemove; 614 615 BlockFile.create(filename, "recycle.unittest", SMALL_BLOCK_SIZE); 616 auto blockfile = BlockFile( 617 filename); 618 scope (exit) { 619 blockfile.close; 620 } 621 auto recycler = Recycler( 622 blockfile); 623 624 RecycleSegment*[] add_indices = 625 [ 626 new RecycleSegment(Index(10UL), 5), 627 new RecycleSegment(Index(1UL), 1) 628 ]; 629 recycler.recycle(add_indices); 630 // recycler.dump; 631 add_indices = 632 [ 633 new RecycleSegment(Index(5UL), 5) 634 ]; 635 recycler.recycle(add_indices); 636 // recycler.dump; 637 assert(recycler.indices.length == 2, "should have merged segments"); 638 639 // upperrange not empty connecting 640 add_indices = 641 [ 642 new RecycleSegment(Index(25UL), 5) 643 ]; 644 recycler.recycle(add_indices); 645 add_indices = 646 [ 647 new RecycleSegment(Index(17UL), 2) 648 ]; 649 recycler.recycle( 650 add_indices); 651 assert( 652 recycler.indices.length == 4); 653 } 654 655 unittest { 656 immutable filename = fileId( 657 "recycle").fullpath; 658 filename.forceRemove; 659 660 BlockFile.create(filename, "recycle.unittest", SMALL_BLOCK_SIZE); 661 auto blockfile = BlockFile( 662 filename); 663 scope (exit) { 664 blockfile.close; 665 } 666 auto recycler = Recycler( 667 blockfile); 668 669 RecycleSegment*[] add_indices = 670 [ 671 new RecycleSegment(Index(10UL), 5), 672 ]; 673 recycler.recycle(add_indices); 674 675 recycler.claim(5); 676 assert(recycler.indices.length == 0); 677 } 678 679 unittest { 680 // test the full recycler flow. 681 immutable filename = fileId("recycle").fullpath; 682 filename.forceRemove; 683 684 BlockFile.create(filename, "recycle.unittest", SMALL_BLOCK_SIZE); 685 auto blockfile = BlockFile(filename); 686 auto recycler = Recycler(blockfile); 687 scope (exit) { 688 blockfile.close; 689 } 690 // add some segments 691 recycler.dispose(Index(1UL), 5); 692 recycler.dispose(Index(6UL), 5); 693 recycler.dispose(Index(25UL), 10); 694 assert(recycler.to_be_recycled.length == 3, "all elements not added to recycler"); 695 696 const(Index) begin = recycler.write(); 697 // writefln("BEGIN INDEX: %s", begin); 698 // recycler.dump(); 699 assert(recycler.to_be_recycled.empty, "should be empty after being recycled"); 700 assert(begin == Index(1UL), "should be 1UL"); 701 702 RecycleSegment*[] expected_segments = [ 703 new RecycleSegment(Index(1UL), 11, Index(25UL)), 704 new RecycleSegment(Index(25UL), 10, Index.init), 705 ]; 706 Indices expected_indices = new Indices(expected_segments); 707 assert(expected_indices == recycler.indices); 708 709 } 710 711 version (unittest) { 712 @safe @recordType("D") 713 static struct Data { 714 715 string text; 716 717 mixin HiBONRecord!(q{ 718 this(string text) { 719 this.text = text; 720 } 721 }); 722 } 723 724 } 725 @safe 726 unittest { 727 { 728 // try to read / load indices. 729 immutable filename = fileId("recycle").fullpath; 730 filename.forceRemove; 731 732 BlockFile.create(filename, "recycle.unittest", SMALL_BLOCK_SIZE); 733 auto blockfile = BlockFile(filename); 734 // auto recycler = Recycler(blockfile); 735 scope (exit) { 736 blockfile.close; 737 } 738 // add some segments 739 740 Data[] datas = [ 741 Data("abc"), 742 Data("1234"), 743 Data("wowo"), 744 Data("hugo"), 745 ]; 746 747 foreach (data; datas) { 748 const index = blockfile.save(data).index; 749 // writefln("block index = %s", index); 750 } 751 blockfile.store(); 752 assert(blockfile.recycler.indices.length == 0, "since we only added blocks to empty recycler nothing should be in recycler"); 753 assert(blockfile.recycler.to_be_recycled.length == 0, "to be recycled should be empty"); 754 const doc = blockfile.load(Index(2)); 755 // writefln("document: %s", doc["text"].get!string); 756 assert(doc["text"].get!string == "1234"); 757 758 blockfile.dispose(Index(2)); 759 blockfile.dispose(Index(3)); 760 761 // writefln("before recycleDump"); 762 // blockfile.recycleDump; 763 blockfile.store(); 764 // writefln("after recycleDump"); 765 // blockfile.recycleDump; 766 // writefln("entire blockfile dump"); 767 // blockfile.dump; 768 769 assert(blockfile.recycler.to_be_recycled.length == 0); 770 // the reason why this becomes one is because the middle gap is filled with the recycler and statistic block. 771 // |D index(1) size(1)|S index(2) size(1)|S index(3) size(1)|D index(4) size(1)|R index(5) size(2)|M index(7) size(1)| 772 773 assert(blockfile.recycler.indices.length == 1, "should contain one recycler segment for the new statistic blocks. "); 774 775 blockfile.close(); 776 blockfile = BlockFile(filename); 777 assert(blockfile.recycler.indices.length == 1, "should be the same after loading"); 778 779 // writeln("recycle dump"); 780 // blockfile.recycler.dump; 781 782 // close and open blockfile again. 783 } 784 785 } 786 787 @safe 788 unittest { 789 /// saving to empty an empty blockfile. 790 // try to read / load indices. 791 immutable filename = fileId("recycle").fullpath; 792 filename.forceRemove; 793 794 BlockFile.create(filename, "recycle.unittest", SMALL_BLOCK_SIZE); 795 auto blockfile = BlockFile(filename); 796 // auto recycler = Recycler(blockfile); 797 scope (exit) { 798 blockfile.close; 799 } 800 801 Data[] datas = [ 802 Data("abc"), 803 Data("1234"), 804 Data("wowo"), 805 Data("hugo"), 806 ]; 807 808 foreach (data; datas) { 809 blockfile.save(data); 810 } 811 812 blockfile.store(); 813 /// No elements should have been added to the recycler. 814 assert(blockfile.recycler.indices.length == 0); 815 816 } 817 818 @safe 819 unittest { 820 immutable filename = fileId("recycle").fullpath; 821 filename.forceRemove; 822 823 BlockFile.create(filename, "recycle.unittest", SMALL_BLOCK_SIZE); 824 auto blockfile = BlockFile(filename); 825 scope (exit) { 826 blockfile.close; 827 } 828 auto recycler = Recycler(blockfile); 829 830 RecycleSegment*[] dispose_segments = [ 831 new RecycleSegment(Index(1UL), 5), 832 new RecycleSegment(Index(10UL), 5), 833 new RecycleSegment(Index(17UL), 5), 834 new RecycleSegment(Index(25UL), 5), 835 ]; 836 837 recycler.insert(dispose_segments[]); 838 assert(recycler.indices.length == 4); 839 assert(recycler.segments.length == 4); 840 841 auto remove_segment = new RecycleSegment(Index(17UL), 5); 842 843 recycler.remove(remove_segment); 844 845 assert(recycler.indices.length == 3); 846 assert(recycler.segments.length == 3); 847 848 RecycleSegment*[] segs = [ 849 new RecycleSegment(Index(1UL), 5), 850 new RecycleSegment(Index(10UL), 5), 851 // new RecycleSegment(Index(17UL), 5, Type.NONE), // This is the one that should be removed 852 new RecycleSegment(Index(25UL), 5), 853 ]; 854 855 // recycler.indices[].array 856 // .sort!((a, b) => a < b) 857 // .each!writeln; 858 859 // recycler.segments[].array 860 // .sort!((a, b) => a < b) 861 // .each!writeln; 862 863 assert(equal(recycler.indices[].array.sort!((a, b) => a < b), recycler.segments[].array.sort!((a, b) => a < b))); 864 865 } 866 867 @safe 868 unittest { 869 // save claim save on same segment. 870 immutable filename = fileId("recycle").fullpath; 871 filename.forceRemove; 872 873 BlockFile.create(filename, "recycle.unittest", SMALL_BLOCK_SIZE); 874 auto blockfile = BlockFile(filename); 875 scope (exit) { 876 blockfile.close; 877 } 878 879 const data = Data("abc"); 880 const index = blockfile.save(data).index; 881 blockfile.store(); 882 // blockfile.dump; 883 assert(blockfile.recycler.indices.length == 0, "Should be empty"); 884 885 blockfile.dispose(index); 886 blockfile.save(data); 887 blockfile.store(); 888 // blockfile.dump; 889 890 } 891 892 @safe 893 unittest { 894 // pseudo random add remove blocks. 895 immutable filename = fileId("recycle").fullpath; 896 filename.forceRemove; 897 898 BlockFile.create(filename, "recycle.unittest", SMALL_BLOCK_SIZE); 899 auto blockfile = BlockFile(filename); 900 scope (exit) { 901 blockfile.close; 902 } 903 904 import std.random; 905 906 auto rnd = Random(1234); 907 const number_of_elems = 100; 908 const to_be_removed = 90; 909 bool[Index] used; 910 911 Data[] datas; 912 foreach (i; 0 .. number_of_elems) { 913 const number_of_chars = uniform(2, 1000, rnd); 914 datas ~= Data(repeat('x', number_of_chars).array); 915 } 916 917 Index[] data_indexes; 918 foreach (data; datas) { 919 const data_idx = blockfile.save(data).index; 920 assert(!(data_idx in used), "segment already recycled"); 921 used[data_idx] = true; 922 data_indexes ~= data_idx; 923 924 } 925 blockfile.store; 926 927 auto sample = randomSample(data_indexes[], to_be_removed).array; 928 929 foreach (remove_index; sample) { 930 blockfile.dispose(remove_index); 931 } 932 933 blockfile.store; 934 // blockfile.recycleStatisticDump; 935 blockfile.close; 936 // writefln("dump after"); 937 // blockfile.dump; 938 939 } 940 941 @safe 942 unittest { 943 // blocksegment range test. 944 immutable filename = fileId("recycle").fullpath; 945 filename.forceRemove; 946 947 BlockFile.create(filename, "recycle.unittest", SMALL_BLOCK_SIZE); 948 auto blockfile = BlockFile(filename); 949 scope (exit) { 950 blockfile.close; 951 } 952 953 Data[] datas = [ 954 Data("abc"), 955 Data("1234"), 956 Data("wowo"), 957 Data("hugo"), 958 ]; 959 960 foreach (data; datas) { 961 blockfile.save(data); 962 } 963 blockfile.store; 964 965 import std.file; 966 967 auto fout = File(deleteme, "w"); 968 scope (exit) { 969 fout.close; 970 deleteme.remove; 971 } 972 973 blockfile.dump(segments_per_line : 6, fout: 974 fout); 975 blockfile.recycleDump(fout); 976 blockfile.statisticDump(fout); 977 blockfile.recycleStatisticDump(fout); 978 979 auto block_segment_range = blockfile.opSlice(); 980 assert(block_segment_range.walkLength == 7, "should contain 2 statistic, 1 master and 4 archives"); 981 982 foreach (i; 0 .. datas.length) { 983 assert(block_segment_range.front.type == "D"); 984 block_segment_range.popFront; 985 } 986 assert(block_segment_range.walkLength == 3); 987 }