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