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