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 }