bundles/org.simantics.db.impl/src/org/simantics/db/impl/query/QueryIdentityHash.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 org.simantics.db.impl.graph.ReadGraphImpl;\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: QueryIdentityHash.java,v 1.1 2008/03/14 11:32:01 tuoksk Exp $\r
  26  */\r
  27 abstract public class QueryIdentityHash extends THash {\r
  28 \r
  29         static final long serialVersionUID = -3461112548087185871L;\r
  30 \r
  31     /** the set of Objects */\r
  32     protected transient CacheEntry[] _set;\r
  33 \r
  34     protected static final CacheEntry REMOVED = new CacheEntry() {\r
  35 \r
  36         @Override\r
  37         public void addParent(CacheEntry entry) {\r
  38             // TODO Auto-generated method stub\r
  39             \r
  40         }\r
  41 \r
  42         @Override\r
  43         public void clearResult(QuerySupport support) {\r
  44             // TODO Auto-generated method stub\r
  45             \r
  46         }\r
  47 \r
  48         @Override\r
  49         public void discard() {\r
  50             // TODO Auto-generated method stub\r
  51             \r
  52         }\r
  53 \r
  54         @Override\r
  55         public void except(Throwable t) {\r
  56             // TODO Auto-generated method stub\r
  57             \r
  58         }\r
  59 \r
  60         @Override\r
  61         public Iterable<CacheEntry> getParents(QueryProcessor processor) {\r
  62             // TODO Auto-generated method stub\r
  63             return null;\r
  64         }\r
  65 \r
  66         @Override\r
  67         public Query getQuery() {\r
  68             // TODO Auto-generated method stub\r
  69             return null;\r
  70         }\r
  71 \r
  72         @Override\r
  73         public <T> T getResult() {\r
  74             // TODO Auto-generated method stub\r
  75             return null;\r
  76         }\r
  77 \r
  78         @Override\r
  79         public boolean hasParents() {\r
  80             // TODO Auto-generated method stub\r
  81             return false;\r
  82         }\r
  83 \r
  84         @Override\r
  85         public boolean isDiscarded() {\r
  86             // TODO Auto-generated method stub\r
  87             return false;\r
  88         }\r
  89 \r
  90         @Override\r
  91         public boolean isExcepted() {\r
  92             // TODO Auto-generated method stub\r
  93             return false;\r
  94         }\r
  95 \r
  96         @Override\r
  97         public boolean isFresh() {\r
  98             // TODO Auto-generated method stub\r
  99             return false;\r
 100         }\r
 101 \r
 102         @Override\r
 103         public boolean isPending() {\r
 104             // TODO Auto-generated method stub\r
 105             return false;\r
 106         }\r
 107 \r
 108         @Override\r
 109         public boolean isReady() {\r
 110             // TODO Auto-generated method stub\r
 111             return false;\r
 112         }\r
 113 \r
 114         @Override\r
 115         public boolean isRefuted() {\r
 116             // TODO Auto-generated method stub\r
 117             return false;\r
 118         }\r
 119 \r
 120         @Override\r
 121         public void performFromCache(ReadGraphImpl graph, Object provider, Object procedure) {\r
 122             // TODO Auto-generated method stub\r
 123             \r
 124         }\r
 125 \r
 126         @Override\r
 127         public void refute() {\r
 128             // TODO Auto-generated method stub\r
 129             \r
 130         }\r
 131 \r
 132         @Override\r
 133         CacheEntry pruneFirstParents() {\r
 134             // TODO Auto-generated method stub\r
 135                 return null;\r
 136         }\r
 137         \r
 138         @Override\r
 139         public void removeParent(CacheEntry entry) {\r
 140             // TODO Auto-generated method stub\r
 141             \r
 142         }\r
 143 \r
 144         @Override\r
 145         public void setPending() {\r
 146             // TODO Auto-generated method stub\r
 147             \r
 148         }\r
 149 \r
 150         @Override\r
 151         public void setReady() {\r
 152             // TODO Auto-generated method stub\r
 153             \r
 154         }\r
 155 \r
 156         @Override\r
 157         public void setResult(Object result) {\r
 158             // TODO Auto-generated method stub\r
 159             \r
 160         }\r
 161         \r
 162         @Override\r
 163         boolean isImmutable(ReadGraphImpl graph) {\r
 164                 return true;\r
 165         }\r
 166 \r
 167                 @Override\r
 168                 boolean shouldBeCollected() {\r
 169                         // TODO Auto-generated method stub\r
 170                         return false;\r
 171                 }\r
 172 \r
 173                 @Override\r
 174                 CacheEntry getFirstParent(QueryProcessor processor) {\r
 175                         // TODO Auto-generated method stub\r
 176                         return null;\r
 177                 }\r
 178                 \r
 179                 @Override\r
 180                 boolean moreThanOneParent(QueryProcessor processor) {\r
 181                         // TODO Auto-generated method stub\r
 182                         return false;\r
 183                 }\r
 184 \r
 185                 @Override\r
 186                 int parentCount(QueryProcessor processor) {\r
 187                         // TODO Auto-generated method stub\r
 188                         return 0;\r
 189                 }\r
 190                 \r
 191                 @Override\r
 192                 short getLevel() {\r
 193                         // TODO Auto-generated method stub\r
 194                         return 0;\r
 195                 }\r
 196 \r
 197                 @Override\r
 198                 short setLevel(short level) {\r
 199                         // TODO Auto-generated method stub\r
 200                         return level;\r
 201                 }\r
 202                 \r
 203                 @Override\r
 204                 void prepareRecompute(QuerySupport querySupport) {\r
 205                         // TODO Auto-generated method stub\r
 206                 }\r
 207 \r
 208                 @Override\r
 209                 int getGCStatus() {\r
 210                         // TODO Auto-generated method stub\r
 211                         return 0;\r
 212                 }\r
 213 \r
 214                 @Override\r
 215                 int setGCStatus(int status) {\r
 216                         // TODO Auto-generated method stub\r
 217                         return 0;\r
 218                 }\r
 219 \r
 220                 @Override\r
 221                 void setGCStatusFlag(int flag, boolean value) {\r
 222                         // TODO Auto-generated method stub\r
 223                         \r
 224                 }\r
 225                 \r
 226                 public Object getOriginalRequest() {\r
 227                         throw new UnsupportedOperationException();\r
 228                 }\r
 229         \r
 230     };\r
 231 \r
 232     /**\r
 233      * Creates a new <code>TObjectHash</code> instance with the\r
 234      * default capacity and load factor.\r
 235      */\r
 236     public QueryIdentityHash() {\r
 237         super();\r
 238     }\r
 239 \r
 240     /**\r
 241      * Creates a new <code>TObjectHash</code> instance whose capacity\r
 242      * is the next highest prime above <tt>initialCapacity + 1</tt>\r
 243      * unless that value is already prime.\r
 244      *\r
 245      * @param initialCapacity an <code>int</code> value\r
 246      */\r
 247     public QueryIdentityHash(int initialCapacity) {\r
 248         super(initialCapacity, 0.75f);\r
 249     }\r
 250 \r
 251     final public int capacity() {\r
 252         return _set.length;\r
 253     }\r
 254 \r
 255     final protected void removeAt(int index) {\r
 256         _set[index] = REMOVED;\r
 257         super.removeAt(index);\r
 258     }\r
 259 \r
 260     /**\r
 261      * initializes the Object set of this hash table.\r
 262      *\r
 263      * @param initialCapacity an <code>int</code> value\r
 264      * @return an <code>int</code> value\r
 265      */\r
 266     final protected int setUp(int initialCapacity) {\r
 267         int capacity;\r
 268 \r
 269         capacity = super.setUp(initialCapacity);\r
 270         _set = new CacheEntry[capacity];\r
 271         return capacity;\r
 272         \r
 273     }\r
 274 \r
 275     /**\r
 276      * Searches the set for <tt>obj</tt>\r
 277      *\r
 278      * @param obj an <code>Object</code> value\r
 279      * @return a <code>boolean</code> value\r
 280      */\r
 281     final public boolean contains(Object obj) {\r
 282         return index(obj) >= 0;\r
 283     }\r
 284 \r
 285     /**\r
 286      * Locates the index of <tt>obj</tt>.\r
 287      *\r
 288      * @param obj an <code>Object</code> value\r
 289      * @return the index of <tt>obj</tt> or -1 if it isn't in the set.\r
 290      */\r
 291     final protected int index(Object obj) {\r
 292 \r
 293         final Object[] set = _set;\r
 294         final int length = set.length;\r
 295         //final int hash = System.identityHashCode(obj) & 0x7fffffff;\r
 296         final int hash = obj.hashCode() & 0x7fffffff;\r
 297         int index = hash % length;\r
 298         Object cur = set[index];\r
 299 \r
 300         if ( cur == null ) return -1;\r
 301 \r
 302         // NOTE: here it has to be REMOVED or FULL (some user-given value)\r
 303         if ( cur == REMOVED || (cur != obj)) {\r
 304             // see Knuth, p. 529\r
 305             final int probe = 1 + (hash % (length - 2));\r
 306 \r
 307             do {\r
 308                 index -= probe;\r
 309                 if (index < 0) {\r
 310                     index += length;\r
 311                 }\r
 312                 cur = set[index];\r
 313             } while (cur != null\r
 314                  && (cur == REMOVED || (cur != obj)));\r
 315         }\r
 316 \r
 317         return cur == null ? -1 : index;\r
 318     }\r
 319     \r
 320 \r
 321     /**\r
 322      * Locates the index at which <tt>obj</tt> can be inserted.  if\r
 323      * there is already a value equal()ing <tt>obj</tt> in the set,\r
 324      * returns that value's index as <tt>-index - 1</tt>.\r
 325      *\r
 326      * @param obj an <code>Object</code> value\r
 327      * @return the index of a FREE slot at which obj can be inserted\r
 328      * or, if obj is already stored in the hash, the negative value of\r
 329      * that index, minus 1: -index -1.\r
 330      */\r
 331     final protected int insertionIndex(Object obj) {\r
 332 \r
 333         final Object[] set = _set;\r
 334         final int length = set.length;\r
 335         //final int hash = System.identityHashCode(obj) & 0x7fffffff;\r
 336         final int hash = obj.hashCode() & 0x7fffffff;\r
 337         int index = hash % length;\r
 338         Object cur = set[index];\r
 339 \r
 340         if (cur == null) {\r
 341             return index;       // empty, all done\r
 342         } else if (cur != REMOVED && (cur == obj)) {\r
 343             return -index -1;   // already stored\r
 344         } else {                // already FULL or REMOVED, must probe\r
 345             // compute the double hash\r
 346             final int probe = 1 + (hash % (length - 2));\r
 347 \r
 348             // if the slot we landed on is FULL (but not removed), probe\r
 349             // until we find an empty slot, a REMOVED slot, or an element\r
 350             // equal to the one we are trying to insert.\r
 351             // finding an empty slot means that the value is not present\r
 352             // and that we should use that slot as the insertion point;\r
 353             // finding a REMOVED slot means that we need to keep searching,\r
 354             // however we want to remember the offset of that REMOVED slot\r
 355             // so we can reuse it in case a "new" insertion (i.e. not an update)\r
 356             // is possible.\r
 357             // finding a matching value means that we've found that our desired\r
 358             // key is already in the table\r
 359             if (cur != REMOVED) {\r
 360                 // starting at the natural offset, probe until we find an\r
 361                 // offset that isn't full.\r
 362                 do {\r
 363                     index -= probe;\r
 364                     if (index < 0) {\r
 365                         index += length;\r
 366                     }\r
 367                     cur = set[index];\r
 368                 } while (cur != null\r
 369                          && cur != REMOVED\r
 370                          && (cur != obj));\r
 371             }\r
 372 \r
 373             // if the index we found was removed: continue probing until we\r
 374             // locate a free location or an element which equal()s the\r
 375             // one we have.\r
 376             if (cur == REMOVED) {\r
 377                 int firstRemoved = index;\r
 378                 while (cur != null\r
 379                        && (cur == REMOVED || (cur != obj))) {\r
 380                     index -= probe;\r
 381                     if (index < 0) {\r
 382                         index += length;\r
 383                     }\r
 384                     cur = set[index];\r
 385                 }\r
 386                 // NOTE: cur cannot == REMOVED in this block\r
 387                 return (cur != null) ? -index -1 : firstRemoved;\r
 388             }\r
 389             // if it's full, the key is already stored\r
 390             // NOTE: cur cannot equal REMOVE here (would have retuned already (see above)\r
 391             return (cur != null) ? -index -1 : index;\r
 392         }\r
 393     }\r
 394 \r
 395 } // TObjectHash\r