001: /*
002: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
003: *
004: * Copyright 1997-2007 Sun Microsystems, Inc. All rights reserved.
005: *
006: * The contents of this file are subject to the terms of either the GNU
007: * General Public License Version 2 only ("GPL") or the Common
008: * Development and Distribution License("CDDL") (collectively, the
009: * "License"). You may not use this file except in compliance with the
010: * License. You can obtain a copy of the License at
011: * http://www.netbeans.org/cddl-gplv2.html
012: * or nbbuild/licenses/CDDL-GPL-2-CP. See the License for the
013: * specific language governing permissions and limitations under the
014: * License. When distributing the software, include this License Header
015: * Notice in each file and include the License file at
016: * nbbuild/licenses/CDDL-GPL-2-CP. Sun designates this
017: * particular file as subject to the "Classpath" exception as provided
018: * by Sun in the GPL Version 2 section of the License file that
019: * accompanied this code. If applicable, add the following below the
020: * License Header, with the fields enclosed by brackets [] replaced by
021: * your own identifying information:
022: * "Portions Copyrighted [year] [name of copyright owner]"
023: *
024: * Contributor(s):
025: *
026: * The Original Software is NetBeans. The Initial Developer of the Original
027: * Software is Sun Microsystems, Inc. Portions Copyright 1997-2006 Sun
028: * Microsystems, Inc. All Rights Reserved.
029: *
030: * If you wish your version of this file to be governed by only the CDDL
031: * or only the GPL Version 2, indicate your decision by adding
032: * "[Contributor] elects to include this software in this distribution
033: * under the [CDDL or GPL Version 2] license." If you do not indicate a
034: * single choice of license, a recipient has the option to distribute
035: * your version of this file under either the CDDL, the GPL Version 2 or
036: * to extend the choice of license to its licensees as provided above.
037: * However, if you add GPL Version 2 code and therefore, elected the GPL
038: * Version 2 license, then the option applies only if the new code is
039: * made subject to such option by the copyright holder.
040: */
041:
042: package org.netbeans.insane.impl;
043:
044: import java.lang.reflect.*;
045: import java.util.*;
046:
047: import org.netbeans.insane.scanner.*;
048:
049: /** This is a special kind of IdentityHashSet.
050: * It hashes the objects according to their system hash code
051: * and in case of colision keeps wrappers to provide unique IDs.
052: * This implementation does even provide flat numeric IDs
053: */
054: class SmallObjectMap2 implements ObjectMap {
055: // the primary table keeping all the known objects
056: // hashed using their system hashcodes, with circular-linear shift
057: // in case of bucket collision.
058: private Object[] table = new Object[128 * 1024];
059: private int size;
060:
061: // this map keeps reference to all objects with system hash collision
062: private Map<Object, Integer> wrappers = new IdentityHashMap<Object, Integer>();
063:
064: int idCounter;
065:
066: int maxDisplace;
067:
068: SmallObjectMap2() {
069: }
070:
071: public boolean isKnown(Object o) {
072: int bucket = System.identityHashCode(o) % table.length;
073:
074: while (table[bucket] != null) {
075: if (table[bucket] == o)
076: return true;
077:
078: bucket = (bucket + 1) % table.length;
079: }
080:
081: return false;
082: }
083:
084: public String getID(Object o) {
085: // find whether it is known and wrapped
086: Integer wid = wrappers.get(o);
087: if (wid != null)
088: return getWrappedId(o, wid.intValue());
089:
090: // ... or at least known
091: if (isKnown(o))
092: return getNormalId(o);
093:
094: // unknown object
095: if (putObject(o)) { //wrapped
096: return getWrappedId(o, wrappers.get(o).intValue());
097: } else {
098: return getNormalId(o);
099: }
100: }
101:
102: private boolean usedId(int id) {
103: if (id > 0 && id < idCounter)
104: return true;
105:
106: int bucket = id % table.length;
107:
108: while (table[bucket] != null) {
109: if (System.identityHashCode(table[bucket]) == id)
110: return true;
111:
112: bucket = (bucket + 1) % table.length;
113: }
114:
115: return false;
116: }
117:
118: private static String getWrappedId(Object o, int i) {
119: return Integer.toHexString(i);
120: }
121:
122: private static String getNormalId(Object o) {
123: return Integer.toHexString(System.identityHashCode(o));
124: }
125:
126: private int nextFreeId() {
127: while (usedId(++idCounter))
128: ;
129: return idCounter;
130: }
131:
132: // knows it is not there.
133: // returns true iff wraps
134: private boolean putObject(Object o) {
135: if (5 * size / 4 > table.length)
136: rehash(3 * table.length / 2);
137:
138: size++;
139: int sysID = System.identityHashCode(o);
140: int bucket = sysID % table.length;
141: boolean wrap = usedId(sysID);
142:
143: int temp = 0;
144: // find an empty slot, look for friends with the same ID
145: while (table[bucket] != null) {
146: // if (System.identityHashCode(table[bucket]) == sysID) wrap = true;
147: temp++;
148: bucket = (bucket + 1) % table.length;
149: }
150: if (temp > maxDisplace)
151: maxDisplace = temp;
152:
153: // fill the slot
154: table[bucket] = o;
155:
156: // add the wrapping info
157: if (wrap)
158: wrappers.put(o, new Integer(nextFreeId()));
159: return wrap;
160: }
161:
162: private void rehash(int newSize) {
163: Object[] newTable = new Object[newSize];
164: for (int i = 0; i < table.length; i++) {
165: Object act = table[i];
166: if (act != null) {
167: int bucket = System.identityHashCode(act)
168: % newTable.length;
169: int temp = 0;
170: while (newTable[bucket] != null) { // find an empty slot
171: temp++;
172: bucket = (bucket + 1) % newTable.length;
173: }
174: if (temp > maxDisplace)
175: maxDisplace = temp;
176:
177: newTable[bucket] = act;
178: }
179: }
180:
181: table = newTable;
182: }
183: }
|