nxt.bitarray source code

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             _length = 0;
103     }
104 
105     /// Check if empty.
106     bool empty() const { return _length == 0; }
107 
108     /// Get length.
109     @property size_t length() const { return _length; }
110     alias opDollar = length;    /// ditto
111 
112     /// Get capacity in number of bits.
113     @property size_t capacity() const { return bitsPerBlock*_blockCount; }
114 
115     /** Get the `i`'th bit. */
116     bool opIndex(size_t i) const @trusted
117     {
118         version(D_Coverage) {} else pragma(inline, true);
119         assert(i < length);        // TODO: nothrow or not?
120         return cast(bool)bt(_blockPtr, i);
121     }
122 
123     /** Set the `i`'th bit to `value`. */
124     bool opIndexAssign(bool value, size_t i) @trusted
125     {
126         version(D_Coverage) {} else pragma(inline, true);
127         if (value)
128             bts(_blockPtr, i);
129         else
130             btr(_blockPtr, i);
131         return value;
132     }
133 
134     /** Set all bits to `value` via slice assignment syntax. */
135     ref typeof(this) opSliceAssign(bool value)
136     {
137         if (value)
138             one();
139         else
140             zero();
141         return this;
142     }
143 
144     /** Clear all bits (to zero). */
145     private void zero()
146     {
147         foreach (ref block; _blocks)
148             block = Block.min;
149     }
150 
151     /** Set all bits (to one). */
152     private void one()
153     {
154         foreach (ref block; _blocks)
155             block = Block.max;
156     }
157 
158     version(none)               // TODO: activate?
159     bool opCast(T : bool)() const
160     {
161         return !this.allZero;
162     }
163 
164     /** Check if `this` has only zeros. */
165     bool allZero()() const @safe pure nothrow @nogc
166     {
167         foreach (const block; _fullBlocks)
168             if (block != Block.min)
169                 return false;
170         static if (!blockAlignedLength)
171             if (_restBlockZeroPadded != Block.min)
172                 return false;
173         return true;
174     }
175 
176     /** Check if `this` has only ones. */
177     bool allOne()() const @safe pure nothrow @nogc
178     {
179         foreach (const block; _fullBlocks)
180             if (block != Block.max)
181                 return false;
182         static if (!blockAlignedLength)
183             if (_restBlockOnePadded != Block.max)
184                 return false;
185         return true;
186     }
187 
188     /** Get number of bits set (to one). */
189     size_t countOnes()() const  // template-lazy
190     {
191         return nxt.bitarray_algorithm.countOnes!(const(Block)[], blockAlignedLength)(_blocks, length);
192     }
193 
194     /** Get number of bits cleared (to zero). */
195     size_t countZeros()() const  // template-lazy
196     {
197         return length - countOnes;
198     }
199 
200     /** Find index of first set (one) bit or `length` if no bit set.
201      *
202      * Optimized for ones-sparsity.
203      */
204     size_t indexOfFirstOne()() const // template-lazy
205     {
206         return nxt.bitarray_algorithm.indexOfFirstOne!(const(Block)[], blockAlignedLength)(_blocks, length);
207     }
208 
209     /** Find index of first cleared (zero) bit or `length` if no bit cleared.
210      *
211      * Optimized for zeros-sparsity.
212      */
213     size_t indexOfFirstZero()() const // template-lazy
214     {
215         return nxt.bitarray_algorithm.indexOfFirstZero!(const(Block)[], blockAlignedLength)(_blocks, length);
216     }
217 
218     /** Equality, operators == and !=. */
219     bool opEquals(const scope ref typeof(this) rhs) const @trusted // TODO: use `in ref` when it compiles
220     {
221         static if (!blockAlignedLength)
222             if (length != rhs.length)
223                 return false;
224         if (_fullBlocks != rhs._fullBlocks)
225             return false;
226         static if (!blockAlignedLength)
227         {
228             const restBitCount = length % bitsPerBlock;
229             if (restBitCount)
230                 return _restBlockZeroPadded == rhs._restBlockZeroPadded;
231         }
232         return true;
233     }
234 
235     /** Only explicit copying via `.dup` for now. */
236     @disable this(this);
237 
238 private:
239 
240     /** Get blocks. */
241     inout(Block)[] _blocks() inout @trusted
242     {
243         return _blockPtr[0 .. _blockCount];
244     }
245 
246     static if (blockAlignedLength)
247     {
248         inout(Block)[] _fullBlocks() inout @trusted
249         {
250             return _blocks;     // all bits of all blocks are used
251         }
252     }
253     else
254     {
255         inout(Block)[] _fullBlocks() inout @trusted
256         {
257             version(D_Coverage) {} else pragma(inline, true);
258             const fullBlockCount = length / bitsPerBlock;
259             return _blocks.ptr[0 .. fullBlockCount];
260         }
261 
262         /** Return rest `Block` with all padding bits set to zero. */
263         Block _restBlockZeroPadded() const @trusted
264         {
265             const restBitCount = length % bitsPerBlock;
266             return _blocks[$-1] & ((1UL << restBitCount) - 1);
267         }
268     }
269 
270     alias Block = size_t;
271     enum bitsPerBlock = 8*Block.sizeof; /// Number of bits per `Block`.
272 
273     /** Number of Block's allocated at `_blockPtr`. */
274     size_t _blockCount;
275 
276     static if (is(Allocator == std.experimental.allocator.gc_allocator.GCAllocator))
277     {
278         Block* _blockPtr;       // GC-allocated store pointer
279     }
280     else
281     {
282         import nxt.gc_traits : NoGc;
283         @NoGc Block* _blockPtr; // non-GC-allocated store pointer
284     }
285 
286     static if (blockAlignedLength)
287     {
288         @property size_t _length() const
289         {
290             return bitsPerBlock * _blockCount;
291         }
292     }
293     else
294     {
295         size_t _length;
296     }
297 }
298 
299 /// Test `_blockCount` and `_fullBlocks.length`.
300 @safe pure nothrow @nogc unittest
301 {
302     static void test(bool blockAlignedLength)()
303     {
304         alias BA = BitArray!(blockAlignedLength);
305 
306         assert(BA.withLength(0)._blockCount == 0);
307         assert(BA.withLength(1)._blockCount == 1);
308 
309         {
310             auto a = BA.withLength(1*BA.bitsPerBlock - 1);
311             assert(a._blockCount == 1);
312             assert(a._fullBlocks.length == 0);
313         }
314 
315         {
316             auto a = BA.withLength(1*BA.bitsPerBlock + 0);
317             assert(a._blockCount == 1);
318             assert(a._fullBlocks.length == 1);
319         }
320 
321         {
322             auto a = BA.withLength(1*BA.bitsPerBlock + 1);
323             assert(a._blockCount == 2);
324             assert(a._fullBlocks.length == 1);
325         }
326 
327         {
328             auto a = BA.withLength(2*BA.bitsPerBlock - 1);
329             assert(a._blockCount == 2);
330             assert(a._fullBlocks.length == 1);
331         }
332 
333         {
334             auto a = BA.withLength(2*BA.bitsPerBlock + 0);
335             assert(a._blockCount == 2);
336             assert(a._fullBlocks.length == 2);
337         }
338 
339         {
340             auto a = BA.withLength(2*BA.bitsPerBlock + 1);
341             assert(a._blockCount == 3);
342             assert(a._fullBlocks.length == 2);
343         }
344     }
345     test!(false)();
346 }
347 
348 /// Test indexing and element assignment.
349 @safe pure nothrow @nogc unittest
350 {
351     static void test(bool blockAlignedLength)(size_t length)
352     {
353         alias BA = BitArray!(blockAlignedLength);
354 
355         auto a = BA.withLength(length);
356 
357         assert(a.length == length);
358         foreach (const i; 0 .. length)
359             assert(!a[i]);
360 
361         a[0] = true;
362         assert(a[0]);
363         foreach (const i; 1 .. length)
364             assert(!a[i]);
365 
366         assert(!a[1]);
367         a[1] = true;
368         assert(a[1]);
369         a[1] = false;
370         assert(!a[1]);
371     }
372     test!(false)(100);
373     test!(true)(64);
374 }
375 
376 /// Test `countOnes` and `countZeros`.
377 @safe pure nothrow @nogc unittest
378 {
379     static void test(bool blockAlignedLength)()
380     {
381         alias BA = BitArray!(blockAlignedLength);
382 
383         foreach (const n; 1 .. 5*BA.bitsPerBlock)
384         {
385             static if (blockAlignedLength)
386                 if (n % BA.bitsPerBlock != 0) // if block aligned length
387                     continue;
388 
389             auto a = BA.withLength(n);
390 
391             // set bits forwards
392             foreach (const i; 0 .. n)
393             {
394                 assert(a.countOnes == i);
395                 assert(a.countZeros == n - i);
396                 a[i] = true;
397                 assert(a.countOnes == i + 1);
398                 assert(a.countZeros == n - (i + 1));
399             }
400 
401             assert(a.countOnes == n);
402             assert(a.countZeros == 0);
403 
404             auto b = a.dup;
405             assert(b.countOnes == n);
406             assert(b.countZeros == 0);
407 
408             assert(a == b);
409 
410             // clear `a` bits forwards
411             foreach (const i; 0 .. n)
412             {
413                 assert(a.countOnes == n - i);
414                 assert(a.countZeros == i);
415                 a[i] = false;
416                 assert(a.countOnes == n - (i + 1));
417                 assert(a.countZeros == i + 1);
418             }
419 
420             b[] = false;
421             assert(a == b);
422 
423             // set bits backwards
424             foreach (const i; 0 .. n)
425             {
426                 assert(a.countOnes == i);
427                 a[n-1 - i] = true;
428                 assert(a.countOnes == i + 1);
429             }
430 
431             b[] = true;
432             assert(a == b);
433         }
434     }
435     test!(false)();
436     test!(true)();
437 }
438 
439 /// Test emptying (resetting) via `.clear` and explicit copying with `.dup`.
440 @safe pure nothrow @nogc unittest
441 {
442     static void test(bool blockAlignedLength)()
443     {
444         alias BA = BitArray!(blockAlignedLength);
445 
446         static if (blockAlignedLength)
447             const n = 5 * BA.bitsPerBlock;
448         else
449             const n = 5 * BA.bitsPerBlock + 1;
450         auto a = BA.withLength(n);
451 
452         assert(a.length == n);
453 
454         a.reset();
455         assert(a.length == 0);
456 
457         a = BA.withLength(n);
458         assert(a.length == n);
459 
460         auto b = a.dup;
461         assert(b.length == n);
462 
463         a.reset();
464         assert(a.length == 0);
465     }
466     test!(false)();
467     test!(true)();
468 }
469 
470 /// Test `indexOfFirstOne` for single set ones.
471 @safe pure nothrow @nogc unittest
472 {
473     static void test(bool blockAlignedLength)()
474     {
475         alias BA = BitArray!(blockAlignedLength);
476 
477         static if (blockAlignedLength)
478             const n = 2 * BA.bitsPerBlock;
479         else
480             const n = 2 * BA.bitsPerBlock + 1;
481         auto a = BA.withLength(n);
482 
483         assert(a.length == n);
484         assert(a.indexOfFirstOne == n); // miss
485 
486         a[0] = true;
487         assert(a.indexOfFirstOne == 0);
488         a[] = false;
489 
490         a[2] = true;
491         assert(a.indexOfFirstOne == 2);
492         a[] = false;
493 
494         a[n/2-1] = true;
495         assert(a.indexOfFirstOne == n/2-1);
496         a[] = false;
497 
498         a[n/2] = true;
499         assert(a.indexOfFirstOne == n/2);
500         a[] = false;
501 
502         a[n/2+1] = true;
503         assert(a.indexOfFirstOne == n/2+1);
504         a[] = false;
505 
506         a[n-1] = true;
507         assert(a.indexOfFirstOne == n-1);
508         a[] = false;
509 
510         assert(a.indexOfFirstOne == n); // miss
511     }
512     test!(false)();
513     test!(true)();
514 }
515 
516 /// Test `indexOfFirstOne` for multi set ones.
517 @safe pure nothrow @nogc unittest
518 {
519     static void test(bool blockAlignedLength)()
520     {
521         alias BA = BitArray!(blockAlignedLength);
522 
523         static if (blockAlignedLength)
524             const n = 2 * BA.bitsPerBlock;
525         else
526             const n = 2 * BA.bitsPerBlock + 1;
527         auto a = BA.withLength(n);
528 
529         a[0] = true;
530         a[BA.bitsPerBlock/2] = true;
531         a[BA.bitsPerBlock - 1] = true;
532         assert(a.indexOfFirstOne == 0);
533     }
534     test!(false)();
535     test!(true)();
536 }
537 
538 /// Test `indexOfFirstZero` for single set zeros.
539 @safe pure nothrow @nogc unittest
540 {
541     static void test(bool blockAlignedLength)()
542     {
543         alias BA = BitArray!(blockAlignedLength);
544 
545         static if (blockAlignedLength)
546             const n = 2 * BA.bitsPerBlock;
547         else
548             const n = 2 * BA.bitsPerBlock + 1;
549         auto a = BA.withLength(n);
550 
551         a[] = true;
552 
553         assert(a.length == n);
554         assert(a.indexOfFirstZero == n); // miss
555 
556         a[0] = false;
557         assert(a.indexOfFirstZero == 0);
558         a[0] = true;
559 
560         a[2] = false;
561         assert(a.indexOfFirstZero == 2);
562         a[2] = true;
563 
564         a[n/2-1] = false;
565         assert(a.indexOfFirstZero == n/2-1);
566         a[n/2-1] = true;
567 
568         a[n/2] = false;
569         assert(a.indexOfFirstZero == n/2);
570         a[n/2] = true;
571 
572         a[n/2+1] = false;
573         assert(a.indexOfFirstZero == n/2+1);
574         a[n/2+1] = true;
575 
576         a[n-1] = false;
577         assert(a.indexOfFirstZero == n-1);
578         a[n-1] = true;
579 
580         assert(a.indexOfFirstZero == n); // miss
581     }
582     test!(false)();
583     test!(true)();
584 }
585 
586 @safe pure nothrow @nogc unittest
587 {
588     alias BA = BitArray!(false);
589     static assert(BitArray!(false).sizeof == 3*BA.Block.sizeof); // one extra word for `length`
590     static assert(BitArray!(true).sizeof == 2*BA.Block.sizeof);
591 }
592 
593 /// Test `indexOfFirstZero` for multi set zeros.
594 @safe pure nothrow @nogc unittest
595 {
596     static void test(bool blockAlignedLength)()
597     {
598         alias BA = BitArray!(blockAlignedLength);
599 
600         static if (blockAlignedLength)
601             const n = 2 * BA.bitsPerBlock;
602         else
603             const n = 2 * BA.bitsPerBlock + 1;
604         auto a = BA.withLength(n);
605 
606         a[] = true;
607 
608         a[0] = false;
609         a[BA.bitsPerBlock/2] = false;
610         a[BA.bitsPerBlock - 1] = false;
611         assert(a.indexOfFirstZero == 0);
612     }
613     test!(false)();
614     test!(true)();
615 }
616 
617 /// Test `indexOfFirstOne` for multi set ones.
618 @safe pure nothrow @nogc unittest
619 {
620     static void test(bool blockAlignedLength)()
621     {
622         alias BA = BitArray!(blockAlignedLength);
623 
624         static if (blockAlignedLength)
625             const n = 2 * BA.bitsPerBlock;
626         else
627             const n = 2 * BA.bitsPerBlock + 1;
628         auto a = BA.withLength(n);
629 
630         a[] = false;
631 
632         a[0] = true;
633         a[BA.bitsPerBlock/2] = true;
634         a[BA.bitsPerBlock - 1] = true;
635         assert(a.indexOfFirstOne == 0);
636     }
637     test!(false)();
638     test!(true)();
639 }
640 
641 /// Test casting to `bool`.
642 @safe pure nothrow @nogc unittest
643 {
644     static void test(bool blockAlignedLength)()
645     {
646         alias BA = BitArray!(blockAlignedLength);
647 
648         static if (blockAlignedLength)
649             const n = 2 * BA.bitsPerBlock;
650         else
651             const n = 2 * BA.bitsPerBlock + 1;
652         auto a = BA.withLength(n);
653 
654         assert(a.allZero);
655 
656         a[0] = true;
657         assert(!a.allZero);
658         a[0] = false;
659         assert(a.allZero);
660     }
661     test!(false)();
662 }
663 
664 ///
665 @trusted pure unittest
666 {
667     import std.exception: assertThrown;
668     import core.exception : AssertError;
669     assertThrown!AssertError(BitArray!(true).withLength(1));
670 }
671 
672 // TODO: use
673 extern (C) private pure @system @nogc nothrow
674 {
675     pragma(mangle, "malloc") void* fakePureMalloc(size_t);
676     pragma(mangle, "calloc") void* fakePureCalloc(size_t nmemb, size_t size);
677     pragma(mangle, "realloc") void* fakePureRealloc(void* ptr, size_t size);
678     pragma(mangle, "free") void fakePureFree(void* ptr);
679 }