/*
 * Copyright (c) 1997, 2025, Oracle and/or its affiliates. All rights reserved.
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
 *
 * This code is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License version 2 only, as
 * published by the Free Software Foundation.
 *
 * This code is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
 * version 2 for more details (a copy is included in the LICENSE file that
 * accompanied this code).
 *
 * You should have received a copy of the GNU General Public License version
 * 2 along with this work; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
 *
 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
 * or visit www.oracle.com if you need additional information or have any
 * questions.
 *
 */

#include "memory/allocation.inline.hpp"
#include "memory/resourceArea.hpp"
#include "runtime/atomic.hpp"
#include "utilities/bitMap.inline.hpp"
#include "utilities/copy.hpp"
#include "utilities/debug.hpp"
#include "utilities/population_count.hpp"

using bm_word_t = BitMap::bm_word_t;
using idx_t = BitMap::idx_t;

STATIC_ASSERT(sizeof(bm_word_t) == BytesPerWord); // "Implementation assumption."

// For the BitMaps with allocators that don't support reallocate
template <class BitMapWithAllocator>
static bm_word_t* pseudo_reallocate(const BitMapWithAllocator& derived, bm_word_t* old_map, size_t old_size_in_words, size_t new_size_in_words) {
  assert(new_size_in_words > 0, "precondition");

  bm_word_t* map = derived.allocate(new_size_in_words);
  if (old_map != nullptr) {
    Copy::disjoint_words((HeapWord*)old_map, (HeapWord*) map,
        MIN2(old_size_in_words, new_size_in_words));
  }

  derived.free(old_map, old_size_in_words);

  return map;
}

template <class BitMapWithAllocator>
void GrowableBitMap<BitMapWithAllocator>::initialize(idx_t size_in_bits, bool clear) {
  assert(map() == nullptr, "precondition");
  assert(size() == 0,   "precondition");

  resize(size_in_bits, clear);
}

template <class BitMapWithAllocator>
void GrowableBitMap<BitMapWithAllocator>::reinitialize(idx_t new_size_in_bits, bool clear) {
  // Remove previous bits - no need to clear
  resize(0, false /* clear */);

  initialize(new_size_in_bits, clear);
}

template <class BitMapWithAllocator>
void GrowableBitMap<BitMapWithAllocator>::resize(idx_t new_size_in_bits, bool clear) {
  const size_t old_size_in_bits = size();
  bm_word_t* const old_map = map();

  const size_t old_size_in_words = calc_size_in_words(size());
  const size_t new_size_in_words = calc_size_in_words(new_size_in_bits);

  BitMapWithAllocator* derived = static_cast<BitMapWithAllocator*>(this);

  if (new_size_in_words == 0) {
    derived->free(old_map, old_size_in_words);
    update(nullptr, 0);
    return;
  }


  bm_word_t* map = derived->reallocate(old_map, old_size_in_words, new_size_in_words);
  if (clear && (new_size_in_bits > old_size_in_bits)) {
    // If old_size_in_bits is not word-aligned, then the preceding
    // copy can include some trailing bits in the final copied word
    // that also need to be cleared.  See clear_range_within_word.
    bm_word_t mask = bit_mask(old_size_in_bits) - 1;
    map[raw_to_words_align_down(old_size_in_bits)] &= mask;
    // Clear the remaining full words.
    clear_range_of_words(map, old_size_in_words, new_size_in_words);
  }

  update(map, new_size_in_bits);
}

