Fixed-width bit arrays, a good deal faster than dynamic ones.

1 files changed, 48 insertions, 0 deletions

diff --git a/crawl-ref/source/bitary.h b/crawl-ref/source/bitary.h
index 7c210f1626..c93be0e7dd 100644
--- a/crawl-ref/source/bitary.h
+++ b/crawl-ref/source/bitary.h
@@ -9,6 +9,8 @@
 #ifndef BITARY_H
 #define BITARY_H
 
+#include "debug.h"
+
 class bit_array
 {
 public:
@@ -30,4 +32,50 @@ protected:
     unsigned long *data;
 };
 
+#define LONGSIZE (sizeof(unsigned long)*8)
+
+template <unsigned int SIZE> class FixedBitArray
+{
+protected:
+    unsigned long data[(SIZE + LONGSIZE - 1) / LONGSIZE];
+public:
+    void reset()
+    {
+        for (unsigned int i = 0; i < sizeof(data) / sizeof(unsigned long); i++)
+            data[i] = 0;
+    }
+
+    FixedBitArray()
+    {
+        reset();
+    }
+
+    inline bool get(unsigned int i) const
+    {
+#ifdef ASSERTS
+        // printed as signed, as in FixedVector
+        if (i >= SIZE)
+            die("bit array range error: %d / %u", (int)i, SIZE);
+#endif
+        return data[i / LONGSIZE] & 1UL << i % LONGSIZE;
+    }
+
+    inline bool operator[](unsigned int i) const
+    {
+        return get(i);
+    }
+
+    inline void set(unsigned int i, bool value)
+    {
+#ifdef ASSERTS
+        if (i >= SIZE)
+            die("bit array range error: %d / %u", (int)i, SIZE);
+#endif
+        if (value)
+            data[i / LONGSIZE] |= 1UL << i % LONGSIZE;
+        else
+            data[i / LONGSIZE] &= ~(1UL << i % LONGSIZE);
+    }
+};
+
 #endif