KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > eclipse > core > internal > preferences > ImmutableMap


1 /*******************************************************************************
2  * Copyright (c) 2005 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.core.internal.preferences;
12
13 import org.eclipse.core.internal.preferences.StringPool;
14
15 /**
16  * Hash table of {String --> String}.
17  *
18  * This map handles collisions using linear probing. When elements are
19  * removed, the entire table is rehashed. Thus this map has good space
20  * characteristics, good insertion and iteration performance, but slower
21  * removal performance than a HashMap.
22  * <p>
23  * This map is thread safe because it is immutable. All methods that modify
24  * the map create and return a new map, rather than modifying the receiver.
25  */
26 public abstract class ImmutableMap implements Cloneable JavaDoc {
27     static class ArrayMap extends ImmutableMap {
28         private static final float LOAD_FACTOR = 0.45f;
29         /**
30          * number of elements in the table
31          */
32         private int elementSize;
33
34         /**
35          * The table keys
36          */
37         private String JavaDoc[] keyTable;
38
39         private int threshold;
40         private String JavaDoc[] valueTable;
41
42         ArrayMap(int size) {
43             this.elementSize = 0;
44             //table size must always be a power of two
45 int tableLen = 1;
46             while (tableLen < size)
47                 tableLen *= 2;
48             this.keyTable = new String JavaDoc[tableLen];
49             this.valueTable = new String JavaDoc[tableLen];
50             this.threshold = (int) (tableLen * LOAD_FACTOR);
51         }
52
53         public String JavaDoc get(String JavaDoc key) {
54             int lengthMask = keyTable.length - 1;
55             int index = key.hashCode() & lengthMask;
56             String JavaDoc currentKey;
57             while ((currentKey = keyTable[index]) != null) {
58                 if (currentKey.equals(key))
59                     return valueTable[index];
60                 index = (index + 1) & lengthMask;
61             }
62             return null;
63         }
64
65         /**
66          * This method destructively adds the key/value pair to the table.
67          * The caller must ensure the table has an empty slot before calling
68          * this method.
69          * @param key
70          * @param value
71          */
72         protected void internalPut(String JavaDoc key, String JavaDoc value) {
73             int lengthMask = keyTable.length - 1;
74             int index = key.hashCode() & lengthMask;
75             String JavaDoc currentKey;
76             while ((currentKey = keyTable[index]) != null) {
77                 if (currentKey.equals(key)) {
78                     valueTable[index] = value;
79                     return;
80                 }
81                 index = (index + 1) & lengthMask;
82             }
83             keyTable[index] = key;
84             valueTable[index] = value;
85             ++elementSize;
86         }
87
88         /**
89          * Returns an array of all keys in this map.
90          */
91         public String JavaDoc[] keys() {
92             if (elementSize == 0)
93                 return EMPTY_STRING_ARRAY;
94             String JavaDoc[] result = new String JavaDoc[elementSize];
95             int next = 0;
96             for (int i = 0; i < keyTable.length; i++)
97                 if (keyTable[i] != null)
98                     result[next++] = keyTable[i];
99             return result;
100         }
101
102         public ImmutableMap put(String JavaDoc key, String JavaDoc value) {
103             ArrayMap result;
104             final int oldLen = keyTable.length;
105             if (elementSize + 1 > threshold) {
106                 //rehash case
107 String JavaDoc currentKey;
108                 result = new ArrayMap(oldLen * 2);
109                 for (int i = oldLen; --i >= 0;)
110                     if ((currentKey = keyTable[i]) != null)
111                         result.internalPut(currentKey, valueTable[i]);
112             } else {
113                 result = new ArrayMap(oldLen);
114                 System.arraycopy(this.keyTable, 0, result.keyTable, 0, this.keyTable.length);
115                 System.arraycopy(this.valueTable, 0, result.valueTable, 0, this.valueTable.length);
116                 result.elementSize = this.elementSize;
117             }
118             result.internalPut(key, value);
119             return result;
120         }
121
122         public ImmutableMap removeKey(String JavaDoc key) {
123             final int lengthMask = keyTable.length - 1;
124             int index = key.hashCode() & lengthMask;
125             String JavaDoc currentKey;
126             while ((currentKey = keyTable[index]) != null) {
127                 if (currentKey.equals(key)) {
128                     if (elementSize <= 1)
129                         return EMPTY;
130                     //return a new map that includes all keys except the current one
131 ImmutableMap result = createMap((int) (elementSize / LOAD_FACTOR));
132                     for (int i = 0; i < index; i++)
133                         if ((currentKey = keyTable[i]) != null)
134                             result.internalPut(currentKey, valueTable[i]);
135                     for (int i = index + 1; i <= lengthMask; i++)
136                         if ((currentKey = keyTable[i]) != null)
137                             result.internalPut(currentKey, valueTable[i]);
138                     return result;
139                 }
140                 index = (index + 1) & lengthMask;
141             }
142             return this;
143         }
144
145         /* (non-Javadoc
146          * Method declared on IStringPoolParticipant
147          */
148         public void shareStrings(StringPool set) {
149             //copy elements for thread safety
150 String JavaDoc[] array = keyTable;
151             if (array == null)
152                 return;
153             for (int i = 0; i < array.length; i++) {
154                 String JavaDoc o = array[i];
155                 if (o != null)
156                     array[i] = set.add(o);
157             }
158             array = valueTable;
159             if (array == null)
160                 return;
161             for (int i = 0; i < array.length; i++) {
162                 String JavaDoc o = array[i];
163                 if (o != null)
164                     array[i] = set.add(o);
165             }
166         }
167
168         public int size() {
169             return elementSize;
170         }
171
172     }
173
174     static class EmptyMap extends ImmutableMap {
175         public String JavaDoc get(String JavaDoc value) {
176             return null;
177         }
178
179         public ImmutableMap removeKey(String JavaDoc key) {
180             return this;
181         }
182         
183         protected void internalPut(String JavaDoc key, String JavaDoc value) {
184             throw new IllegalStateException JavaDoc();//cannot put elements in the empty map
185 }
186
187         public String JavaDoc[] keys() {
188             return EMPTY_STRING_ARRAY;
189         }
190
191         public ImmutableMap put(String JavaDoc key, String JavaDoc value) {
192             ImmutableMap result = createMap(4);
193             result.internalPut(key, value);
194             return result;
195         }
196
197         public int size() {
198             return 0;
199         }
200     }
201
202     /**
203      * The empty hash map. Since instances are immutable, the empty map
204      * can be a singleton, with accessor methods optimized for the empty map case.
205      */
206     public static final ImmutableMap EMPTY = new EmptyMap();
207
208     protected static final String JavaDoc[] EMPTY_STRING_ARRAY = new String JavaDoc[0];
209
210     /**
211      * Returns the value associated with this key in the map, or
212      * <code>null</code> if the key is not present in the map.
213      * @param key
214      * @return The value associated with this key, or <code>null</code>
215      */
216     public abstract String JavaDoc get(String JavaDoc key);
217     
218     protected static ImmutableMap createMap(int i) {
219         if (i <= 0)
220             return EMPTY;
221         return new ArrayMap(i);
222     }
223
224     /**
225      * Destructively adds a key/value pair to this map. The caller must ensure
226      * there is enough room in this map to proceed.
227      *
228      * @param key
229      * @param value
230      */
231     protected abstract void internalPut(String JavaDoc key, String JavaDoc value);
232
233     /**
234      * Returns an array of all keys in this map.
235      */
236     public abstract String JavaDoc[] keys();
237
238     /**
239      * Returns a new map that is equal to this one, except with the given
240      * key/value pair added.
241      *
242      * @param key
243      * @param value
244      * @return The map containing the given key/value pair
245      */
246     public abstract ImmutableMap put(String JavaDoc key, String JavaDoc value);
247
248     /**
249      * Returns a map that is equal to this one, except without the given
250      * key.
251      * @param key
252      * @return A map with the given key removed
253      */
254     public abstract ImmutableMap removeKey(String JavaDoc key);
255
256     /* (non-Javadoc
257      * Method declared on IStringPoolParticipant
258      */
259     public void shareStrings(StringPool set) {
260     }
261
262     /**
263      * Returns the number of keys in this map.
264      * @return the number of keys in this map.
265      */
266     public abstract int size();
267
268     public String JavaDoc toString() {
269         StringBuffer JavaDoc s = new StringBuffer JavaDoc();
270         String JavaDoc[] keys = keys();
271         for (int i = 0, length = keys.length; i < length; i++)
272             s.append(keys[i]).append(" -> ").append(get(keys[i])).append("\n"); //$NON-NLS-2$ //$NON-NLS-1$
273 return s.toString();
274     }
275 }
276
Popular Tags