1 files changed, 57 insertions, 0 deletions
diff --git a/src/main/smp/sys/adt/bitset.smp b/src/main/smp/sys/adt/bitset.smp
new file mode 100644
index 00000000..d02cd2fe
--- /dev/null
+++ b/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;
+    };
+};