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 sets
023 */
024 abstract class AbstractHashSetRVM<T> implements Iterable<T> {
025
026 protected static final int DEFAULT_SIZE = 7;
027 private static final float LOAD = 3;
028 protected AbstractBucket<T>[] buckets;
029 protected int numElems = 0;
030
031 abstract static class AbstractBucket<T> {
032 /**
033 * Change the next bucket after this bucket, possibly constructing a new
034 * abstract bucket
035 */
036 abstract AbstractBucket<T> setNext(AbstractBucket<T> next);
037
038 abstract AbstractBucket<T> getNext();
039
040 abstract T getKey();
041 }
042
043 abstract AbstractBucket<T> createNewBucket(T key, AbstractBucket<T> next);
044
045 @SuppressWarnings("unchecked")
046 protected AbstractBucket<T>[] newBucketArray(int size) {
047 return new AbstractBucket[size];
048 }
049
050 AbstractHashSetRVM(int size) {
051 buckets = newBucketArray(size);
052 }
053
054 public int size() {
055 return numElems;
056 }
057
058 /**
059 * Advise against growing the buckets if they are immortal, as it will lead
060 * to multiple sets of buckets that will be scanned
061 */
062 private boolean growMapAllowed() {
063 return !VM.runningVM || !MemoryManager.isImmortal(buckets);
064 }
065
066 public void add(T key) {
067 if (VM.VerifyAssertions) VM._assert(key != null);
068 if (growMapAllowed() && numElems > (buckets.length * LOAD)) {
069 growMap();
070 }
071
072 int bucketIdx = bucketIndex(key, buckets.length);
073 AbstractBucket<T> cur = buckets[bucketIdx];
074 while (cur != null && !cur.getKey().equals(key)) {
075 cur = cur.getNext();
076 }
077 if (cur == null) {
078 buckets[bucketIdx] = createNewBucket(key, buckets[bucketIdx]);
079 numElems++;
080 }
081 }
082
083 public T get(T key) {
084 if (key == null) {
085 return null;
086 }
087 int bucketIdx = bucketIndex(key, buckets.length);
088 AbstractBucket<T> cur = buckets[bucketIdx];
089 while (cur != null && !cur.getKey().equals(key)) {
090 cur = cur.getNext();
091 }
092 if (cur == null) {
093 return null;
094 } else {
095 return cur.getKey();
096 }
097 }
098
099 public boolean contains(T key) {
100 return get(key) != null;
101 }
102
103 public void addAll(AbstractHashSetRVM<T> c) {
104 for (T t : c) {
105 add(t);
106 }
107 }
108
109 private void growMap() {
110 AbstractBucket<T>[] newBuckets = newBucketArray(buckets.length * 2 + 1);
111 for (AbstractBucket<T> cur : buckets) {
112 while (cur != null) {
113 AbstractBucket<T> next = cur.getNext();
114 int newIdx = bucketIndex(cur.getKey(), newBuckets.length);
115 cur = cur.setNext(newBuckets[newIdx]);
116 newBuckets[newIdx] = cur;
117 cur = next;
118 }
119 }
120 buckets = newBuckets;
121 }
122
123 public void remove(T key) {
124 if (VM.VerifyAssertions) VM._assert(key != null);
125 int bucketIdx = bucketIndex(key, buckets.length);
126 AbstractBucket<T> cur = buckets[bucketIdx];
127 AbstractBucket<T> prev = null;
128 while (cur != null && !cur.getKey().equals(key)) {
129 prev = cur;
130 cur = cur.getNext();
131 }
132 if (cur != null) {
133 if (prev == null) {
134 // removing first bucket in chain.
135 buckets[bucketIdx] = cur.getNext();
136 } else {
137 AbstractBucket<T> newPrev = prev.setNext(cur.getNext());
138 if (newPrev != prev) {
139 throw new UnsupportedOperationException();
140 }
141 }
142 numElems--;
143 }
144 }
145
146 public void removeAll() {
147 for (int i=0; i<buckets.length; i++) {
148 buckets[i] = null;
149 }
150 numElems = 0;
151 }
152
153 public Iterator<T> iterator() {
154 return new SetIterator();
155 }
156
157 private int bucketIndex(T key, int divisor) {
158 if (key == null) {
159 return 0;
160 } else {
161 return (key.hashCode() & 0x7fffffff) % divisor;
162 }
163 }
164
165 /**
166 * Iterator
167 */
168 class SetIterator implements Iterator<T> {
169 private int bucketIndex = 0;
170 private AbstractBucket<T> next = null;
171 private int numVisited = 0;
172
173 public T next() {
174 if (!hasNext()) {
175 throw new NoSuchElementException();
176 }
177
178 while (next == null) {
179 next = buckets[bucketIndex++];
180 }
181 AbstractBucket<T> ans = next;
182 next = ans.getNext();
183 numVisited++;
184 return ans.getKey();
185 }
186
187 public boolean hasNext() {
188 return numVisited < numElems;
189 }
190
191 public void remove() {
192 throw new UnsupportedOperationException();
193 }
194 }
195 }