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 public Iterator<V> iterator() {
180 return AbstractHashMapRVM.this.valueIterator();
181 }
182 };
183 }
184
185 /**
186 *
187 * @return a java.lang.Iterable for the values in the hash map
188 */
189 public final Iterable<K> keys() {
190 return new Iterable<K>() {
191 public Iterator<K> iterator() {
192 return AbstractHashMapRVM.this.keyIterator();
193 }
194 };
195 }
196
197 /**
198 * Iterator types for key and value
199 */
200 private class BucketIterator {
201 private int bucketIndex = 0;
202 private AbstractBucket<K, V> next = null;
203 private int numVisited = 0;
204
205 public AbstractBucket<K, V> nextBucket() {
206 if (!hasNext()) {
207 throw new NoSuchElementException();
208 }
209
210 while (next == null) {
211 next = buckets[bucketIndex++];
212 }
213 AbstractBucket<K, V> ans = next;
214 next = ans.getNext();
215 numVisited++;
216 return ans;
217 }
218
219 public boolean hasNext() {
220 return numVisited < numElems;
221 }
222
223 public void remove() {
224 throw new UnsupportedOperationException();
225 }
226 }
227
228 private final class KeyIterator extends BucketIterator implements Iterator<K> {
229 public K next() {
230 AbstractBucket<K, V> cur = nextBucket();
231 return cur.getKey();
232 }
233 }
234
235 private final class ValueIterator extends BucketIterator implements Iterator<V> {
236 public V next() {
237 AbstractBucket<K, V> cur = nextBucket();
238 return cur.getValue();
239 }
240 }
241 }