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.jikesrvm.util;
014
015import java.util.Iterator;
016import java.util.NoSuchElementException;
017
018import org.jikesrvm.VM;
019import org.jikesrvm.mm.mminterface.MemoryManager;
020
021/**
022 * Common super class for all VM hash maps.
023 */
024abstract 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     * @param n the new value for the next bucket
039     * @return previous bucket of the given bucket
040     */
041    abstract AbstractBucket<K, V> setNext(AbstractBucket<K, V> n);
042
043    abstract K getKey();
044
045    abstract V getValue();
046
047    abstract void setValue(V v);
048  }
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   * @return whether it is allowed to grow the map
085   */
086  private boolean growMapAllowed() {
087    return !VM.runningVM || !MemoryManager.isImmortal(buckets);
088  }
089
090  public final V put(K key, V value) {
091    if (VM.VerifyAssertions) VM._assert(key != null);
092    if (growMapAllowed() && numElems > (buckets.length * LOAD)) {
093      growMap();
094    }
095
096    int bucketIdx = bucketIndex(key, buckets.length);
097    AbstractBucket<K, V> cur = buckets[bucketIdx];
098    while (cur != null && !same(cur.getKey(), key)) {
099      cur = cur.getNext();
100    }
101    if (cur != null) {
102      // replacing existing <key,value> pair
103      V tmp = cur.getValue();
104      cur.setValue(value);
105      return tmp;
106    } else {
107      buckets[bucketIdx] = createNewBucket(key, value, buckets[bucketIdx]);
108      numElems++;
109      return null;
110    }
111  }
112
113  @SuppressWarnings("unchecked")
114  private AbstractBucket<K, V>[] newBucketArray(int size) {
115    return new AbstractBucket[size];
116  }
117
118  private void growMap() {
119    AbstractBucket<K, V>[] newBuckets = newBucketArray(buckets.length * 2 + 1);
120    // Iterate over all buckets
121    for (AbstractBucket<K, V> cur : buckets) {
122      // Iterate over all values in a bucket
123      while (cur != null) {
124        AbstractBucket<K, V> next = cur.getNext();
125        int newIdx = bucketIndex(cur.getKey(), newBuckets.length);
126        cur = cur.setNext(newBuckets[newIdx]);
127        newBuckets[newIdx] = cur;
128        cur = next;
129      }
130    }
131    buckets = newBuckets;
132  }
133
134  public V remove(K key) {
135    if (VM.VerifyAssertions) VM._assert(key != null);
136    int bucketIdx = bucketIndex(key, buckets.length);
137    AbstractBucket<K, V> cur = buckets[bucketIdx];
138    AbstractBucket<K, V> prev = null;
139    while (cur != null && !same(cur.getKey(), key)) {
140      prev = cur;
141      cur = cur.getNext();
142    }
143    if (cur != null) {
144      if (prev == null) {
145        // removing first bucket in chain.
146        buckets[bucketIdx] = cur.getNext();
147      } else {
148        AbstractBucket<K, V> newPrev = prev.setNext(cur.getNext());
149        if (newPrev != prev) {
150          throw new UnsupportedOperationException();
151        }
152      }
153      numElems--;
154      return cur.getValue();
155    } else {
156      return null;
157    }
158  }
159
160  public void removeAll() {
161    for (int i = 0; i < buckets.length; i++) {
162      buckets[i] = null;
163    }
164    numElems = 0;
165  }
166
167  public final Iterator<V> valueIterator() {
168    return new ValueIterator();
169  }
170
171  public final Iterator<K> keyIterator() {
172    return new KeyIterator();
173  }
174
175  private int bucketIndex(K key, int divisor) {
176    if (key == null) {
177      return 0;
178    } else {
179      return (hashTheKey(key) & 0x7fffffff) % divisor;
180    }
181  }
182
183  /**
184   * @return a java.lang.Iterable for the values in the hash map
185   */
186  public final Iterable<V> values() {
187    return new Iterable<V>() {
188      @Override
189      public Iterator<V> iterator() {
190        return AbstractHashMapRVM.this.valueIterator();
191      }
192    };
193  }
194
195  /**
196   *
197   * @return a java.lang.Iterable for the values in the hash map
198   */
199  public final Iterable<K> keys() {
200    return new Iterable<K>() {
201      @Override
202      public Iterator<K> iterator() {
203        return AbstractHashMapRVM.this.keyIterator();
204      }
205    };
206  }
207
208  /**
209   * Iterator types for key and value
210   */
211  private class BucketIterator {
212    private int bucketIndex = 0;
213    private AbstractBucket<K, V> next = null;
214    private int numVisited = 0;
215
216    public AbstractBucket<K, V> nextBucket() {
217      if (!hasNext()) {
218        throw new NoSuchElementException();
219      }
220
221      while (next == null) {
222        next = buckets[bucketIndex++];
223      }
224      AbstractBucket<K, V> ans = next;
225      next = ans.getNext();
226      numVisited++;
227      return ans;
228    }
229
230    public boolean hasNext() {
231      return numVisited < numElems;
232    }
233
234    public void remove() {
235      throw new UnsupportedOperationException();
236    }
237  }
238
239  private final class KeyIterator extends BucketIterator implements Iterator<K> {
240    @Override
241    public K next() {
242      AbstractBucket<K, V> cur = nextBucket();
243      return cur.getKey();
244    }
245  }
246
247  private final class ValueIterator extends BucketIterator implements Iterator<V> {
248    @Override
249    public V next() {
250      AbstractBucket<K, V> cur = nextBucket();
251      return cur.getValue();
252    }
253  }
254}