001: /* Soot - a J*va Optimization Framework
002: * Copyright (C) 2002 Ondrej Lhotak
003: *
004: * This library is free software; you can redistribute it and/or
005: * modify it under the terms of the GNU Lesser General Public
006: * License as published by the Free Software Foundation; either
007: * version 2.1 of the License, or (at your option) any later version.
008: *
009: * This library is distributed in the hope that it will be useful,
010: * but WITHOUT ANY WARRANTY; without even the implied warranty of
011: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
012: * Lesser General Public License for more details.
013: *
014: * You should have received a copy of the GNU Lesser General Public
015: * License along with this library; if not, write to the
016: * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
017: * Boston, MA 02111-1307, USA.
018: */
019:
020: package soot.util;
021:
022: import java.util.*;
023:
024: /** A java.util.Map-like map with Numberable objects as the keys.
025: *
026: * @author Ondrej Lhotak
027: */
028:
029: public final class SmallNumberedMap {
030: public SmallNumberedMap(ArrayNumberer universe) {
031: this .universe = universe;
032: }
033:
034: /** Associates a value with a key. */
035: public boolean put(Numberable key, Object value) {
036: int pos = findPosition(key);
037: if (array[pos] == key) {
038: if (values[pos] == value)
039: return false;
040: values[pos] = value;
041: return true;
042: }
043: size++;
044: if (size * 3 > array.length * 2) {
045: doubleSize();
046: pos = findPosition(key);
047: }
048: array[pos] = key;
049: values[pos] = value;
050: return true;
051: }
052:
053: /** Returns the value associated with a given key. */
054: public Object get(Numberable key) {
055: return values[findPosition(key)];
056: }
057:
058: /** Returns the number of non-null values in this map. */
059: public int nonNullSize() {
060: int ret = 0;
061: for (Object element : values) {
062: if (element != null)
063: ret++;
064: }
065: return ret;
066: }
067:
068: /** Returns an iterator over the keys with non-null values. */
069: public Iterator keyIterator() {
070: return new KeyIterator(this );
071: }
072:
073: /** Returns an iterator over the non-null values. */
074: public Iterator iterator() {
075: return new ValueIterator(this );
076: }
077:
078: abstract class SmallNumberedMapIterator implements Iterator {
079: SmallNumberedMap map;
080: int cur = 0;
081:
082: SmallNumberedMapIterator(SmallNumberedMap map) {
083: this .map = map;
084: seekNext();
085: }
086:
087: protected final void seekNext() {
088: try {
089: while (map.values[cur] == null) {
090: cur++;
091: }
092: } catch (ArrayIndexOutOfBoundsException e) {
093: cur = -1;
094: }
095: }
096:
097: public final boolean hasNext() {
098: return cur != -1;
099: }
100:
101: public abstract Object next();
102:
103: public void remove() {
104: throw new RuntimeException("Not implemented.");
105: }
106: }
107:
108: class KeyIterator extends SmallNumberedMapIterator {
109: KeyIterator(SmallNumberedMap map) {
110: super (map);
111: }
112:
113: public final Object next() {
114: Numberable ret = array[cur];
115: cur++;
116: seekNext();
117: return ret;
118: }
119: }
120:
121: class ValueIterator extends SmallNumberedMapIterator {
122: ValueIterator(SmallNumberedMap map) {
123: super (map);
124: }
125:
126: public final Object next() {
127: Object ret = values[cur];
128: cur++;
129: seekNext();
130: return ret;
131: }
132: }
133:
134: /* Private stuff. */
135:
136: private final int findPosition(Numberable o) {
137: int number = o.getNumber();
138: if (number == 0)
139: throw new RuntimeException("unnumbered");
140: number = number & (array.length - 1);
141: while (true) {
142: if (array[number] == o)
143: return number;
144: if (array[number] == null)
145: return number;
146: number = (number + 1) & (array.length - 1);
147: }
148: }
149:
150: private final void doubleSize() {
151: int uniSize = universe.size();
152: if (array.length * 128 > uniSize) {
153: }
154: Numberable[] oldArray = array;
155: Object[] oldValues = values;
156: int newLength = array.length * 2;
157: values = new Object[newLength];
158: array = new Numberable[newLength];
159: for (int i = 0; i < oldArray.length; i++) {
160: Numberable element = oldArray[i];
161: if (element != null) {
162: int pos = findPosition(element);
163: array[pos] = element;
164: values[pos] = oldValues[i];
165: }
166: }
167: }
168:
169: private Numberable[] array = new Numberable[8];
170: private Object[] values = new Object[8];
171: private int size = 0;
172: private ArrayNumberer universe;
173: }
|