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

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