bundles/org.simantics.db.impl/src/org/simantics/db/impl/query/StableHashMap.java

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