dmd.root.bitarray source code

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