bundles/org.simantics.db.impl/src/org/simantics/db/impl/query/DoubleKeyQueryHash.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 import gnu.trove.impl.hash.THash;
  15
  16 import java.lang.reflect.Array;
  17
  18
  19 /**
  20  * An open addressed hashing implementation for Object types.
  21  *
  22  * Created: Sun Nov  4 08:56:06 2001
  23  *
  24  * @author Eric D. Friedman
  25  * @version $Id: UnaryQueryHash.java,v 1.2 2008/03/14 11:38:53 tuoksk Exp $
  26  */
  27 abstract public class DoubleKeyQueryHash<Procedure> extends THash {
  28     static final long serialVersionUID = -3461112548087185871L;
  29
  30     /** the set of Objects */
  31     protected transient DoubleKeyValueMap<Procedure>[] _set;
  32
  33     protected final DoubleKeyValueMap<Procedure> REMOVED = new DoubleKeyValueMap<Procedure>(-1);
  34
  35     /**
  36      * Creates a new <code>TObjectHash</code> instance with the
  37      * default capacity and load factor.
  38      */
  39     public DoubleKeyQueryHash() {
  40         super(DEFAULT_CAPACITY, 0.75f);
  41     }
  42
  43     public int capacity() {
  44         return _set.length;
  45     }
  46
  47     protected void removeAt(int index) {
  48         _set[index] = REMOVED;
  49         super.removeAt(index);
  50     }
  51
  52     /**
  53      * initializes the Object set of this hash table.
  54      *
  55      * @param initialCapacity an <code>int</code> value
  56      * @return an <code>int</code> value
  57      */
  58     @SuppressWarnings("unchecked")
  59         protected int setUp(int initialCapacity) {
  60         int capacity;
  61
  62         capacity = super.setUp(initialCapacity);
  63         _set = (DoubleKeyValueMap[])Array.newInstance(DoubleKeyValueMap.class, capacity);
  64         return capacity;
  65
  66     }
  67
  68     protected int index(final int id) {
  69
  70         final DoubleKeyValueMap<Procedure>[] set = _set;
  71         final int length = set.length;
  72         final int hash = (31 * id) & 0x7fffffff;
  73         int index = hash % length;
  74         DoubleKeyValueMap<Procedure> cur = set[index];
  75
  76         if ( cur == null ) return -1;
  77
  78         // NOTE: here it has to be REMOVED or FULL (some user-given value)
  79         if ( cur == REMOVED || !(id == cur.id)) {
  80             // see Knuth, p. 529
  81             final int probe = 1 + (hash % (length - 2));
  82
  83             do {
  84                 index -= probe;
  85                 if (index < 0) {
  86                     index += length;
  87                 }
  88                 cur = set[index];
  89             } while (cur != null
  90                  && (cur == REMOVED || !(id == cur.id)));
  91         }
  92
  93         return cur == null ? -1 : index;
  94
  95     }
  96
  97     final protected DoubleKeyValueMap<Procedure> index2(final int id) {
  98
  99         final DoubleKeyValueMap<Procedure>[] set = _set;
 100         final int length = set.length;
 101         final int hash = (31 * id) & 0x7fffffff;
 102         int index = hash % length;
 103         DoubleKeyValueMap<Procedure> cur = set[index];
 104
 105         if ( cur == null ) return null;
 106
 107         // NOTE: here it has to be REMOVED or FULL (some user-given value)
 108         if ( cur == REMOVED || (id != cur.id)) {
 109             // see Knuth, p. 529
 110             final int probe = 1 + (hash % (length - 2));
 111
 112             do {
 113                 index -= probe;
 114                 if (index < 0) {
 115                     index += length;
 116                 }
 117                 cur = set[index];
 118             } while (cur != null
 119                  && (cur == REMOVED || (id != cur.id)));
 120         }
 121
 122         return cur;
 123
 124     }
 125
 126
 127     /**
 128      * Locates the index at which <tt>obj</tt> can be inserted.  if
 129      * there is already a value equal()ing <tt>obj</tt> in the set,
 130      * returns that value's index as <tt>-index - 1</tt>.
 131      *
 132      * @param obj an <code>Object</code> value
 133      * @return the index of a FREE slot at which obj can be inserted
 134      * or, if obj is already stored in the hash, the negative value of
 135      * that index, minus 1: -index -1.
 136      */
 137     protected int insertionIndex(final int id) {
 138
 139         final DoubleKeyValueMap<Procedure>[] set = _set;
 140         final int length = set.length;
 141         final int hash = (31 * id) & 0x7fffffff;
 142         int index = hash % length;
 143         DoubleKeyValueMap<Procedure> cur = set[index];
 144
 145         if (cur == null) {
 146             return index;       // empty, all done
 147         } else if (cur != REMOVED && (id == cur.id)) {
 148             return -index -1;   // already stored
 149         } else {                // already FULL or REMOVED, must probe
 150             // compute the double hash
 151             final int probe = 1 + (hash % (length - 2));
 152
 153             // if the slot we landed on is FULL (but not removed), probe
 154             // until we find an empty slot, a REMOVED slot, or an element
 155             // equal to the one we are trying to insert.
 156             // finding an empty slot means that the value is not present
 157             // and that we should use that slot as the insertion point;
 158             // finding a REMOVED slot means that we need to keep searching,
 159             // however we want to remember the offset of that REMOVED slot
 160             // so we can reuse it in case a "new" insertion (i.e. not an update)
 161             // is possible.
 162             // finding a matching value means that we've found that our desired
 163             // key is already in the table
 164             if (cur != REMOVED) {
 165                 // starting at the natural offset, probe until we find an
 166                 // offset that isn't full.
 167                 do {
 168                     index -= probe;
 169                     if (index < 0) {
 170                         index += length;
 171                     }
 172                     cur = set[index];
 173                 } while (cur != null
 174                          && cur != REMOVED
 175                          && ! (id == cur.id));
 176             }
 177
 178             // if the index we found was removed: continue probing until we
 179             // locate a free location or an element which equal()s the
 180             // one we have.
 181             if (cur == REMOVED) {
 182                 int firstRemoved = index;
 183                 while (cur != null
 184                        && (cur == REMOVED || ! (id == cur.id))) {
 185                     index -= probe;
 186                     if (index < 0) {
 187                         index += length;
 188                     }
 189                     cur = set[index];
 190                 }
 191                 // NOTE: cur cannot == REMOVED in this block
 192                 return (cur != null) ? -index -1 : firstRemoved;
 193             }
 194             // if it's full, the key is already stored
 195             // NOTE: cur cannot equal REMOVE here (would have retuned already (see above)
 196             return (cur != null) ? -index -1 : index;
 197         }
 198     }
 199
 200     protected int insertionIndex2(final int id, final DoubleKeyValueMap<Procedure>[] set) {
 201
 202         final int length = set.length;
 203         final int hash = (31 * id) & 0x7fffffff;
 204         int index = hash % length;
 205         DoubleKeyValueMap<Procedure> cur = set[index];
 206
 207         if (cur == null) {
 208             return index;       // empty, all done
 209         } else if (cur != REMOVED && (id == cur.id)) {
 210             return -index -1;   // already stored
 211         } else {                // already FULL or REMOVED, must probe
 212             // compute the double hash
 213             final int probe = 1 + (hash % (length - 2));
 214
 215             // if the slot we landed on is FULL (but not removed), probe
 216             // until we find an empty slot, a REMOVED slot, or an element
 217             // equal to the one we are trying to insert.
 218             // finding an empty slot means that the value is not present
 219             // and that we should use that slot as the insertion point;
 220             // finding a REMOVED slot means that we need to keep searching,
 221             // however we want to remember the offset of that REMOVED slot
 222             // so we can reuse it in case a "new" insertion (i.e. not an update)
 223             // is possible.
 224             // finding a matching value means that we've found that our desired
 225             // key is already in the table
 226             if (cur != REMOVED) {
 227                 // starting at the natural offset, probe until we find an
 228                 // offset that isn't full.
 229                 do {
 230                     index -= probe;
 231                     if (index < 0) {
 232                         index += length;
 233                     }
 234                     cur = set[index];
 235                 } while (cur != null
 236                          && cur != REMOVED
 237                          && ! (id == cur.id));
 238             }
 239
 240             // if the index we found was removed: continue probing until we
 241             // locate a free location or an element which equal()s the
 242             // one we have.
 243             if (cur == REMOVED) {
 244                 int firstRemoved = index;
 245                 while (cur != null
 246                        && (cur == REMOVED || ! (id == cur.id))) {
 247                     index -= probe;
 248                     if (index < 0) {
 249                         index += length;
 250                     }
 251                     cur = set[index];
 252                 }
 253                 // NOTE: cur cannot == REMOVED in this block
 254                 return (cur != null) ? -index -1 : firstRemoved;
 255             }
 256             // if it's full, the key is already stored
 257             // NOTE: cur cannot equal REMOVE here (would have retuned already (see above)
 258             return (cur != null) ? -index -1 : index;
 259         }
 260     }
 261
 262     /**
 263      * Convenience methods for subclasses to use in throwing exceptions about
 264      * badly behaved user objects employed as keys.  We have to throw an
 265      * IllegalArgumentException with a rather verbose message telling the
 266      * user that they need to fix their object implementation to conform
 267      * to the general contract for java.lang.Object.
 268      *
 269      * @param o1 the first of the equal elements with unequal hash codes.
 270      * @param o2 the second of the equal elements with unequal hash codes.
 271      * @exception IllegalArgumentException the whole point of this method.
 272      */
 273     protected final void throwObjectContractViolation(Object o1, Object o2)
 274         throws IllegalArgumentException {
 275         throw new IllegalArgumentException("Equal objects must have equal hashcodes. "
 276                                            + "During rehashing, Trove discovered that "
 277                                            + "the following two objects claim to be "
 278                                            + "equal (as in java.lang.Object.equals()) "
 279                                            + "but their hashCodes (or those calculated by "
 280                                            + "your TObjectHashingStrategy) are not equal."
 281                                            + "This violates the general contract of "
 282                                            + "java.lang.Object.hashCode().  See bullet point two "
 283                                            + "in that method's documentation. "
 284                                            + "object #1 =" + o1
 285                                            + "; object #2 =" + o2);
 286     }
 287 } // TObjectHash