Unofficial Dub Package Documentation 
1 /** Bitarray.
2  */
3 module nxt.bitarray;
4 
5 @safe:
6 
7 /** Array of bits.
8  *
9  * Like `std.bitmanip.BitArray` but @safe pure nothrow @nogc.
10  *
11  * Set `blockAlignedLength` to true if `this.length` is always a multiple of
12  * `Block.size`.
13  *
14  * TODO use `Flag` instead, or wrap in `BlockAlignedBitArray` where this class
15  * is made private _BitArray and alias BitArray = _BitArray!(true).
16  *
17  * TODO support append bit via `pushBack(bool)`.
18  */
19 struct BitArray(bool blockAlignedLength = false,
20                 alias Allocator = null) // TODO use Allocator
21 {
22     import core.bitop : bt, bts, btr;
23     import nxt.bitarray_algorithm;
24 
25 @safe pure nothrow @nogc:
26 
27     /** Construct with `length` number of zero bits. */
28     static typeof(this) withLength(size_t length)
29     {
30         return typeof(this)(length);
31     }
32 
33     /** Construct with `length` number of zero bits stored in `blocks`. */
34     private static typeof(this) withLengthAndBlocks(size_t length,
35                                                     const scope Block[] blocks)
36     {
37         return typeof(return)(length, blocks);
38     }
39 
40     /** Helper constructor for `length` number of bits. */
41     private this(size_t length) @trusted
42     {
43         static if (blockAlignedLength)
44         {
45             assert(length % bitsPerBlock == 0,
46                    "Parameter `length` is not a multiple `Block` bit size " ~ bitsPerBlock.stringof);
47             _blockCount = length / bitsPerBlock; // number of whole blocks
48         }
49         else
50         {
51             _blockCount = (length + bitsPerBlock-1) / bitsPerBlock;
52             _length = length;
53         }
54         _blockPtr = cast(Block*)fakePureCalloc(bitsPerBlock, _blockCount); // TODO use `Allocator`
55     }
56 
57     /** Helper constructor. */
58     private this(size_t length,
59                  const scope Block[] blocks) @trusted
60     {
61         _blockCount = blocks.length;
62         _blockPtr = cast(Block*)fakePureMalloc(bitsPerBlock * _blockCount); // TODO use `Allocator`
63         _blocks[] = blocks; // copy block array
64         static if (!blockAlignedLength)
65         {
66             _length = length;
67         }
68     }
69 
70     /// Destroy.
71     ~this() @nogc
72     {
73         release();
74     }
75 
76     /// Explicit copying (duplicate).
77     typeof(this) dup()
78     {
79         return typeof(this).withLengthAndBlocks(_length, _blocks);
80     }
81 
82     /// Empty.
83     void reset()
84     {
85         release();
86         resetInternalData();
87     }
88     alias clear = reset;
89 
90     /// Release internal store.
91     private void release() @trusted @nogc
92     {
93         fakePureFree(_blockPtr);
94     }
95 
96     /// Reset internal data.
97     private void resetInternalData()
98     {
99         _blockPtr = null;
100         _blockCount = 0;
101         static if (!blockAlignedLength)
102         {
103             _length = 0;
104         }
105     }
106 
107     /// Check if empty.
108     bool empty() const { return _length == 0; }
109 
110     /// Get length.
111     @property size_t length() const { return _length; }
112     alias opDollar = length;    /// ditto
113 
114     /// Get capacity in number of bits.
115     @property size_t capacity() const { return bitsPerBlock*_blockCount; }
116 
117     /** Get the `i`'th bit. */
118     bool opIndex(size_t i) const @trusted
119     {
120         version(D_Coverage) {} else pragma(inline, true);
121         assert(i < length);        // TODO nothrow or not?
122         return cast(bool)bt(_blockPtr, i);
123     }
124 
125     /** Set the `i`'th bit to `value`. */
126     bool opIndexAssign(bool value, size_t i) @trusted
127     {
128         version(D_Coverage) {} else pragma(inline, true);
129         if (value)
130         {
131             bts(_blockPtr, i);
132         }
133         else
134         {
135             btr(_blockPtr, i);
136         }
137         return value;
138     }
139 
140     /** Set all bits to `value` via slice assignment syntax. */
141     ref typeof(this) opSliceAssign(bool value)
142     {
143         if (value)
144         {
145             one();
146         }
147         else
148         {
149             zero();
150         }
151         return this;
152     }
153 
154     /** Clear all bits (to zero). */
155     private void zero()
156     {
157         foreach (ref block; _blocks)
158         {
159             block = Block.min;
160         }
161     }
162 
163     /** Set all bits (to one). */
164     private void one()
165     {
166         foreach (ref block; _blocks)
167         {
168             block = Block.max;
169         }
170     }
171 
172     version(none)               // TODO activate?
173     bool opCast(T : bool)() const
174     {
175         return !this.allZero;
176     }
177 
178     /** Check if `this` has only zeros. */
179     bool allZero()() const @safe pure nothrow @nogc
180     {
181         foreach (const block; _fullBlocks)
182         {
183             if (block != Block.min)
184             {
185                 return false;
186             }
187         }
188         static if (!blockAlignedLength)
189         {
190             if (_restBlockZeroPadded != Block.min)
191             {
192                 return false;
193             }
194         }
195         return true;
196     }
197 
198     /** Check if `this` has only ones. */
199     bool allOne()() const @safe pure nothrow @nogc
200     {
201         foreach (const block; _fullBlocks)
202         {
203             if (block != Block.max)
204             {
205                 return false;
206             }
207         }
208         static if (!blockAlignedLength)
209         {
210             if (_restBlockOnePadded != Block.max)
211             {
212                 return false;
213             }
214         }
215         return true;
216     }
217 
218     /** Get number of bits set (to one). */
219     size_t countOnes()() const  // template-lazy
220     {
221         return nxt.bitarray_algorithm.countOnes!(const(Block)[], blockAlignedLength)(_blocks, length);
222     }
223 
224     /** Get number of bits cleared (to zero). */
225     size_t countZeros()() const  // template-lazy
226     {
227         return length - countOnes;
228     }
229 
230     /** Find index of first set (one) bit or `length` if no bit set.
231      *
232      * Optimized for ones-sparsity.
233      */
234     size_t indexOfFirstOne()() const // template-lazy
235     {
236         return nxt.bitarray_algorithm.indexOfFirstOne!(const(Block)[], blockAlignedLength)(_blocks, length);
237     }
238 
239     /** Find index of first cleared (zero) bit or `length` if no bit cleared.
240      *
241      * Optimized for zeros-sparsity.
242      */
243     size_t indexOfFirstZero()() const // template-lazy
244     {
245         return nxt.bitarray_algorithm.indexOfFirstZero!(const(Block)[], blockAlignedLength)(_blocks, length);
246     }
247 
248     /** Equality, operators == and !=. */
249     bool opEquals(in ref typeof(this) rhs) const @trusted
250     {
251         static if (!blockAlignedLength)
252         {
253             if (length != rhs.length)
254             {
255                 return false;
256             }
257         }
258         if (_fullBlocks != rhs._fullBlocks)
259         {
260             return false;
261         }
262         static if (!blockAlignedLength)
263         {
264             const restBitCount = length % bitsPerBlock;
265             if (restBitCount)
266             {
267                 return _restBlockZeroPadded == rhs._restBlockZeroPadded;
268             }
269         }
270         return true;
271     }
272 
273     /** Only explicit copying via `.dup` for now. */
274     @disable this(this);
275 
276 private:
277 
278     /** Get blocks. */
279     inout(Block)[] _blocks() inout @trusted
280     {
281         return _blockPtr[0 .. _blockCount];
282     }
283 
284     static if (blockAlignedLength)
285     {
286         inout(Block)[] _fullBlocks() inout @trusted
287         {
288             return _blocks;     // all bits of all blocks are used
289         }
290     }
291     else
292     {
293         inout(Block)[] _fullBlocks() inout @trusted
294         {
295             version(D_Coverage) {} else pragma(inline, true);
296             const fullBlockCount = length / bitsPerBlock;
297             return _blocks.ptr[0 .. fullBlockCount];
298         }
299 
300         /** Return rest `Block` with all padding bits set to zero. */
301         Block _restBlockZeroPadded() const @trusted
302         {
303             const restBitCount = length % bitsPerBlock;
304             return _blocks[$-1] & ((1UL << restBitCount) - 1);
305         }
306     }
307 
308     alias Block = size_t;
309     enum bitsPerBlock = 8*Block.sizeof; /// Number of bits per `Block`.
310 
311     /** Number of Block's allocated at `_blockPtr`. */
312     size_t _blockCount;
313 
314     static if (is(Allocator == std.experimental.allocator.gc_allocator.GCAllocator))
315     {
316         Block* _blockPtr;       // GC-allocated store pointer
317     }
318     else
319     {
320         import nxt.gc_traits : NoGc;
321         @NoGc Block* _blockPtr; // non-GC-allocated store pointer
322     }
323 
324     static if (blockAlignedLength)
325     {
326         @property size_t _length() const
327         {
328             return bitsPerBlock * _blockCount;
329         }
330     }
331     else
332     {
333         size_t _length;
334     }
335 }
336 
337 /// Test `_blockCount` and `_fullBlocks.length`.
338 @safe pure nothrow @nogc unittest
339 {
340     static void test(bool blockAlignedLength)()
341     {
342         alias BA = BitArray!(blockAlignedLength);
343 
344         assert(BA.withLength(0)._blockCount == 0);
345         assert(BA.withLength(1)._blockCount == 1);
346 
347         {
348             auto a = BA.withLength(1*BA.bitsPerBlock - 1);
349             assert(a._blockCount == 1);
350             assert(a._fullBlocks.length == 0);
351         }
352 
353         {
354             auto a = BA.withLength(1*BA.bitsPerBlock + 0);
355             assert(a._blockCount == 1);
356             assert(a._fullBlocks.length == 1);
357         }
358 
359         {
360             auto a = BA.withLength(1*BA.bitsPerBlock + 1);
361             assert(a._blockCount == 2);
362             assert(a._fullBlocks.length == 1);
363         }
364 
365         {
366             auto a = BA.withLength(2*BA.bitsPerBlock - 1);
367             assert(a._blockCount == 2);
368             assert(a._fullBlocks.length == 1);
369         }
370 
371         {
372             auto a = BA.withLength(2*BA.bitsPerBlock + 0);
373             assert(a._blockCount == 2);
374             assert(a._fullBlocks.length == 2);
375         }
376 
377         {
378             auto a = BA.withLength(2*BA.bitsPerBlock + 1);
379             assert(a._blockCount == 3);
380             assert(a._fullBlocks.length == 2);
381         }
382     }
383     test!(false)();
384 }
385 
386 /// Test indexing and element assignment.
387 @safe pure nothrow @nogc unittest
388 {
389     static void test(bool blockAlignedLength)(size_t length)
390     {
391         alias BA = BitArray!(blockAlignedLength);
392 
393         auto a = BA.withLength(length);
394 
395         assert(a.length == length);
396         foreach (const i; 0 .. length)
397         {
398             assert(!a[i]);
399         }
400 
401         a[0] = true;
402         assert(a[0]);
403         foreach (const i; 1 .. length)
404         {
405             assert(!a[i]);
406         }
407 
408         assert(!a[1]);
409         a[1] = true;
410         assert(a[1]);
411         a[1] = false;
412         assert(!a[1]);
413     }
414     test!(false)(100);
415     test!(true)(64);
416 }
417 
418 /// Test `countOnes` and `countZeros`.
419 @safe pure nothrow @nogc unittest
420 {
421     static void test(bool blockAlignedLength)()
422     {
423         alias BA = BitArray!(blockAlignedLength);
424 
425         foreach (const n; 1 .. 5*BA.bitsPerBlock)
426         {
427             static if (blockAlignedLength)
428             {
429                 if (n % BA.bitsPerBlock != 0) // if block aligned length
430                 {
431                     continue;
432                 }
433             }
434 
435             auto a = BA.withLength(n);
436 
437             // set bits forwards
438             foreach (const i; 0 .. n)
439             {
440                 assert(a.countOnes == i);
441                 assert(a.countZeros == n - i);
442                 a[i] = true;
443                 assert(a.countOnes == i + 1);
444                 assert(a.countZeros == n - (i + 1));
445             }
446 
447             assert(a.countOnes == n);
448             assert(a.countZeros == 0);
449 
450             auto b = a.dup;
451             assert(b.countOnes == n);
452             assert(b.countZeros == 0);
453 
454             assert(a == b);
455 
456             // clear `a` bits forwards
457             foreach (const i; 0 .. n)
458             {
459                 assert(a.countOnes == n - i);
460                 assert(a.countZeros == i);
461                 a[i] = false;
462                 assert(a.countOnes == n - (i + 1));
463                 assert(a.countZeros == i + 1);
464             }
465 
466             b[] = false;
467             assert(a == b);
468 
469             // set bits backwards
470             foreach (const i; 0 .. n)
471             {
472                 assert(a.countOnes == i);
473                 a[n-1 - i] = true;
474                 assert(a.countOnes == i + 1);
475             }
476 
477             b[] = true;
478             assert(a == b);
479         }
480     }
481     test!(false)();
482     test!(true)();
483 }
484 
485 /// Test emptying (resetting) via `.clear` and explicit copying with `.dup`.
486 @safe pure nothrow @nogc unittest
487 {
488     static void test(bool blockAlignedLength)()
489     {
490         alias BA = BitArray!(blockAlignedLength);
491 
492         static if (blockAlignedLength)
493         {
494             const n = 5 * BA.bitsPerBlock;
495         }
496         else
497         {
498             const n = 5 * BA.bitsPerBlock + 1;
499         }
500         auto a = BA.withLength(n);
501 
502         assert(a.length == n);
503 
504         a.reset();
505         assert(a.length == 0);
506 
507         a = BA.withLength(n);
508         assert(a.length == n);
509 
510         auto b = a.dup;
511         assert(b.length == n);
512 
513         a.reset();
514         assert(a.length == 0);
515     }
516     test!(false)();
517     test!(true)();
518 }
519 
520 /// Test `indexOfFirstOne` for single set ones.
521 @safe pure nothrow @nogc unittest
522 {
523     static void test(bool blockAlignedLength)()
524     {
525         alias BA = BitArray!(blockAlignedLength);
526 
527         static if (blockAlignedLength)
528         {
529             const n = 2 * BA.bitsPerBlock;
530         }
531         else
532         {
533             const n = 2 * BA.bitsPerBlock + 1;
534         }
535         auto a = BA.withLength(n);
536 
537         assert(a.length == n);
538         assert(a.indexOfFirstOne == n); // miss
539 
540         a[0] = true;
541         assert(a.indexOfFirstOne == 0);
542         a[] = false;
543 
544         a[2] = true;
545         assert(a.indexOfFirstOne == 2);
546         a[] = false;
547 
548         a[n/2-1] = true;
549         assert(a.indexOfFirstOne == n/2-1);
550         a[] = false;
551 
552         a[n/2] = true;
553         assert(a.indexOfFirstOne == n/2);
554         a[] = false;
555 
556         a[n/2+1] = true;
557         assert(a.indexOfFirstOne == n/2+1);
558         a[] = false;
559 
560         a[n-1] = true;
561         assert(a.indexOfFirstOne == n-1);
562         a[] = false;
563 
564         assert(a.indexOfFirstOne == n); // miss
565     }
566     test!(false)();
567     test!(true)();
568 }
569 
570 /// Test `indexOfFirstOne` for multi set ones.
571 @safe pure nothrow @nogc unittest
572 {
573     static void test(bool blockAlignedLength)()
574     {
575         alias BA = BitArray!(blockAlignedLength);
576 
577         static if (blockAlignedLength)
578         {
579             const n = 2 * BA.bitsPerBlock;
580         }
581         else
582         {
583             const n = 2 * BA.bitsPerBlock + 1;
584         }
585         auto a = BA.withLength(n);
586 
587         a[0] = true;
588         a[BA.bitsPerBlock/2] = true;
589         a[BA.bitsPerBlock - 1] = true;
590         assert(a.indexOfFirstOne == 0);
591     }
592     test!(false)();
593     test!(true)();
594 }
595 
596 /// Test `indexOfFirstZero` for single set zeros.
597 @safe pure nothrow @nogc unittest
598 {
599     static void test(bool blockAlignedLength)()
600     {
601         alias BA = BitArray!(blockAlignedLength);
602 
603         static if (blockAlignedLength)
604         {
605             const n = 2 * BA.bitsPerBlock;
606         }
607         else
608         {
609             const n = 2 * BA.bitsPerBlock + 1;
610         }
611         auto a = BA.withLength(n);
612 
613         a[] = true;
614 
615         assert(a.length == n);
616         assert(a.indexOfFirstZero == n); // miss
617 
618         a[0] = false;
619         assert(a.indexOfFirstZero == 0);
620         a[0] = true;
621 
622         a[2] = false;
623         assert(a.indexOfFirstZero == 2);
624         a[2] = true;
625 
626         a[n/2-1] = false;
627         assert(a.indexOfFirstZero == n/2-1);
628         a[n/2-1] = true;
629 
630         a[n/2] = false;
631         assert(a.indexOfFirstZero == n/2);
632         a[n/2] = true;
633 
634         a[n/2+1] = false;
635         assert(a.indexOfFirstZero == n/2+1);
636         a[n/2+1] = true;
637 
638         a[n-1] = false;
639         assert(a.indexOfFirstZero == n-1);
640         a[n-1] = true;
641 
642         assert(a.indexOfFirstZero == n); // miss
643     }
644     test!(false)();
645     test!(true)();
646 }
647 
648 @safe pure nothrow @nogc unittest
649 {
650     alias BA = BitArray!(false);
651     static assert(BitArray!(false).sizeof == 3*BA.Block.sizeof); // one extra word for `length`
652     static assert(BitArray!(true).sizeof == 2*BA.Block.sizeof);
653 }
654 
655 /// Test `indexOfFirstZero` for multi set zeros.
656 @safe pure nothrow @nogc unittest
657 {
658     static void test(bool blockAlignedLength)()
659     {
660         alias BA = BitArray!(blockAlignedLength);
661 
662         static if (blockAlignedLength)
663         {
664             const n = 2 * BA.bitsPerBlock;
665         }
666         else
667         {
668             const n = 2 * BA.bitsPerBlock + 1;
669         }
670         auto a = BA.withLength(n);
671 
672         a[] = true;
673 
674         a[0] = false;
675         a[BA.bitsPerBlock/2] = false;
676         a[BA.bitsPerBlock - 1] = false;
677         assert(a.indexOfFirstZero == 0);
678     }
679     test!(false)();
680     test!(true)();
681 }
682 
683 /// Test `indexOfFirstOne` for multi set ones.
684 @safe pure nothrow @nogc unittest
685 {
686     static void test(bool blockAlignedLength)()
687     {
688         alias BA = BitArray!(blockAlignedLength);
689 
690         static if (blockAlignedLength)
691         {
692             const n = 2 * BA.bitsPerBlock;
693         }
694         else
695         {
696             const n = 2 * BA.bitsPerBlock + 1;
697         }
698         auto a = BA.withLength(n);
699 
700         a[] = false;
701 
702         a[0] = true;
703         a[BA.bitsPerBlock/2] = true;
704         a[BA.bitsPerBlock - 1] = true;
705         assert(a.indexOfFirstOne == 0);
706     }
707     test!(false)();
708     test!(true)();
709 }
710 
711 /// Test casting to `bool`.
712 @safe pure nothrow @nogc unittest
713 {
714     static void test(bool blockAlignedLength)()
715     {
716         alias BA = BitArray!(blockAlignedLength);
717 
718         static if (blockAlignedLength)
719         {
720             const n = 2 * BA.bitsPerBlock;
721         }
722         else
723         {
724             const n = 2 * BA.bitsPerBlock + 1;
725         }
726         auto a = BA.withLength(n);
727 
728         assert(a.allZero);
729 
730         a[0] = true;
731         assert(!a.allZero);
732         a[0] = false;
733         assert(a.allZero);
734     }
735     test!(false)();
736 }
737 
738 ///
739 @trusted pure unittest
740 {
741     import std.exception: assertThrown;
742     import core.exception : AssertError;
743     assertThrown!AssertError(BitArray!(true).withLength(1));
744 }
745 
746 // TODO use
747 extern (C) private pure @system @nogc nothrow
748 {
749     pragma(mangle, "malloc") void* fakePureMalloc(size_t);
750     pragma(mangle, "calloc") void* fakePureCalloc(size_t nmemb, size_t size);
751     pragma(mangle, "realloc") void* fakePureRealloc(void* ptr, size_t size);
752     pragma(mangle, "free") void fakePureFree(void* ptr);
753 }

Page generated by adrdox