template <class BitMapWithAllocator>
bm_word_t* GrowableBitMap<BitMapWithAllocator>::copy_of_range(idx_t start_bit, idx_t end_bit) {
  assert(start_bit < end_bit, "End bit must come after start bit");
  assert(end_bit <= size(), "End bit not in bitmap");

  // We might have extra bits at the end that we don't want to lose
  const idx_t cutoff = bit_in_word(end_bit);
  const idx_t start_word = to_words_align_down(start_bit);
  const idx_t end_word = to_words_align_up(end_bit);
  const bm_word_t* const old_map = map();

  const BitMapWithAllocator* const derived = static_cast<BitMapWithAllocator*>(this);

  bm_word_t* const new_map = derived->allocate(end_word - start_word);

  // All words need to be shifted by this amount
  const idx_t shift = bit_in_word(start_bit);
  // Bits shifted out by a word need to be passed into the next
  bm_word_t carry = 0;

  // Iterate the map backwards as the shift will result in carry-out bits
  for (idx_t i = end_word; i-- > start_word;) {
    new_map[i-start_word] = old_map[i] >> shift;

    if (shift != 0) {
      new_map[i-start_word] |= carry;
      carry = old_map[i] << (BitsPerWord - shift);
    }
  }

  return new_map;
}

template <class BitMapWithAllocator>
void GrowableBitMap<BitMapWithAllocator>::truncate(idx_t start_bit, idx_t end_bit) {
  const size_t old_size_in_words = calc_size_in_words(size());
  const idx_t new_size_in_bits = end_bit - start_bit;
  bm_word_t* const old_map = map();

  bm_word_t* const new_map = copy_of_range(start_bit, end_bit);

  const BitMapWithAllocator* const derived = static_cast<BitMapWithAllocator*>(this);
  // Free and clear old map to avoid left over bits
  derived->free(old_map, old_size_in_words);
  update(nullptr, 0);
  update(new_map, new_size_in_bits);
}

ArenaBitMap::ArenaBitMap(Arena* arena, idx_t size_in_bits, bool clear)
  : GrowableBitMap<ArenaBitMap>(), _arena(arena) {
  initialize(size_in_bits, clear);
}

bm_word_t* ArenaBitMap::allocate(idx_t size_in_words) const {
  return (bm_word_t*)_arena->Amalloc(size_in_words * BytesPerWord);
}

bm_word_t* ArenaBitMap::reallocate(bm_word_t* old_map, size_t old_size_in_words, size_t new_size_in_words) const {
  return pseudo_reallocate(*this, old_map, old_size_in_words, new_size_in_words);
}

ResourceBitMap::ResourceBitMap(idx_t size_in_bits, bool clear)
  : GrowableBitMap<ResourceBitMap>() {
  initialize(size_in_bits, clear);
}

bm_word_t* ResourceBitMap::allocate(idx_t size_in_words) const {
  return (bm_word_t*)NEW_RESOURCE_ARRAY(bm_word_t, size_in_words);
}

bm_word_t* ResourceBitMap::reallocate(bm_word_t* old_map, size_t old_size_in_words, size_t new_size_in_words) const {
  return pseudo_reallocate(*this, old_map, old_size_in_words, new_size_in_words);
}

CHeapBitMap::CHeapBitMap(idx_t size_in_bits, MemTag mem_tag, bool clear)
  : GrowableBitMap<CHeapBitMap>(), _mem_tag(mem_tag) {
  initialize(size_in_bits, clear);
}

CHeapBitMap::~CHeapBitMap() {
  free(map(), size_in_words());
}

bm_word_t* CHeapBitMap::allocate(idx_t size_in_words) const {
  return MallocArrayAllocator<bm_word_t>::allocate(size_in_words, _mem_tag);
}

// GrowableBitMap<T>::resize uses free(ptr, size) for T as CHeapBitMap, ArenaBitMap and ResourceBitMap allocators.
// The free(ptr, size) signature is kept but the size parameter is ignored.
void CHeapBitMap::free(bm_word_t* map, idx_t size_in_words) const {
  MallocArrayAllocator<bm_word_t>::free(map);
}

bm_word_t* CHeapBitMap::reallocate(bm_word_t* map, size_t old_size_in_words, size_t new_size_in_words) const {
  return MallocArrayAllocator<bm_word_t>::reallocate(map, new_size_in_words, _mem_tag);
}

