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