1 /** 2 * Implementation of a bit array. 3 * 4 * Copyright: Copyright (C) 1999-2022 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 lengthBitArray26 size_t length() const @nogc nothrow pure @safe 27 { 28 return len; 29 } 30 lengthBitArray31 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 opAssignBitArray46 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 opIndexBitArray54 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 opIndexAssignBitArray62 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 opEqualsBitArray73 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 zeroBitArray78 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 */ isZeroBitArray87 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 orBitArray98 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 */ swapBitArray108 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 ~thisBitArray120 ~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 chunksBitArray145 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 bytesBitArray151 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 } 190