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