From 4ae6a06d94b228a5eb67c8473131a791e310c233 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Sat, 24 Oct 2026 15:25:58 -0700 Subject: Rename modules chapter to 28a --- chapter28a/src/main/smp/sys/adt/bitset.smp | 57 ++++++++++++++++++++++++++++++ 1 file changed, 57 insertions(+) create mode 100644 chapter28a/src/main/smp/sys/adt/bitset.smp (limited to 'chapter28a/src/main/smp/sys/adt') diff --git a/chapter28a/src/main/smp/sys/adt/bitset.smp b/chapter28a/src/main/smp/sys/adt/bitset.smp new file mode 100644 index 00000000..d02cd2fe --- /dev/null +++ b/chapter28a/src/main/smp/sys/adt/bitset.smp @@ -0,0 +1,57 @@ + +// A set of non-negative integers, represented one bit per value. +struct bitset { + i64[] !_bits; + + new bitset = { -> + _bits = new i64[1]; + }; + + // Return 0 for missing, non-zero for true + val get = { int bit -> + if( (bit >> 6) >= _bits# ) return false; + i64 mask = 1 << (bit & 63); + return (_bits[bit >> 6] & mask); + }; + + val _grow = { int bit -> + int x = bit >> 6; + int len = _bits#; + if( x < len ) return self; + while( x >= len ) len *= 2; + var bits = new i64[len]; + for( int i=0; i<_bits#; i++ ) + bits[i] = _bits[i]; + _bits = bits; + return self; + }; + + // Set + val set = { int bit -> + i64 mask = 1 << (bit & 63); + _grow(bit)._bits[bit >> 6] |= mask; + return self; + }; + + // Test and set + val tset = { int bit -> + int idx = bit >> 6; + i64 mask = 1 << (bit & 63); + if( _grow(bit)._bits[idx] & mask ) + return true; // Already set + _bits[idx] |= mask; + return false; // Was false (and now set) + }; + + val clr = { int bit -> + if( (bit >> 6) >= _bits# ) return self; + i64 mask = 1 << (bit & 63); + _bits[bit >> 6] &= (mask ^ -1); + return self; + }; + + val clear = { -> + for( int i=0; i<_bits#; i++ ) _bits[i] = 0; + return self; + }; +}; -- cgit v1.2.3