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