GlueGen v2.6.0-rc-20250712
GlueGen, Native Binding Generator for Java™ (public API).
IntIntHashMap.java
Go to the documentation of this file.
1/**
2 * Copyright 2010 JogAmp Community. All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without modification, are
5 * permitted provided that the following conditions are met:
6 *
7 * 1. Redistributions of source code must retain the above copyright notice, this list of
8 * conditions and the following disclaimer.
9 *
10 * 2. Redistributions in binary form must reproduce the above copyright notice, this list
11 * of conditions and the following disclaimer in the documentation and/or other materials
12 * provided with the distribution.
13 *
14 * THIS SOFTWARE IS PROVIDED BY JogAmp Community ``AS IS'' AND ANY EXPRESS OR IMPLIED
15 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
16 * FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL JogAmp Community OR
17 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
18 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
19 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
20 * ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
21 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
22 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
23 *
24 * The views and conclusions contained in the software and documentation are those of the
25 * authors and should not be interpreted as representing official policies, either expressed
26 * or implied, of JogAmp Community.
27 */
28
29/**
30 * Created on Sunday, March 28 2010 21:01
31 */
32package com.jogamp.common.util;
33
34import com.jogamp.common.JogampRuntimeException;
35import java.lang.reflect.Constructor;
36import java.lang.reflect.Method;
37import java.security.PrivilegedAction;
38import java.util.ArrayList;
39import java.util.Arrays;
40import java.util.Iterator;
41
42/*
43 * Note: this map is used as template for other maps.
44 */
45
46/**
47 * Fast HashMap for primitive data. Optimized for being GC friendly.
48 * Original code is based on the <a href="http://code.google.com/p/skorpios/"> skorpios project</a>
49 * released under new BSD license.
50 *
51 * @author Michael Bien
52 * @author Simon Goller
53 * @author Sven Gothel
54 *
55 * @see IntObjectHashMap
56 * @see IntLongHashMap
57 * @see LongObjectHashMap
58 * @see LongLongHashMap
59 * @see LongIntHashMap
60 */
61public class /*name*/IntIntHashMap/*name*/ implements Cloneable,
62 Iterable< /*name*/IntIntHashMap/*name*/.Entry > {
63 private final float loadFactor;
64
65 private Entry[] table;
66
67 private int size;
68 private int mask;
69 private int capacity;
70 private int threshold;
71 private /*value*/int/*value*/ keyNotFoundValue = /*null*/-1/*null*/;
72
73 private static final boolean isPrimitive;
74 private static final Constructor</*name*/IntIntHashMap/*name*/.Entry> entryConstructor;
75 private static final Method equalsMethod;
76
77 static class EntryCM { EntryCM() { c = null; m1 = null; } Constructor<Entry> c; Method m1; }
78
79 static {
80 final Class<?> valueClazz = /*value*/int/*value*/.class;
81 final Class<?> keyClazz = /*key*/int/*key*/.class;
82
83 isPrimitive = valueClazz.isPrimitive();
84
85 if(!isPrimitive) {
86 final EntryCM cm = SecurityUtil.doPrivileged(new PrivilegedAction<EntryCM>() {
87 @Override
88 @SuppressWarnings("unchecked")
89 public EntryCM run() {
90 final EntryCM r = new EntryCM();
91 r.c = (Constructor<Entry>)
93 new Class[] { keyClazz, valueClazz, Entry.class } );
94 try {
95 r.m1 = valueClazz.getDeclaredMethod("equals", Object.class);
96 } catch (final NoSuchMethodException ex) {
97 throw new JogampRuntimeException("Class "+valueClazz+" doesn't support equals(Object)");
98 }
99 return r;
100 } } );
101 entryConstructor = cm.c;
102 equalsMethod = cm.m1;
103 } else {
104 entryConstructor = null;
105 equalsMethod = null;
106 }
107 }
108
109 public /*name*/IntIntHashMap/*name*/() {
110 this(16, 0.75f);
111 }
112
113 public /*name*/IntIntHashMap/*name*/(final int initialCapacity) {
114 this(initialCapacity, 0.75f);
115 }
116
117 public /*name*/IntIntHashMap/*name*/(final int initialCapacity, final float loadFactor) {
118 if (initialCapacity > 1 << 30) {
119 throw new IllegalArgumentException("initialCapacity is too large.");
120 }
121 if (initialCapacity < 0) {
122 throw new IllegalArgumentException("initialCapacity must be greater than zero.");
123 }
124 if (loadFactor <= 0) {
125 throw new IllegalArgumentException("loadFactor must be greater than zero.");
126 }
127 capacity = 1;
128 while (capacity < initialCapacity) {
129 capacity <<= 1;
130 }
131 this.loadFactor = loadFactor;
132 this.threshold = (int) (capacity * loadFactor);
133 this.table = new Entry[capacity];
134 this.mask = capacity - 1;
135 }
136
137 private /*name*/IntIntHashMap/*name*/(final float loadFactor, final int table_size, final int size,
138 final int mask, final int capacity, final int threshold,
139 final /*value*/int/*value*/ keyNotFoundValue) {
140 this.loadFactor = loadFactor;
141 this.table = new Entry[table_size];
142 this.size = size;
143
144 this.mask = mask;
145 this.capacity = capacity;
146 this.threshold = threshold;
147
148 this.keyNotFoundValue = keyNotFoundValue;
149 }
150
151 /**
152 * Disclaimer: If the value type doesn't implement {@link Object#clone() clone()}, only the reference is copied.
153 * Note: Due to private fields we cannot implement a copy constructor, sorry.
154 *
155 * @param source the primitive hash map to copy
156 */
157 @Override
158 public Object clone() {
159 final /*name*/IntIntHashMap/*name*/ n =
160 new /*name*/IntIntHashMap/*name*/(loadFactor, table.length, size,
161 mask, capacity, threshold,
162 keyNotFoundValue);
163
164 final ArrayList<Entry> entries = new ArrayList<Entry>();
165 for(int i=table.length-1; i>=0; i--) {
166 // single linked list -> ArrayList
167 Entry se = table[i];
168 while(null != se) {
169 entries.add(se);
170 se = se.next;
171 }
172 // clone ArrayList -> single linked list (bwd)
173 final int count = entries.size();
174 Entry de_next = null;
175 for(int j=count-1; j>=0; j--) {
176 se = entries.remove(j);
177 if( isPrimitive ) {
178 de_next = new Entry(se.key, se.value, de_next);
179 } else {
180 final Object v = ReflectionUtil.callMethod( se.value, getCloneMethod(se.value) );
181 de_next = (Entry) ReflectionUtil.createInstance(entryConstructor, se.key, v, de_next);
182 }
183 }
184 // 1st elem of linked list is table entry
185 n.table[i] = de_next;
186 }
187 return n;
188 }
189
190 public boolean containsValue(final /*value*/int/*value*/ value) {
191 final Entry[] t = this.table;
192 for (int i = t.length; i-- > 0;) {
193 for (Entry e = t[i]; e != null; e = e.next) {
194 if( isPrimitive ) {
195 if (e.value == value) {
196 return true;
197 }
198 } else {
199 final Boolean b = (Boolean) ReflectionUtil.callMethod(value, equalsMethod, e.value);
200 if(b.booleanValue()) {
201 return true;
202 }
203 }
204 }
205 }
206 return false;
207 }
208
209// @SuppressWarnings(value="cast")
210 public boolean containsKey(final /*key*/int/*key*/ key) {
211 final Entry[] t = this.table;
212 final int index = /*keyHash*/key/*keyHash*/ & mask;
213 for (Entry e = t[index]; e != null; e = e.next) {
214 if (e.key == key) {
215 return true;
216 }
217 }
218 return false;
219 }
220
221 /**
222 * Returns the value to which the specified key is mapped,
223 * or {@link #getKeyNotFoundValue} if this map contains no mapping for the key.
224 */
225// @SuppressWarnings(value="cast")
226 public /*value*/int/*value*/ get(final /*key*/int/*key*/ key) {
227 final Entry[] t = this.table;
228 final int index = /*keyHash*/key/*keyHash*/ & mask;
229 for (Entry e = t[index]; e != null; e = e.next) {
230 if (e.key == key) {
231 return e.value;
232 }
233 }
234 return keyNotFoundValue;
235 }
236
237 /**
238 * Maps the key to the specified value. If a mapping to this key already exists,
239 * the previous value will be returned (otherwise {@link #getKeyNotFoundValue}).
240 */
241// @SuppressWarnings(value="cast")
242 public /*value*/int/*value*/ put(final /*key*/int/*key*/ key, final /*value*/int/*value*/ value) {
243 final Entry[] t = this.table;
244 final int index = /*keyHash*/key/*keyHash*/ & mask;
245 // Check if key already exists.
246 for (Entry e = t[index]; e != null; e = e.next) {
247 if (e.key != key) {
248 continue;
249 }
250 final /*value*/int/*value*/ oldValue = e.value;
251 e.value = value;
252 return oldValue;
253 }
254 t[index] = new Entry(key, value, t[index]);
255
256 if (size++ >= threshold) {
257 // Rehash.
258 final int newCapacity = 2 * capacity;
259 final Entry[] newTable = new Entry[newCapacity];
260 final int newMask = newCapacity - 1;
261 for (int j = 0; j < t.length; j++) {
262 Entry e = t[j];
263 if (e != null) {
264 t[j] = null;
265 do {
266 final Entry next = e.next;
267 final int index2 = /*keyHash*/e.key/*keyHash*/ & newMask;
268 e.next = newTable[index2];
269 newTable[index2] = e;
270 e = next;
271 } while (e != null);
272 }
273 }
274 table = newTable;
275 capacity = newCapacity;
276 threshold = (int) (newCapacity * loadFactor);
277 mask = newMask;
278 }
279 return keyNotFoundValue;
280 }
281
282 /**
283 * Copies all of the mappings from the specified map to this map.
284 */
285 public void putAll(final /*name*/IntIntHashMap/*name*/ source) {
286 final Iterator<Entry> itr = source.iterator();
287 while(itr.hasNext()) {
288 final Entry e = itr.next();
289 put(e.key, e.value);
290 }
291 }
292
293 /**
294 * Removes the key-value mapping from this map.
295 * Returns the previously mapped value or {@link #getKeyNotFoundValue} if no such mapping exists.
296 */
297// @SuppressWarnings(value="cast")
298 public /*value*/int/*value*/ remove(final /*key*/int/*key*/ key) {
299 final Entry[] t = this.table;
300 final int index = /*keyHash*/key/*keyHash*/ & mask;
301 Entry prev = t[index];
302 Entry e = prev;
303
304 while (e != null) {
305 final Entry next = e.next;
306 if (e.key == key) {
307 size--;
308 if (prev == e) {
309 t[index] = next;
310 } else {
311 prev.next = next;
312 }
313 return e.value;
314 }
315 prev = e;
316 e = next;
317 }
318 return keyNotFoundValue;
319 }
320
321 /**
322 * Returns the current number of key-value mappings in this map.
323 */
324 public int size() {
325 return size;
326 }
327
328 /**
329 * Returns the current capacity (buckets) in this map.
330 */
331 public int capacity() {
332 return capacity;
333 }
334
335 /**
336 * Clears the entire map. The size is 0 after this operation.
337 */
338 public void clear() {
339 Arrays.fill(table, null);
340 size = 0;
341 }
342
343 /**
344 * Returns a new {@link Iterator}.
345 * Note: this Iterator does not yet support removal of elements.
346 */
347 @Override
348 public Iterator<Entry> iterator() {
349 return new EntryIterator(table);
350 }
351
352 /**
353 * Sets the new key not found value.
354 * For primitive types (int, long) the default is -1,
355 * for Object types, the default is null.
356 *
357 * @return the previous key not found value
358 * @see #get
359 * @see #put
360 */
361 public /*value*/int/*value*/ setKeyNotFoundValue(final /*value*/int/*value*/ newKeyNotFoundValue) {
362 final /*value*/int/*value*/ t = keyNotFoundValue;
363 keyNotFoundValue = newKeyNotFoundValue;
364 return t;
365 }
366
367 /**
368 * Returns the value which is returned if no value has been found for the specified key.
369 * @see #get
370 * @see #put
371 */
372 public /*value*/int/*value*/ getKeyNotFoundValue() {
373 return keyNotFoundValue;
374 }
375
376 /**
377 * @param sb if null, a new StringBuilder is created
378 * @return StringBuilder instance with appended string information of this Entry
379 */
380 public StringBuilder toString(StringBuilder sb) {
381 if(null == sb) {
382 sb = new StringBuilder();
383 }
384 sb.append("{");
385 final Iterator<Entry> itr = iterator();
386 while(itr.hasNext()) {
387 itr.next().toString(sb);
388 if(itr.hasNext()) {
389 sb.append(", ");
390 }
391 }
392 sb.append("}");
393 return sb;
394 }
395
396 @Override
397 public String toString() {
398 return toString(null).toString();
399 }
400
401 private final static class EntryIterator implements Iterator<Entry> {
402
403 private final Entry[] entries;
404
405 private int index;
406 private Entry next;
407
408 private EntryIterator(final Entry[] entries){
409 this.entries = entries;
410 // load next
411 next();
412 }
413
414 @Override
415 public boolean hasNext() {
416 return next != null;
417 }
418
419 @Override
420 public Entry next() {
421 final Entry current = next;
422
423 if(current != null && current.next != null) {
424 next = current.next;
425 }else{
426 while(index < entries.length) {
427 final Entry e = entries[index++];
428 if(e != null) {
429 next = e;
430 return current;
431 }
432 }
433 next = null;
434 }
435
436 return current;
437 }
438
439 @Override
440 public void remove() {
441 throw new UnsupportedOperationException("Not supported yet.");
442 }
443
444 }
445
446 /**
447 * An entry mapping a key to a value.
448 */
449 public final static class Entry {
450
451 public final /*key*/int/*key*/ key;
452 public /*value*/int/*value*/ value;
453
454 Entry next;
455
456 Entry(final /*key*/int/*key*/ k, final /*value*/int/*value*/ v, final Entry n) {
457 key = k;
458 value = v;
459 next = n;
460 }
461
462 /**
463 * Returns the key of this entry.
464 */
465 public /*key*/int/*key*/ getKey() {
466 return key;
467 }
468
469 /**
470 * Returns the value of this entry.
471 */
472 public /*value*/int/*value*/ getValue() {
473 return value;
474 }
475
476 /**
477 * Sets the value for this entry.
478 */
479 public void setValue(final /*value*/int/*value*/ value) {
480 this.value = value;
481 }
482
483 /**
484 * @param sb if null, a new StringBuilder is created
485 * @return StringBuilder instance with appended string information of this Entry
486 */
487 public StringBuilder toString(StringBuilder sb) {
488 if(null == sb) {
489 sb = new StringBuilder();
490 }
491 sb.append("[").append(key).append(":").append(value).append("]");
492 return sb;
493 }
494
495 @Override
496 public String toString() {
497 return toString(null).toString();
498 }
499
500 }
501
502 private static Method getCloneMethod(final Object obj) {
503 final Class<?> clazz = obj.getClass();
504 return SecurityUtil.doPrivileged(new PrivilegedAction<Method>() {
505 @Override
506 public Method run() {
507 try {
508 return clazz.getDeclaredMethod("clone");
509 } catch (final NoSuchMethodException ex) {
510 throw new JogampRuntimeException("Class "+clazz+" doesn't support clone()", ex);
511 }
512 } } );
513 }
514}
A generic unchecked exception for Jogamp errors used throughout the binding as a substitute for Runti...
An entry mapping a key to a value.
int getKey()
Returns the key of this entry.
void setValue(final int value)
Sets the value for this entry.
int getValue()
Returns the value of this entry.
StringBuilder toString(StringBuilder sb)
Fast HashMap for primitive data.
boolean containsValue(final int value)
void putAll(final IntIntHashMap source)
Copies all of the mappings from the specified map to this map.
StringBuilder toString(StringBuilder sb)
int size()
Returns the current number of key-value mappings in this map.
int getKeyNotFoundValue()
Returns the value which is returned if no value has been found for the specified key.
Iterator< Entry > iterator()
Returns a new Iterator.
int put(final int key, final int value)
Maps the key to the specified value.
int setKeyNotFoundValue(final int newKeyNotFoundValue)
Sets the new key not found value.
Object clone()
Disclaimer: If the value type doesn't implement clone(), only the reference is copied.
int capacity()
Returns the current capacity (buckets) in this map.
void clear()
Clears the entire map.
static final Object createInstance(final Constructor<?> cstr, final Object ... cstrArgs)
static final Constructor<?> getConstructor(final String clazzName, final Class<?>[] cstrArgTypes, final boolean initializeClazz, final ClassLoader cl)
static final Object callMethod(final Object instance, final Method method, final Object ... args)
static< T > T doPrivileged(final PrivilegedAction< T > o)
Call wrapper for java.security.AccessController#doPrivileged(PrivilegedAction).