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