bundles/org.simantics.db.impl/src/org/simantics/db/impl/query/StableObjectHash.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.impl.hash.THash;\r
  33 import gnu.trove.procedure.TObjectProcedure;\r
  34 import gnu.trove.strategy.HashingStrategy;\r
  35 \r
  36 import java.io.IOException;\r
  37 import java.io.ObjectInput;\r
  38 import java.io.ObjectOutput;\r
  39 import java.util.Arrays;\r
  40 \r
  41 \r
  42 /**\r
  43 * An open addressed hashing implementation for Object types.\r
  44 *\r
  45 * Created: Sun Nov  4 08:56:06 2001\r
  46 *\r
  47 * @author Eric D. Friedman\r
  48 * @version $Id: TObjectHash.java,v 1.26 2008/05/07 21:25:45 robeden Exp $\r
  49 */\r
  50 abstract public class StableObjectHash<T> extends THash\r
  51  implements HashingStrategy<T> {\r
  52 \r
  53  static final long serialVersionUID = -3461112548087185871L;\r
  54 \r
  55 \r
  56  /** the set of Objects */\r
  57  protected transient Object[] _set;\r
  58 \r
  59  /** the strategy used to hash objects in this collection. */\r
  60  protected HashingStrategy<T> _hashingStrategy;\r
  61 \r
  62  protected static final Object REMOVED = new Object(), FREE = new Object();\r
  63 \r
  64  /**\r
  65   * Creates a new <code>TObjectHash</code> instance with the\r
  66   * default capacity and load factor.\r
  67   */\r
  68  public StableObjectHash() {\r
  69      super(DEFAULT_CAPACITY, 0.75f);\r
  70      this._hashingStrategy = this;\r
  71  }\r
  72 \r
  73 // /**\r
  74 //  * Creates a new <code>TObjectHash</code> instance with the\r
  75 //  * default capacity and load factor and a custom hashing strategy.\r
  76 //  *\r
  77 //  * @param strategy used to compute hash codes and to compare objects.\r
  78 //  */\r
  79 // public StableObjectHash(TObjectHashingStrategy<T> strategy) {\r
  80 //     super();\r
  81 //     this._hashingStrategy = strategy;\r
  82 // }\r
  83 //\r
  84 // /**\r
  85 //  * Creates a new <code>TObjectHash</code> instance whose capacity\r
  86 //  * is the next highest prime above <tt>initialCapacity + 1</tt>\r
  87 //  * unless that value is already prime.\r
  88 //  *\r
  89 //  * @param initialCapacity an <code>int</code> value\r
  90 //  */\r
  91 // public StableObjectHash(int initialCapacity) {\r
  92 //     super(initialCapacity);\r
  93 //     this._hashingStrategy = this;\r
  94 // }\r
  95 //\r
  96 // /**\r
  97 //  * Creates a new <code>TObjectHash</code> instance whose capacity\r
  98 //  * is the next highest prime above <tt>initialCapacity + 1</tt>\r
  99 //  * unless that value is already prime.  Uses the specified custom\r
 100 //  * hashing strategy.\r
 101 //  *\r
 102 //  * @param initialCapacity an <code>int</code> value\r
 103 //  * @param strategy used to compute hash codes and to compare objects.\r
 104 //  */\r
 105 // public StableObjectHash(int initialCapacity, TObjectHashingStrategy<T> strategy) {\r
 106 //     super(initialCapacity);\r
 107 //     this._hashingStrategy = strategy;\r
 108 // }\r
 109 //\r
 110 // /**\r
 111 //  * Creates a new <code>TObjectHash</code> instance with a prime\r
 112 //  * value at or near the specified capacity and load factor.\r
 113 //  *\r
 114 //  * @param initialCapacity used to find a prime capacity for the table.\r
 115 //  * @param loadFactor used to calculate the threshold over which\r
 116 //  * rehashing takes place.\r
 117 //  */\r
 118 // public StableObjectHash(int initialCapacity, float loadFactor) {\r
 119 //     super(initialCapacity, loadFactor);\r
 120 //     this._hashingStrategy = this;\r
 121 // }\r
 122 //\r
 123 // /**\r
 124 //  * Creates a new <code>TObjectHash</code> instance with a prime\r
 125 //  * value at or near the specified capacity and load factor.  Uses\r
 126 //  * the specified custom hashing strategy.\r
 127 //  *\r
 128 //  * @param initialCapacity used to find a prime capacity for the table.\r
 129 //  * @param loadFactor used to calculate the threshold over which\r
 130 //  * rehashing takes place.\r
 131 //  * @param strategy used to compute hash codes and to compare objects.\r
 132 //  */\r
 133 // public StableObjectHash(int initialCapacity, float loadFactor, TObjectHashingStrategy<T> strategy) {\r
 134 //     super(initialCapacity, loadFactor);\r
 135 //     this._hashingStrategy = strategy;\r
 136 // }\r
 137 \r
 138  /**\r
 139   * @return a shallow clone of this collection\r
 140   */\r
 141  public StableObjectHash<T> clone() {\r
 142      StableObjectHash<T> h;\r
 143      try {\r
 144          h = (StableObjectHash<T>)super.clone();\r
 145      } catch (CloneNotSupportedException e) {\r
 146          // It's supported\r
 147          throw new Error(e);\r
 148      }\r
 149      h._set = (Object[])this._set.clone();\r
 150      return h;\r
 151  }\r
 152 \r
 153  public int capacity() {\r
 154      return _set.length;\r
 155  }\r
 156 \r
 157  protected void removeAt(int index) {\r
 158      _set[index] = REMOVED;\r
 159      super.removeAt(index);\r
 160  }\r
 161 \r
 162  /**\r
 163   * initializes the Object set of this hash table.\r
 164   *\r
 165   * @param initialCapacity an <code>int</code> value\r
 166   * @return an <code>int</code> value\r
 167   */\r
 168  protected int setUp(int initialCapacity) {\r
 169      int capacity;\r
 170 \r
 171      capacity = super.setUp(initialCapacity);\r
 172      _set = new Object[capacity];\r
 173      Arrays.fill(_set,FREE);\r
 174      return capacity;\r
 175  }\r
 176 \r
 177  /**\r
 178   * Executes <tt>procedure</tt> for each element in the set.\r
 179   *\r
 180   * @param procedure a <code>TObjectProcedure</code> value\r
 181   * @return false if the loop over the set terminated because\r
 182   * the procedure returned false for some value.\r
 183   */\r
 184  public boolean forEach(TObjectProcedure<T> procedure) {\r
 185      Object[] set = _set;\r
 186      for (int i = set.length; i-- > 0;) {\r
 187          if (set[i] != FREE\r
 188              && set[i] != REMOVED\r
 189              && ! procedure.execute((T) set[i])) {\r
 190              return false;\r
 191          }\r
 192      }\r
 193      return true;\r
 194  }\r
 195 \r
 196  /**\r
 197   * Searches the set for <tt>obj</tt>\r
 198   *\r
 199   * @param obj an <code>Object</code> value\r
 200   * @return a <code>boolean</code> value\r
 201   */\r
 202  public boolean contains(Object obj) {\r
 203      throw new UnsupportedOperationException();\r
 204  }\r
 205 \r
 206  /**\r
 207   * Locates the index of <tt>obj</tt>.\r
 208   *\r
 209   * @param obj an <code>Object</code> value\r
 210   * @return the index of <tt>obj</tt> or -1 if it isn't in the set.\r
 211   */\r
 212  protected int index(T obj, Object[] _set) {\r
 213 \r
 214      final Object[] set = _set;\r
 215      final int length = set.length;\r
 216      final int hash = obj.hashCode() & 0x7fffffff;\r
 217      int index = hash % length;\r
 218      Object cur = set[index];\r
 219 \r
 220      if ( cur == FREE ) return -1;\r
 221 \r
 222      // NOTE: here it has to be REMOVED or FULL (some user-given value)\r
 223      if ( cur == REMOVED || !obj.equals(cur)) {\r
 224          // see Knuth, p. 529\r
 225          final int probe = 1 + (hash % (length - 2));\r
 226 \r
 227          do {\r
 228              index -= probe;\r
 229              if (index < 0) {\r
 230                  index += length;\r
 231              }\r
 232              cur = set[index];\r
 233          } while (cur != FREE\r
 234               && (cur == REMOVED || !obj.equals(cur)));\r
 235      }\r
 236 \r
 237      return cur == FREE ? -1 : index;\r
 238  }\r
 239 \r
 240  protected int index(T obj, int hash_, Object[] _set) {\r
 241 \r
 242      final Object[] set = _set;\r
 243      final int length = set.length;\r
 244      final int hash = hash_ & 0x7fffffff;\r
 245      int index = hash % length;\r
 246      Object cur = set[index];\r
 247 \r
 248      if ( cur == FREE ) return -1;\r
 249 \r
 250      // NOTE: here it has to be REMOVED or FULL (some user-given value)\r
 251      if ( cur == REMOVED || !obj.equals(cur)) {\r
 252          // see Knuth, p. 529\r
 253          final int probe = 1 + (hash % (length - 2));\r
 254 \r
 255          do {\r
 256              index -= probe;\r
 257              if (index < 0) {\r
 258                  index += length;\r
 259              }\r
 260              cur = set[index];\r
 261          } while (cur != FREE\r
 262               && (cur == REMOVED || !obj.equals(cur)));\r
 263      }\r
 264 \r
 265      return cur == FREE ? -1 : index;\r
 266  }\r
 267  \r
 268  /**\r
 269   * Locates the index at which <tt>obj</tt> can be inserted.  if\r
 270   * there is already a value equal()ing <tt>obj</tt> in the set,\r
 271   * returns that value's index as <tt>-index - 1</tt>.\r
 272   *\r
 273   * @param obj an <code>Object</code> value\r
 274   * @return the index of a FREE slot at which obj can be inserted\r
 275   * or, if obj is already stored in the hash, the negative value of\r
 276   * that index, minus 1: -index -1.\r
 277   */\r
 278  protected int insertionIndex(T obj) {\r
 279 \r
 280      final Object[] set = _set;\r
 281      final int length = set.length;\r
 282      final int hash = obj.hashCode() & 0x7fffffff;\r
 283      int index = hash % length;\r
 284      Object cur = set[index];\r
 285 \r
 286      if (cur == FREE) {\r
 287          return index;       // empty, all done\r
 288      } else if (cur != REMOVED && obj.equals((T) cur)) {\r
 289          return -index -1;   // already stored\r
 290      } else {                // already FULL or REMOVED, must probe\r
 291          // compute the double hash\r
 292          final int probe = 1 + (hash % (length - 2));\r
 293 \r
 294          // if the slot we landed on is FULL (but not removed), probe\r
 295          // until we find an empty slot, a REMOVED slot, or an element\r
 296          // equal to the one we are trying to insert.\r
 297          // finding an empty slot means that the value is not present\r
 298          // and that we should use that slot as the insertion point;\r
 299          // finding a REMOVED slot means that we need to keep searching,\r
 300          // however we want to remember the offset of that REMOVED slot\r
 301          // so we can reuse it in case a "new" insertion (i.e. not an update)\r
 302          // is possible.\r
 303          // finding a matching value means that we've found that our desired\r
 304          // key is already in the table\r
 305          if (cur != REMOVED) {\r
 306              // starting at the natural offset, probe until we find an\r
 307              // offset that isn't full.\r
 308              do {\r
 309                  index -= probe;\r
 310                  if (index < 0) {\r
 311                      index += length;\r
 312                  }\r
 313                  cur = set[index];\r
 314              } while (cur != FREE\r
 315                       && cur != REMOVED\r
 316                       && ! obj.equals((T) cur));\r
 317          }\r
 318 \r
 319          // if the index we found was removed: continue probing until we\r
 320          // locate a free location or an element which equal()s the\r
 321          // one we have.\r
 322          if (cur == REMOVED) {\r
 323              int firstRemoved = index;\r
 324              while (cur != FREE\r
 325                     && (cur == REMOVED || ! obj.equals((T) cur))) {\r
 326                  index -= probe;\r
 327                  if (index < 0) {\r
 328                      index += length;\r
 329                  }\r
 330                  cur = set[index];\r
 331              }\r
 332              // NOTE: cur cannot == REMOVED in this block\r
 333              return (cur != FREE) ? -index -1 : firstRemoved;\r
 334          }\r
 335          // if it's full, the key is already stored\r
 336          // NOTE: cur cannot equal REMOVE here (would have retuned already (see above)\r
 337          return (cur != FREE) ? -index -1 : index;\r
 338      }\r
 339  }\r
 340 \r
 341  protected int insertionIndex(T obj, int hash_) {\r
 342 \r
 343      final Object[] set = _set;\r
 344      final int length = set.length;\r
 345      final int hash = hash_ & 0x7fffffff;\r
 346      int index = hash % length;\r
 347      Object cur = set[index];\r
 348 \r
 349      if (cur == FREE) {\r
 350          return index;       // empty, all done\r
 351      } else if (cur != REMOVED && obj.equals((T) cur)) {\r
 352          return -index -1;   // already stored\r
 353      } else {                // already FULL or REMOVED, must probe\r
 354          // compute the double hash\r
 355          final int probe = 1 + (hash % (length - 2));\r
 356 \r
 357          // if the slot we landed on is FULL (but not removed), probe\r
 358          // until we find an empty slot, a REMOVED slot, or an element\r
 359          // equal to the one we are trying to insert.\r
 360          // finding an empty slot means that the value is not present\r
 361          // and that we should use that slot as the insertion point;\r
 362          // finding a REMOVED slot means that we need to keep searching,\r
 363          // however we want to remember the offset of that REMOVED slot\r
 364          // so we can reuse it in case a "new" insertion (i.e. not an update)\r
 365          // is possible.\r
 366          // finding a matching value means that we've found that our desired\r
 367          // key is already in the table\r
 368          if (cur != REMOVED) {\r
 369              // starting at the natural offset, probe until we find an\r
 370              // offset that isn't full.\r
 371              do {\r
 372                  index -= probe;\r
 373                  if (index < 0) {\r
 374                      index += length;\r
 375                  }\r
 376                  cur = set[index];\r
 377              } while (cur != FREE\r
 378                       && cur != REMOVED\r
 379                       && ! obj.equals((T) cur));\r
 380          }\r
 381 \r
 382          // if the index we found was removed: continue probing until we\r
 383          // locate a free location or an element which equal()s the\r
 384          // one we have.\r
 385          if (cur == REMOVED) {\r
 386              int firstRemoved = index;\r
 387              while (cur != FREE\r
 388                     && (cur == REMOVED || ! obj.equals((T) cur))) {\r
 389                  index -= probe;\r
 390                  if (index < 0) {\r
 391                      index += length;\r
 392                  }\r
 393                  cur = set[index];\r
 394              }\r
 395              // NOTE: cur cannot == REMOVED in this block\r
 396              return (cur != FREE) ? -index -1 : firstRemoved;\r
 397          }\r
 398          // if it's full, the key is already stored\r
 399          // NOTE: cur cannot equal REMOVE here (would have retuned already (see above)\r
 400          return (cur != FREE) ? -index -1 : index;\r
 401      }\r
 402  }\r
 403  \r
 404  /**\r
 405   * This is the default implementation of TObjectHashingStrategy:\r
 406   * it delegates hashing to the Object's hashCode method.\r
 407   *\r
 408   * @param o for which the hashcode is to be computed\r
 409   * @return the hashCode\r
 410   * @see Object#hashCode()\r
 411   */\r
 412  public final int computeHashCode(T o) {\r
 413      return o == null ? 0 : o.hashCode();\r
 414  }\r
 415 \r
 416  /**\r
 417   * This is the default implementation of TObjectHashingStrategy:\r
 418   * it delegates equality comparisons to the first parameter's\r
 419   * equals() method.\r
 420   *\r
 421   * @param o1 an <code>Object</code> value\r
 422   * @param o2 an <code>Object</code> value\r
 423   * @return true if the objects are equal\r
 424   * @see Object#equals(Object)\r
 425   */\r
 426  public final boolean equals(T o1, T o2) {\r
 427      return o1 == null ? o2 == null : o1.equals(o2);\r
 428  }\r
 429 \r
 430  /**\r
 431   * Convenience methods for subclasses to use in throwing exceptions about\r
 432   * badly behaved user objects employed as keys.  We have to throw an\r
 433   * IllegalArgumentException with a rather verbose message telling the\r
 434   * user that they need to fix their object implementation to conform\r
 435   * to the general contract for java.lang.Object.\r
 436   *\r
 437   * @param o1 the first of the equal elements with unequal hash codes.\r
 438   * @param o2 the second of the equal elements with unequal hash codes.\r
 439   * @exception IllegalArgumentException the whole point of this method.\r
 440   */\r
 441  protected final void throwObjectContractViolation(Object o1, Object o2)\r
 442      throws IllegalArgumentException {\r
 443      throw new IllegalArgumentException("Equal objects must have equal hashcodes. "\r
 444                                         + "During rehashing, Trove discovered that "\r
 445                                         + "the following two objects claim to be "\r
 446                                         + "equal (as in java.lang.Object.equals()) "\r
 447                                         + "but their hashCodes (or those calculated by "\r
 448                                         + "your TObjectHashingStrategy) are not equal."\r
 449                                         + "This violates the general contract of "\r
 450                                         + "java.lang.Object.hashCode().  See bullet point two "\r
 451                                         + "in that method's documentation. "\r
 452                                         + "object #1 =" + o1\r
 453                                         + "; object #2 =" + o2);\r
 454  }\r
 455 \r
 456 \r
 457  @Override\r
 458  public void writeExternal( ObjectOutput out ) throws IOException {\r
 459      super.writeExternal( out );\r
 460 \r
 461      // VERSION\r
 462      out.writeByte( 0 );\r
 463 \r
 464      // HASHING STRATEGY\r
 465      out.writeObject( _hashingStrategy );\r
 466  }\r
 467 \r
 468  @Override\r
 469  public void readExternal( ObjectInput in )\r
 470      throws IOException, ClassNotFoundException {\r
 471 \r
 472      super.readExternal( in );\r
 473 \r
 474      // VERSION\r
 475      in.readByte();\r
 476 \r
 477      // HASHING STRATEGY\r
 478      //noinspection unchecked\r
 479      _hashingStrategy = ( HashingStrategy<T> ) in.readObject();\r
 480  }\r
 481 } // TObjectHash\r