tiny.simd.AtomicBitSet

1pub fn AtomicBitSet(comptime size: usize) type {2    requireCapacity(size);3    const Word = usize;4    const word_bits: usize = @bitSizeOf(Word);5    const word_count = std.math.divCeil(usize, size, word_bits) catch unreachable;6    const AtomicWord = std.atomic.Value(Word);78    return struct {9        words: [word_count]AtomicWord = @as([word_count]AtomicWord, @splat(AtomicWord.init(0))),1011        const Self = @This();12        pub const capacity: usize = size;13        pub const max_size: usize = capacity;1415        pub fn maxSize(_: *const Self) usize {16            return max_size;17        }1819        pub fn set(self: *Self, index: usize) void {20            std.debug.assert(index < max_size);21            _ = self.words[atomicWordIndex(index)].fetchOr(22                atomicBit(atomicBitIndex(index)),23                .release,24            );25        }2627        pub fn clear(self: *Self, index: usize) void {28            std.debug.assert(index < max_size);29            _ = self.words[atomicWordIndex(index)].fetchAnd(30                ~atomicBit(atomicBitIndex(index)),31                .release,32            );33            if (runtime_assertions) std.debug.assert(!self.get(index));34        }3536        pub fn get(self: *const Self, index: usize) bool {37            std.debug.assert(index < max_size);38            return self.words[atomicWordIndex(index)].load(.acquire) &39                atomicBit(atomicBitIndex(index)) != 0;40        }4142        pub fn any(self: *const Self) bool {43            for (&self.words) |*word| {44                if (word.load(.acquire) != 0) return true;45            }46            return false;47        }4849        pub fn all(self: *const Self) bool {50            for (self.words[0 .. word_count - 1]) |*word| {51                if (word.load(.acquire) != std.math.maxInt(Word)) return false;52            }53            const last = self.words[word_count - 1].load(.acquire);54            const remainder = max_size % word_bits;55            return if (remainder == 0)56                last == std.math.maxInt(Word)57            else58                @popCount(last) == remainder;59        }6061        pub fn first(self: *const Self) usize {62            if (runtime_assertions) std.debug.assert(self.any());63            for (&self.words, 0..) |*word, word_index| {64                const bits = word.load(.acquire);65                if (bits != 0) {66                    return word_index * word_bits + atomicFirstBit(bits);67                }68            }69            unreachable;70        }7172        pub fn first0(self: *const Self) usize {73            if (runtime_assertions) std.debug.assert(!self.all());74            for (&self.words, 0..) |*word, word_index| {75                const inverted = ~word.load(.acquire);76                if (inverted != 0) {77                    const index = word_index * word_bits +78                        atomicFirstBit(inverted);79                    std.debug.assert(index < max_size);80                    return index;81                }82            }83            unreachable;84        }8586        pub fn foreach(self: *const Self, function: anytype) void {87            for (&self.words, 0..) |*word, word_index| {88                visitAtomicWord(89                    word.load(.acquire),90                    word_index * word_bits,91                    function,92                );93            }94        }9596        pub fn count(self: *const Self) usize {97            var total: usize = 0;98            for (&self.words) |*word| total += @popCount(word.load(.acquire));99            std.debug.assert(total <= max_size);100            return total;101        }102103        fn atomicWordIndex(index: usize) usize {104            return index / word_bits;105        }106107        fn atomicBitIndex(index: usize) usize {108            return index % word_bits;109        }110111        fn atomicBit(index: usize) Word {112            std.debug.assert(index < word_bits);113            return @as(Word, 1) << @intCast(index);114        }115116        fn atomicFirstBit(bits: Word) usize {117            std.debug.assert(bits != 0);118            return @ctz(bits);119        }120121        fn visitAtomicWord(bits: Word, base: usize, function: anytype) void {122            var remaining = bits;123            while (remaining != 0) {124                const index = atomicFirstBit(remaining);125                remaining &= remaining - 1;126                function.call(base + index);127            }128        }129    };130}

1pub const AtomicBitSet = bitset.AtomicBitSet;