#ifdef ASSERT
void BitMap::verify_index(idx_t bit) const {
  assert(bit < _size,
         "BitMap index out of bounds: %zu >= %zu",
         bit, _size);
}

void BitMap::verify_limit(idx_t bit) const {
  assert(bit <= _size,
         "BitMap limit out of bounds: %zu > %zu",
         bit, _size);
}

void BitMap::verify_range(idx_t beg, idx_t end) const {
  assert(beg <= end,
         "BitMap range error: %zu > %zu", beg, end);
  verify_limit(end);
}
#endif // #ifdef ASSERT

void BitMap::pretouch() {
  os::pretouch_memory(word_addr(0), word_addr(size()));
}

void BitMap::set_range_within_word(idx_t beg, idx_t end) {
  // With a valid range (beg <= end), this test ensures that end != 0, as
  // required by inverted_bit_mask_for_range.  Also avoids an unnecessary write.
  if (beg != end) {
    bm_word_t mask = inverted_bit_mask_for_range(beg, end);
    *word_addr(beg) |= ~mask;
  }
}

void BitMap::clear_range_within_word(idx_t beg, idx_t end) {
  // With a valid range (beg <= end), this test ensures that end != 0, as
  // required by inverted_bit_mask_for_range.  Also avoids an unnecessary write.
  if (beg != end) {
    bm_word_t mask = inverted_bit_mask_for_range(beg, end);
    *word_addr(beg) &= mask;
  }
}

void BitMap::par_put_range_within_word(idx_t beg, idx_t end, bool value) {
  assert(value == 0 || value == 1, "0 for clear, 1 for set");
  // With a valid range (beg <= end), this test ensures that end != 0, as
  // required by inverted_bit_mask_for_range.  Also avoids an unnecessary write.
  if (beg != end) {
    volatile bm_word_t* pw = word_addr(beg);
    bm_word_t w = Atomic::load(pw);
    bm_word_t mr = inverted_bit_mask_for_range(beg, end);
    bm_word_t nw = value ? (w | ~mr) : (w & mr);
    while (true) {
      bm_word_t res = Atomic::cmpxchg(pw, w, nw);
      if (res == w) break;
      w  = res;
      nw = value ? (w | ~mr) : (w & mr);
    }
  }
}

void BitMap::set_range(idx_t beg, idx_t end) {
  verify_range(beg, end);

  idx_t beg_full_word = to_words_align_up(beg);
  idx_t end_full_word = to_words_align_down(end);

  if (beg_full_word < end_full_word) {
    // The range includes at least one full word.
    set_range_within_word(beg, bit_index(beg_full_word));
    set_range_of_words(beg_full_word, end_full_word);
    set_range_within_word(bit_index(end_full_word), end);
  } else {
    // The range spans at most 2 partial words.
    idx_t boundary = MIN2(bit_index(beg_full_word), end);
    set_range_within_word(beg, boundary);
    set_range_within_word(boundary, end);
  }
}

void BitMap::clear_range(idx_t beg, idx_t end) {
  verify_range(beg, end);

  idx_t beg_full_word = to_words_align_up(beg);
  idx_t end_full_word = to_words_align_down(end);

  if (beg_full_word < end_full_word) {
    // The range includes at least one full word.
    clear_range_within_word(beg, bit_index(beg_full_word));
    clear_range_of_words(beg_full_word, end_full_word);
    clear_range_within_word(bit_index(end_full_word), end);
  } else {
    // The range spans at most 2 partial words.
    idx_t boundary = MIN2(bit_index(beg_full_word), end);
    clear_range_within_word(beg, boundary);
    clear_range_within_word(boundary, end);
  }
}

