gcc/d/dmd/root/bitarray.d

/**
 * Implementation of a bit array.
 *
 * Copyright:   Copyright (C) 1999-2022 by The D Language Foundation, All Rights Reserved
 * Authors:     $(LINK2 https://www.digitalmars.com, Walter Bright)
 * License:     $(LINK2 https://www.boost.org/LICENSE_1_0.txt, Boost License 1.0)
 * Source:      $(LINK2 https://github.com/dlang/dmd/blob/master/src/dmd/root/bitarray.d, root/_bitarray.d)
 * Documentation:  https://dlang.org/phobos/dmd_root_array.html
 * Coverage:    https://codecov.io/gh/dlang/dmd/src/master/src/dmd/root/bitarray.d
 */

module dmd.root.bitarray;

import core.stdc.stdio;
import core.stdc.string;

import dmd.root.rmem;

struct BitArray
{

    alias Chunk_t = size_t;
    enum ChunkSize = Chunk_t.sizeof;
    enum BitsPerChunk = ChunkSize * 8;

    size_t length() const @nogc nothrow pure @safe
    {
        return len;
    }

    void length(size_t nlen) nothrow pure
    {
        immutable ochunks = chunks(len);
        immutable nchunks = chunks(nlen);
        if (ochunks != nchunks)
        {
            ptr = cast(size_t*)mem.xrealloc_noscan(ptr, nchunks * ChunkSize);
        }
        if (nchunks > ochunks)
           ptr[ochunks .. nchunks] = 0;
        if (nlen & (BitsPerChunk - 1))
           ptr[nchunks - 1] &= (cast(Chunk_t)1 << (nlen & (BitsPerChunk - 1))) - 1;
        len = nlen;
    }

    void opAssign(const ref BitArray b) nothrow pure
    {
        if (!len)
            length(b.len);
        assert(len == b.len);
        memcpy(ptr, b.ptr, bytes(len));
    }

    bool opIndex(size_t idx) const @nogc nothrow pure
    {
        import core.bitop : bt;

        assert(idx < len);
        return !!bt(ptr, idx);
    }

    void opIndexAssign(bool val, size_t idx) @nogc nothrow pure
    {
        import core.bitop : btc, bts;

        assert(idx < len);
        if (val)
            bts(ptr, idx);
        else
            btc(ptr, idx);
    }

    bool opEquals(const ref BitArray b) const @nogc nothrow pure
    {
        return len == b.len && memcmp(ptr, b.ptr, bytes(len)) == 0;
    }

    void zero() @nogc nothrow pure
    {
        memset(ptr, 0, bytes(len));
    }

    /******
     * Returns:
     *  true if no bits are set
     */
    bool isZero() @nogc nothrow pure
    {
        const nchunks = chunks(len);
        foreach (i; 0 .. nchunks)
        {
            if (ptr[i])
                return false;
        }
        return true;
    }

    void or(const ref BitArray b) @nogc nothrow pure
    {
        assert(len == b.len);
        const nchunks = chunks(len);
        foreach (i; 0 .. nchunks)
            ptr[i] |= b.ptr[i];
    }

    /* Swap contents of `this` with `b`
     */
    void swap(ref BitArray b) @nogc nothrow pure
    {
        assert(len == b.len);
        const nchunks = chunks(len);
        foreach (i; 0 .. nchunks)
        {
            const chunk = ptr[i];
            ptr[i] = b.ptr[i];
            b.ptr[i] = chunk;
        }
    }

    ~this() nothrow pure
    {
        debug
        {
            // Stomp the allocated memory
            const nchunks = chunks(len);
            foreach (i; 0 .. nchunks)
            {
                ptr[i] = cast(Chunk_t)0xFEFEFEFE_FEFEFEFE;
            }
        }
        mem.xfree(ptr);
        debug
        {
            // Set to implausible values
            len = cast(size_t)0xFEFEFEFE_FEFEFEFE;
            ptr = cast(size_t*)cast(size_t)0xFEFEFEFE_FEFEFEFE;
        }
    }

private:
    size_t len;         // length in bits
    size_t *ptr;

    /// Returns: The amount of chunks used to store len bits
    static size_t chunks(const size_t len) @nogc nothrow pure @safe
    {
        return (len + BitsPerChunk - 1) / BitsPerChunk;
    }

    /// Returns: The amount of bytes used to store len bits
    static size_t bytes(const size_t len) @nogc nothrow pure @safe
    {
        return chunks(len) * ChunkSize;
    }
}

nothrow pure unittest
{
    BitArray array;
    array.length = 20;
    assert(array[19] == 0);
    array[10] = 1;
    assert(array[10] == 1);
    array[10] = 0;
    assert(array[10] == 0);
    assert(array.length == 20);

    BitArray a,b;
    assert(a != array);
    a.length = 200;
    assert(a != array);
    assert(a.isZero());
    a[100] = true;
    b.length = 200;
    b[100] = true;
    assert(a == b);

    a.length = 300;
    b.length = 300;
    assert(a == b);
    b[299] = true;
    assert(a != b);
    assert(!a.isZero());
    a.swap(b);
    assert(a[299] == true);
    assert(b[299] == false);
    a = b;
    assert(a == b);
}