]> gerrit.simantics Code Review - simantics/platform.git/blob - bundles/org.simantics.db.impl/src/org/simantics/db/impl/query/StableObjectHash.java
Fail safe import fixes made by Antti
[simantics/platform.git] / 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