Mercurial > hg > blitz_stable

comparison src/org/dancres/blitz/entry/ci/BitmapIndexer.java @ 0:3dc0c5604566

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Initial checkin of blitz 2.0 fcs - no installer yet.
author Dan Creswell <dan.creswell@gmail.com>
date Sat, 21 Mar 2009 11:00:06 +0000
parents
children
comparison
equal deleted inserted replaced
-1:000000000000 0:3dc0c5604566
1 package org.dancres.blitz.entry.ci;
2
3 import java.util.ArrayList;
4 import java.util.Iterator;
5 import java.util.Collection;
6 import java.util.HashMap;
7
8 import java.util.logging.*;
9
10 import org.dancres.blitz.entry.EntrySleeve;
11 import org.dancres.blitz.entry.TupleLocator;
12
13 import org.dancres.blitz.mangler.MangledField;
14 import org.dancres.blitz.mangler.MangledEntry;
15
16 import org.dancres.blitz.cache.Cache;
17 import org.dancres.blitz.cache.CacheListener;
18 import org.dancres.blitz.cache.Identifiable;
19
20 import org.dancres.blitz.oid.OID;
21
22 import org.dancres.blitz.Logging;
23
24 import org.dancres.struct.BitIndex;
25 import org.dancres.struct.BitListener;
26
27 /**
28 CacheIndexer is responsible for indexing EntrySleeves held in any
29 cache capable of support CacheListener instances. It supports searching
30 as per other forms of storage via a TupleLocator::find mechanism.
31
32 @todo Maybe use some other kind of list rather than ArrayList which, for
33 large sizes, may not be so good.
34 */
35 public class BitmapIndexer extends CacheIndexer implements CacheListener {
36
37 private BitIndex theFreeSlots;
38
39 /**
40 Because fields are ordered and always present, even if they are null
41 we don't need to use a HashMap here.
42 */
43 private BitCacheLines[] theCacheLines;
44
45 /**
46 Contains all ids we know about which is required for a wildcard
47 search. A possibly better solution would iterate across all indexes but
48 then there's the need to do intersection to prevent repeated passes over
49 the same id which means much more complex code and might perform worse
50 than this simple solution.
51 */
52 private OID[] theAllIDs;
53
54 /**
55 Given an ID, will tell you where the ID is indexed to if present
56 */
57 private HashMap theOffsets = new HashMap();
58
59 private String theType;
60
61 BitmapIndexer(Cache aCache, String aType) {
62 aCache.add(this);
63 theType = aType;
64 theFreeSlots = new BitIndex(aCache.getSize());
65 /*
66 for (int i = 0; i < aCache.getSize(); i++) {
67 theFreeSlots.set(i);
68 }
69 */
70
71 theAllIDs = new OID[aCache.getSize()];
72 }
73
74 public void loaded(Identifiable anIdentifiable) {
75 // System.err.println("CI:Loaded: " + anIdentifiable.getId() + "," + this);
76
77 EntrySleeve mySleeve = (EntrySleeve) anIdentifiable;
78
79 /*
80 No point indexing something that's already deleted - we only want
81 to generate load requests in response to explicit address'ing via
82 UID.
83 */
84 if (mySleeve.isDeleted())
85 return;
86
87 initBarrier(mySleeve);
88
89 insert(mySleeve);
90 }
91
92 public void flushed(Identifiable anIdentifiable) {
93 // System.err.println("CI:Flushed: " + anIdentifiable.getId() + "," + this);
94
95 EntrySleeve mySleeve = (EntrySleeve) anIdentifiable;
96 initBarrier(mySleeve);
97
98 remove(mySleeve);
99 }
100
101 public void dirtied(Identifiable anIdentifiable) {
102 // System.err.println("CI:Dirtied: " + anIdentifiable.getId() + "," + this);
103
104 EntrySleeve mySleeve = (EntrySleeve) anIdentifiable;
105 initBarrier(mySleeve);
106
107 if (mySleeve.isDeleted()) {
108 // System.err.println("CI:Removed: " + anIdentifiable.getId() + ", " + this);
109 remove(mySleeve);
110 }
111 }
112
113 public TupleLocator find(MangledEntry anEntry) {
114 try {
115 return findImpl(anEntry);
116 } catch (ArrayIndexOutOfBoundsException anE) {
117 theLogger.log(Level.SEVERE, "Find broke - did you add/remove fields in your Entry?", anE);
118 theLogger.log(Level.SEVERE, "CacheIndexer for: " +
119 theType);
120 theLogger.log(Level.SEVERE, "Entry looks like");
121 theLogger.log(Level.SEVERE, "Entry type: " +
122 anEntry.getType());
123 for (int i = 0; i < anEntry.getFields().length; i++) {
124 MangledField myField = anEntry.getField(i);
125
126 theLogger.log(Level.SEVERE, "Name: " +
127 myField.getName() + ", hashcode:" +
128 myField.hashCode() + ", offset:" +
129 i + ", isNull: " +
130 myField.isNull());
131 }
132 theLogger.log(Level.SEVERE, "Cachelines looks like");
133 theLogger.log(Level.SEVERE, "Cachelines size:" +
134 theCacheLines.length);
135 for (int i = 0; i < theCacheLines.length; i++) {
136 theLogger.log(Level.SEVERE, "Name: " +
137 theCacheLines[i].getName() +
138 " Offset: " + i +
139 " size: " +
140 theCacheLines[i].getSize());
141 }
142
143 throw anE;
144 }
145 }
146
147 private TupleLocator findImpl(MangledEntry anEntry) {
148 /*
149 Unlike the cache listener methods which can only be called with
150 an entry of this indexers type, there's a possibility this method's
151 first entry will be a different type. If it is, it can't be used
152 to init the barrier - thus, if we fail to init the barrier we should
153 return an empty locator
154 */
155 if (!initBarrier(anEntry))
156 return ArrayLocatorImpl.EMPTY_LOCATOR;
157
158 if ((anEntry == null) || (anEntry.isWildcard())) {
159 // Handle wildcard requests
160 //
161 if (theLogger.isLoggable(Level.FINE))
162 theLogger.log(Level.FINE, "Wildcard match");
163
164 synchronized(theAllIDs) {
165 if (theOffsets.size() == 0) {
166 // System.err.println("No matches");
167 return ArrayLocatorImpl.EMPTY_LOCATOR;
168 } else {
169 // System.err.println("Sparse");
170 /*
171 OID[] myUids = new OID[theAllIDs.length];
172 System.arraycopy(theAllIDs, 0, myUids, 0,
173 theAllIDs.length);
174 */
175 return new BitLocatorImpl(theFreeSlots, theAllIDs,
176 false);
177 }
178 }
179 } else {
180 // Proper indexing effort
181 //
182 if (theLogger.isLoggable(Level.FINE))
183 theLogger.log(Level.FINE, "Specific match");
184
185 MangledField myChoice = null;
186 int myChoicesSize = 0;
187 int myChoicesOffset = 0;
188
189 // Find the smallest index available
190 for (int i = 0; i < anEntry.getFields().length; i++) {
191 MangledField myField = anEntry.getField(i);
192 int mySize;
193
194 if (theLogger.isLoggable(Level.FINE))
195 theLogger.log(Level.FINE, "Consider: " + myField.getName());
196
197 // If field is empty, we can't search on it
198 if (myField.isNull())
199 continue;
200
201 mySize = getSize(myField, i);
202
203 /*
204 Field is searchable - but, if we get no hits from cache
205 indexes, that means we have no matches in memory. This
206 works because for a match to succeed it must match on
207 all fields in the template. Thus if the template has a
208 field with a hashcode that produces no hits then whilst
209 we may have Entry's that match other fields of the template
210 we know that none of these Entry's will match this field
211 of the template so we should stop now.
212 */
213 if (mySize == 0) {
214 if (theLogger.isLoggable(Level.FINE))
215 theLogger.log(Level.FINE,
216 "One key not indexed - abort");
217 return ArrayLocatorImpl.EMPTY_LOCATOR;
218 }
219
220 if (theLogger.isLoggable(Level.FINE))
221 theLogger.log(Level.FINE, "Available size: " + mySize);
222
223 if (myChoice == null) {
224 myChoice = myField;
225 myChoicesSize = mySize;
226 myChoicesOffset = i;
227 } else {
228 if (mySize < myChoicesSize) {
229 myChoice = myField;
230 myChoicesSize = mySize;
231 myChoicesOffset = i;
232 }
233 }
234 }
235
236 if (myChoice == null) {
237 return ArrayLocatorImpl.EMPTY_LOCATOR;
238 } else {
239 if (theLogger.isLoggable(Level.FINE))
240 theLogger.log(Level.FINE, "Chose: " + myChoicesSize +
241 myChoice.getName());
242 return getIds(myChoice, myChoicesOffset);
243 }
244 }
245 }
246
247 private TupleLocator getIds(MangledField aField, int anOffset) {
248 BitCacheLines myLine = getCacheLines(anOffset);
249 BitIndex myIndex = myLine.getHits(aField.hashCode());
250
251 if (myIndex == null)
252 return ArrayLocatorImpl.EMPTY_LOCATOR;
253 else {
254 /*
255 synchronized(theAllIDs) {
256 OID[] myUids = new OID[theAllIDs.length];
257 System.arraycopy(theAllIDs, 0, myUids, 0, theAllIDs.length);
258 }
259 */
260 return new BitLocatorImpl(myIndex, theAllIDs, false);
261 }
262 }
263
264 private int getSize(MangledField aField, int anOffset) {
265 BitCacheLines myLine = getCacheLines(anOffset);
266 return myLine.getSize(aField.hashCode());
267 }
268
269 private boolean initBarrier(EntrySleeve aSleeve) {
270 synchronized(this) {
271 if (theCacheLines == null)
272 return initBarrier(aSleeve.getEntry());
273 else
274 return true;
275 }
276 }
277
278 /**
279 @return true if the barrier is already inited or if
280 the barrier was successfully inited, false otherwise.
281 */
282 private boolean initBarrier(MangledEntry anEntry) {
283 synchronized(this) {
284 if (theCacheLines == null) {
285 theLogger.log(Level.FINE,
286 "Initing cache indexer: " + theType);
287
288 if (!anEntry.getType().equals(theType)) {
289 theLogger.log(Level.FINE,
290 "Can't init indexer with this: " +
291 anEntry.getType());
292 return false;
293 }
294
295 theLogger.log(Level.FINE, "Entry looks like");
296 theLogger.log(Level.FINE, "Entry type: " +
297 anEntry.getType());
298 for (int i = 0; i < anEntry.getFields().length; i++) {
299 MangledField myField = anEntry.getField(i);
300
301 theLogger.log(Level.FINE, "Name: " +
302 myField.getName() + ", hashcode:" +
303 myField.hashCode() + ", offset:" +
304 i + ", isNull: " +
305 myField.isNull());
306 }
307
308 MangledField[] myFields = anEntry.getFields();
309 theCacheLines = new BitCacheLines[myFields.length];
310
311 for (int i = 0; i < myFields.length; i++) {
312 theCacheLines[i] = new BitCacheLines(i,
313 myFields[i].getName(),
314 theAllIDs.length);
315 }
316 }
317
318 return true;
319 }
320 }
321
322 private BitCacheLines getCacheLines(int anOffset) {
323 return theCacheLines[anOffset];
324 }
325
326 private static final class FreeSlotReceiver implements BitListener {
327 private int theFree;
328
329 public boolean active(int aPos) {
330 throw new RuntimeException("Shouldn't have been called");
331 }
332
333 public boolean inactive(int aPos) {
334 theFree = aPos;
335 return true;
336 }
337
338 int getIndex() {
339 return theFree;
340 }
341 }
342
343 /**
344 Store the id of the passed sleeve into a free slot and return the slot
345 assigned.
346 */
347 private int assignSlot(EntrySleeve aSleeve) {
348 // Find slot
349 FreeSlotReceiver myFreeSlot = new FreeSlotReceiver();
350 theFreeSlots.iterateZero(myFreeSlot);
351
352 // Populate
353 theFreeSlots.set(myFreeSlot.getIndex());
354 theAllIDs[myFreeSlot.getIndex()] = aSleeve.getOID();
355 theOffsets.put(aSleeve.getOID(), new Integer(myFreeSlot.getIndex()));
356
357 /*
358 System.out.println("Inserting: " + aSleeve.getOID() + " at " +
359 myFreeSlot.getIndex());
360 */
361 return myFreeSlot.getIndex();
362 }
363
364 /**
365 Locate the id of the passed sleeve and remove it from it's slot
366 return the index of the slot it was in
367
368 @return -1 if the id was not present
369 */
370 private int freeSlot(EntrySleeve aSleeve) {
371 Integer myKey = (Integer) theOffsets.remove(aSleeve.getOID());
372
373 if (myKey == null)
374 return -1;
375 else {
376 /*
377 System.out.println("Removing: " + aSleeve.getOID() + " at " +
378 myKey);
379 */
380 }
381
382 int mySlot = myKey.intValue();
383 theFreeSlots.clear(mySlot);
384 theAllIDs[mySlot] = null;
385
386 return mySlot;
387 }
388
389 /**
390 Add a sleeve to the indexer
391 */
392 private void insert(EntrySleeve aSleeve) {
393 int mySlot;
394
395 synchronized(theAllIDs) {
396 mySlot = assignSlot(aSleeve);
397
398 for (int i = 0; i < theCacheLines.length; i++) {
399 theCacheLines[i].insert(aSleeve, mySlot);
400 }
401 }
402 }
403
404 /**
405 Remove a sleeve from the indexer
406 */
407 private void remove(EntrySleeve aSleeve) {
408 int mySlot;
409
410 synchronized(theAllIDs) {
411 mySlot = freeSlot(aSleeve);
412
413 if (mySlot != -1) {
414 // System.out.println("CI:Did remove: " + aSleeve.getOID());
415 for (int i = 0; i < theCacheLines.length; i++) {
416 theCacheLines[i].remove(aSleeve, mySlot);
417 }
418 } else {
419 // System.out.println("CI:Not removed: " + aSleeve.getOID());
420 }
421 }
422 }
423 }