1 /**
2  * Implementation of a bit array.
3  *
4  * Copyright:   Copyright (C) 1999-2020 by The D Language Foundation, All Rights Reserved
5  * Authors:     $(LINK2 http://www.digitalmars.com, Walter Bright)
6  * License:     $(LINK2 http://www.boost.org/LICENSE_1_0.txt, Boost License 1.0)
7  * Source:      $(LINK2 https://github.com/dlang/dmd/blob/master/src/dmd/root/bitarray.d, root/_bitarray.d)
8  * Documentation:  https://dlang.org/phobos/dmd_root_array.html
9  * Coverage:    https://codecov.io/gh/dlang/dmd/src/master/src/dmd/root/bitarray.d
10  */
11 
12 module dmd.root.bitarray;
13 
14 import core.stdc.stdio;
15 import core.stdc.string;
16 
17 import dmd.root.rmem;
18 
19 struct BitArray
20 {
21 nothrow:
22 
23     alias Chunk_t = size_t;
24     enum ChunkSize = Chunk_t.sizeof;
25     enum BitsPerChunk = ChunkSize * 8;
26 
27     size_t length() const pure nothrow @nogc @safe
28     {
29         return len;
30     }
31 
32     void length(size_t nlen) pure nothrow
33     {
34         immutable ochunks = chunks(len);
35         immutable nchunks = chunks(nlen);
36         if (ochunks != nchunks)
37         {
38             ptr = cast(size_t*)mem.xrealloc_noscan(ptr, nchunks * ChunkSize);
39         }
40         if (nchunks > ochunks)
41            ptr[ochunks .. nchunks] = 0;
42         if (nlen & (BitsPerChunk - 1))
43            ptr[nchunks - 1] &= (cast(Chunk_t)1 << (nlen & (BitsPerChunk - 1))) - 1;
44         len = nlen;
45     }
46 
47     void opAssign(const ref BitArray b)
48     {
49         if (!len)
50             length(b.len);
51         assert(len == b.len);
52         memcpy(ptr, b.ptr, bytes(len));
53     }
54 
55     bool opIndex(size_t idx) const pure nothrow @nogc
56     {
57         import core.bitop : bt;
58 
59         assert(idx < len);
60         return !!bt(ptr, idx);
61     }
62 
63     void opIndexAssign(bool val, size_t idx) pure nothrow @nogc
64     {
65         import core.bitop : btc, bts;
66 
67         assert(idx < len);
68         if (val)
69             bts(ptr, idx);
70         else
71             btc(ptr, idx);
72     }
73 
74     bool opEquals(const ref BitArray b) const
75     {
76         return len == b.len && memcmp(ptr, b.ptr, bytes(len)) == 0;
77     }
78 
79     void zero()
80     {
81         memset(ptr, 0, bytes(len));
82     }
83 
84     /******
85      * Returns:
86      *  true if no bits are set
87      */
88     bool isZero()
89     {
90         const nchunks = chunks(len);
91         foreach (i; 0 .. nchunks)
92         {
93             if (ptr[i])
94                 return false;
95         }
96         return true;
97     }
98 
99     void or(const ref BitArray b)
100     {
101         assert(len == b.len);
102         const nchunks = chunks(len);
103         foreach (i; 0 .. nchunks)
104             ptr[i] |= b.ptr[i];
105     }
106 
107     /* Swap contents of `this` with `b`
108      */
109     void swap(ref BitArray b)
110     {
111         assert(len == b.len);
112         const nchunks = chunks(len);
113         foreach (i; 0 .. nchunks)
114         {
115             const chunk = ptr[i];
116             ptr[i] = b.ptr[i];
117             b.ptr[i] = chunk;
118         }
119     }
120 
121     ~this() pure nothrow
122     {
123         debug
124         {
125             // Stomp the allocated memory
126             const nchunks = chunks(len);
127             foreach (i; 0 .. nchunks)
128             {
129                 ptr[i] = cast(Chunk_t)0xFEFEFEFE_FEFEFEFE;
130             }
131         }
132         mem.xfree(ptr);
133         debug
134         {
135             // Set to implausible values
136             len = cast(size_t)0xFEFEFEFE_FEFEFEFE;
137             ptr = cast(size_t*)cast(size_t)0xFEFEFEFE_FEFEFEFE;
138         }
139     }
140 
141 private:
142     size_t len;         // length in bits
143     size_t *ptr;
144 
145     /// Returns: The amount of chunks used to store len bits
146     static size_t chunks(const size_t len) @nogc nothrow pure @safe
147     {
148         return (len + BitsPerChunk - 1) / BitsPerChunk;
149     }
150 
151     /// Returns: The amount of bytes used to store len bits
152     static size_t bytes(const size_t len) @nogc nothrow pure @safe
153     {
154         return chunks(len) * ChunkSize;
155     }
156 }
157 
158 unittest
159 {
160     BitArray array;
161     array.length = 20;
162     assert(array[19] == 0);
163     array[10] = 1;
164     assert(array[10] == 1);
165     array[10] = 0;
166     assert(array[10] == 0);
167     assert(array.length == 20);
168 
169     BitArray a,b;
170     assert(a != array);
171     a.length = 200;
172     assert(a != array);
173     assert(a.isZero());
174     a[100] = true;
175     b.length = 200;
176     b[100] = true;
177     assert(a == b);
178 
179     a.length = 300;
180     b.length = 300;
181     assert(a == b);
182     b[299] = true;
183     assert(a != b);
184     assert(!a.isZero());
185     a.swap(b);
186     assert(a[299] == true);
187     assert(b[299] == false);
188     a = b;
189     assert(a == b);
190 }
191 
192 
193