gcc/d/dmd/root/bitarray.d

   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 }