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