Source code: ognl/IntHashMap.java
1 //--------------------------------------------------------------------------
2 // Copyright (c) 1998-2004, Drew Davidson and Luke Blanshard
3 // All rights reserved.
4 //
5 // Redistribution and use in source and binary forms, with or without
6 // modification, are permitted provided that the following conditions are
7 // met:
8 //
9 // Redistributions of source code must retain the above copyright notice,
10 // this list of conditions and the following disclaimer.
11 // Redistributions in binary form must reproduce the above copyright
12 // notice, this list of conditions and the following disclaimer in the
13 // documentation and/or other materials provided with the distribution.
14 // Neither the name of the Drew Davidson nor the names of its contributors
15 // may be used to endorse or promote products derived from this software
16 // without specific prior written permission.
17 //
18 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
19 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
20 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
21 // FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
22 // COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
23 // INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
24 // BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
25 // OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
26 // AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
27 // OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF
28 // THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH
29 // DAMAGE.
30 //--------------------------------------------------------------------------
31 package ognl;
32
33 import java.util.*;
34
35 /**
36 * A Map that uses ints as the keys.
37 * <p>Use just like any java.util.Map, except that the keys must be ints.
38 * This is much faster than creating a new Integer for each access.</p>
39 * <p>For non-Map access (faster) use the put(int, Object) method.</p>
40 * <p>This class implements Map for convenience, but this is not the most
41 * efficient usage.</p>
42 * @see java.util.HashMap
43 * @see java.util.Map
44 */
45 public class IntHashMap extends Object implements Map
46 {
47 private Entry table[];
48 private int count;
49 private int threshold;
50 private float loadFactor;
51
52 /*===================================================================
53 Private static classes
54 ===================================================================*/
55 private static class IntHashMapIterator implements Iterator
56 {
57 boolean keys;
58 int index;
59 Entry table[];
60 Entry entry;
61
62 IntHashMapIterator(Entry table[], boolean keys)
63 {
64 super();
65 this.table = table;
66 this.keys = keys;
67 this.index = table.length;
68 }
69
70 /*===================================================================
71 Iterator interface
72 ===================================================================*/
73 public boolean hasNext()
74 {
75 if (entry != null) {
76 return true;
77 }
78 while (index-- > 0) {
79 if ((entry = table[index]) != null) {
80 return true;
81 }
82 }
83 return false;
84 }
85
86 public Object next()
87 {
88 if (entry == null) {
89 while ((index-- > 0) && ((entry = table[index]) == null)) {
90 /* do nothing */
91 }
92 }
93 if (entry != null) {
94 Entry e = entry;
95
96 entry = e.next;
97 return keys ? new Integer(e.key) : e.value;
98 }
99 throw new NoSuchElementException("IntHashMapIterator");
100 }
101
102 public void remove()
103 {
104 throw new UnsupportedOperationException("remove");
105 }
106 }
107
108 /*===================================================================
109 Public static classes
110 ===================================================================*/
111 public static class Entry extends Object
112 {
113 int hash;
114 int key;
115 Object value;
116 Entry next;
117
118 public Entry()
119 {
120 super();
121 }
122 }
123
124 /*===================================================================
125 Constructors
126 ===================================================================*/
127 public IntHashMap(int initialCapacity, float loadFactor)
128 {
129 super();
130 if (initialCapacity <= 0 || loadFactor <= 0.0) {
131 throw new IllegalArgumentException();
132 }
133 this.loadFactor = loadFactor;
134 table = new Entry[initialCapacity];
135 threshold = (int)(initialCapacity * loadFactor);
136 }
137
138 public IntHashMap(int initialCapacity)
139 {
140 this(initialCapacity, 0.75f);
141 }
142
143 public IntHashMap()
144 {
145 this(101, 0.75f);
146 }
147
148 /*===================================================================
149 Protected methods
150 ===================================================================*/
151 protected void rehash()
152 {
153 int oldCapacity = table.length;
154 Entry oldTable[] = table;
155 int newCapacity = oldCapacity * 2 + 1;
156 Entry newTable[] = new Entry[newCapacity];
157
158 threshold = (int)(newCapacity * loadFactor);
159 table = newTable;
160 for (int i = oldCapacity ; i-- > 0 ;) {
161 for (Entry old = oldTable[i] ; old != null;) {
162 Entry e = old;
163 int index = ( e.hash & 0x7FFFFFFF ) % newCapacity;
164
165 old = old.next;
166 e.next = newTable[index];
167 newTable[index] = e;
168 }
169 }
170 }
171
172 /*===================================================================
173 Public methods
174 ===================================================================*/
175 public final boolean containsKey(int key)
176 {
177 int index = (key & 0x7FFFFFFF) % table.length;
178
179 for (Entry e = table[index] ; e != null ; e = e.next) {
180 if ((e.hash == key) && (e.key == key)) {
181 return true;
182 }
183 }
184 return false;
185 }
186
187 public final Object get(int key)
188 {
189 int index = (key & 0x7FFFFFFF) % table.length;
190
191 for (Entry e = table[index] ; e != null ; e = e.next) {
192 if ((e.hash == key) && (e.key == key)) {
193 return e.value;
194 }
195 }
196 return null;
197 }
198
199 public final Object put(int key, Object value)
200 {
201 int index = ( key & 0x7FFFFFFF ) % table.length;
202
203 if (value == null) {
204 throw new IllegalArgumentException();
205 }
206 for (Entry e = table[index] ; e != null ; e = e.next) {
207 if ((e.hash == key) && (e.key == key)) {
208 Object old = e.value;
209
210 e.value = value;
211 return old;
212 }
213 }
214
215 if (count >= threshold) {
216 // Rehash the table if the threshold is exceeded.
217 rehash();
218 return put(key, value);
219 }
220
221 Entry e = new Entry();
222
223 e.hash = key;
224 e.key = key;
225 e.value = value;
226 e.next = table[index];
227 table[index] = e;
228 ++count;
229 return null;
230 }
231
232 public final Object remove(int key)
233 {
234 int index = (key & 0x7FFFFFFF) % table.length;
235
236 for (Entry e = table[index], prev = null ; e != null ; prev = e, e = e.next) {
237 if ((e.hash == key) && (e.key == key)) {
238 if ( prev != null ) {
239 prev.next = e.next;
240 } else {
241 table[index] = e.next;
242 }
243 --count;
244 return e.value;
245 }
246 }
247 return null;
248 }
249
250 /*===================================================================
251 Map interface
252 ===================================================================*/
253 public int size()
254 {
255 return count;
256 }
257
258 public boolean isEmpty()
259 {
260 return count == 0;
261 }
262
263 public Object get(Object key)
264 {
265 if (!(key instanceof Number)) {
266 throw new IllegalArgumentException("key is not an Number subclass");
267 }
268 return get(((Number)key).intValue());
269 }
270
271 public Object put(Object key, Object value)
272 {
273 if (!(key instanceof Number)) {
274 throw new IllegalArgumentException( "key cannot be null" );
275 }
276 return put(((Number)key).intValue(), value );
277 }
278
279 public void putAll(Map otherMap)
280 {
281 for (Iterator it = otherMap.keySet().iterator(); it.hasNext();) {
282 Object k = it.next();
283
284 put(k, otherMap.get(k));
285 }
286 }
287
288 public Object remove(Object key)
289 {
290 if (!(key instanceof Number)) {
291 throw new IllegalArgumentException("key cannot be null");
292 }
293 return remove(((Number)key).intValue());
294 }
295
296 public void clear()
297 {
298 Entry tab[] = table;
299
300 for (int index = tab.length; --index >= 0;) {
301 tab[index] = null;
302 }
303 count = 0;
304 }
305
306 public boolean containsKey(Object key)
307 {
308 if (!(key instanceof Number)) {
309 throw new InternalError( "key is not an Number subclass" );
310 }
311 return containsKey(((Number)key).intValue());
312 }
313
314 public boolean containsValue(Object value)
315 {
316 Entry tab[] = table;
317
318 if (value == null) {
319 throw new IllegalArgumentException();
320 }
321 for (int i = tab.length ; i-- > 0;) {
322 for (Entry e = tab[i] ; e != null ; e = e.next ) {
323 if (e.value.equals(value)) {
324 return true;
325 }
326 }
327 }
328 return false;
329 }
330
331 public Set keySet()
332 {
333 Set result = new HashSet();
334
335 for (Iterator it = new IntHashMapIterator(table, true); it.hasNext();) {
336 result.add(it.next());
337 }
338 return result;
339 }
340
341 public Collection values()
342 {
343 List result = new ArrayList();
344
345 for (Iterator it = new IntHashMapIterator(table, false); it.hasNext();) {
346 result.add(it.next());
347 }
348 return result;
349 }
350
351 public Set entrySet()
352 {
353 throw new UnsupportedOperationException("entrySet");
354 }
355 }