--- /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 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