KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > eclipse > jdt > internal > compiler > util > SimpleLookupTable


1 /*******************************************************************************
2  * Copyright (c) 2000, 2007 IBM Corporation and others.
3  * All rights reserved. This program and the accompanying materials
4  * are made available under the terms of the Eclipse Public License v1.0
5  * which accompanies this distribution, and is available at
6  * http://www.eclipse.org/legal/epl-v10.html
7  *
8  * Contributors:
9  * IBM Corporation - initial API and implementation
10  *******************************************************************************/
11 package org.eclipse.jdt.internal.compiler.util;
12
13 /**
14  * A simple lookup table is a non-synchronized Hashtable, whose keys
15  * and values are Objects. It also uses linear probing to resolve collisions
16  * rather than a linked list of hash table entries.
17  */
18 public final class SimpleLookupTable implements Cloneable JavaDoc {
19
20 // to avoid using Enumerations, walk the individual tables skipping nulls
21 public Object JavaDoc[] keyTable;
22 public Object JavaDoc[] valueTable;
23 public int elementSize; // number of elements in the table
24 public int threshold;
25
26 public SimpleLookupTable() {
27     this(13);
28 }
29
30 public SimpleLookupTable(int size) {
31     this.elementSize = 0;
32     this.threshold = size; // size represents the expected number of elements
33 int extraRoom = (int) (size * 1.5f);
34     if (this.threshold == extraRoom)
35         extraRoom++;
36     this.keyTable = new Object JavaDoc[extraRoom];
37     this.valueTable = new Object JavaDoc[extraRoom];
38 }
39
40 public Object JavaDoc clone() throws CloneNotSupportedException JavaDoc {
41     SimpleLookupTable result = (SimpleLookupTable) super.clone();
42     result.elementSize = this.elementSize;
43     result.threshold = this.threshold;
44
45     int length = this.keyTable.length;
46     result.keyTable = new Object JavaDoc[length];
47     System.arraycopy(this.keyTable, 0, result.keyTable, 0, length);
48
49     length = this.valueTable.length;
50     result.valueTable = new Object JavaDoc[length];
51     System.arraycopy(this.valueTable, 0, result.valueTable, 0, length);
52     return result;
53 }
54
55 public boolean containsKey(Object JavaDoc key) {
56     int length = keyTable.length;
57     int index = (key.hashCode() & 0x7FFFFFFF) % length;
58     Object JavaDoc currentKey;
59     while ((currentKey = keyTable[index]) != null) {
60         if (currentKey.equals(key)) return true;
61         if (++index == length) index = 0;
62     }
63     return false;
64 }
65
66 public Object JavaDoc get(Object JavaDoc key) {
67     int length = keyTable.length;
68     int index = (key.hashCode() & 0x7FFFFFFF) % length;
69     Object JavaDoc currentKey;
70     while ((currentKey = keyTable[index]) != null) {
71         if (currentKey.equals(key)) return valueTable[index];
72         if (++index == length) index = 0;
73     }
74     return null;
75 }
76
77 public Object JavaDoc getKey(Object JavaDoc key) {
78     int length = keyTable.length;
79     int index = (key.hashCode() & 0x7FFFFFFF) % length;
80     Object JavaDoc currentKey;
81     while ((currentKey = keyTable[index]) != null) {
82         if (currentKey.equals(key)) return currentKey;
83         if (++index == length) index = 0;
84     }
85     return key;
86 }
87
88 public Object JavaDoc keyForValue(Object JavaDoc valueToMatch) {
89     if (valueToMatch != null)
90         for (int i = 0, l = keyTable.length; i < l; i++)
91             if (keyTable[i] != null && valueToMatch.equals(valueTable[i]))
92                 return keyTable[i];
93     return null;
94 }
95
96 public Object JavaDoc put(Object JavaDoc key, Object JavaDoc value) {
97     int length = keyTable.length;
98     int index = (key.hashCode() & 0x7FFFFFFF) % length;
99     Object JavaDoc currentKey;
100     while ((currentKey = keyTable[index]) != null) {
101         if (currentKey.equals(key)) return valueTable[index] = value;
102         if (++index == length) index = 0;
103     }
104     keyTable[index] = key;
105     valueTable[index] = value;
106
107     // assumes the threshold is never equal to the size of the table
108 if (++elementSize > threshold) rehash();
109     return value;
110 }
111
112 public Object JavaDoc removeKey(Object JavaDoc key) {
113     int length = keyTable.length;
114     int index = (key.hashCode() & 0x7FFFFFFF) % length;
115     Object JavaDoc currentKey;
116     while ((currentKey = keyTable[index]) != null) {
117         if (currentKey.equals(key)) {
118             elementSize--;
119             Object JavaDoc oldValue = valueTable[index];
120             keyTable[index] = null;
121             valueTable[index] = null;
122             if (keyTable[index + 1 == length ? 0 : index + 1] != null)
123                 rehash(); // only needed if a possible collision existed
124 return oldValue;
125         }
126         if (++index == length) index = 0;
127     }
128     return null;
129 }
130
131 public void removeValue(Object JavaDoc valueToRemove) {
132     boolean rehash = false;
133     for (int i = 0, l = valueTable.length; i < l; i++) {
134         Object JavaDoc value = valueTable[i];
135         if (value != null && value.equals(valueToRemove)) {
136             elementSize--;
137             keyTable[i] = null;
138             valueTable[i] = null;
139             if (!rehash && keyTable[i + 1 == l ? 0 : i + 1] != null)
140                 rehash = true; // only needed if a possible collision existed
141 }
142     }
143     if (rehash) rehash();
144 }
145
146 private void rehash() {
147     SimpleLookupTable newLookupTable = new SimpleLookupTable(elementSize * 2); // double the number of expected elements
148 Object JavaDoc currentKey;
149     for (int i = keyTable.length; --i >= 0;)
150         if ((currentKey = keyTable[i]) != null)
151             newLookupTable.put(currentKey, valueTable[i]);
152
153     this.keyTable = newLookupTable.keyTable;
154     this.valueTable = newLookupTable.valueTable;
155     this.elementSize = newLookupTable.elementSize;
156     this.threshold = newLookupTable.threshold;
157 }
158
159 public String JavaDoc toString() {
160     String JavaDoc s = ""; //$NON-NLS-1$
161 Object JavaDoc object;
162     for (int i = 0, l = valueTable.length; i < l; i++)
163         if ((object = valueTable[i]) != null)
164             s += keyTable[i].toString() + " -> " + object.toString() + "\n"; //$NON-NLS-2$ //$NON-NLS-1$
165 return s;
166 }
167 }
168
Popular Tags