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.jikesrvm.util;
014
015 import java.util.Iterator;
016 import java.util.NoSuchElementException;
017
018 import org.jikesrvm.VM;
019 import org.jikesrvm.mm.mminterface.MemoryManager;
020
021 /**
022 * Common super class for all VM hash maps.
023 */
024 abstract class AbstractHashMapRVM<K, V> {
025
026 protected static final int DEFAULT_SIZE = 7;
027 private static final float LOAD = 3;
028 protected AbstractBucket<K, V>[] buckets;
029 protected int numElems = 0;
030
031 abstract static class AbstractBucket<K, V> {
032 abstract AbstractBucket<K, V> getNext();
033
034 /**
035 * Change the next bucket after this bucket, possibly constructing a new
036 * abstract bucket.
037 */
038 abstract AbstractBucket<K, V> setNext(AbstractBucket<K, V> n);
039
040 abstract K getKey();
041
042 abstract V getValue();
043
044 abstract void setValue(V v);
045 }
046
047 /**
048 * Are two keys the same?
049 */
050 abstract boolean same(K key1, K key2);
051
052 abstract int hashTheKey(K key);
053
054 abstract AbstractBucket<K,V> createNewBucket(K k, V v, AbstractBucket<K,V> n);
055
056 AbstractHashMapRVM(int size) {
057 buckets = newBucketArray(size);
058 }
059
060 public final int size() {
061 return numElems;
062 }
063
064 public final V get(K key) {
065 if (key == null) {
066 return null;
067 }
068 int bucketIdx = bucketIndex(key, buckets.length);
069 AbstractBucket<K, V> cur = buckets[bucketIdx];
070 while (cur != null && !same(cur.getKey(), key)) {
071 cur = cur.getNext();
072 }
073 if (cur == null) {
074 return null;
075 } else {
076 return cur.getValue();
077 }
078 }
079
080 /**
081 * Advise against growing the buckets if they are immortal, as it will lead
082 * to multiple sets of buckets that will be scanned
083 */
084 private boolean growMapAllowed() {
085 return !VM.runningVM || !MemoryManager.isImmortal(buckets);
086 }
087
088 public final V put(K key, V value) {
089 if (VM.VerifyAssertions) VM._assert(key != null);
090 if (growMapAllowed() && numElems > (buckets.length * LOAD)) {
091 growMap();
092 }
093
094 int bucketIdx = bucketIndex(key, buckets.length);
095 AbstractBucket<K, V> cur = buckets[bucketIdx];
096 while (cur != null && !same(cur.getKey(), key)) {
097 cur = cur.getNext();
098 }
099 if (cur != null) {
100 // replacing existing <key,value> pair
101 V tmp = cur.getValue();
102 cur.setValue(value);
103 return tmp;
104 } else {
105 buckets[bucketIdx] = createNewBucket(key, value, buckets[bucketIdx]);
106 numElems++;
107 return null;
108 }
109 }
110
111 @SuppressWarnings("unchecked")
112 private AbstractBucket<K, V>[] newBucketArray(int size) {
113 return new AbstractBucket[size];
114 }
115
116 private void growMap() {
117 AbstractBucket<K, V>[] newBuckets = newBucketArray(buckets.length * 2 + 1);
118 // Iterate over all buckets
119 for (AbstractBucket<K, V> cur : buckets) {
120 // Iterate over all values in a bucket
121 while (cur != null) {
122 AbstractBucket<K, V> next = cur.getNext();
123 int newIdx = bucketIndex(cur.getKey(), newBuckets.length);
124 cur = cur.setNext(newBuckets[newIdx]);
125 newBuckets[newIdx] = cur;
126 cur = next;
127 }
128 }
129 buckets = newBuckets;
130 }
131
132 public V remove(K key) {
133 if (VM.VerifyAssertions) VM._assert(key != null);
134 int bucketIdx = bucketIndex(key, buckets.length);
135 AbstractBucket<K, V> cur = buckets[bucketIdx];
136 AbstractBucket<K, V> prev = null;
137 while (cur != null && !same(cur.getKey(), key)) {
138 prev = cur;
139 cur = cur.getNext();
140 }
141 if (cur != null) {
142 if (prev == null) {
143 // removing first bucket in chain.
144 buckets[bucketIdx] = cur.getNext();
145 } else {
146 AbstractBucket<K, V> newPrev = prev.setNext(cur.getNext());
147 if (newPrev != prev) {
148 throw new UnsupportedOperationException();
149 }
150 }
151 numElems--;
152 return cur.getValue();
153 } else {
154 return null;
155 }
156 }
157
158 public final Iterator<V> valueIterator() {
159 return new ValueIterator();
160 }
161
162 public final Iterator<K> keyIterator() {
163 return new KeyIterator();
164 }
165
166 private int bucketIndex(K key, int divisor) {
167 if (key == null) {
168 return 0;
169 } else {
170 return (hashTheKey(key) & 0x7fffffff) % divisor;
171 }
172 }
173
174 /**
175 * @return a java.lang.Iterable for the values in the hash map
176 */
177 public final Iterable<V> values() {
178 return new Iterable<V>() {
179 @Override
180 public Iterator<V> iterator() {
181 return AbstractHashMapRVM.this.valueIterator();
182 }
183 };
184 }
185
186 /**
187 *
188 * @return a java.lang.Iterable for the values in the hash map
189 */
190 public final Iterable<K> keys() {
191 return new Iterable<K>() {
192 @Override
193 public Iterator<K> iterator() {
194 return AbstractHashMapRVM.this.keyIterator();
195 }
196 };
197 }
198
199 /**
200 * Iterator types for key and value
201 */
202 private class BucketIterator {
203 private int bucketIndex = 0;
204 private AbstractBucket<K, V> next = null;
205 private int numVisited = 0;
206
207 public AbstractBucket<K, V> nextBucket() {
208 if (!hasNext()) {
209 throw new NoSuchElementException();
210 }
211
212 while (next == null) {
213 next = buckets[bucketIndex++];
214 }
215 AbstractBucket<K, V> ans = next;
216 next = ans.getNext();
217 numVisited++;
218 return ans;
219 }
220
221 public boolean hasNext() {
222 return numVisited < numElems;
223 }
224
225 public void remove() {
226 throw new UnsupportedOperationException();
227 }
228 }
229
230 private final class KeyIterator extends BucketIterator implements Iterator<K> {
231 @Override
232 public K next() {
233 AbstractBucket<K, V> cur = nextBucket();
234 return cur.getKey();
235 }
236 }
237
238 private final class ValueIterator extends BucketIterator implements Iterator<V> {
239 @Override
240 public V next() {
241 AbstractBucket<K, V> cur = nextBucket();
242 return cur.getValue();
243 }
244 }
245 }