src/main/java/com/android/tools/r8/utils/SimpleHashMap.java

// Copyright (c) 2016, the R8 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.
package com.android.tools.r8.utils;

abstract class SimpleHashMap {

  private int size = 0;  // number of elements in this hash map.
  private int limit;  // resize when size reaches limit.
  private int mask;  // length - 1.

  // Constants for capacity.
  static final int MIN_CAPACITY = 2;
  static final int DEFAULT_CAPACITY = 50;

  // Constant for loadfactor.
  static final double MIN_LOAD_FACTOR = 0.2;
  static final double MAX_LOAD_FACTOR = 0.8;
  static final double DEFAULT_LOAD_FACTOR = 0.6;

  SimpleHashMap() {
    this(DEFAULT_CAPACITY);
  }

  SimpleHashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
  }

  SimpleHashMap(int initialCapacity, double loadFactor) {
    initialCapacity = Math.max(MIN_CAPACITY, initialCapacity);
    loadFactor = Math.min(MAX_LOAD_FACTOR, Math.max(MIN_LOAD_FACTOR, loadFactor));
    final int initialLength = roundToPow2((int) ((double) initialCapacity / loadFactor));
    initialize(initialLength, (int) ((double) initialLength * loadFactor));
  }

  public int size() {
    return size;
  }

  public String toString() {
    return this.getClass().getName() + ", " + size + "(length " + length() + ")";
  }

  int length() {
    return mask + 1;
  }

  void initialize(final int length, final int limit) {
    size = 0;
    mask = length - 1;
    this.limit = limit;
  }

  void resize() {
    // Double length and limit.
    initialize(length() << 1, limit << 1);
  }

  void ensureCapacity() {
    if (size >= limit) {
      resize();
    }
  }

  void incrementSize() {
    size++;
  }

  private int roundToPow2(int number) {
    number--;
    number |= number >> 1;
    number |= number >> 2;
    number |= number >> 4;
    number |= number >> 8;
    number |= number >> 16;
    return number + 1;
  }

  int firstProbe(final int hash) {
    return hash & mask;
  }

  int nextProbe(final int last, final int index) {
    return (last + index) & mask;
  }
}