bool BitMap::is_small_range_of_words(idx_t beg_full_word, idx_t end_full_word) {
  // There is little point to call large version on small ranges.
  // Need to check carefully, keeping potential idx_t over/underflow in mind,
  // because beg_full_word > end_full_word can occur when beg and end are in
  // the same word.
  // The threshold should be at least one word.
  STATIC_ASSERT(small_range_words >= 1);
  return beg_full_word + small_range_words >= end_full_word;
}

void BitMap::set_large_range(idx_t beg, idx_t end) {
  verify_range(beg, end);

  idx_t beg_full_word = to_words_align_up(beg);
  idx_t end_full_word = to_words_align_down(end);

  if (is_small_range_of_words(beg_full_word, end_full_word)) {
    set_range(beg, end);
    return;
  }

  // The range includes at least one full word.
  set_range_within_word(beg, bit_index(beg_full_word));
  set_large_range_of_words(beg_full_word, end_full_word);
  set_range_within_word(bit_index(end_full_word), end);
}

void BitMap::clear_large_range(idx_t beg, idx_t end) {
  verify_range(beg, end);

  idx_t beg_full_word = to_words_align_up(beg);
  idx_t end_full_word = to_words_align_down(end);

  if (is_small_range_of_words(beg_full_word, end_full_word)) {
    clear_range(beg, end);
    return;
  }

  // The range includes at least one full word.
  clear_range_within_word(beg, bit_index(beg_full_word));
  clear_large_range_of_words(beg_full_word, end_full_word);
  clear_range_within_word(bit_index(end_full_word), end);
}

void BitMap::at_put(idx_t bit, bool value) {
  if (value) {
    set_bit(bit);
  } else {
    clear_bit(bit);
  }
}

// Return true to indicate that this thread changed
// the bit, false to indicate that someone else did.
// In either case, the requested bit is in the
// requested state some time during the period that
// this thread is executing this call. More importantly,
// if no other thread is executing an action to
// change the requested bit to a state other than
// the one that this thread is trying to set it to,
// then the bit is in the expected state
// at exit from this method. However, rather than
// make such a strong assertion here, based on
// assuming such constrained use (which though true
// today, could change in the future to service some
// funky parallel algorithm), we encourage callers
// to do such verification, as and when appropriate.
bool BitMap::par_at_put(idx_t bit, bool value) {
  return value ? par_set_bit(bit) : par_clear_bit(bit);
}

void BitMap::at_put_range(idx_t beg, idx_t end, bool value) {
  if (value) {
    set_range(beg, end);
  } else {
    clear_range(beg, end);
  }
}

void BitMap::par_at_put_range(idx_t beg, idx_t end, bool value) {
  verify_range(beg, end);

  idx_t beg_full_word = to_words_align_up(beg);
  idx_t end_full_word = to_words_align_down(end);

  if (beg_full_word < end_full_word) {
    // The range includes at least one full word.
    par_put_range_within_word(beg, bit_index(beg_full_word), value);
    if (value) {
      set_range_of_words(beg_full_word, end_full_word);
    } else {
      clear_range_of_words(beg_full_word, end_full_word);
    }
    par_put_range_within_word(bit_index(end_full_word), end, value);
  } else {
    // The range spans at most 2 partial words.
    idx_t boundary = MIN2(bit_index(beg_full_word), end);
    par_put_range_within_word(beg, boundary, value);
    par_put_range_within_word(boundary, end, value);
  }

}

void BitMap::at_put_large_range(idx_t beg, idx_t end, bool value) {
  if (value) {
    set_large_range(beg, end);
  } else {
    clear_large_range(beg, end);
  }
}

void BitMap::par_at_put_large_range(idx_t beg, idx_t end, bool value) {
  verify_range(beg, end);

  idx_t beg_full_word = to_words_align_up(beg);
  idx_t end_full_word = to_words_align_down(end);

  if (is_small_range_of_words(beg_full_word, end_full_word)) {
    par_at_put_range(beg, end, value);
    return;
  }

  // The range includes at least one full word.
  par_put_range_within_word(beg, bit_index(beg_full_word), value);
  if (value) {
    set_large_range_of_words(beg_full_word, end_full_word);
  } else {
    clear_large_range_of_words(beg_full_word, end_full_word);
  }
  par_put_range_within_word(bit_index(end_full_word), end, value);
}

