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: */
053: class SmallObjectMap implements ObjectMap {
054: // the primary table keeping all the known objects
055: // hashed using their system hashcodes, with circular-linear shift
056: // in case of bucket collision.
057: private Object[] table = new Object[128 * 1024];
058: private int size;
059:
060: // this map keeps reference to all objects with system hash collision
061: private Map<Object, Integer> wrappers = new IdentityHashMap<Object, Integer>();
062:
063: int idCounter;
064:
065: int maxDisplace;
066:
067: SmallObjectMap() {
068: }
069:
070: public boolean isKnown(Object o) {
071: int bucket = System.identityHashCode(o) % table.length;
072:
073: while (table[bucket] != null) {
074: if (table[bucket] == o)
075: return true;
076:
077: bucket = (bucket + 1) % table.length;
078: }
079:
080: return false;
081: }
082:
083: public String getID(Object o) {
084: // find whether it is known and wrapped
085: Integer wid = wrappers.get(o);
086: if (wid != null)
087: return getWrappedId(o, wid.intValue());
088:
089: // ... or at least known
090: if (isKnown(o))
091: return getNormalId(o);
092:
093: // unknown object
094: if (putObject(o)) { //wrapped
095: return getWrappedId(o, wrappers.get(o).intValue());
096: } else {
097: return getNormalId(o);
098: }
099: }
100:
101: private static String getWrappedId(Object o, int i) {
102: return Integer.toHexString(System.identityHashCode(o)) + '.'
103: + Integer.toHexString(i);
104: }
105:
106: private static String getNormalId(Object o) {
107: return Integer.toHexString(System.identityHashCode(o));
108: }
109:
110: // knows it is not there.
111: // returns true iff wraps
112: private boolean putObject(Object o) {
113: if (5 * size / 4 > table.length)
114: rehash(3 * table.length / 2);
115:
116: size++;
117: int sysID = System.identityHashCode(o);
118: int bucket = sysID % table.length;
119: boolean wrap = false;
120:
121: int temp = 0;
122: // find an empty slot, look for friends with the same ID
123: while (table[bucket] != null) {
124: if (System.identityHashCode(table[bucket]) == sysID)
125: wrap = true;
126: temp++;
127: bucket = (bucket + 1) % table.length;
128: }
129: if (temp > maxDisplace)
130: maxDisplace = temp;
131:
132: // fill the slot
133: table[bucket] = o;
134:
135: // add the wrapping info
136: if (wrap)
137: wrappers.put(o, new Integer(idCounter++));
138: return wrap;
139: }
140:
141: private void rehash(int newSize) {
142: Object[] newTable = new Object[newSize];
143: for (int i = 0; i < table.length; i++) {
144: Object act = table[i];
145: if (act != null) {
146: int bucket = System.identityHashCode(act)
147: % newTable.length;
148: int temp = 0;
149: while (newTable[bucket] != null) { // find an empty slot
150: temp++;
151: bucket = (bucket + 1) % newTable.length;
152: }
153: if (temp > maxDisplace)
154: maxDisplace = temp;
155:
156: newTable[bucket] = act;
157: }
158: }
159:
160: table = newTable;
161: }
162: }
|