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 @Override
154 public Iterator<T> iterator() {
155 return new SetIterator();
156 }
157
158 private int bucketIndex(T key, int divisor) {
159 if (key == null) {
160 return 0;
161 } else {
162 return (key.hashCode() & 0x7fffffff) % divisor;
163 }
164 }
165
166 /**
167 * Iterator
168 */
169 class SetIterator implements Iterator<T> {
170 private int bucketIndex = 0;
171 private AbstractBucket<T> next = null;
172 private int numVisited = 0;
173
174 @Override
175 public T next() {
176 if (!hasNext()) {
177 throw new NoSuchElementException();
178 }
179
180 while (next == null) {
181 next = buckets[bucketIndex++];
182 }
183 AbstractBucket<T> ans = next;
184 next = ans.getNext();
185 numVisited++;
186 return ans.getKey();
187 }
188
189 @Override
190 public boolean hasNext() {
191 return numVisited < numElems;
192 }
193
194 @Override
195 public void remove() {
196 throw new UnsupportedOperationException();
197 }
198 }
199 }