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