--- /dev/null
+/*******************************************************************************\r
+ * Copyright (c) 2007, 2010 Association for Decentralized Information Management\r
+ * in Industry THTH ry.\r
+ * All rights reserved. This program and the accompanying materials\r
+ * are made available under the terms of the Eclipse Public License v1.0\r
+ * which accompanies this distribution, and is available at\r
+ * http://www.eclipse.org/legal/epl-v10.html\r
+ *\r
+ * Contributors:\r
+ * VTT Technical Research Centre of Finland - initial API and implementation\r
+ *******************************************************************************/\r
+package org.simantics.db.impl.query;\r
+\r
+import gnu.trove.impl.hash.THash;\r
+\r
+import org.simantics.db.impl.graph.ReadGraphImpl;\r
+\r
+\r
+/**\r
+ * An open addressed hashing implementation for Object types.\r
+ *\r
+ * Created: Sun Nov 4 08:56:06 2001\r
+ *\r
+ * @author Eric D. Friedman\r
+ * @version $Id: QueryIdentityHash.java,v 1.1 2008/03/14 11:32:01 tuoksk Exp $\r
+ */\r
+abstract public class QueryIdentityHash extends THash {\r
+\r
+ static final long serialVersionUID = -3461112548087185871L;\r
+\r
+ /** the set of Objects */\r
+ protected transient CacheEntry[] _set;\r
+\r
+ protected static final CacheEntry REMOVED = new CacheEntry() {\r
+\r
+ @Override\r
+ public void addParent(CacheEntry entry) {\r
+ // TODO Auto-generated method stub\r
+ \r
+ }\r
+\r
+ @Override\r
+ public void clearResult(QuerySupport support) {\r
+ // TODO Auto-generated method stub\r
+ \r
+ }\r
+\r
+ @Override\r
+ public void discard() {\r
+ // TODO Auto-generated method stub\r
+ \r
+ }\r
+\r
+ @Override\r
+ public void except(Throwable t) {\r
+ // TODO Auto-generated method stub\r
+ \r
+ }\r
+\r
+ @Override\r
+ public Iterable<CacheEntry> getParents(QueryProcessor processor) {\r
+ // TODO Auto-generated method stub\r
+ return null;\r
+ }\r
+\r
+ @Override\r
+ public Query getQuery() {\r
+ // TODO Auto-generated method stub\r
+ return null;\r
+ }\r
+\r
+ @Override\r
+ public <T> T getResult() {\r
+ // TODO Auto-generated method stub\r
+ return null;\r
+ }\r
+\r
+ @Override\r
+ public boolean hasParents() {\r
+ // TODO Auto-generated method stub\r
+ return false;\r
+ }\r
+\r
+ @Override\r
+ public boolean isDiscarded() {\r
+ // TODO Auto-generated method stub\r
+ return false;\r
+ }\r
+\r
+ @Override\r
+ public boolean isExcepted() {\r
+ // TODO Auto-generated method stub\r
+ return false;\r
+ }\r
+\r
+ @Override\r
+ public boolean isFresh() {\r
+ // TODO Auto-generated method stub\r
+ return false;\r
+ }\r
+\r
+ @Override\r
+ public boolean isPending() {\r
+ // TODO Auto-generated method stub\r
+ return false;\r
+ }\r
+\r
+ @Override\r
+ public boolean isReady() {\r
+ // TODO Auto-generated method stub\r
+ return false;\r
+ }\r
+\r
+ @Override\r
+ public boolean isRefuted() {\r
+ // TODO Auto-generated method stub\r
+ return false;\r
+ }\r
+\r
+ @Override\r
+ public void performFromCache(ReadGraphImpl graph, Object provider, Object procedure) {\r
+ // TODO Auto-generated method stub\r
+ \r
+ }\r
+\r
+ @Override\r
+ public void refute() {\r
+ // TODO Auto-generated method stub\r
+ \r
+ }\r
+\r
+ @Override\r
+ CacheEntry pruneFirstParents() {\r
+ // TODO Auto-generated method stub\r
+ return null;\r
+ }\r
+ \r
+ @Override\r
+ public void removeParent(CacheEntry entry) {\r
+ // TODO Auto-generated method stub\r
+ \r
+ }\r
+\r
+ @Override\r
+ public void setPending() {\r
+ // TODO Auto-generated method stub\r
+ \r
+ }\r
+\r
+ @Override\r
+ public void setReady() {\r
+ // TODO Auto-generated method stub\r
+ \r
+ }\r
+\r
+ @Override\r
+ public void setResult(Object result) {\r
+ // TODO Auto-generated method stub\r
+ \r
+ }\r
+ \r
+ @Override\r
+ boolean isImmutable(ReadGraphImpl graph) {\r
+ return true;\r
+ }\r
+\r
+ @Override\r
+ boolean shouldBeCollected() {\r
+ // TODO Auto-generated method stub\r
+ return false;\r
+ }\r
+\r
+ @Override\r
+ CacheEntry getFirstParent(QueryProcessor processor) {\r
+ // TODO Auto-generated method stub\r
+ return null;\r
+ }\r
+ \r
+ @Override\r
+ boolean moreThanOneParent(QueryProcessor processor) {\r
+ // TODO Auto-generated method stub\r
+ return false;\r
+ }\r
+\r
+ @Override\r
+ int parentCount(QueryProcessor processor) {\r
+ // TODO Auto-generated method stub\r
+ return 0;\r
+ }\r
+ \r
+ @Override\r
+ short getLevel() {\r
+ // TODO Auto-generated method stub\r
+ return 0;\r
+ }\r
+\r
+ @Override\r
+ short setLevel(short level) {\r
+ // TODO Auto-generated method stub\r
+ return level;\r
+ }\r
+ \r
+ @Override\r
+ void prepareRecompute(QuerySupport querySupport) {\r
+ // TODO Auto-generated method stub\r
+ }\r
+\r
+ @Override\r
+ int getGCStatus() {\r
+ // TODO Auto-generated method stub\r
+ return 0;\r
+ }\r
+\r
+ @Override\r
+ int setGCStatus(int status) {\r
+ // TODO Auto-generated method stub\r
+ return 0;\r
+ }\r
+\r
+ @Override\r
+ void setGCStatusFlag(int flag, boolean value) {\r
+ // TODO Auto-generated method stub\r
+ \r
+ }\r
+ \r
+ public Object getOriginalRequest() {\r
+ throw new UnsupportedOperationException();\r
+ }\r
+ \r
+ };\r
+\r
+ /**\r
+ * Creates a new <code>TObjectHash</code> instance with the\r
+ * default capacity and load factor.\r
+ */\r
+ public QueryIdentityHash() {\r
+ super();\r
+ }\r
+\r
+ /**\r
+ * Creates a new <code>TObjectHash</code> instance whose capacity\r
+ * is the next highest prime above <tt>initialCapacity + 1</tt>\r
+ * unless that value is already prime.\r
+ *\r
+ * @param initialCapacity an <code>int</code> value\r
+ */\r
+ public QueryIdentityHash(int initialCapacity) {\r
+ super(initialCapacity, 0.75f);\r
+ }\r
+\r
+ final public int capacity() {\r
+ return _set.length;\r
+ }\r
+\r
+ final protected void removeAt(int index) {\r
+ _set[index] = REMOVED;\r
+ super.removeAt(index);\r
+ }\r
+\r
+ /**\r
+ * initializes the Object set of this hash table.\r
+ *\r
+ * @param initialCapacity an <code>int</code> value\r
+ * @return an <code>int</code> value\r
+ */\r
+ final protected int setUp(int initialCapacity) {\r
+ int capacity;\r
+\r
+ capacity = super.setUp(initialCapacity);\r
+ _set = new CacheEntry[capacity];\r
+ return capacity;\r
+ \r
+ }\r
+\r
+ /**\r
+ * Searches the set for <tt>obj</tt>\r
+ *\r
+ * @param obj an <code>Object</code> value\r
+ * @return a <code>boolean</code> value\r
+ */\r
+ final public boolean contains(Object obj) {\r
+ return index(obj) >= 0;\r
+ }\r
+\r
+ /**\r
+ * Locates the index of <tt>obj</tt>.\r
+ *\r
+ * @param obj an <code>Object</code> value\r
+ * @return the index of <tt>obj</tt> or -1 if it isn't in the set.\r
+ */\r
+ final protected int index(Object obj) {\r
+\r
+ final Object[] set = _set;\r
+ final int length = set.length;\r
+ //final int hash = System.identityHashCode(obj) & 0x7fffffff;\r
+ final int hash = obj.hashCode() & 0x7fffffff;\r
+ int index = hash % length;\r
+ Object cur = set[index];\r
+\r
+ if ( cur == null ) return -1;\r
+\r
+ // NOTE: here it has to be REMOVED or FULL (some user-given value)\r
+ if ( cur == REMOVED || (cur != obj)) {\r
+ // see Knuth, p. 529\r
+ final int probe = 1 + (hash % (length - 2));\r
+\r
+ do {\r
+ index -= probe;\r
+ if (index < 0) {\r
+ index += length;\r
+ }\r
+ cur = set[index];\r
+ } while (cur != null\r
+ && (cur == REMOVED || (cur != obj)));\r
+ }\r
+\r
+ return cur == null ? -1 : index;\r
+ }\r
+ \r
+\r
+ /**\r
+ * Locates the index at which <tt>obj</tt> can be inserted. if\r
+ * there is already a value equal()ing <tt>obj</tt> in the set,\r
+ * returns that value's index as <tt>-index - 1</tt>.\r
+ *\r
+ * @param obj an <code>Object</code> value\r
+ * @return the index of a FREE slot at which obj can be inserted\r
+ * or, if obj is already stored in the hash, the negative value of\r
+ * that index, minus 1: -index -1.\r
+ */\r
+ final protected int insertionIndex(Object obj) {\r
+\r
+ final Object[] set = _set;\r
+ final int length = set.length;\r
+ //final int hash = System.identityHashCode(obj) & 0x7fffffff;\r
+ final int hash = obj.hashCode() & 0x7fffffff;\r
+ int index = hash % length;\r
+ Object cur = set[index];\r
+\r
+ if (cur == null) {\r
+ return index; // empty, all done\r
+ } else if (cur != REMOVED && (cur == obj)) {\r
+ return -index -1; // already stored\r
+ } else { // already FULL or REMOVED, must probe\r
+ // compute the double hash\r
+ final int probe = 1 + (hash % (length - 2));\r
+\r
+ // if the slot we landed on is FULL (but not removed), probe\r
+ // until we find an empty slot, a REMOVED slot, or an element\r
+ // equal to the one we are trying to insert.\r
+ // finding an empty slot means that the value is not present\r
+ // and that we should use that slot as the insertion point;\r
+ // finding a REMOVED slot means that we need to keep searching,\r
+ // however we want to remember the offset of that REMOVED slot\r
+ // so we can reuse it in case a "new" insertion (i.e. not an update)\r
+ // is possible.\r
+ // finding a matching value means that we've found that our desired\r
+ // key is already in the table\r
+ if (cur != REMOVED) {\r
+ // starting at the natural offset, probe until we find an\r
+ // offset that isn't full.\r
+ do {\r
+ index -= probe;\r
+ if (index < 0) {\r
+ index += length;\r
+ }\r
+ cur = set[index];\r
+ } while (cur != null\r
+ && cur != REMOVED\r
+ && (cur != obj));\r
+ }\r
+\r
+ // if the index we found was removed: continue probing until we\r
+ // locate a free location or an element which equal()s the\r
+ // one we have.\r
+ if (cur == REMOVED) {\r
+ int firstRemoved = index;\r
+ while (cur != null\r
+ && (cur == REMOVED || (cur != obj))) {\r
+ index -= probe;\r
+ if (index < 0) {\r
+ index += length;\r
+ }\r
+ cur = set[index];\r
+ }\r
+ // NOTE: cur cannot == REMOVED in this block\r
+ return (cur != null) ? -index -1 : firstRemoved;\r
+ }\r
+ // if it's full, the key is already stored\r
+ // NOTE: cur cannot equal REMOVE here (would have retuned already (see above)\r
+ return (cur != null) ? -index -1 : index;\r
+ }\r
+ }\r
+\r
+} // TObjectHash\r
Code Review / simantics / platform.git / blobdiff