inline bm_word_t tail_mask(idx_t tail_bits) {
  assert(tail_bits != 0, "precondition"); // Works, but shouldn't be called.
  assert(tail_bits < (idx_t)BitsPerWord, "precondition");
  return (bm_word_t(1) << tail_bits) - 1;
}

// Get the low tail_bits of value, which is the last partial word of a map.
inline bm_word_t tail_of_map(bm_word_t value, idx_t tail_bits) {
  return value & tail_mask(tail_bits);
}

// Compute the new last word of a map with a non-aligned length.
// new_value has the new trailing bits of the map in the low tail_bits.
// old_value is the last word of the map, including bits beyond the end.
// Returns old_value with the low tail_bits replaced by the corresponding
// bits in new_value.
inline bm_word_t merge_tail_of_map(bm_word_t new_value,
                                   bm_word_t old_value,
                                   idx_t tail_bits) {
  bm_word_t mask = tail_mask(tail_bits);
  return (new_value & mask) | (old_value & ~mask);
}

bool BitMap::contains(const BitMap& other) const {
  assert(size() == other.size(), "must have same size");
  const bm_word_t* dest_map = map();
  const bm_word_t* other_map = other.map();
  idx_t limit = to_words_align_down(size());
  for (idx_t index = 0; index < limit; ++index) {
    // false if other bitmap has bits set which are clear in this bitmap.
    if ((~dest_map[index] & other_map[index]) != 0) return false;
  }
  idx_t rest = bit_in_word(size());
  // true unless there is a partial-word tail in which the other
  // bitmap has bits set which are clear in this bitmap.
  return (rest == 0) || tail_of_map(~dest_map[limit] & other_map[limit], rest) == 0;
}

bool BitMap::intersects(const BitMap& other) const {
  assert(size() == other.size(), "must have same size");
  const bm_word_t* dest_map = map();
  const bm_word_t* other_map = other.map();
  idx_t limit = to_words_align_down(size());
  for (idx_t index = 0; index < limit; ++index) {
    if ((dest_map[index] & other_map[index]) != 0) return true;
  }
  idx_t rest = bit_in_word(size());
  // false unless there is a partial-word tail with non-empty intersection.
  return (rest > 0) && tail_of_map(dest_map[limit] & other_map[limit], rest) != 0;
}

void BitMap::set_union(const BitMap& other) {
  assert(size() == other.size(), "must have same size");
  bm_word_t* dest_map = map();
  const bm_word_t* other_map = other.map();
  idx_t limit = to_words_align_down(size());
  for (idx_t index = 0; index < limit; ++index) {
    dest_map[index] |= other_map[index];
  }
  idx_t rest = bit_in_word(size());
  if (rest > 0) {
    bm_word_t orig = dest_map[limit];
    dest_map[limit] = merge_tail_of_map(orig | other_map[limit], orig, rest);
  }
}

void BitMap::set_difference(const BitMap& other) {
  assert(size() == other.size(), "must have same size");
  bm_word_t* dest_map = map();
  const bm_word_t* other_map = other.map();
  idx_t limit = to_words_align_down(size());
  for (idx_t index = 0; index < limit; ++index) {
    dest_map[index] &= ~other_map[index];
  }
  idx_t rest = bit_in_word(size());
  if (rest > 0) {
    bm_word_t orig = dest_map[limit];
    dest_map[limit] = merge_tail_of_map(orig & ~other_map[limit], orig, rest);
  }
}

