bitset.h

Go to the documentation of this file.

/* Copyright (c) 2008-2022 the MRtrix3 contributors.
 *
 * This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at http://mozilla.org/MPL/2.0/.
 *
 * Covered Software is provided under this License on an "as is"
 * basis, without warranty of any kind, either expressed, implied, or
 * statutory, including, without limitation, warranties that the
 * Covered Software is free of defects, merchantable, fit for a
 * particular purpose or non-infringing.
 * See the Mozilla Public License v. 2.0 for more details.
 *
 * For more details, see http://www.mrtrix.org/.
 */
 
#ifndef __misc_bitset_h__
#define __misc_bitset_h__
 
 
#include <atomic>
#include <stdint.h>
 
#include "mrtrix.h"
 
 
 
namespace MR {
 
 
 
 
  class BitSet { NOMEMALIGN
 
    public:
 
      class Value { NOMEMALIGN
        public:
        Value (BitSet& master, const size_t offset) : d (master), p (offset) { assert (p < d.size()); }
        operator bool()                  const { return d.test (p); }
        bool   operator== (const bool i) const { return (i == d.test (p)); }
        bool   operator=  (const bool i)       { i ? d.set (p) : d.reset (p); return i; }
        Value& operator|= (const bool i)       { (i || bool(*this)) ? d.set (p) : d.reset (p); return *this; }
        Value& operator&= (const bool i)       { (i && bool(*this)) ? d.set (p) : d.reset (p); return *this; }
        friend std::ostream& operator<< (std::ostream& stream, const Value& V) { stream << (bool(V) ? '1' : '0'); return stream; }
        private:
        BitSet& d;
        const size_t p;
      };
      class ConstValue { NOMEMALIGN
        public:
          ConstValue (const BitSet& master, const size_t offset) : d (master), p (offset) { assert (p < d.size()); }
          operator bool()                  const { return d.test (p); }
          bool   operator== (const bool i) const { return (i == d.test (p)); }
          friend std::ostream& operator<< (std::ostream& stream, const ConstValue& V) { stream << (bool(V) ? '1' : '0'); return stream; }
        private:
          const BitSet& d;
          const size_t p;
      };
 
 
 
      BitSet (const size_t, const bool allocator = false);
 
 
      BitSet (const BitSet&);
      ~BitSet();
 
 
      void resize (const size_t, const bool allocator = false);
 
 
      void clear  (const bool allocator = false);
 
 
      ConstValue operator[] (const size_t i) const { assert (i < bits); return ConstValue (*this, i); }
      Value      operator[] (const size_t i)       { assert (i < bits); return Value      (*this, i); }
 
 
      size_t size() const { return bits; }
 
 
      bool full()  const;
 
 
      bool empty() const;
 
 
      size_t count() const;
 
 
      BitSet& operator=  (const BitSet&);
      bool    operator== (const BitSet&) const;
      bool    operator!= (const BitSet&) const;
      BitSet& operator|= (const BitSet&);
      BitSet& operator&= (const BitSet&);
      BitSet& operator^= (const BitSet&);
      BitSet  operator|  (const BitSet&) const;
      BitSet  operator&  (const BitSet&) const;
      BitSet  operator^  (const BitSet&) const;
      BitSet  operator~  () const;
 
      const uint8_t* get_data_ptr() const { return data; }
 
      friend std::ostream& operator<< (std::ostream&, const BitSet&);
 
 
    protected:
      size_t bits;
      size_t bytes;
 
      bool have_excess_bits() const { return (bits & size_t(7)); }
      size_t excess_bits() const { return (8*bytes - bits); }
      uint8_t excess_bit_mask() const { assert (have_excess_bits()); return 0xFF << (8-excess_bits()); }
 
      bool test  (const size_t index) const
      {
        assert (index < bits);
        return (data[index>>3] & masks[index&size_t(7)]);
      }
 
      void set   (const size_t index)
      {
        assert (index < bits);
        std::atomic<uint8_t>* at = reinterpret_cast<std::atomic<uint8_t>*> (((uint8_t*) data) + (index>>3));
        uint8_t prev = *at, new_value;
        do { new_value = prev | masks[index&size_t(7)]; } while (!at->compare_exchange_weak (prev, new_value));
      }
 
      void reset (const size_t index)
      {
        assert (index < bits);
        std::atomic<uint8_t>* at = reinterpret_cast<std::atomic<uint8_t>*> (((uint8_t*) data) + (index>>3));
        uint8_t prev = *at, new_value;
        do { new_value = prev & ~masks[index&size_t(7)]; } while (!at->compare_exchange_weak (prev, new_value));
      }
 
 
    private:
      uint8_t* data;
 
      static const uint8_t masks[8];
 
  };
 
 
 
}
 
#endif