simple_static_bitarray source code

1 /**
2  * Static bit array container for internal usage.
3  */
4 module simple_static_bitarray;
5 
6 @safe:
7 
8 alias DefaultBlock = size_t;    ///< Default block type.
9 
10 struct StaticBitArray(uint capacity)
11 {
12 @safe pure nothrow @nogc:
13     import core.bitop : bt, bts, btr;
14 
15     /** Number of bits. */
16     enum length = capacity;
17 
18     alias Block = DefaultBlock; ///< Block type.
19 
20     /** Number of bits per `Block`. */
21     enum bitsPerBlock = 8*Block.sizeof;
22 
23     /** Number of blocks of type `Block`. */
24     enum blockCount = (capacity + (bitsPerBlock-1)) / bitsPerBlock;
25 
26     /** Reset all bits (to zero). */
27     void reset()
28     {
29         version(D_Coverage) {} else pragma(inline, true);
30         _blocks[] = 0;          // TODO is this the fastest way?
31     }
32 
33     /** Gets the $(D idx)'th bit. */
34     bool opIndex(size_t idx) const @trusted
35     in
36     {
37         assert(idx < length);     // TODO nothrow or not?
38     }
39     body
40     {
41         version(D_Coverage) {} else pragma(inline, true);
42         return cast(bool)bt(_blocks.ptr, idx);
43     }
44 
45     /** Sets the $(D idx)'th bit. */
46     bool opIndexAssign(bool b, size_t idx) @trusted
47     in
48     {
49         assert(idx < length);     // TODO nothrow or not?
50     }
51     body
52     {
53         version(D_Coverage) {} else pragma(inline, true);
54         if (b)
55         {
56             bts(_blocks.ptr, cast(size_t)idx);
57         }
58         else
59         {
60             btr(_blocks.ptr, cast(size_t)idx);
61         }
62         return b;
63     }
64 
65     /** Find index of first cleared (zero) bit or `typeof(return).max` if no bit set.
66      *
67      * Optimized for zeros-sparsity.
68      */
69     size_t indexOfFirstZero()() const
70     {
71         import nxt.bitarray_algorithm;
72         enum bool blockAlignedLength = capacity % (8*Block.sizeof) == 0;
73         return nxt.bitarray_algorithm.indexOfFirstZero!(const(Block)[blockCount],
74                                                         blockAlignedLength)(_blocks, length);
75     }
76 
77     /** Find index of first set (one) bit or `typeof(return).max` if no bit set.
78      *
79      * Optimized for ones-sparsity.
80      */
81     size_t indexOfFirstOne()() const
82     {
83         import nxt.bitarray_algorithm;
84         enum bool blockAlignedLength = capacity % (8*Block.sizeof) == 0;
85         return nxt.bitarray_algorithm.indexOfFirstOne!(const(Block)[blockCount],
86                                                        blockAlignedLength)(_blocks, length);
87     }
88 
89     private Block[blockCount] _blocks;
90 }
91 
92 ///
93 @trusted pure unittest
94 {
95     enum blockCount = 2;
96     enum length = blockCount * 8*DefaultBlock.sizeof - 1; // 2 blocks minus one
97 
98     StaticBitArray!(length) x;
99     static assert(x.blockCount == blockCount);
100 
101     // import std.exception: assertThrown;
102     // import core.exception : AssertError;
103     // assertThrown!AssertError(x[length] = false);
104 
105     x[length/2 - 1] = true;
106     assert(x[length/2 - 1]);
107 
108     x[length/2 - 1] = false;
109     assert(!x[length/2 - 1]);
110 
111     x[length - 1] = true;
112     assert(x[length - 1]);
113 
114     x[length - 1] = false;
115     assert(!x[length - 1]);
116 }
117 
118 /// Test `indexOfFirstZero` for multi set zeros.
119 @safe pure nothrow @nogc unittest
120 {
121     static void test(bool blockAlignedLength)()
122     {
123         static if (blockAlignedLength)
124         {
125             const n = 2 * 8*DefaultBlock.sizeof;
126         }
127         else
128         {
129             const n = 2 * 8*DefaultBlock.sizeof + 1;
130         }
131         alias BA = StaticBitArray!(n);
132 
133         auto a = BA();
134 
135         a[0] = false;
136         a[BA.bitsPerBlock/2] = false;
137         a[BA.bitsPerBlock - 1] = false;
138         assert(a.indexOfFirstZero == 0);
139     }
140     test!(false)();
141     test!(true)();
142 }
143 
144 /// Test `indexOfFirstOne` for multi set ones.
145 @safe pure nothrow @nogc unittest
146 {
147     static void test(bool blockAlignedLength)()
148     {
149         static if (blockAlignedLength)
150         {
151             const n = 2 * 8*Block.sizeof;
152         }
153         else
154         {
155             const n = 2 * 8*DefaultBlock.sizeof + 1;
156         }
157         alias BA = StaticBitArray!(n);
158 
159         auto a = BA();
160 
161         a[0] = true;
162         a[BA.bitsPerBlock/2] = true;
163         a[BA.bitsPerBlock - 1] = true;
164         assert(a.indexOfFirstOne == 0);
165     }
166     test!(false)();
167 }