001: //
002: // Copyright (C) 2005 United States Government as represented by the
003: // Administrator of the National Aeronautics and Space Administration
004: // (NASA). All Rights Reserved.
005: //
006: // This software is distributed under the NASA Open Source Agreement
007: // (NOSA), version 1.3. The NOSA has been approved by the Open Source
008: // Initiative. See the file NOSA-1.3-JPF at the top of the distribution
009: // directory tree for the complete NOSA document.
010: //
011: // THE SUBJECT SOFTWARE IS PROVIDED "AS IS" WITHOUT ANY WARRANTY OF ANY
012: // KIND, EITHER EXPRESSED, IMPLIED, OR STATUTORY, INCLUDING, BUT NOT
013: // LIMITED TO, ANY WARRANTY THAT THE SUBJECT SOFTWARE WILL CONFORM TO
014: // SPECIFICATIONS, ANY IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR
015: // A PARTICULAR PURPOSE, OR FREEDOM FROM INFRINGEMENT, ANY WARRANTY THAT
016: // THE SUBJECT SOFTWARE WILL BE ERROR FREE, OR ANY WARRANTY THAT
017: // DOCUMENTATION, IF PROVIDED, WILL CONFORM TO THE SUBJECT SOFTWARE.
018: //
019: package gov.nasa.jpf.util;
020:
021: import java.util.Hashtable;
022: import java.util.Iterator;
023: import java.util.Set;
024: import java.util.TreeSet;
025:
026: /**
027: * data structure used to do hash collapsing. All the major state components
028: * (fields, Monitors, StackFrames, uThreadData) are stored in pools to
029: * determine if they are new. Only the pool index values are used to
030: * compute hash values
031: *
032: * <2do> pcm - check if an open hashing scheme wouldn't be more efficient. This
033: * looks like a major memory hotspot
034: */
035: public class HashPool {
036: private static final int DELTA = 10;
037: private Hashtable pool;
038: private int size;
039: private int length;
040: private Object[] objects;
041:
042: public HashPool() {
043: pool = new Hashtable();
044: objects = new Object[length = DELTA];
045: objects[0] = null;
046: size = 1;
047: }
048:
049: public PoolEntry getEntry(Object o) {
050: if (o == null) {
051: return null;
052: }
053:
054: PoolEntry e = (PoolEntry) pool.get(o);
055:
056: if (e != null) {
057: return e;
058: }
059:
060: return put(o);
061: }
062:
063: public int getIndex(Object o) {
064: if (o == null) {
065: return -1;
066: }
067:
068: PoolEntry e = (PoolEntry) pool.get(o);
069:
070: if (e != null) {
071: return e.idx;
072: }
073:
074: return put(o).idx;
075: }
076:
077: public Object getObject(int idx) {
078: return objects[idx];
079: }
080:
081: public Object get(Object o) {
082: if (o == null) {
083: return null;
084: }
085:
086: PoolEntry e = (PoolEntry) pool.get(o);
087:
088: if (e != null) {
089: return e.obj;
090: }
091:
092: return put(o).obj;
093: }
094:
095: public synchronized void print() {
096: System.out.println("{");
097:
098: Set s = new TreeSet(pool.values());
099:
100: for (Iterator i = s.iterator(); i.hasNext();) {
101: Object entry = i.next();
102: System.out.println("\t" + entry);
103: }
104:
105: System.out.println("}");
106: }
107:
108: public synchronized PoolEntry put(Object o) {
109: PoolEntry e = (PoolEntry) pool.get(o);
110:
111: if (e != null) {
112: return e;
113: }
114:
115: if (length < (size + 1)) {
116: Object[] newObjects = new Object[length + DELTA];
117: System.arraycopy(objects, 0, newObjects, 0, length);
118: objects = newObjects;
119: length += DELTA;
120: }
121:
122: objects[size] = o;
123: pool.put(o, e = new PoolEntry(o, size++));
124:
125: return e;
126: }
127:
128: public synchronized int size() {
129: return size;
130: }
131:
132: /**
133: * DOCUMENT ME!
134: */
135: public class PoolEntry implements Comparable {
136: private Object obj;
137: private int idx;
138:
139: public PoolEntry(Object o, int i) {
140: obj = o;
141: idx = i;
142: }
143:
144: public int getIndex() {
145: return idx;
146: }
147:
148: public Object getObject() {
149: return obj;
150: }
151:
152: public int compareTo(Object o) {
153: PoolEntry other = (PoolEntry) o;
154:
155: return (idx - other.idx);
156: }
157:
158: public boolean equals(Object obj) {
159: PoolEntry other = (PoolEntry) obj;
160:
161: return (other.idx == idx);
162: }
163:
164: public int hashCode() {
165: return idx;
166: }
167:
168: public String toString() {
169: return idx + " => " + obj;
170: }
171: }
172: }
|