X-Git-Url: https://gerrit.simantics.org/r/gitweb?p=simantics%2Fplatform.git;a=blobdiff_plain;f=bundles%2Forg.simantics.db.impl%2Fsrc%2Forg%2Fsimantics%2Fdb%2Fimpl%2Fquery%2FQueryIdentityHash.java;h=2db67c67970b165f836317cbbaaabea40fa6994d;hp=8f684736ede693b79f21e93211a453a873e768ea;hb=HEAD;hpb=969bd23cab98a79ca9101af33334000879fb60c5 diff --git a/bundles/org.simantics.db.impl/src/org/simantics/db/impl/query/QueryIdentityHash.java b/bundles/org.simantics.db.impl/src/org/simantics/db/impl/query/QueryIdentityHash.java index 8f684736e..2db67c679 100644 --- a/bundles/org.simantics.db.impl/src/org/simantics/db/impl/query/QueryIdentityHash.java +++ b/bundles/org.simantics.db.impl/src/org/simantics/db/impl/query/QueryIdentityHash.java @@ -1,395 +1,402 @@ -/******************************************************************************* - * 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 +/******************************************************************************* + * 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 java.util.Collection; + +import org.simantics.db.exception.DatabaseException; +import org.simantics.db.impl.graph.ReadGraphImpl; + +import gnu.trove.impl.hash.THash; + + +/** + * 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 Collection getParents(QueryProcessor processor) { + // TODO Auto-generated method stub + return null; + } + + @Override + public Query getQuery() { + // 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 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(QuerySupport querySupport) { + // 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(); + } + + @Override + Object performFromCache(ReadGraphImpl graph, Object procedure) throws DatabaseException { + // TODO Auto-generated method stub + return null; + } + + @Override + public Object getResult() { + // TODO Auto-generated method stub + return null; + } + + @Override + void pruneParentSet() { + } + + }; + + /** + * 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