Mercurial > hg > blitz_condensed
comparison src/org/dancres/blitz/entry/ci/BitmapIndexer.java @ 0:3dc0c5604566
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 } |