3a7eb61820203ffc5e079d0a57b12f7fe8c86842
[simantics/platform.git] / 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