src/hotspot/share/utilities/packedTable.cpp

/*
 * Copyright (c) 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 <cstring>

#include "utilities/align.hpp"
#include "utilities/count_leading_zeros.hpp"
#include "utilities/packedTable.hpp"

// The thresholds are inclusive, and in practice the limits are rounded
// to the nearest power-of-two - 1.
// Based on the max_key and max_value we figure out the number of bits required to store
// key and value; imagine that only as bits (not aligned to byte boundary... yet).
// Then we concatenate the bits for key and value, and 'add' 1-7 padding zeroes
// (high-order bits) to align on bytes.
// In the end we have each element in the table consuming 1-8 bytes (case with 0 bits for key
// is ruled out).
PackedTableBase::PackedTableBase(uint32_t max_key, uint32_t max_value) {
  unsigned int key_bits = max_key == 0 ? 0 : 32 - count_leading_zeros(max_key);
  unsigned int value_bits = max_value == 0 ? 0 : 32 - count_leading_zeros(max_value);
  _element_bytes = align_up(key_bits + value_bits, 8) / 8;
  // shifting left by 32 is undefined behaviour, and in practice returns 1
  _key_mask = key_bits >= 32 ? -1 : (1U << key_bits) - 1;
  _value_shift = key_bits;
  _value_mask = value_bits >= 32 ? -1 : (1U << value_bits) - 1;
  guarantee(_element_bytes > 0, "wouldn't work");
  assert(_element_bytes <= sizeof(uint64_t), "shouldn't happen");
}

// Note: we require the supplier to provide the elements in the final order as we can't easily sort
// within this method - qsort() accepts only pure function as comparator.
void PackedTableBuilder::fill(u1* table, size_t table_length, Supplier &supplier) const {
  uint32_t key, value;
  size_t offset = 0;
  for (; offset <= table_length && supplier.next(&key, &value); offset += _element_bytes) {
    assert((key & ~_key_mask) == 0, "key out of bounds");
    assert((value & ~_value_mask) == 0, "value out of bounds: %x vs. %x (%x)", value, _value_mask, ~_value_mask);
    uint64_t element = static_cast<uint64_t>(key) | (static_cast<uint64_t>(value) << _value_shift);
    for (unsigned int i = 0; i < _element_bytes; ++i) {
      table[offset + i] = static_cast<u1>(0xFF & element);
      element >>= 8;
    }
  }

  assert(offset == table_length, "Did not fill whole array");
  assert(!supplier.next(&key, &value), "Supplier has more elements");
}

uint64_t PackedTableLookup::read_element(size_t offset) const {
  uint64_t element = 0;
  for (unsigned int i = 0; i < _element_bytes; ++i) {
    element |= static_cast<uint64_t>(_table[offset + i]) << (8 * i);
  }
  assert((element & ~((uint64_t) _key_mask | ((uint64_t) _value_mask << _value_shift))) == 0, "read too much");
  return element;
}

bool PackedTableLookup::search(Comparator& comparator, uint32_t* found_key, uint32_t* found_value) const {
  unsigned int low = 0, high = checked_cast<unsigned int>(_table_length / _element_bytes);
  assert(low < high, "must be");
  while (low < high) {
    unsigned int mid = low + (high - low) / 2;
    assert(mid >= low && mid < high, "integer overflow?");
    uint64_t element = read_element(_element_bytes * mid);
    // Ignoring high 32 bits in element on purpose
    uint32_t key = static_cast<uint32_t>(element) & _key_mask;
    int cmp = comparator.compare_to(key);
    if (cmp == 0) {
      *found_key = key;
      // Since __builtin_memcpy in read_element does not copy bits outside the element
      // anything above _value_mask << _value_shift should be zero.
      *found_value = checked_cast<uint32_t>(element >> _value_shift) & _value_mask;
      return true;
    } else if (cmp < 0) {
      high = mid;
    } else {
      low = mid + 1;
    }
  }
  return false;
}

#ifdef ASSERT
void PackedTableLookup::validate_order(Comparator &comparator) const {
  auto validator = [&] (size_t offset, uint32_t key, uint32_t value) {
    if (offset != 0) {
      assert(comparator.compare_to(key) < 0, "not sorted");
    }
    comparator.reset(key);
  };
  iterate(validator);
}
#endif