Mercurial > hg > blitz_condensed
diff 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 |
line wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/org/dancres/blitz/entry/ci/BitmapIndexer.java Sat Mar 21 11:00:06 2009 +0000 @@ -0,0 +1,423 @@ +package org.dancres.blitz.entry.ci; + +import java.util.ArrayList; +import java.util.Iterator; +import java.util.Collection; +import java.util.HashMap; + +import java.util.logging.*; + +import org.dancres.blitz.entry.EntrySleeve; +import org.dancres.blitz.entry.TupleLocator; + +import org.dancres.blitz.mangler.MangledField; +import org.dancres.blitz.mangler.MangledEntry; + +import org.dancres.blitz.cache.Cache; +import org.dancres.blitz.cache.CacheListener; +import org.dancres.blitz.cache.Identifiable; + +import org.dancres.blitz.oid.OID; + +import org.dancres.blitz.Logging; + +import org.dancres.struct.BitIndex; +import org.dancres.struct.BitListener; + +/** + CacheIndexer is responsible for indexing EntrySleeves held in any + cache capable of support CacheListener instances. It supports searching + as per other forms of storage via a TupleLocator::find mechanism. + + @todo Maybe use some other kind of list rather than ArrayList which, for + large sizes, may not be so good. +*/ +public class BitmapIndexer extends CacheIndexer implements CacheListener { + + private BitIndex theFreeSlots; + + /** + Because fields are ordered and always present, even if they are null + we don't need to use a HashMap here. + */ + private BitCacheLines[] theCacheLines; + + /** + Contains all ids we know about which is required for a wildcard + search. A possibly better solution would iterate across all indexes but + then there's the need to do intersection to prevent repeated passes over + the same id which means much more complex code and might perform worse + than this simple solution. + */ + private OID[] theAllIDs; + + /** + Given an ID, will tell you where the ID is indexed to if present + */ + private HashMap theOffsets = new HashMap(); + + private String theType; + + BitmapIndexer(Cache aCache, String aType) { + aCache.add(this); + theType = aType; + theFreeSlots = new BitIndex(aCache.getSize()); + /* + for (int i = 0; i < aCache.getSize(); i++) { + theFreeSlots.set(i); + } + */ + + theAllIDs = new OID[aCache.getSize()]; + } + + public void loaded(Identifiable anIdentifiable) { + // System.err.println("CI:Loaded: " + anIdentifiable.getId() + "," + this); + + EntrySleeve mySleeve = (EntrySleeve) anIdentifiable; + + /* + No point indexing something that's already deleted - we only want + to generate load requests in response to explicit address'ing via + UID. + */ + if (mySleeve.isDeleted()) + return; + + initBarrier(mySleeve); + + insert(mySleeve); + } + + public void flushed(Identifiable anIdentifiable) { + // System.err.println("CI:Flushed: " + anIdentifiable.getId() + "," + this); + + EntrySleeve mySleeve = (EntrySleeve) anIdentifiable; + initBarrier(mySleeve); + + remove(mySleeve); + } + + public void dirtied(Identifiable anIdentifiable) { + // System.err.println("CI:Dirtied: " + anIdentifiable.getId() + "," + this); + + EntrySleeve mySleeve = (EntrySleeve) anIdentifiable; + initBarrier(mySleeve); + + if (mySleeve.isDeleted()) { + // System.err.println("CI:Removed: " + anIdentifiable.getId() + ", " + this); + remove(mySleeve); + } + } + + public TupleLocator find(MangledEntry anEntry) { + try { + return findImpl(anEntry); + } catch (ArrayIndexOutOfBoundsException anE) { + theLogger.log(Level.SEVERE, "Find broke - did you add/remove fields in your Entry?", anE); + theLogger.log(Level.SEVERE, "CacheIndexer for: " + + theType); + theLogger.log(Level.SEVERE, "Entry looks like"); + theLogger.log(Level.SEVERE, "Entry type: " + + anEntry.getType()); + for (int i = 0; i < anEntry.getFields().length; i++) { + MangledField myField = anEntry.getField(i); + + theLogger.log(Level.SEVERE, "Name: " + + myField.getName() + ", hashcode:" + + myField.hashCode() + ", offset:" + + i + ", isNull: " + + myField.isNull()); + } + theLogger.log(Level.SEVERE, "Cachelines looks like"); + theLogger.log(Level.SEVERE, "Cachelines size:" + + theCacheLines.length); + for (int i = 0; i < theCacheLines.length; i++) { + theLogger.log(Level.SEVERE, "Name: " + + theCacheLines[i].getName() + + " Offset: " + i + + " size: " + + theCacheLines[i].getSize()); + } + + throw anE; + } + } + + private TupleLocator findImpl(MangledEntry anEntry) { + /* + Unlike the cache listener methods which can only be called with + an entry of this indexers type, there's a possibility this method's + first entry will be a different type. If it is, it can't be used + to init the barrier - thus, if we fail to init the barrier we should + return an empty locator + */ + if (!initBarrier(anEntry)) + return ArrayLocatorImpl.EMPTY_LOCATOR; + + if ((anEntry == null) || (anEntry.isWildcard())) { + // Handle wildcard requests + // + if (theLogger.isLoggable(Level.FINE)) + theLogger.log(Level.FINE, "Wildcard match"); + + synchronized(theAllIDs) { + if (theOffsets.size() == 0) { + // System.err.println("No matches"); + return ArrayLocatorImpl.EMPTY_LOCATOR; + } else { + // System.err.println("Sparse"); + /* + OID[] myUids = new OID[theAllIDs.length]; + System.arraycopy(theAllIDs, 0, myUids, 0, + theAllIDs.length); + */ + return new BitLocatorImpl(theFreeSlots, theAllIDs, + false); + } + } + } else { + // Proper indexing effort + // + if (theLogger.isLoggable(Level.FINE)) + theLogger.log(Level.FINE, "Specific match"); + + MangledField myChoice = null; + int myChoicesSize = 0; + int myChoicesOffset = 0; + + // Find the smallest index available + for (int i = 0; i < anEntry.getFields().length; i++) { + MangledField myField = anEntry.getField(i); + int mySize; + + if (theLogger.isLoggable(Level.FINE)) + theLogger.log(Level.FINE, "Consider: " + myField.getName()); + + // If field is empty, we can't search on it + if (myField.isNull()) + continue; + + mySize = getSize(myField, i); + + /* + Field is searchable - but, if we get no hits from cache + indexes, that means we have no matches in memory. This + works because for a match to succeed it must match on + all fields in the template. Thus if the template has a + field with a hashcode that produces no hits then whilst + we may have Entry's that match other fields of the template + we know that none of these Entry's will match this field + of the template so we should stop now. + */ + if (mySize == 0) { + if (theLogger.isLoggable(Level.FINE)) + theLogger.log(Level.FINE, + "One key not indexed - abort"); + return ArrayLocatorImpl.EMPTY_LOCATOR; + } + + if (theLogger.isLoggable(Level.FINE)) + theLogger.log(Level.FINE, "Available size: " + mySize); + + if (myChoice == null) { + myChoice = myField; + myChoicesSize = mySize; + myChoicesOffset = i; + } else { + if (mySize < myChoicesSize) { + myChoice = myField; + myChoicesSize = mySize; + myChoicesOffset = i; + } + } + } + + if (myChoice == null) { + return ArrayLocatorImpl.EMPTY_LOCATOR; + } else { + if (theLogger.isLoggable(Level.FINE)) + theLogger.log(Level.FINE, "Chose: " + myChoicesSize + + myChoice.getName()); + return getIds(myChoice, myChoicesOffset); + } + } + } + + private TupleLocator getIds(MangledField aField, int anOffset) { + BitCacheLines myLine = getCacheLines(anOffset); + BitIndex myIndex = myLine.getHits(aField.hashCode()); + + if (myIndex == null) + return ArrayLocatorImpl.EMPTY_LOCATOR; + else { + /* + synchronized(theAllIDs) { + OID[] myUids = new OID[theAllIDs.length]; + System.arraycopy(theAllIDs, 0, myUids, 0, theAllIDs.length); + } + */ + return new BitLocatorImpl(myIndex, theAllIDs, false); + } + } + + private int getSize(MangledField aField, int anOffset) { + BitCacheLines myLine = getCacheLines(anOffset); + return myLine.getSize(aField.hashCode()); + } + + private boolean initBarrier(EntrySleeve aSleeve) { + synchronized(this) { + if (theCacheLines == null) + return initBarrier(aSleeve.getEntry()); + else + return true; + } + } + + /** + @return true if the barrier is already inited or if + the barrier was successfully inited, false otherwise. + */ + private boolean initBarrier(MangledEntry anEntry) { + synchronized(this) { + if (theCacheLines == null) { + theLogger.log(Level.FINE, + "Initing cache indexer: " + theType); + + if (!anEntry.getType().equals(theType)) { + theLogger.log(Level.FINE, + "Can't init indexer with this: " + + anEntry.getType()); + return false; + } + + theLogger.log(Level.FINE, "Entry looks like"); + theLogger.log(Level.FINE, "Entry type: " + + anEntry.getType()); + for (int i = 0; i < anEntry.getFields().length; i++) { + MangledField myField = anEntry.getField(i); + + theLogger.log(Level.FINE, "Name: " + + myField.getName() + ", hashcode:" + + myField.hashCode() + ", offset:" + + i + ", isNull: " + + myField.isNull()); + } + + MangledField[] myFields = anEntry.getFields(); + theCacheLines = new BitCacheLines[myFields.length]; + + for (int i = 0; i < myFields.length; i++) { + theCacheLines[i] = new BitCacheLines(i, + myFields[i].getName(), + theAllIDs.length); + } + } + + return true; + } + } + + private BitCacheLines getCacheLines(int anOffset) { + return theCacheLines[anOffset]; + } + + private static final class FreeSlotReceiver implements BitListener { + private int theFree; + + public boolean active(int aPos) { + throw new RuntimeException("Shouldn't have been called"); + } + + public boolean inactive(int aPos) { + theFree = aPos; + return true; + } + + int getIndex() { + return theFree; + } + } + + /** + Store the id of the passed sleeve into a free slot and return the slot + assigned. + */ + private int assignSlot(EntrySleeve aSleeve) { + // Find slot + FreeSlotReceiver myFreeSlot = new FreeSlotReceiver(); + theFreeSlots.iterateZero(myFreeSlot); + + // Populate + theFreeSlots.set(myFreeSlot.getIndex()); + theAllIDs[myFreeSlot.getIndex()] = aSleeve.getOID(); + theOffsets.put(aSleeve.getOID(), new Integer(myFreeSlot.getIndex())); + + /* + System.out.println("Inserting: " + aSleeve.getOID() + " at " + + myFreeSlot.getIndex()); + */ + return myFreeSlot.getIndex(); + } + + /** + Locate the id of the passed sleeve and remove it from it's slot + return the index of the slot it was in + + @return -1 if the id was not present + */ + private int freeSlot(EntrySleeve aSleeve) { + Integer myKey = (Integer) theOffsets.remove(aSleeve.getOID()); + + if (myKey == null) + return -1; + else { + /* + System.out.println("Removing: " + aSleeve.getOID() + " at " + + myKey); + */ + } + + int mySlot = myKey.intValue(); + theFreeSlots.clear(mySlot); + theAllIDs[mySlot] = null; + + return mySlot; + } + + /** + Add a sleeve to the indexer + */ + private void insert(EntrySleeve aSleeve) { + int mySlot; + + synchronized(theAllIDs) { + mySlot = assignSlot(aSleeve); + + for (int i = 0; i < theCacheLines.length; i++) { + theCacheLines[i].insert(aSleeve, mySlot); + } + } + } + + /** + Remove a sleeve from the indexer + */ + private void remove(EntrySleeve aSleeve) { + int mySlot; + + synchronized(theAllIDs) { + mySlot = freeSlot(aSleeve); + + if (mySlot != -1) { + // System.out.println("CI:Did remove: " + aSleeve.getOID()); + for (int i = 0; i < theCacheLines.length; i++) { + theCacheLines[i].remove(aSleeve, mySlot); + } + } else { + // System.out.println("CI:Not removed: " + aSleeve.getOID()); + } + } + } +}