runtime/vm/bit_set.h

// Copyright (c) 2012, the Dart project authors.  Please see the AUTHORS file
// for details. All rights reserved. Use of this source code is governed by a
// BSD-style license that can be found in the LICENSE file.

#ifndef RUNTIME_VM_BIT_SET_H_
#define RUNTIME_VM_BIT_SET_H_

#include "platform/utils.h"
#include "vm/globals.h"

namespace dart {

// Just like its namesake in the STL, a BitSet object contains a fixed
// length sequence of bits.
template <intptr_t N>
class BitSet {
 public:
  BitSet() { Reset(); }

  void Set(intptr_t i, bool value) {
    ASSERT(i >= 0);
    ASSERT(i < N);
    uword mask = (static_cast<uword>(1) << (i & (kBitsPerWord - 1)));
    if (value) {
      data_[i >> kBitsPerWordLog2] |= mask;
    } else {
      data_[i >> kBitsPerWordLog2] &= ~mask;
    }
  }

  bool Test(intptr_t i) const {
    ASSERT(i >= 0);
    ASSERT(i < N);
    uword mask = (static_cast<uword>(1) << (i & (kBitsPerWord - 1)));
    return (data_[i >> kBitsPerWordLog2] & mask) != 0;
  }

  intptr_t Next(intptr_t i) const {
    ASSERT(i >= 0);
    ASSERT(i < N);
    intptr_t w = i >> kBitsPerWordLog2;
    uword mask = ~static_cast<uword>(0) << (i & (kBitsPerWord - 1));
    if ((data_[w] & mask) != 0) {
      uword tz = Utils::CountTrailingZerosWord(data_[w] & mask);
      return (w << kBitsPerWordLog2) + tz;
    }
    while (++w < kLengthInWords) {
      if (data_[w] != 0) {
        return (w << kBitsPerWordLog2) +
               Utils::CountTrailingZerosWord(data_[w]);
      }
    }
    return -1;
  }

  intptr_t Last() const {
    for (int w = kLengthInWords - 1; w >= 0; --w) {
      uword d = data_[w];
      if (d != 0) {
        return ((w + 1) << kBitsPerWordLog2) - Utils::CountLeadingZerosWord(d) -
               1;
      }
    }
    return -1;
  }

  intptr_t ClearLastAndFindPrevious(intptr_t current_last) {
    ASSERT(Test(current_last));
    ASSERT(Last() == current_last);
    intptr_t w = current_last >> kBitsPerWordLog2;
    uword bits = data_[w];
    // Clear the current last.
    bits ^= (static_cast<uword>(1) << (current_last & (kBitsPerWord - 1)));
    data_[w] = bits;
    // Search backwards for a non-zero word.
    while (bits == 0 && w > 0) {
      bits = data_[--w];
    }
    if (bits == 0) {
      // None found.
      return -1;
    } else {
      // Bitlength incl. w, minus leading zeroes of w, minus 1 to 0-based index.
      return ((w + 1) << kBitsPerWordLog2) -
             Utils::CountLeadingZerosWord(bits) - 1;
    }
  }

  void Reset() { memset(data_, 0, sizeof(data_)); }

  intptr_t Size() const { return N; }

 private:
  static constexpr int kLengthInWords = 1 + ((N - 1) / kBitsPerWord);
  uword data_[kLengthInWords];
};

}  // namespace dart

#endif  // RUNTIME_VM_BIT_SET_H_