]> gerrit.simantics Code Review - simantics/platform.git/blob - bundles/org.simantics.db.impl/src/org/simantics/db/impl/query/StableHashMap.java
Fail safe import fixes made by Antti
[simantics/platform.git] / bundles / org.simantics.db.impl / src / org / simantics / db / impl / query / StableHashMap.java
1 /*******************************************************************************
2  * Copyright (c) 2007, 2010 Association for Decentralized Information Management
3  * in Industry THTH ry.
4  * All rights reserved. This program and the accompanying materials
5  * are made available under the terms of the Eclipse Public License v1.0
6  * which accompanies this distribution, and is available at
7  * http://www.eclipse.org/legal/epl-v10.html
8  *
9  * Contributors:
10  *     VTT Technical Research Centre of Finland - initial API and implementation
11  *******************************************************************************/
12 package org.simantics.db.impl.query;
13
14 ///////////////////////////////////////////////////////////////////////////////
15 //Copyright (c) 2001, Eric D. Friedman All Rights Reserved.
16 //
17 //This library is free software; you can redistribute it and/or
18 //modify it under the terms of the GNU Lesser General Public
19 //License as published by the Free Software Foundation; either
20 //version 2.1 of the License, or (at your option) any later version.
21 //
22 //This library is distributed in the hope that it will be useful,
23 //but WITHOUT ANY WARRANTY; without even the implied warranty of
24 //MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
25 //GNU General Public License for more details.
26 //
27 //You should have received a copy of the GNU Lesser General Public
28 //License along with this program; if not, write to the Free Software
29 //Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
30 ///////////////////////////////////////////////////////////////////////////////
31
32 import gnu.trove.function.TObjectFunction;
33 import gnu.trove.procedure.TObjectObjectProcedure;
34 import gnu.trove.procedure.TObjectProcedure;
35
36 import java.io.Externalizable;
37 import java.util.ArrayList;
38 import java.util.Arrays;
39 import java.util.Collection;
40 import java.util.Iterator;
41 import java.util.Map;
42 import java.util.Set;
43
44 /**
45  * An implementation of the Map interface which uses an open addressed
46  * hash table to store its contents.
47  *
48  * Created: Sun Nov  4 08:52:45 2001
49  *
50  * @author Eric D. Friedman
51  * @version $Id: THashMap.java,v 1.33 2008/05/08 17:42:55 robeden Exp $
52  */
53 public class StableHashMap<K,V> extends StableObjectHash<K> implements Map<K,V>, Externalizable {
54     static final long serialVersionUID = 1L;
55
56     /** the values of the  map */
57     protected transient V[] _values;
58
59     /**
60      * Creates a new <code>THashMap</code> instance with the default
61      * capacity and load factor.
62      */
63     public StableHashMap() {
64         super();
65     }
66
67 //    /**
68 //     * Creates a new <code>THashMap</code> instance with a prime
69 //     * capacity equal to or greater than <tt>initialCapacity</tt> and
70 //     * with the default load factor.
71 //     *
72 //     * @param initialCapacity an <code>int</code> value
73 //     */
74 //    public StableHashMap(int initialCapacity) {
75 //        super(initialCapacity);
76 //    }
77
78 //    /**
79 //     * Creates a new <code>THashMap</code> instance with a prime
80 //     * capacity equal to or greater than <tt>initialCapacity</tt> and
81 //     * with the default load factor.
82 //     *
83 //     * @param initialCapacity an <code>int</code> value
84 //     * @param strategy used to compute hash codes and to compare objects.
85 //     */
86 //    public StableHashMap(int initialCapacity, TObjectHashingStrategy<K> strategy) {
87 //        super(initialCapacity, strategy);
88 //    }
89
90 //    /**
91 //     * Creates a new <code>THashMap</code> instance with a prime
92 //     * capacity equal to or greater than <tt>initialCapacity</tt> and
93 //     * with the specified load factor.
94 //     *
95 //     * @param initialCapacity an <code>int</code> value
96 //     * @param loadFactor a <code>float</code> value
97 //     */
98 //    public StableHashMap(int initialCapacity, float loadFactor) {
99 //        super(initialCapacity, loadFactor);
100 //    }
101
102 //    /**
103 //     * Creates a new <code>THashMap</code> instance with a prime
104 //     * capacity equal to or greater than <tt>initialCapacity</tt> and
105 //     * with the specified load factor.
106 //     *
107 //     * @param initialCapacity an <code>int</code> value
108 //     * @param loadFactor a <code>float</code> value
109 //     * @param strategy used to compute hash codes and to compare objects.
110 //     */
111 //    public StableHashMap(int initialCapacity, float loadFactor, TObjectHashingStrategy<K> strategy) {
112 //        super(initialCapacity, loadFactor, strategy);
113 //    }
114
115 //    /**
116 //     * Creates a new <code>THashMap</code> instance which contains the
117 //     * key/value pairs in <tt>map</tt>.
118 //     *
119 //     * @param map a <code>Map</code> value
120 //     */
121 //    public StableHashMap(Map<K,V> map) {
122 //        this(map.size());
123 //        putAll(map);
124 //    }
125 //
126 //    /**
127 //     * Creates a new <code>THashMap</code> instance which contains the
128 //     * key/value pairs in <tt>map</tt>.
129 //     *
130 //     * @param map a <code>Map</code> value
131 //     * @param strategy used to compute hash codes and to compare objects.
132 //     */
133 //    public StableHashMap(Map<K,V> map, TObjectHashingStrategy<K> strategy) {
134 //        this(map.size(), strategy);
135 //        putAll(map);
136 //    }
137
138     /**
139      * @return a shallow clone of this collection
140      */
141     public StableHashMap<K,V> clone() {
142         StableHashMap<K,V> m = (StableHashMap<K,V>)super.clone();
143         m._values = this._values.clone();
144         return m;
145     }
146
147     /**
148      * initialize the value array of the map.
149      *
150      * @param initialCapacity an <code>int</code> value
151      * @return an <code>int</code> value
152      */
153     protected int setUp(int initialCapacity) {
154         int capacity;
155
156         capacity = super.setUp(initialCapacity);
157         //noinspection unchecked
158         _values = (V[]) new Object[capacity];
159         return capacity;
160     }
161
162     /**
163      * Inserts a key/value pair into the map.
164      *
165      * @param key an <code>Object</code> value
166      * @param value an <code>Object</code> value
167      * @return the previous value associated with <tt>key</tt>,
168      * or {@code null} if none was found.
169      */
170     public V put(K key, V value) {
171         int index = insertionIndex(key);
172         return doPut(key, value, index);
173     }
174
175     public V put(K key, V value, int hash) {
176         int index = insertionIndex(key, hash);
177         return doPut(key, value, index);
178     }
179     
180     /**
181      * Inserts a key/value pair into the map if the specified key is not already
182      * associated with a value.
183      * 
184      * @param key an <code>Object</code> value
185      * @param value an <code>Object</code> value
186      * @return the previous value associated with <tt>key</tt>,
187      * or {@code null} if none was found.
188      */
189     public V putIfAbsent(K key, V value) {
190         int index = insertionIndex(key);
191         if (index < 0)
192             return _values[-index - 1];
193         return doPut(key, value, index);
194     }
195
196     private V doPut(K key, V value, int index) {
197         V previous = null;
198         Object oldKey;
199         boolean isNewMapping = true;
200         if (index < 0) {
201             index = -index -1;
202             previous = _values[index];
203             isNewMapping = false;
204         }
205         oldKey = _set[index];
206         _set[index] = key;
207         _values[index] = value;
208         if (isNewMapping) {
209             postInsertHook(oldKey == FREE);
210         }
211
212         return previous;
213     }
214
215     /**
216      * Compares this map with another map for equality of their stored
217      * entries.
218      *
219      * @param other an <code>Object</code> value
220      * @return a <code>boolean</code> value
221      */
222     public boolean equals(Object other) {
223         if (! (other instanceof Map)) {
224             return false;
225         }
226         Map<K, V> that = (Map<K, V>)other;
227         if (that.size() != this.size()) {
228             return false;
229         }
230         return forEachEntry(new EqProcedure<K,V>(that));
231     }
232
233     public int hashCode() {
234         HashProcedure p = new HashProcedure();
235         forEachEntry(p);
236         return p.getHashCode();
237     }
238
239     public String toString() {
240         final StringBuilder buf = new StringBuilder("{");
241         forEachEntry(new TObjectObjectProcedure<K,V>() {
242             private boolean first = true;
243             public boolean execute(K key, V value) {
244                 if ( first ) first = false;
245                 else buf.append( "," );
246
247                 buf.append(key);
248                 buf.append("=");
249                 buf.append(value);
250                 return true;
251             }
252         });
253         buf.append("}");
254         return buf.toString();
255     }
256
257     private final class HashProcedure implements TObjectObjectProcedure<K,V> {
258         private int h = 0;
259
260         public int getHashCode() {
261             return h;
262         }
263
264         public final boolean execute(K key, V value) {
265             h += _hashingStrategy.computeHashCode(key) ^ (value == null ? 0 : value.hashCode());
266             return true;
267         }
268     }
269
270     private static final class EqProcedure<K,V> implements TObjectObjectProcedure<K,V> {
271         private final Map<K,V> _otherMap;
272
273         EqProcedure(Map<K,V> otherMap) {
274             _otherMap = otherMap;
275         }
276
277         public final boolean execute(K key, V value) {
278             // Check to make sure the key is there. This avoids problems that come up with
279             // null values. Since it is only caused in that cause, only do this when the
280             // value is null (to avoid extra work).
281             if (value == null && !_otherMap.containsKey(key)) return false;
282
283             V oValue = _otherMap.get(key);
284             return oValue == value || (oValue != null && oValue.equals(value));
285         }
286     }
287
288     /**
289      * Executes <tt>procedure</tt> for each key in the map.
290      *
291      * @param procedure a <code>TObjectProcedure</code> value
292      * @return false if the loop over the keys terminated because
293      * the procedure returned false for some key.
294      */
295     public boolean forEachKey(TObjectProcedure<K> procedure) {
296         return forEach(procedure);
297     }
298
299     /**
300      * Executes <tt>procedure</tt> for each value in the map.
301      *
302      * @param procedure a <code>TObjectProcedure</code> value
303      * @return false if the loop over the values terminated because
304      * the procedure returned false for some value.
305      */
306     public boolean forEachValue(TObjectProcedure<V> procedure) {
307         V[] values = _values;
308         Object[] set = _set;
309         for (int i = values.length; i-- > 0;) {
310             if (set[i] != FREE
311                     && set[i] != REMOVED
312                     && ! procedure.execute(values[i])) {
313                 return false;
314             }
315         }
316         return true;
317     }
318
319     /**
320      * Executes <tt>procedure</tt> for each key/value entry in the
321      * map.
322      *
323      * @param procedure a <code>TObjectObjectProcedure</code> value
324      * @return false if the loop over the entries terminated because
325      * the procedure returned false for some entry.
326      */
327     public boolean forEachEntry(TObjectObjectProcedure<K,V> procedure) {
328         Object[] keys = _set;
329         V[] values = _values;
330         for (int i = keys.length; i-- > 0;) {
331             if (keys[i] != FREE
332                     && keys[i] != REMOVED
333                     && ! procedure.execute((K) keys[i],values[i])) {
334                 return false;
335             }
336         }
337         return true;
338     }
339
340     /**
341      * Retains only those entries in the map for which the procedure
342      * returns a true value.
343      *
344      * @param procedure determines which entries to keep
345      * @return true if the map was modified.
346      */
347     public boolean retainEntries(TObjectObjectProcedure<K,V> procedure) {
348         boolean modified = false;
349         Object[] keys = _set;
350         V[] values = _values;
351
352         // Temporarily disable compaction. This is a fix for bug #1738760
353         tempDisableAutoCompaction();
354         try {
355             for (int i = keys.length; i-- > 0;) {
356                 if (keys[i] != FREE
357                         && keys[i] != REMOVED
358                         && ! procedure.execute((K) keys[i],values[i])) {
359                     removeAt(i);
360                     modified = true;
361                 }
362             }
363         }
364         finally {
365             reenableAutoCompaction(true);
366         }
367
368         return modified;
369     }
370
371     /**
372      * Transform the values in this map using <tt>function</tt>.
373      *
374      * @param function a <code>TObjectFunction</code> value
375      */
376     public void transformValues(TObjectFunction<V,V> function) {
377         V[] values = _values;
378         Object[] set = _set;
379         for (int i = values.length; i-- > 0;) {
380             if (set[i] != FREE && set[i] != REMOVED) {
381                 values[i] = function.execute(values[i]);
382             }
383         }
384     }
385
386     /**
387      * rehashes the map to the new capacity.
388      *
389      * @param newCapacity an <code>int</code> value
390      */
391     protected void rehash(int newCapacity) {
392         int oldCapacity = _set.length;
393         Object oldKeys[] = _set;
394         V oldVals[] = _values;
395
396         _set = new Object[newCapacity];
397         Arrays.fill(_set, FREE);
398         _values = (V[]) new Object[newCapacity];
399
400         for (int i = oldCapacity; i-- > 0;) {
401             if(oldKeys[i] != FREE && oldKeys[i] != REMOVED) {
402                 Object o = oldKeys[i];
403                 int index = insertionIndex((K) o);
404                 if (index < 0) {
405                     throwObjectContractViolation(_set[(-index -1)], o);
406                 }
407                 _set[index] = o;
408                 _values[index] = oldVals[i];
409             }
410         }
411     }
412
413     /**
414      * retrieves the value for <tt>key</tt>
415      *
416      * @param key an <code>Object</code> value
417      * @return the value of <tt>key</tt> or null if no such mapping exists.
418      */
419     public V get(Object key) {
420         Object[] set = _set;
421         V[] values = _values;
422         int index = index((K) key, set);
423         return index < 0 ? null : values[index];
424     }
425
426     public V get(Object key, int hash) {
427         Object[] set = _set;
428         V[] values = _values;
429         int index = index((K) key, hash, set);
430         return index < 0 ? null : values[index];
431     }
432     
433     /**
434      * Empties the map.
435      *
436      */
437     public void clear() {
438         if (size() == 0) return; // optimization
439
440         super.clear();
441
442         Arrays.fill(_set, 0, _set.length, FREE);
443         Arrays.fill(_values, 0, _values.length, null);
444     }
445
446     /**
447      * Deletes a key/value pair from the map.
448      *
449      * @param key an <code>Object</code> value
450      * @return an <code>Object</code> value
451      */
452     public V remove(Object key) {
453         Object[] set = _set;
454         V[] values = _values;
455         V prev = null;
456         int index = index((K) key, set);
457         if (index >= 0) {
458             prev = values[index];
459             removeAt(index);    // clear key,state; adjust size
460         }
461         return prev;
462     }
463     
464     protected void removeAt(int index) {
465         _values[index] = null;
466         super.removeAt(index);  // clear key, state; adjust size
467     }
468
469     /**
470      * removes the mapping at <tt>index</tt> from the map.
471      *
472      * @param index an <code>int</code> value
473      */
474     protected void removeAt(int index, V[] values) {
475         values[index] = null;
476         super.removeAt(index);  // clear key, state; adjust size
477     }
478
479     public void values(int level, CacheCollectionResult result) {
480
481         for (int i = _set.length; i-- > 0;) {
482                 if(_set[i] != null && _set[i] != REMOVED && _set[i] != FREE) {
483                         CacheEntryBase e = (CacheEntryBase)_values[i];
484                         if(e.getLevel() <= level)
485                                 result.add(e);
486                 }
487         }
488
489     }
490     
491     /**
492      * Returns a view on the values of the map.
493      *
494      * @return a <code>Collection</code> value
495      */
496     public Collection<V> values() {
497
498         Collection<V> result = new ArrayList<V>();
499
500         for (int i = _set.length; i-- > 0;) {
501                 if(_set[i] != null && _set[i] != REMOVED && _set[i] != FREE) {
502                         result.add((V)_values[i]);
503                 }
504         }
505
506         return result;
507         
508     }
509
510     /**
511      * returns a Set view on the keys of the map.
512      *
513      * @return a <code>Set</code> value
514      */
515     public Set<K> keySet() {
516         throw new UnsupportedOperationException();
517     }
518
519     /**
520      * Returns a Set view on the entries of the map.
521      *
522      * @return a <code>Set</code> value
523      */
524     public Set<Map.Entry<K,V>> entrySet() {
525         throw new UnsupportedOperationException();
526     }
527
528     /**
529      * checks for the presence of <tt>val</tt> in the values of the map.
530      *
531      * @param val an <code>Object</code> value
532      * @return a <code>boolean</code> value
533      */
534     public boolean containsValue(Object val) {
535         Object[] set = _set;
536         V[] vals = _values;
537
538         // special case null values so that we don't have to
539         // perform null checks before every call to equals()
540         if (null == val) {
541             for (int i = vals.length; i-- > 0;) {
542                 if ((set[i] != FREE && set[i] != REMOVED) &&
543                         val == vals[i]) {
544                     return true;
545                 }
546             }
547         } else {
548             for (int i = vals.length; i-- > 0;) {
549                 if ((set[i] != FREE && set[i] != REMOVED) &&
550                         (val == vals[i] || val.equals(vals[i]))) {
551                     return true;
552                 }
553             }
554         } // end of else
555         return false;
556     }
557
558     /**
559      * checks for the present of <tt>key</tt> in the keys of the map.
560      *
561      * @param key an <code>Object</code> value
562      * @return a <code>boolean</code> value
563      */
564     public boolean containsKey(Object key) {
565         return contains(key);
566     }
567
568     /**
569      * copies the key/value mappings in <tt>map</tt> into this map.
570      *
571      * @param map a <code>Map</code> value
572      */
573     public void putAll(Map<? extends K, ? extends V> map) {
574         ensureCapacity(map.size());
575         // could optimize this for cases when map instanceof THashMap
576         for (Iterator<? extends Map.Entry<? extends K,? extends V>> i = map.entrySet().iterator(); i.hasNext();) {
577             Map.Entry<? extends K,? extends V> e = i.next();
578             put(e.getKey(),e.getValue());
579         }
580     }
581     
582 } // THashMap