001: /*
002: * Licensed to the Apache Software Foundation (ASF) under one or more
003: * contributor license agreements. See the NOTICE file distributed with
004: * this work for additional information regarding copyright ownership.
005: * The ASF licenses this file to You under the Apache License, Version 2.0
006: * (the "License"); you may not use this file except in compliance with
007: * the License. You may obtain a copy of the License at
008: *
009: * http://www.apache.org/licenses/LICENSE-2.0
010: *
011: * Unless required by applicable law or agreed to in writing, software
012: * distributed under the License is distributed on an "AS IS" BASIS,
013: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014: * See the License for the specific language governing permissions and
015: * limitations under the License.
016: */
017:
018: package org.apache.harmony.kernel.vm;
019:
020: import java.lang.ref.ReferenceQueue;
021: import java.lang.ref.WeakReference;
022:
023: /**
024: * Implements weak hash map specialized for storing interned string pool.
025: * @see java.util.WeakHashMap
026: * @see WeakReference
027: */
028: public class InternMap {
029:
030: private final ReferenceQueue<String> referenceQueue;
031:
032: int elementCount;
033:
034: Entry[] elementData;
035:
036: private final int loadFactor;
037:
038: private int threshold;
039:
040: //Simple utility method to isolate unchecked cast for array creation
041: private static Entry[] newEntryArray(int size) {
042: return new Entry[size];
043: }
044:
045: private static final class Entry extends WeakReference<String> {
046: int hash;
047: Entry next;
048:
049: Entry(String key, ReferenceQueue<String> queue) {
050: super (key, queue);
051: hash = key.hashCode();
052: }
053: }
054:
055: public InternMap(int capacity) {
056: if (capacity >= 0) {
057: elementCount = 0;
058: elementData = newEntryArray(capacity == 0 ? 1 : capacity);
059: loadFactor = 7500; // Default load factor of 0.75
060: computeMaxSize();
061: referenceQueue = new ReferenceQueue<String>();
062: } else {
063: throw new IllegalArgumentException();
064: }
065: }
066:
067: private void computeMaxSize() {
068: threshold = (int) ((long) elementData.length * loadFactor / 10000);
069: }
070:
071: void poll() {
072: Entry toRemove;
073: while ((toRemove = (Entry) (WeakReference<String>) referenceQueue
074: .poll()) != null) {
075: removeEntry(toRemove);
076: }
077: }
078:
079: void removeEntry(Entry toRemove) {
080: Entry entry, last = null;
081: int index = (toRemove.hash & 0x7FFFFFFF) % elementData.length;
082: entry = elementData[index];
083: // Ignore queued entries which cannot be found, the user could
084: // have removed them before they were queued, i.e. using clear()
085: while (entry != null) {
086: if (toRemove == entry) {
087: if (last == null) {
088: elementData[index] = entry.next;
089: } else {
090: last.next = entry.next;
091: }
092: elementCount--;
093: break;
094: }
095: last = entry;
096: entry = entry.next;
097: }
098: }
099:
100: public String intern(String key) {
101: int index = 0;
102: Entry entry;
103: String interned = null;
104: if (key == null)
105: return null;
106: int hash = key.hashCode();
107: int length = elementData.length;
108: index = (hash & 0x7FFFFFFF) % length;
109: entry = elementData[index];
110: while (entry != null
111: && !key.equals(interned = (String) entry.get())) {
112: entry = entry.next;
113: }
114:
115: // if we found the entry, return it
116: if (entry != null) {
117: return interned;
118: }
119:
120: // no interned string found, put a new entry for it
121: if (++elementCount > threshold) {
122: rehash();
123: index = (key.hashCode() & 0x7FFFFFFF) % elementData.length;
124: }
125: entry = new Entry(key, referenceQueue);
126: entry.next = elementData[index];
127: elementData[index] = entry;
128: return key;
129: }
130:
131: private void rehash() {
132: poll();
133: int length = elementData.length << 1;
134: if (length == 0) {
135: length = 1;
136: }
137: Entry[] newData = newEntryArray(length);
138: for (int i = 0; i < elementData.length; i++) {
139: Entry entry = elementData[i];
140: while (entry != null) {
141: int index = (entry.hash & 0x7FFFFFFF) % length;
142: Entry next = entry.next;
143: entry.next = newData[index];
144: newData[index] = entry;
145: entry = next;
146: }
147: }
148: elementData = newData;
149: computeMaxSize();
150: }
151: }
|