bundles/org.simantics.db.impl/src/org/simantics/db/impl/query/QueryIdentityHashSet.java

   1 /*******************************************************************************\r
   2  * Copyright (c) 2007, 2010 Association for Decentralized Information Management\r
   3  * in Industry THTH ry.\r
   4  * All rights reserved. This program and the accompanying materials\r
   5  * are made available under the terms of the Eclipse Public License v1.0\r
   6  * which accompanies this distribution, and is available at\r
   7  * http://www.eclipse.org/legal/epl-v10.html\r
   8  *\r
   9  * Contributors:\r
  10  *     VTT Technical Research Centre of Finland - initial API and implementation\r
  11  *******************************************************************************/\r
  12 package org.simantics.db.impl.query;\r
  13 \r
  14 import java.util.Arrays;\r
  15 import java.util.Iterator;\r
  16 \r
  17 \r
  18 /**\r
  19  * An implementation of the <tt>Set</tt> interface that uses an\r
  20  * open-addressed hash table to store its contents.\r
  21  *\r
  22  * Created: Sat Nov  3 10:38:17 2001\r
  23  *\r
  24  * @author Eric D. Friedman\r
  25  * @version $Id: QueryIdentityHashSet.java,v 1.1 2008/03/14 11:32:01 tuoksk Exp $\r
  26  */\r
  27 \r
  28 final public class QueryIdentityHashSet extends QueryIdentityHash implements Iterable<CacheEntry> {\r
  29     \r
  30     /**\r
  31      * Creates a new <code>THashSet</code> instance with a prime\r
  32      * capacity equal to or greater than <tt>initialCapacity</tt> and\r
  33      * with the default load factor.\r
  34      *\r
  35      * @param initialCapacity an <code>int</code> value\r
  36      */\r
  37     public QueryIdentityHashSet(int initialCapacity) {\r
  38         super(initialCapacity);\r
  39     }\r
  40 \r
  41     /**\r
  42      * Inserts a value into the set.\r
  43      *\r
  44      * @param obj an <code>Object</code> value\r
  45      * @return true if the set was modified by the add operation\r
  46      */\r
  47     final public boolean add(final CacheEntry obj) {\r
  48         \r
  49         final int index = insertionIndex(obj);\r
  50 \r
  51         if (index < 0) {\r
  52             return false;       // already present in set, nothing to add\r
  53         }\r
  54 \r
  55         final CacheEntry old = _set[index];\r
  56         _set[index] = obj;\r
  57 \r
  58         postInsertHook(old == null);\r
  59         return true;            // yes, we added something\r
  60         \r
  61     }\r
  62 \r
  63     /**\r
  64      * Expands the set to accomodate new values.\r
  65      *\r
  66      * @param newCapacity an <code>int</code> value\r
  67      */\r
  68     final protected void rehash(int newCapacity) {\r
  69         \r
  70         final int oldCapacity = _set.length;\r
  71         final CacheEntry oldSet[] = _set;\r
  72 \r
  73         _set = new CacheEntry[newCapacity];\r
  74 \r
  75         for (int i = oldCapacity; i-- > 0;) {\r
  76             if(oldSet[i] != null && oldSet[i] != REMOVED) {\r
  77                 final CacheEntry o = oldSet[i];\r
  78                 //if(o.isDiscarded()) continue;\r
  79                 final int index = insertionIndex(o);\r
  80                 if(index < 0) {\r
  81                     new Exception().printStackTrace();\r
  82                     System.out.println("rehash " + i + " " + o);\r
  83                     for (int j = oldCapacity; j-- > 0;) {\r
  84                         System.out.println("rehash " + j+ " " + oldSet[j] + " " + System.identityHashCode(oldSet[j]));\r
  85                     }\r
  86                 }\r
  87                 else _set[index] = o;\r
  88             }\r
  89         }\r
  90         \r
  91     }\r
  92 \r
  93     /**\r
  94      * Removes <tt>obj</tt> from the set.\r
  95      *\r
  96      * @param obj an <code>Object</code> value\r
  97      * @return true if the set was modified by the remove operation.\r
  98      */\r
  99     final public boolean remove(Object obj) {\r
 100         int index = index(obj);\r
 101         if (index >= 0) {\r
 102             removeAt(index);\r
 103             return true;\r
 104         }\r
 105         return false;\r
 106     }\r
 107     \r
 108     private int knownBound = 10;\r
 109     \r
 110     final public void purge() {\r
 111         \r
 112         if(size() > (knownBound<<1)) {\r
 113                 \r
 114                 knownBound=10;\r
 115                 for(int i=0;i<_set.length;i++) {\r
 116                     CacheEntry entry = _set[i];\r
 117                     if(entry != null && REMOVED != entry) {\r
 118                         if(entry.isDiscarded()) {\r
 119                                 removeAt(i); \r
 120                         } else {\r
 121                                 knownBound++;\r
 122                         }\r
 123                     }\r
 124                 }\r
 125                 \r
 126         }\r
 127         \r
 128     }\r
 129 \r
 130     final public CacheEntry removeDiscarded() {\r
 131         \r
 132         tempDisableAutoCompaction();\r
 133         try {\r
 134                 \r
 135                 for(int i=0;i<_set.length;i++) {\r
 136                     CacheEntry entry = _set[i];\r
 137                     if(entry != null && REMOVED != entry) {\r
 138                         removeAt(i);\r
 139                         if(!entry.isDiscarded()) return entry; \r
 140                     }\r
 141                 }\r
 142                 \r
 143                 return null;\r
 144                 \r
 145         } finally {\r
 146                 reenableAutoCompaction(false);\r
 147         }\r
 148         \r
 149     }\r
 150     \r
 151     /**\r
 152      * Creates an iterator over the values of the set.  The iterator\r
 153      * supports element deletion.\r
 154      *\r
 155      * @return an <code>Iterator</code> value\r
 156      */\r
 157     final public Iterator<CacheEntry> iterator() {\r
 158         \r
 159         class Iter implements Iterator<CacheEntry> {\r
 160 \r
 161             private int index = capacity();\r
 162             \r
 163             public Iter() {\r
 164                 advance();\r
 165             }\r
 166 \r
 167             private void advance() {\r
 168                 while (index-- > 0 && (_set[index] == null || _set[index] == QueryIdentityHash.REMOVED)) ;\r
 169             }\r
 170             \r
 171             @Override\r
 172             public boolean hasNext() {\r
 173                 return index >= 0;\r
 174             }\r
 175 \r
 176             @Override\r
 177             public CacheEntry next() {\r
 178                 if(index >= 0) {\r
 179                     CacheEntry result = (CacheEntry)_set[index];\r
 180                     advance();\r
 181                     return result;\r
 182                 }\r
 183                 return null;\r
 184             }\r
 185 \r
 186             @Override\r
 187             public void remove() {\r
 188                 throw new Error("Not supported.");\r
 189             }\r
 190             \r
 191         };\r
 192         \r
 193         return new Iter();\r
 194         \r
 195     }\r
 196 \r
 197     public void clear() {\r
 198         super.clear();\r
 199 \r
 200         Arrays.fill(_set, 0, _set.length, null);\r
 201     }\r
 202     \r
 203 } // THashSet\r