void BitMap::set_intersection(const BitMap& other) {
  assert(size() == other.size(), "must have same size");
  bm_word_t* dest_map = map();
  const bm_word_t* other_map = other.map();
  idx_t limit = to_words_align_down(size());
  for (idx_t index = 0; index < limit; ++index) {
    dest_map[index] &= other_map[index];
  }
  idx_t rest = bit_in_word(size());
  if (rest > 0) {
    bm_word_t orig = dest_map[limit];
    dest_map[limit] = merge_tail_of_map(orig & other_map[limit], orig, rest);
  }
}

bool BitMap::set_union_with_result(const BitMap& other) {
  assert(size() == other.size(), "must have same size");
  bool changed = false;
  bm_word_t* dest_map = map();
  const bm_word_t* other_map = other.map();
  idx_t limit = to_words_align_down(size());
  for (idx_t index = 0; index < limit; ++index) {
    bm_word_t orig = dest_map[index];
    bm_word_t temp = orig | other_map[index];
    changed = changed || (temp != orig);
    dest_map[index] = temp;
  }
  idx_t rest = bit_in_word(size());
  if (rest > 0) {
    bm_word_t orig = dest_map[limit];
    bm_word_t temp = merge_tail_of_map(orig | other_map[limit], orig, rest);
    changed = changed || (temp != orig);
    dest_map[limit] = temp;
  }
  return changed;
}

bool BitMap::set_difference_with_result(const BitMap& other) {
  assert(size() == other.size(), "must have same size");
  bool changed = false;
  bm_word_t* dest_map = map();
  const bm_word_t* other_map = other.map();
  idx_t limit = to_words_align_down(size());
  for (idx_t index = 0; index < limit; ++index) {
    bm_word_t orig = dest_map[index];
    bm_word_t temp = orig & ~other_map[index];
    changed = changed || (temp != orig);
    dest_map[index] = temp;
  }
  idx_t rest = bit_in_word(size());
  if (rest > 0) {
    bm_word_t orig = dest_map[limit];
    bm_word_t temp = merge_tail_of_map(orig & ~other_map[limit], orig, rest);
    changed = changed || (temp != orig);
    dest_map[limit] = temp;
  }
  return changed;
}

bool BitMap::set_intersection_with_result(const BitMap& other) {
  assert(size() == other.size(), "must have same size");
  bool changed = false;
  bm_word_t* dest_map = map();
  const bm_word_t* other_map = other.map();
  idx_t limit = to_words_align_down(size());
  for (idx_t index = 0; index < limit; ++index) {
    bm_word_t orig = dest_map[index];
    bm_word_t temp = orig & other_map[index];
    changed = changed || (temp != orig);
    dest_map[index] = temp;
  }
  idx_t rest = bit_in_word(size());
  if (rest > 0) {
    bm_word_t orig = dest_map[limit];
    bm_word_t temp = merge_tail_of_map(orig & other_map[limit], orig, rest);
    changed = changed || (temp != orig);
    dest_map[limit] = temp;
  }
  return changed;
}

void BitMap::set_from(const BitMap& other) {
  assert(size() == other.size(), "must have same size");
  bm_word_t* dest_map = map();
  const bm_word_t* other_map = other.map();
  idx_t copy_words = to_words_align_down(size());
  Copy::disjoint_words((HeapWord*)other_map, (HeapWord*)dest_map, copy_words);
  idx_t rest = bit_in_word(size());
  if (rest > 0) {
    dest_map[copy_words] = merge_tail_of_map(other_map[copy_words],
                                             dest_map[copy_words],
                                             rest);
  }
}

bool BitMap::is_same(const BitMap& other) const {
  assert(size() == other.size(), "must have same size");
  const bm_word_t* dest_map = map();
  const bm_word_t* other_map = other.map();
  idx_t limit = to_words_align_down(size());
  for (idx_t index = 0; index < limit; ++index) {
    if (dest_map[index] != other_map[index]) return false;
  }
  idx_t rest = bit_in_word(size());
  return (rest == 0) || (tail_of_map(dest_map[limit] ^ other_map[limit], rest) == 0);
}

