bundles/org.simantics.db.impl/src/org/simantics/db/impl/query/BinaryQueryHash.java

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