/*
 * Copyright 2005-2006 Sun Microsystems, Inc.  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 Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
 * CA 95054 USA or visit www.sun.com if you need additional information or
 * have any questions.
 *
 */

inline bool BitMap::par_set_bit(idx_t bit) {
  verify_index(bit);
  volatile idx_t* const addr = word_addr(bit);
  const idx_t mask = bit_mask(bit);
  idx_t old_val = *addr;

  do {
    const idx_t new_val = old_val | mask;
    if (new_val == old_val) {
      return false;     // Someone else beat us to it.
    }
    const idx_t cur_val = (idx_t) Atomic::cmpxchg_ptr((void*) new_val,
                                                      (volatile void*) addr,
                                                      (void*) old_val);
    if (cur_val == old_val) {
      return true;      // Success.
    }
    old_val = cur_val;  // The value changed, try again.
  } while (true);
}

inline bool BitMap::par_clear_bit(idx_t bit) {
  verify_index(bit);
  volatile idx_t* const addr = word_addr(bit);
  const idx_t mask = ~bit_mask(bit);
  idx_t old_val = *addr;

  do {
    const idx_t new_val = old_val & mask;
    if (new_val == old_val) {
      return false;     // Someone else beat us to it.
    }
    const idx_t cur_val = (idx_t) Atomic::cmpxchg_ptr((void*) new_val,
                                                      (volatile void*) addr,
                                                      (void*) old_val);
    if (cur_val == old_val) {
      return true;      // Success.
    }
    old_val = cur_val;  // The value changed, try again.
  } while (true);
}

inline BitMap::idx_t
BitMap::find_next_one_bit(idx_t beg_bit, idx_t end_bit) const
{
  verify_range(beg_bit, end_bit);
  assert(bit_in_word(end_bit) == 0, "end_bit not word-aligned");

  if (beg_bit == end_bit) {
    return beg_bit;
  }

  idx_t   index = word_index(beg_bit);
  idx_t r_index = word_index(end_bit);
  idx_t res_bit = beg_bit;

  // check bits including and to the _left_ of offset's position
  idx_t res = map(index) >> bit_in_word(res_bit);
  if (res != (uintptr_t) NoBits) {
    // find the position of the 1-bit
    for (; !(res & 1); res_bit++) {
      res = res >> 1;
    }
    assert(res_bit >= beg_bit && res_bit < end_bit, "just checking");
    return res_bit;
  }
  // skip over all word length 0-bit runs
  for (index++; index < r_index; index++) {
    res = map(index);
    if (res != (uintptr_t) NoBits) {
      // found a 1, return the offset
      for (res_bit = bit_index(index); !(res & 1); res_bit++) {
        res = res >> 1;
      }
      assert(res & 1, "tautology; see loop condition");
      assert(res_bit >= beg_bit && res_bit < end_bit, "just checking");
      return res_bit;
    }
  }
  return end_bit;
}