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