bool BitMap::is_full() const {
  const bm_word_t* words = map();
  idx_t limit = to_words_align_down(size());
  for (idx_t index = 0; index < limit; ++index) {
    if (~words[index] != 0) return false;
  }
  idx_t rest = bit_in_word(size());
  return (rest == 0) || (tail_of_map(~words[limit], rest) == 0);
}

bool BitMap::is_empty() const {
  const bm_word_t* words = map();
  idx_t limit = to_words_align_down(size());
  for (idx_t index = 0; index < limit; ++index) {
    if (words[index] != 0) return false;
  }
  idx_t rest = bit_in_word(size());
  return (rest == 0) || (tail_of_map(words[limit], rest) == 0);
}

void BitMap::clear_large() {
  clear_large_range_of_words(0, size_in_words());
}

BitMap::idx_t BitMap::count_one_bits_in_range_of_words(idx_t beg_full_word, idx_t end_full_word) const {
  idx_t sum = 0;
  for (idx_t i = beg_full_word; i < end_full_word; i++) {
    bm_word_t w = map()[i];
    sum += population_count(w);
  }
  return sum;
}

BitMap::idx_t BitMap::count_one_bits_within_word(idx_t beg, idx_t end) const {
  if (beg != end) {
    assert(end > beg, "must be");
    bm_word_t mask = ~inverted_bit_mask_for_range(beg, end);
    bm_word_t w = *word_addr(beg);
    w &= mask;
    return population_count(w);
  }
  return 0;
}

BitMap::idx_t BitMap::count_one_bits() const {
  return count_one_bits(0, size());
}

// Returns the number of bits set within  [beg, end).
BitMap::idx_t BitMap::count_one_bits(idx_t beg, idx_t end) const {
  verify_range(beg, end);

  idx_t beg_full_word = to_words_align_up(beg);
  idx_t end_full_word = to_words_align_down(end);

  idx_t sum = 0;

  if (beg_full_word < end_full_word) {
    // The range includes at least one full word.
    sum += count_one_bits_within_word(beg, bit_index(beg_full_word));
    sum += count_one_bits_in_range_of_words(beg_full_word, end_full_word);
    sum += count_one_bits_within_word(bit_index(end_full_word), end);
  } else {
    // The range spans at most 2 partial words.
    idx_t boundary = MIN2(bit_index(beg_full_word), end);
    sum += count_one_bits_within_word(beg, boundary);
    sum += count_one_bits_within_word(boundary, end);
  }

  assert(sum <= (end - beg), "must be");

  return sum;

}

void BitMap::print_range_on(outputStream* st, const char* prefix) const {
  st->print_cr("%s[" PTR_FORMAT ", " PTR_FORMAT ")",
      prefix, p2i(map()), p2i((char*)map() + (size() >> LogBitsPerByte)));
}

void BitMap::write_to(bm_word_t* buffer, size_t buffer_size_in_bytes) const {
  assert(buffer_size_in_bytes == size_in_bytes(), "must be");
  memcpy(buffer, _map, size_in_bytes());
}

#ifdef ASSERT
void BitMap::IteratorImpl::assert_not_empty() const {
  assert(!is_empty(), "empty iterator");
}
#endif

void BitMap::print_on(outputStream* st) const {
  st->print("Bitmap (%zu bits):", size());
  for (idx_t index = 0; index < size(); index++) {
    if ((index % 64) == 0) {
      st->cr();
      st->print("%5zu:", index);
    }
    if ((index % 8) == 0) {
      st->print(" ");
    }
    st->print("%c", at(index) ? 'S' : '.');
  }
  st->cr();
}

template class GrowableBitMap<ArenaBitMap>;
template class GrowableBitMap<ResourceBitMap>;
template class GrowableBitMap<CHeapBitMap>;