1 /** Bitarray. 2 */ 3 module nxt.bitarray; 4 5 @safe: 6 7 /** Array of bits. 8 * 9 * Like `std.bitmanip.BitArray` but @safe pure nothrow @nogc. 10 * 11 * Set `blockAlignedLength` to true if `this.length` is always a multiple of 12 * `Block.size`. 13 * 14 * TODO: use `Flag` instead, or wrap in `BlockAlignedBitArray` where this class 15 * is made private _BitArray and alias BitArray = _BitArray!(true). 16 * 17 * TODO: support append bit via `pushBack(bool)`. 18 */ 19 struct BitArray(bool blockAlignedLength = false, 20 alias Allocator = null) // TODO: use Allocator 21 { 22 import core.bitop : bt, bts, btr; 23 import nxt.bitarray_algorithm; 24 25 @safe pure nothrow @nogc: 26 27 /** Construct with `length` number of zero bits. */ 28 static typeof(this) withLength(size_t length) 29 => typeof(this)(length); 30 31 /** Construct with `length` number of zero bits stored in `blocks`. */ 32 private static typeof(this) withLengthAndBlocks(size_t length, const scope Block[] blocks) 33 => typeof(return)(length, blocks); 34 35 /** Helper constructor for `length` number of bits. */ 36 private this(size_t length) @trusted 37 { 38 static if (blockAlignedLength) 39 { 40 assert(length % bitsPerBlock == 0, 41 "Parameter `length` is not a multiple `Block` bit size " ~ bitsPerBlock.stringof); 42 _blockCount = length / bitsPerBlock; // number of whole blocks 43 } 44 else 45 { 46 _blockCount = (length + bitsPerBlock-1) / bitsPerBlock; 47 _length = length; 48 } 49 _blockPtr = cast(Block*)fakePureCalloc(bitsPerBlock, _blockCount); // TODO: use `Allocator` 50 } 51 52 /** Helper constructor. */ 53 private this(size_t length, 54 const scope Block[] blocks) @trusted 55 { 56 _blockCount = blocks.length; 57 _blockPtr = cast(Block*)fakePureMalloc(bitsPerBlock * _blockCount); // TODO: use `Allocator` 58 _blocks[] = blocks; // copy block array 59 static if (!blockAlignedLength) 60 { 61 _length = length; 62 } 63 } 64 65 /// Destroy. 66 ~this() nothrow @nogc => release(); 67 68 /// Explicit copying (duplicate). 69 typeof(this) dup() => typeof(this).withLengthAndBlocks(_length, _blocks); 70 71 /// Empty. 72 void reset() 73 { 74 release(); 75 resetInternalData(); 76 } 77 alias clear = reset; 78 79 /// Release internal store. 80 private void release() @trusted @nogc => fakePureFree(_blockPtr); 81 82 /// Reset internal data. 83 private void resetInternalData() 84 { 85 _blockPtr = null; 86 _blockCount = 0; 87 static if (!blockAlignedLength) 88 _length = 0; 89 } 90 91 /// Check if empty. 92 bool empty() const @property { return _length == 0; } 93 94 /// Get length. 95 @property size_t length() const => _length; 96 alias opDollar = length; /// ditto 97 98 /// Get capacity in number of bits. 99 @property size_t capacity() const => bitsPerBlock*_blockCount; 100 101 /** Get the `i`'th bit. */ 102 bool opIndex(size_t i) const @trusted 103 { 104 version(D_Coverage) {} else pragma(inline, true); 105 assert(i < length); // TODO: nothrow or not? 106 return cast(bool)bt(_blockPtr, i); 107 } 108 109 /** Set the `i`'th bit to `value`. */ 110 bool opIndexAssign(bool value, size_t i) @trusted 111 { 112 version(D_Coverage) {} else pragma(inline, true); 113 if (value) 114 bts(_blockPtr, i); 115 else 116 btr(_blockPtr, i); 117 return value; 118 } 119 120 /** Set all bits to `value` via slice assignment syntax. */ 121 ref typeof(this) opSliceAssign(bool value) 122 { 123 if (value) 124 one(); 125 else 126 zero(); 127 return this; 128 } 129 130 /** Clear all bits (to zero). */ 131 private void zero() 132 { 133 foreach (ref block; _blocks) 134 block = Block.min; 135 } 136 137 /** Set all bits (to one). */ 138 private void one() 139 { 140 foreach (ref block; _blocks) 141 block = Block.max; 142 } 143 144 version(none) // TODO: activate? 145 bool opCast(T : bool)() const => !this.allZero; 146 147 /** Check if `this` has only zeros. */ 148 bool allZero()() const @safe pure nothrow @nogc 149 { 150 foreach (const block; _fullBlocks) 151 if (block != Block.min) 152 return false; 153 static if (!blockAlignedLength) 154 if (_restBlockZeroPadded != Block.min) 155 return false; 156 return true; 157 } 158 159 /** Check if `this` has only ones. */ 160 bool allOne()() const @safe pure nothrow @nogc 161 { 162 foreach (const block; _fullBlocks) 163 if (block != Block.max) 164 return false; 165 static if (!blockAlignedLength) 166 if (_restBlockOnePadded != Block.max) 167 return false; 168 return true; 169 } 170 171 /** Get number of bits set (to one). */ 172 size_t countOnes()() const /* template-lazy */ 173 => nxt.bitarray_algorithm.countOnes!(const(Block)[], blockAlignedLength)(_blocks, length); 174 175 /** Get number of bits cleared (to zero). */ 176 size_t countZeros()() const /* template-lazy */ 177 => length - countOnes; 178 179 /** Find index of first set (one) bit or `length` if no bit set. 180 * 181 * Optimized for ones-sparsity. 182 */ 183 size_t indexOfFirstOne()() const /* template-lazy */ 184 => nxt.bitarray_algorithm.indexOfFirstOne!(const(Block)[], blockAlignedLength)(_blocks, length); 185 186 /** Find index of first cleared (zero) bit or `length` if no bit cleared. 187 * 188 * Optimized for zeros-sparsity. 189 */ 190 size_t indexOfFirstZero()() const /* template-lazy */ 191 => nxt.bitarray_algorithm.indexOfFirstZero!(const(Block)[], blockAlignedLength)(_blocks, length); 192 193 /** Equality, operators == and !=. */ 194 bool opEquals(const scope ref typeof(this) rhs) const @trusted // TODO: use `in ref` when it compiles 195 { 196 static if (!blockAlignedLength) 197 if (length != rhs.length) 198 return false; 199 if (_fullBlocks != rhs._fullBlocks) 200 return false; 201 static if (!blockAlignedLength) 202 { 203 const restBitCount = length % bitsPerBlock; 204 if (restBitCount) 205 return _restBlockZeroPadded == rhs._restBlockZeroPadded; 206 } 207 return true; 208 } 209 210 /** Only explicit copying via `.dup` for now. */ 211 @disable this(this); 212 213 private: 214 215 /** Get blocks. */ 216 inout(Block)[] _blocks() inout @trusted => _blockPtr[0 .. _blockCount]; 217 218 static if (blockAlignedLength) 219 inout(Block)[] _fullBlocks() inout @trusted => _blocks; // all bits of all blocks are used 220 else 221 { 222 inout(Block)[] _fullBlocks() inout @trusted => _blocks.ptr[0 .. (length / bitsPerBlock)]; 223 /** Return rest `Block` with all padding bits set to zero. */ 224 Block _restBlockZeroPadded() const @trusted => _blocks[$-1] & ((1UL << (length % bitsPerBlock)) - 1); 225 } 226 227 alias Block = size_t; 228 enum bitsPerBlock = 8*Block.sizeof; /// Number of bits per `Block`. 229 230 /** Number of Block's allocated at `_blockPtr`. */ 231 size_t _blockCount; 232 233 static if (is(Allocator == std.experimental.allocator.gc_allocator.GCAllocator)) 234 Block* _blockPtr; // GC-allocated store pointer 235 else 236 { 237 import nxt.gc_traits : NoGc; 238 @NoGc Block* _blockPtr; // non-GC-allocated store pointer 239 } 240 241 static if (blockAlignedLength) 242 @property size_t _length() const => bitsPerBlock * _blockCount; 243 else 244 size_t _length; 245 } 246 247 /// Test `_blockCount` and `_fullBlocks.length`. 248 @safe pure nothrow @nogc unittest 249 { 250 static void test(bool blockAlignedLength)() 251 { 252 alias BA = BitArray!(blockAlignedLength); 253 254 assert(BA.withLength(0)._blockCount == 0); 255 assert(BA.withLength(1)._blockCount == 1); 256 257 { 258 auto a = BA.withLength(1*BA.bitsPerBlock - 1); 259 assert(a._blockCount == 1); 260 assert(a._fullBlocks.length == 0); 261 } 262 263 { 264 auto a = BA.withLength(1*BA.bitsPerBlock + 0); 265 assert(a._blockCount == 1); 266 assert(a._fullBlocks.length == 1); 267 } 268 269 { 270 auto a = BA.withLength(1*BA.bitsPerBlock + 1); 271 assert(a._blockCount == 2); 272 assert(a._fullBlocks.length == 1); 273 } 274 275 { 276 auto a = BA.withLength(2*BA.bitsPerBlock - 1); 277 assert(a._blockCount == 2); 278 assert(a._fullBlocks.length == 1); 279 } 280 281 { 282 auto a = BA.withLength(2*BA.bitsPerBlock + 0); 283 assert(a._blockCount == 2); 284 assert(a._fullBlocks.length == 2); 285 } 286 287 { 288 auto a = BA.withLength(2*BA.bitsPerBlock + 1); 289 assert(a._blockCount == 3); 290 assert(a._fullBlocks.length == 2); 291 } 292 } 293 test!(false)(); 294 } 295 296 /// Test indexing and element assignment. 297 @safe pure nothrow @nogc unittest 298 { 299 static void test(bool blockAlignedLength)(size_t length) 300 { 301 alias BA = BitArray!(blockAlignedLength); 302 303 auto a = BA.withLength(length); 304 305 assert(a.length == length); 306 foreach (const i; 0 .. length) 307 assert(!a[i]); 308 309 a[0] = true; 310 assert(a[0]); 311 foreach (const i; 1 .. length) 312 assert(!a[i]); 313 314 assert(!a[1]); 315 a[1] = true; 316 assert(a[1]); 317 a[1] = false; 318 assert(!a[1]); 319 } 320 test!(false)(100); 321 test!(true)(64); 322 } 323 324 /// Test `countOnes` and `countZeros`. 325 @safe pure nothrow @nogc unittest 326 { 327 static void test(bool blockAlignedLength)() 328 { 329 alias BA = BitArray!(blockAlignedLength); 330 331 foreach (const n; 1 .. 5*BA.bitsPerBlock) 332 { 333 static if (blockAlignedLength) 334 if (n % BA.bitsPerBlock != 0) // if block aligned length 335 continue; 336 337 auto a = BA.withLength(n); 338 339 // set bits forwards 340 foreach (const i; 0 .. n) 341 { 342 assert(a.countOnes == i); 343 assert(a.countZeros == n - i); 344 a[i] = true; 345 assert(a.countOnes == i + 1); 346 assert(a.countZeros == n - (i + 1)); 347 } 348 349 assert(a.countOnes == n); 350 assert(a.countZeros == 0); 351 352 auto b = a.dup; 353 assert(b.countOnes == n); 354 assert(b.countZeros == 0); 355 356 assert(a == b); 357 358 // clear `a` bits forwards 359 foreach (const i; 0 .. n) 360 { 361 assert(a.countOnes == n - i); 362 assert(a.countZeros == i); 363 a[i] = false; 364 assert(a.countOnes == n - (i + 1)); 365 assert(a.countZeros == i + 1); 366 } 367 368 b[] = false; 369 assert(a == b); 370 371 // set bits backwards 372 foreach (const i; 0 .. n) 373 { 374 assert(a.countOnes == i); 375 a[n-1 - i] = true; 376 assert(a.countOnes == i + 1); 377 } 378 379 b[] = true; 380 assert(a == b); 381 } 382 } 383 test!(false)(); 384 test!(true)(); 385 } 386 387 /// Test emptying (resetting) via `.clear` and explicit copying with `.dup`. 388 @safe pure nothrow @nogc unittest 389 { 390 static void test(bool blockAlignedLength)() 391 { 392 alias BA = BitArray!(blockAlignedLength); 393 394 static if (blockAlignedLength) 395 const n = 5 * BA.bitsPerBlock; 396 else 397 const n = 5 * BA.bitsPerBlock + 1; 398 auto a = BA.withLength(n); 399 400 assert(a.length == n); 401 402 a.reset(); 403 assert(a.length == 0); 404 405 a = BA.withLength(n); 406 assert(a.length == n); 407 408 auto b = a.dup; 409 assert(b.length == n); 410 411 a.reset(); 412 assert(a.length == 0); 413 } 414 test!(false)(); 415 test!(true)(); 416 } 417 418 /// Test `indexOfFirstOne` for single set ones. 419 @safe pure nothrow @nogc unittest 420 { 421 static void test(bool blockAlignedLength)() 422 { 423 alias BA = BitArray!(blockAlignedLength); 424 425 static if (blockAlignedLength) 426 const n = 2 * BA.bitsPerBlock; 427 else 428 const n = 2 * BA.bitsPerBlock + 1; 429 auto a = BA.withLength(n); 430 431 assert(a.length == n); 432 assert(a.indexOfFirstOne == n); // miss 433 434 a[0] = true; 435 assert(a.indexOfFirstOne == 0); 436 a[] = false; 437 438 a[2] = true; 439 assert(a.indexOfFirstOne == 2); 440 a[] = false; 441 442 a[n/2-1] = true; 443 assert(a.indexOfFirstOne == n/2-1); 444 a[] = false; 445 446 a[n/2] = true; 447 assert(a.indexOfFirstOne == n/2); 448 a[] = false; 449 450 a[n/2+1] = true; 451 assert(a.indexOfFirstOne == n/2+1); 452 a[] = false; 453 454 a[n-1] = true; 455 assert(a.indexOfFirstOne == n-1); 456 a[] = false; 457 458 assert(a.indexOfFirstOne == n); // miss 459 } 460 test!(false)(); 461 test!(true)(); 462 } 463 464 /// Test `indexOfFirstOne` for multi set ones. 465 @safe pure nothrow @nogc unittest 466 { 467 static void test(bool blockAlignedLength)() 468 { 469 alias BA = BitArray!(blockAlignedLength); 470 471 static if (blockAlignedLength) 472 const n = 2 * BA.bitsPerBlock; 473 else 474 const n = 2 * BA.bitsPerBlock + 1; 475 auto a = BA.withLength(n); 476 477 a[0] = true; 478 a[BA.bitsPerBlock/2] = true; 479 a[BA.bitsPerBlock - 1] = true; 480 assert(a.indexOfFirstOne == 0); 481 } 482 test!(false)(); 483 test!(true)(); 484 } 485 486 /// Test `indexOfFirstZero` for single set zeros. 487 @safe pure nothrow @nogc unittest 488 { 489 static void test(bool blockAlignedLength)() 490 { 491 alias BA = BitArray!(blockAlignedLength); 492 493 static if (blockAlignedLength) 494 const n = 2 * BA.bitsPerBlock; 495 else 496 const n = 2 * BA.bitsPerBlock + 1; 497 auto a = BA.withLength(n); 498 499 a[] = true; 500 501 assert(a.length == n); 502 assert(a.indexOfFirstZero == n); // miss 503 504 a[0] = false; 505 assert(a.indexOfFirstZero == 0); 506 a[0] = true; 507 508 a[2] = false; 509 assert(a.indexOfFirstZero == 2); 510 a[2] = true; 511 512 a[n/2-1] = false; 513 assert(a.indexOfFirstZero == n/2-1); 514 a[n/2-1] = true; 515 516 a[n/2] = false; 517 assert(a.indexOfFirstZero == n/2); 518 a[n/2] = true; 519 520 a[n/2+1] = false; 521 assert(a.indexOfFirstZero == n/2+1); 522 a[n/2+1] = true; 523 524 a[n-1] = false; 525 assert(a.indexOfFirstZero == n-1); 526 a[n-1] = true; 527 528 assert(a.indexOfFirstZero == n); // miss 529 } 530 test!(false)(); 531 test!(true)(); 532 } 533 534 @safe pure nothrow @nogc unittest 535 { 536 alias BA = BitArray!(false); 537 static assert(BitArray!(false).sizeof == 3*BA.Block.sizeof); // one extra word for `length` 538 static assert(BitArray!(true).sizeof == 2*BA.Block.sizeof); 539 } 540 541 /// Test `indexOfFirstZero` for multi set zeros. 542 @safe pure nothrow @nogc unittest 543 { 544 static void test(bool blockAlignedLength)() 545 { 546 alias BA = BitArray!(blockAlignedLength); 547 548 static if (blockAlignedLength) 549 const n = 2 * BA.bitsPerBlock; 550 else 551 const n = 2 * BA.bitsPerBlock + 1; 552 auto a = BA.withLength(n); 553 554 a[] = true; 555 556 a[0] = false; 557 a[BA.bitsPerBlock/2] = false; 558 a[BA.bitsPerBlock - 1] = false; 559 assert(a.indexOfFirstZero == 0); 560 } 561 test!(false)(); 562 test!(true)(); 563 } 564 565 /// Test `indexOfFirstOne` for multi set ones. 566 @safe pure nothrow @nogc unittest 567 { 568 static void test(bool blockAlignedLength)() 569 { 570 alias BA = BitArray!(blockAlignedLength); 571 572 static if (blockAlignedLength) 573 const n = 2 * BA.bitsPerBlock; 574 else 575 const n = 2 * BA.bitsPerBlock + 1; 576 auto a = BA.withLength(n); 577 578 a[] = false; 579 580 a[0] = true; 581 a[BA.bitsPerBlock/2] = true; 582 a[BA.bitsPerBlock - 1] = true; 583 assert(a.indexOfFirstOne == 0); 584 } 585 test!(false)(); 586 test!(true)(); 587 } 588 589 /// Test casting to `bool`. 590 @safe pure nothrow @nogc unittest 591 { 592 static void test(bool blockAlignedLength)() 593 { 594 alias BA = BitArray!(blockAlignedLength); 595 596 static if (blockAlignedLength) 597 const n = 2 * BA.bitsPerBlock; 598 else 599 const n = 2 * BA.bitsPerBlock + 1; 600 auto a = BA.withLength(n); 601 602 assert(a.allZero); 603 604 a[0] = true; 605 assert(!a.allZero); 606 a[0] = false; 607 assert(a.allZero); 608 } 609 test!(false)(); 610 } 611 612 /// 613 @trusted pure unittest 614 { 615 import std.exception: assertThrown; 616 import core.exception : AssertError; 617 assertThrown!AssertError(BitArray!(true).withLength(1)); 618 } 619 620 // TODO: use 621 extern (C) private pure @system @nogc nothrow 622 { 623 pragma(mangle, "malloc") void* fakePureMalloc(size_t); 624 pragma(mangle, "calloc") void* fakePureCalloc(size_t nmemb, size_t size); 625 pragma(mangle, "realloc") void* fakePureRealloc(void* ptr, size_t size); 626 pragma(mangle, "free") void fakePureFree(void* ptr); 627 }