001/*
002 *  This file is part of the Jikes RVM project (http://jikesrvm.org).
003 *
004 *  This file is licensed to You under the Eclipse Public License (EPL);
005 *  You may not use this file except in compliance with the License. You
006 *  may obtain a copy of the License at
007 *
008 *      http://www.opensource.org/licenses/eclipse-1.0.php
009 *
010 *  See the COPYRIGHT.txt file distributed with this work for information
011 *  regarding copyright ownership.
012 */
013package org.mmtk.utility;
014
015import static org.mmtk.utility.Constants.*;
016
017import org.mmtk.policy.RawPageSpace;
018import org.mmtk.vm.VM;
019
020import org.vmmagic.pragma.*;
021import org.vmmagic.unboxed.*;
022
023/**
024 * This class implements a simple hashtable. It is intended for use
025 * in sanity checking or debugging, not high-performance algorithms.<p>
026 *
027 * This class is <i>not thread safe</i>.
028 */
029@Uninterruptible public abstract class SimpleHashtable {
030  /** The number of low order bits to ignore */
031  private static final int HASH_SHIFT = 3;
032
033  /** Offset to the key */
034  private static final Offset KEY_OFFSET = Offset.zero();
035
036  /** Offset to the data */
037  private static final Offset DATA_OFFSET = Offset.fromIntSignExtend(BYTES_IN_WORD);
038
039  /** The size of each entry in the table */
040  private final Extent entrySize;
041
042  /** The mask to use to get the hash code */
043  private final Word mask;
044
045  /** The start address of the data table */
046  private Address base;
047
048  /** The full size of the table */
049  private final Extent size;
050
051  /** The space to use for allocating the data structure */
052  private final RawPageSpace space;
053
054  /** Is this table valid (created) */
055  private boolean valid;
056
057  /**
058   * Create a new data table of a specified size.
059   *
060   * @param rps The space to acquire the data structure from.
061   * @param logSize The log of the number of table entries.
062   * @param es The size of each entry.
063   */
064  protected SimpleHashtable(RawPageSpace rps, int logSize, Extent es) {
065    mask = Word.fromIntZeroExtend((1 << logSize) - 1);
066    entrySize = es.plus(BYTES_IN_WORD);
067    size = Extent.fromIntZeroExtend((1 << logSize) * entrySize.toInt());
068    base = Address.zero();
069    space = rps;
070    valid = false;
071  }
072
073  /**
074   * Create a (zeroed) table.
075   */
076  public final void acquireTable() {
077    base = space.acquire(Conversions.bytesToPages(size));
078    VM.memory.zero(false, base, size);
079    valid = true;
080  }
081
082  /**
083   * Drop the table (after collection).
084   */
085  public final void releaseTable() {
086    space.release(base);
087    valid = false;
088  }
089
090  /**
091   * @return True if this table has backing data and is ready for use.
092   */
093  public final boolean isValid() {
094    return valid;
095  }
096
097  /**
098   * Retrieve a pointer to the entry for the given object, or zero if one
099   * does not exist, unless create is passed.<p>
100   *
101   * If create is {@code true}, the return is guaranteed to be non-{@code null}.
102   *
103   * @param key The key used to lookup.
104   * @param create Create a new entry if not found.
105   * @return A pointer to the reference or {@code null}.
106   */
107  @Inline
108  public final Address getEntry(Word key, boolean create) {
109    int startIndex = computeHash(key);
110    int index = startIndex;
111    Word curAddress;
112    Address entry;
113    do {
114      entry = getEntry(index);
115      curAddress = entry.loadWord(KEY_OFFSET);
116      index = (index + 1) & mask.toInt();
117    } while(curAddress.NE(key) &&
118            !curAddress.isZero() &&
119            index != startIndex);
120
121    if (index == startIndex) {
122      VM.assertions.fail("No room left in table!");
123    }
124
125    if (curAddress.isZero()) {
126      if (!create) return Address.zero();
127      entry.store(key, KEY_OFFSET);
128    }
129
130    return entry;
131  }
132
133  /**
134   * Compute the hashtable index for a given object.
135   *
136   * @param key The key.
137   * @return The index.
138   */
139  @Inline
140  private int computeHash(Word key) {
141    return key.rshl(HASH_SHIFT).and(mask).toInt();
142  }
143
144  /**
145   * Return the address of a specified entry in the table.
146   *
147   * @param index The index of the entry.
148   * @return An address to the entry.
149   */
150  @Inline
151  private Address getEntry(int index) {
152    return base.plus(Extent.fromIntZeroExtend(index * entrySize.toInt()));
153  }
154
155  /**
156   * Does the passed object have an entry in the table?
157   *
158   * @param key The key to find an entry for
159   * @return True if there is an entry for that object.
160   */
161  public final boolean contains(Word key) {
162    return !getEntry(key, false).isZero();
163  }
164
165  /**
166   * @return The first non-zero element in the table, or null if
167   * the table is empty.
168   */
169  public final Address getFirst() {
170    return getNext(base.minus(entrySize));
171  }
172
173  /**
174   * The next element in the table after the passed entry, or
175   * null if it is the last entry.
176   *
177   * @param curr The object to look for the next entry from.
178   * @return The next entry or {@code null}.
179   */
180  public final Address getNext(Address curr) {
181    Address entry = curr.plus(entrySize);
182    while (entry.LT(base.plus(size))) {
183      if (!entry.loadWord().isZero()) return entry;
184      entry = entry.plus(entrySize);
185    }
186    return Address.zero();
187  }
188
189  /**
190   * Given an address of an entry, return a pointer to the payload.
191   *
192   * @param entry The entry
193   * @return The object reference.
194   */
195  public static Address getPayloadAddress(Address entry) {
196    return entry.plus(DATA_OFFSET);
197  }
198
199  /**
200   * Given a key, return a pointer to the payload.
201   *
202   * @param key The key
203   * @return The object reference.
204   */
205  public final Address getPayloadAddress(Word key) {
206    Address entry = getEntry(key, false);
207    if (entry.isZero()) return Address.zero();
208
209    return entry.plus(DATA_OFFSET);
210  }
211
212
213  /**
214   * Return the key for a given entry.
215   *
216   * @param entry The entry.
217   * @return The key.
218   */
219  public static Word getKey(Address entry) {
220    return entry.loadWord(KEY_OFFSET);
221  }
222
223  /**
224   * Update the key for a given entry. This operation is not
225   * safe without rehashing
226   *
227   * @param entry The entry to update.
228   * @param key The new key.
229   */
230  public static void replaceKey(Address entry, Word key) {
231    entry.store(key, KEY_OFFSET);
232  }
233
234}