-/*******************************************************************************\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 java.util.Arrays;\r
-import java.util.Iterator;\r
-\r
-\r
-/**\r
- * An implementation of the <tt>Set</tt> interface that uses an\r
- * open-addressed hash table to store its contents.\r
- *\r
- * Created: Sat Nov 3 10:38:17 2001\r
- *\r
- * @author Eric D. Friedman\r
- * @version $Id: QueryIdentityHashSet.java,v 1.1 2008/03/14 11:32:01 tuoksk Exp $\r
- */\r
-\r
-final public class QueryIdentityHashSet extends QueryIdentityHash implements Iterable<CacheEntry> {\r
- \r
- /**\r
- * Creates a new <code>THashSet</code> instance with a prime\r
- * capacity equal to or greater than <tt>initialCapacity</tt> and\r
- * with the default load factor.\r
- *\r
- * @param initialCapacity an <code>int</code> value\r
- */\r
- public QueryIdentityHashSet(int initialCapacity) {\r
- super(initialCapacity);\r
- }\r
-\r
- /**\r
- * Inserts a value into the set.\r
- *\r
- * @param obj an <code>Object</code> value\r
- * @return true if the set was modified by the add operation\r
- */\r
- final public boolean add(final CacheEntry obj) {\r
- \r
- final int index = insertionIndex(obj);\r
-\r
- if (index < 0) {\r
- return false; // already present in set, nothing to add\r
- }\r
-\r
- final CacheEntry old = _set[index];\r
- _set[index] = obj;\r
-\r
- postInsertHook(old == null);\r
- return true; // yes, we added something\r
- \r
- }\r
-\r
- /**\r
- * Expands the set to accomodate new values.\r
- *\r
- * @param newCapacity an <code>int</code> value\r
- */\r
- final protected void rehash(int newCapacity) {\r
- \r
- final int oldCapacity = _set.length;\r
- final CacheEntry oldSet[] = _set;\r
-\r
- _set = new CacheEntry[newCapacity];\r
-\r
- for (int i = oldCapacity; i-- > 0;) {\r
- if(oldSet[i] != null && oldSet[i] != REMOVED) {\r
- final CacheEntry o = oldSet[i];\r
- //if(o.isDiscarded()) continue;\r
- final int index = insertionIndex(o);\r
- if(index < 0) {\r
- new Exception().printStackTrace();\r
- System.out.println("rehash " + i + " " + o);\r
- for (int j = oldCapacity; j-- > 0;) {\r
- System.out.println("rehash " + j+ " " + oldSet[j] + " " + System.identityHashCode(oldSet[j]));\r
- }\r
- }\r
- else _set[index] = o;\r
- }\r
- }\r
- \r
- }\r
-\r
- /**\r
- * Removes <tt>obj</tt> from the set.\r
- *\r
- * @param obj an <code>Object</code> value\r
- * @return true if the set was modified by the remove operation.\r
- */\r
- final public boolean remove(Object obj) {\r
- int index = index(obj);\r
- if (index >= 0) {\r
- removeAt(index);\r
- return true;\r
- }\r
- return false;\r
- }\r
- \r
- private int knownBound = 10;\r
- \r
- final public void purge() {\r
- \r
- if(size() > (knownBound<<1)) {\r
- \r
- knownBound=10;\r
- for(int i=0;i<_set.length;i++) {\r
- CacheEntry entry = _set[i];\r
- if(entry != null && REMOVED != entry) {\r
- if(entry.isDiscarded()) {\r
- removeAt(i); \r
- } else {\r
- knownBound++;\r
- }\r
- }\r
- }\r
- \r
- }\r
- \r
- }\r
-\r
- final public CacheEntry removeDiscarded() {\r
- \r
- tempDisableAutoCompaction();\r
- try {\r
- \r
- for(int i=0;i<_set.length;i++) {\r
- CacheEntry entry = _set[i];\r
- if(entry != null && REMOVED != entry) {\r
- removeAt(i);\r
- if(!entry.isDiscarded()) return entry; \r
- }\r
- }\r
- \r
- return null;\r
- \r
- } finally {\r
- reenableAutoCompaction(false);\r
- }\r
- \r
- }\r
- \r
- /**\r
- * Creates an iterator over the values of the set. The iterator\r
- * supports element deletion.\r
- *\r
- * @return an <code>Iterator</code> value\r
- */\r
- final public Iterator<CacheEntry> iterator() {\r
- \r
- class Iter implements Iterator<CacheEntry> {\r
-\r
- private int index = capacity();\r
- \r
- public Iter() {\r
- advance();\r
- }\r
-\r
- private void advance() {\r
- while (index-- > 0 && (_set[index] == null || _set[index] == QueryIdentityHash.REMOVED)) ;\r
- }\r
- \r
- @Override\r
- public boolean hasNext() {\r
- return index >= 0;\r
- }\r
-\r
- @Override\r
- public CacheEntry next() {\r
- if(index >= 0) {\r
- CacheEntry result = (CacheEntry)_set[index];\r
- advance();\r
- return result;\r
- }\r
- return null;\r
- }\r
-\r
- @Override\r
- public void remove() {\r
- throw new Error("Not supported.");\r
- }\r
- \r
- };\r
- \r
- return new Iter();\r
- \r
- }\r
-\r
- public void clear() {\r
- super.clear();\r
-\r
- Arrays.fill(_set, 0, _set.length, null);\r
- }\r
- \r
-} // THashSet\r
+/*******************************************************************************
+ * 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.Arrays;
+import java.util.Iterator;
+
+
+/**
+ * An implementation of the <tt>Set</tt> interface that uses an
+ * open-addressed hash table to store its contents.
+ *
+ * Created: Sat Nov 3 10:38:17 2001
+ *
+ * @author Eric D. Friedman
+ * @version $Id: QueryIdentityHashSet.java,v 1.1 2008/03/14 11:32:01 tuoksk Exp $
+ */
+
+final public class QueryIdentityHashSet extends QueryIdentityHash implements Iterable<CacheEntry> {
+
+ /**
+ * Creates a new <code>THashSet</code> instance with a prime
+ * capacity equal to or greater than <tt>initialCapacity</tt> and
+ * with the default load factor.
+ *
+ * @param initialCapacity an <code>int</code> value
+ */
+ public QueryIdentityHashSet(int initialCapacity) {
+ super(initialCapacity);
+ }
+
+ /**
+ * Inserts a value into the set.
+ *
+ * @param obj an <code>Object</code> value
+ * @return true if the set was modified by the add operation
+ */
+ final public boolean add(final CacheEntry obj) {
+
+ final int index = insertionIndex(obj);
+
+ if (index < 0) {
+ return false; // already present in set, nothing to add
+ }
+
+ final CacheEntry old = _set[index];
+ _set[index] = obj;
+
+ postInsertHook(old == null);
+ return true; // yes, we added something
+
+ }
+
+ /**
+ * Expands the set to accomodate new values.
+ *
+ * @param newCapacity an <code>int</code> value
+ */
+ final protected void rehash(int newCapacity) {
+
+ final int oldCapacity = _set.length;
+ final CacheEntry oldSet[] = _set;
+
+ _set = new CacheEntry[newCapacity];
+
+ for (int i = oldCapacity; i-- > 0;) {
+ if(oldSet[i] != null && oldSet[i] != REMOVED) {
+ final CacheEntry o = oldSet[i];
+ //if(o.isDiscarded()) continue;
+ final int index = insertionIndex(o);
+ if(index < 0) {
+ new Exception().printStackTrace();
+ System.out.println("rehash " + i + " " + o);
+ for (int j = oldCapacity; j-- > 0;) {
+ System.out.println("rehash " + j+ " " + oldSet[j] + " " + System.identityHashCode(oldSet[j]));
+ }
+ }
+ else _set[index] = o;
+ }
+ }
+
+ }
+
+ /**
+ * Removes <tt>obj</tt> from the set.
+ *
+ * @param obj an <code>Object</code> value
+ * @return true if the set was modified by the remove operation.
+ */
+ final public boolean remove(Object obj) {
+ int index = index(obj);
+ if (index >= 0) {
+ removeAt(index);
+ return true;
+ }
+ return false;
+ }
+
+ private int knownBound = 10;
+
+ final public void purge() {
+
+ if(size() > (knownBound<<1)) {
+
+ knownBound=10;
+ for(int i=0;i<_set.length;i++) {
+ CacheEntry entry = _set[i];
+ if(entry != null && REMOVED != entry) {
+ if(entry.isDiscarded()) {
+ removeAt(i);
+ } else {
+ knownBound++;
+ }
+ }
+ }
+
+ }
+
+ }
+
+ final public CacheEntry removeDiscarded() {
+
+ tempDisableAutoCompaction();
+ try {
+
+ for(int i=0;i<_set.length;i++) {
+ CacheEntry entry = _set[i];
+ if(entry != null && REMOVED != entry) {
+ removeAt(i);
+ if(!entry.isDiscarded()) return entry;
+ }
+ }
+
+ return null;
+
+ } finally {
+ reenableAutoCompaction(false);
+ }
+
+ }
+
+ /**
+ * Creates an iterator over the values of the set. The iterator
+ * supports element deletion.
+ *
+ * @return an <code>Iterator</code> value
+ */
+ final public Iterator<CacheEntry> iterator() {
+
+ class Iter implements Iterator<CacheEntry> {
+
+ private int index = capacity();
+
+ public Iter() {
+ advance();
+ }
+
+ private void advance() {
+ while (index-- > 0 && (_set[index] == null || _set[index] == QueryIdentityHash.REMOVED)) ;
+ }
+
+ @Override
+ public boolean hasNext() {
+ return index >= 0;
+ }
+
+ @Override
+ public CacheEntry next() {
+ if(index >= 0) {
+ CacheEntry result = (CacheEntry)_set[index];
+ advance();
+ return result;
+ }
+ return null;
+ }
+
+ @Override
+ public void remove() {
+ throw new Error("Not supported.");
+ }
+
+ };
+
+ return new Iter();
+
+ }
+
+ public void clear() {
+ super.clear();
+
+ Arrays.fill(_set, 0, _set.length, null);
+ }
+
+} // THashSet