vmkit/mmtk/java/src/org/mmtk/utility/SimpleHashtable.java

/*
 *  This file is part of the Jikes RVM project (http://jikesrvm.org).
 *
 *  This file is licensed to You under the Eclipse Public License (EPL);
 *  You may not use this file except in compliance with the License. You
 *  may obtain a copy of the License at
 *
 *      http://www.opensource.org/licenses/eclipse-1.0.php
 *
 *  See the COPYRIGHT.txt file distributed with this work for information
 *  regarding copyright ownership.
 */
package org.mmtk.utility;

import org.mmtk.policy.RawPageSpace;
import org.mmtk.vm.VM;

import org.vmmagic.pragma.*;
import org.vmmagic.unboxed.*;

/**
 * This class implements a simple hashtable. It is intended for use
 * in sanity checking or debugging, not high-performance algorithms.<p>
 *
 * This class is not thread safe.
 */
@Uninterruptible public abstract class SimpleHashtable implements Constants {
  /** The number of low order bits to ignore */
  private static final int HASH_SHIFT = 3;

  /** Offset to the key */
  private static final Offset KEY_OFFSET = Offset.zero();

  /** Offset to the data */
  private static final Offset DATA_OFFSET = Offset.fromIntSignExtend(BYTES_IN_WORD);

  /** The size of each entry in the table */
  private final Extent entrySize;

  /** The mask to use to get the hash code */
  private final Word mask;

  /** The start address of the data table */
  private Address base;

  /** The full size of the table */
  private final Extent size;

  /** The space to use for allocating the data structure */
  private final RawPageSpace space;

  /** Is this table valid (created) */
  private boolean valid;

  /**
   * Create a new data table of a specified size.
   *
   * @param rps The space to acquire the data structure from.
   * @param logSize The log of the number of table entries.
   * @param es The size of each entry.
   */
  protected SimpleHashtable(RawPageSpace rps, int logSize, Extent es) {
    mask = Word.fromIntZeroExtend((1 << logSize) - 1);
    entrySize = es.plus(BYTES_IN_WORD);
    size = Extent.fromIntZeroExtend((1 << logSize) * entrySize.toInt());
    base = Address.zero();
    space = rps;
    valid = false;
  }

  /**
   * Create a (zeroed) table.
   */
  public final void acquireTable() {
    base = space.acquire(Conversions.bytesToPages(size));
    VM.memory.zero(base, size);
    valid = true;
  }

  /**
   * Drop the table (after collection).
   */
  public final void releaseTable() {
    space.release(base);
    valid = false;
  }

  /**
   * @return True if this table has backing data and is ready for use.
   */
  public final boolean isValid() {
    return valid;
  }

  /**
   * Retrieve a pointer to the entry for the given object, or zero if one
   * does not exist, unless create is passed.<p>
   *
   * If create is true, the return is guaranteed to be non-null.
   *
   * @param key The key used to lookup.
   * @param create Create a new entry if not found.
   * @return A pointer to the reference or null.
   */
  @Inline
  public final Address getEntry(Word key, boolean create) {
    int startIndex = computeHash(key);
    int index = startIndex;
    Word curAddress;
    Address entry;
    do {
      entry = getEntry(index);
      curAddress = entry.loadWord(KEY_OFFSET);
      index = (index + 1) & mask.toInt();
    } while(curAddress.NE(key) &&
            !curAddress.isZero() &&
            index != startIndex);

    if (index == startIndex) {
      VM.assertions.fail("No room left in table!");
    }

    if (curAddress.isZero()) {
      if (!create) return Address.zero();
      entry.store(key, KEY_OFFSET);
    }

    return entry;
  }

  /**
   * Compute the hashtable index for a given object.
   *
   * @param key The key.
   * @return The index.
   */
  @Inline
  private int computeHash(Word key) {
    return key.rshl(HASH_SHIFT).and(mask).toInt();
  }

  /**
   * Return the address of a specified entry in the table.
   *
   * @param index The index of the entry.
   * @return An address to the entry.
   */
  @Inline
  private Address getEntry(int index) {
    return base.plus(Extent.fromIntZeroExtend(index * entrySize.toInt()));
  }

  /**
   * Does the passed object have an entry in the table?
   *
   * @param key The key to find an entry for
   * @return True if there is an entry for that object.
   */
  public final boolean contains(Word key) {
    return !getEntry(key, false).isZero();
  }

  /**
   * @return The first non-zero element in the table, or null if
   * the table is empty.
   */
  public final Address getFirst() {
    return getNext(base.minus(entrySize));
  }

  /**
   * The next element in the table after the passed entry, or
   * null if it is the last entry.
   *
   * @param curr The object to look for the next entry from.
   * @return The next entry or null.
   */
  public final Address getNext(Address curr) {
    Address entry = curr.plus(entrySize);
    while (entry.LT(base.plus(size))) {
      if (!entry.loadWord().isZero()) return entry;
      entry = entry.plus(entrySize);
    }
    return Address.zero();
  }

  /**
   * Given an address of an entry, return a pointer to the payload.
   *
   * @param entry The entry
   * @return The object reference.
   */
  public static Address getPayloadAddress(Address entry) {
    return entry.plus(DATA_OFFSET);
  }

  /**
   * Given a key, return a pointer to the payload.
   *
   * @param key The key
   * @return The object reference.
   */
  public final Address getPayloadAddress(Word key) {
    Address entry = getEntry(key, false);
    if (entry.isZero()) return Address.zero();

    return entry.plus(DATA_OFFSET);
  }


  /**
   * Return the key for a given entry.
   *
   * @param entry The entry.
   * @return The key.
   */
  public static Word getKey(Address entry) {
    return entry.loadWord(KEY_OFFSET);
  }

  /**
   * Update the key for a given entry. This operation is not
   * safe without rehashing
   *
   * @param entry The entry to update.
   * @param key The new key.
   */
  public static void replaceKey(Address entry, Word key) {
    entry.store(key, KEY_OFFSET);
  }

}