 |
*************************** SDBTree.h ********************************
@class SDBTreeCursor, NSStore;
extern NSString *SDBTreeIndexDidBecomeInvalid;
@interface SDBTree:NSObject
{
NSString *name;
NSMutableDictionary *contentDictionary;
NSMutableArray *orderedKeys;
int (*comparator)(id,id,void *);
void *comparatorContext;
// NSMutableArray *cursorList;
unsigned int blockNumber;
SDStore *storeFile;
BOOL dirty;
}
+ (int (*) (id,id,void *)) defaultComparator;
+ (void) freeFromBlock:(unsigned int) aBlockNumber inStore:(SDStore *)aStoreFile;
- (id) initInStore:(SDStore *)aStoreFile;
- (id) initFromBlock:(unsigned int) blockNo inStore:(SDStore *)aStoreFile;
- (void) setComparator: (SDComparator *)aComparator andContext:(void *)aContext ;
- (void) getComparator: (SDComparator **)aComparator andContext:(void **)aContext;
- (unsigned int) indexForKey:(NSData *)aKey exactMatch: (BOOL *)exactMatch;
- (BOOL) insertValue:(NSData *)aValue andKey:(NSData *)aKey atIndex:(unsigned int)index ;
- (void) removeValueAtIndex:(unsigned int)index withKey:(NSData *)key;
- (NSData *) valueAtIndex:(unsigned int)index;
- (NSData *) keyAtIndex:(unsigned int) index;
- (BOOL) indexBeyondLastKey:(unsigned int) index;
- (int)lastIndex;
- (BOOL) isEmpty;
- (void) setDirty:(BOOL) flag;
- (BOOL) isDirty;
- (int) blockNumber;
- (void) getBlock:(unsigned int *)aBlock andStore:(SDStore **)aStore;
- (void) commitTransaction;
- (unsigned) keyLimit;
- (void) empty;
- (unsigned) count;
- (void) freeFromStore;
- (void) setStore: (SDStore *)aStore;
@end
*************************** SDBTree.m ********************************
#import "ixCover.h"
@interface SDBTree(PrivateMethods)
- (void) buildOrderedKeys;
- (void) invalidateCursors;
@end
NSString *SDBTreeIndexDidBecomeInvalid = @"SDBTreeIndexDidBecomeInvalid";
@implementation SDBTree:NSObject
///////////////////////////////////////////////////////////////////////////
//
// IXKit cover methods
//
///////////////////////////////////////////////////////////////////////////
- (id) initInStore:(SDStore *)aStoreFile
{
[super init];
[self setStore:aStoreFile];
contentDictionary = [[NSMutableDictionary allocWithZone:[self zone]] initWithCapacity:1];
comparator = [SDBTree defaultComparator];
// cursorList = nil;
orderedKeys = [[NSMutableArray allocWithZone:[self zone]] initWithCapacity:1];
[storeFile createBlock:&blockNumber withSize:0];
[self setDirty:YES];
return self;
}
- (id) initFromBlock:(unsigned int) blockNo inStore:(SDStore *)aStoreFile
{
NSData *blockData;
blockNumber = blockNo;
[self setStore:aStoreFile];
blockData = [storeFile readBlock:blockNumber];
contentDictionary = [[NSUnarchiver unarchiveObjectWithData:blockData]retain];
[self setComparator:[SDBTree defaultComparator] andContext:NULL];
[self buildOrderedKeys];
[self setDirty:NO];
return self;
}
+ (void) freeFromBlock:(unsigned int) aBlockNumber inStore:(SDStore *)aStoreFile
{
[aStoreFile freeBlock:aBlockNumber];
}
///////////////////////////////////////////////////////////////////////////
// Comparators
//
// Comparators are functions used by the btree for inserting
// and finding keys.
//
// A simple comparator could treat the key as a characters or
// an integer.
//
// A more complex comparator could use the passed-in context
// to parse the key.
//
////////////////////////////////////////////////////////////////////////////
- (void) setComparator: (SDComparator *)aComparator andContext:(void *)aContext
{
BOOL needsRebuild = NO;
if ((comparator != aComparator)) {
comparator = aComparator;
needsRebuild = YES;
}
if (comparatorContext != aContext) {
// do I need to copy the context?
comparatorContext = aContext;
needsRebuild = YES;
}
// if the comparator or context changes, the ordered key array needs to
// be reconstructed
if (needsRebuild)
[self buildOrderedKeys];
}
- (void) getComparator: (SDComparator **)aComparator andContext:(void **)aContext
{
*aComparator = comparator;
*aContext = comparatorContext;
}
- (void) getBlock:(unsigned int *)aBlock andStore:(SDStore **)aStore
{
*aBlock = blockNumber;
*aStore = storeFile;
}
-(void) freeFromStore
{
[storeFile freeBlock:blockNumber];
storeFile = nil;
}
- (void) commitTransaction
{
NSData *data;
if ([self isDirty]) {
data = [NSArchiver archivedDataWithRootObject:contentDictionary];
[storeFile writeData:data toBlock:blockNumber];
[self setDirty:NO];
}
}
- (unsigned) keyLimit
{
return 1024; // ACK completely arbitrary
}
- (unsigned) count
{
return [orderedKeys count];
}
///////////////////////////////////////////////////////////////////////////
// Empty
//
// Removes all key/value pairs from the IXBTree, and reduces
// its storage allocation to the smallest possible size
//
////////////////////////////////////////////////////////////////////////////
- (void) empty
{
[contentDictionary removeAllObjects];
[orderedKeys removeAllObjects];
[self invalidateCursors];
}
+ (int (*) (id,id,void *)) defaultComparator
{
return SDCompareStringData;
}
///////////////////////////////////////////////////////////////////////////
//
// Methods for manipulating ordered key array
//
////////////////////////////////////////////////////////////////////////////
- (void) buildOrderedKeys
{
NSArray *t1 = [contentDictionary allKeys];
NSArray *t2 = [t1 sortedArrayUsingFunction:comparator context:comparatorContext];
if (orderedKeys) [orderedKeys release];
orderedKeys = [t2 mutableCopyWithZone:[self zone]];
}
- (void) rebuildOrderedKeys
{
NSData *hint;
NSArray *newArray;
hint = [orderedKeys sortedArrayHint];
newArray = [orderedKeys sortedArrayUsingFunction:comparator context:comparatorContext hint:hint];
[orderedKeys release];
orderedKeys = [newArray mutableCopyWithZone:[self zone]];
}
- (int) findClosestIndexHigherThanKey:(NSData *)aKey
{
int low, high, mid;
int comparatorResult;
// if the array is empty, bail
if ([orderedKeys count] == 0) return 0;
low = 0; high = [orderedKeys count]-1;
do {
mid = (low + high) / 2;
comparatorResult = (*comparator)(aKey,[orderedKeys objectAtIndex:mid],comparatorContext);
if (comparatorResult == NSOrderedAscending)
high = mid-1;
else
low = mid+1;
} while ((comparatorResult != NSOrderedSame) && (low <= high));
if (comparatorResult == NSOrderedSame)
return mid;
else if (comparatorResult == NSOrderedAscending)
return mid;
else if (comparatorResult == NSOrderedDescending)
return mid+1;
return 0; //something seriously wrong
}
- (void) commitTransaction:(NSNotification *)aNotification
{
if ([aNotification object] == storeFile)
[self commitTransaction];
}
- (void) invalidateCursors
{
[[NSNotificationCenter defaultCenter] postNotificationName:SDBTreeIndexDidBecomeInvalid object:self];
}
- (void)registerForTransactions
{
[[NSNotificationCenter defaultCenter] addObserver:self selector:@selector(commitTransaction:) name: SDStoreTransactionWasCommitted object:storeFile];
}
- (void) unregisterForTransactions
{
[[NSNotificationCenter defaultCenter]removeObserver:self name:SDStoreTransactionWasCommitted object:storeFile];
}
- (void) setStore: (SDStore *)aStore
{
storeFile = aStore;
[self registerForTransactions];
}
- (unsigned int) indexForKey:(NSData *)aKey exactMatch: (BOOL *)exactMatch
{
unsigned int returnValue;
if ((returnValue = [orderedKeys indexOfObject:aKey]) != NSNotFound) {
*exactMatch = YES;
return returnValue;
} else {
*exactMatch = NO;
// find index of closest value immediately *after* aKey
return [self findClosestIndexHigherThanKey:aKey];
}
}
// return YES if new value inserted; NO if old value overwritten
- (BOOL) insertValue:(NSData *)aValue andKey:(NSData *)aKey atIndex:(unsigned int)index
{
NSData *tmp = [contentDictionary objectForKey:aKey];
NSData *tmpKey = nil;
// insert key/value pair into dictionary
// if the key already exists, overwrite the value
[contentDictionary setObject:aValue forKey:aKey];
[self setDirty:YES];
// if we don't have an index location, we'll need to rebuild the sortedKey array. If we do have an index location, insert the key into the sorted array if it's not already there
if (index != NSNotFound) {
if (tmp) { // replace
// should be the same key
tmpKey = [orderedKeys objectAtIndex:index];
if (![tmpKey isEqual:aKey]) {
// we have a problem
[orderedKeys replaceObjectAtIndex:index withObject:aKey];
}
} else {
// we assume that the index points to the key *after* the point at which the new key should be inserted
if (index < [orderedKeys count])
[orderedKeys insertObject:aKey atIndex:index];
else
[orderedKeys addObject:aKey];
[self invalidateCursors];
}
} else {
[orderedKeys addObject:aValue];
[self rebuildOrderedKeys];
[self invalidateCursors];
}
return tmp?NO:YES;
}
- (void) removeValueAtIndex:(unsigned int)index withKey:(NSData *)key
{
NSData *tmpKey = [orderedKeys objectAtIndex:index];
NSData *tmpData = [contentDictionary objectForKey:key];
if (!tmpData) ; // should raise exception here
else if (![key isEqual:tmpKey]) {
; // we have another big problem
} else {
[contentDictionary removeObjectForKey:key];
[orderedKeys removeObjectAtIndex:index];
[self setDirty:YES];
[self invalidateCursors];
// anytime an object is removed or added to the array,
// the indices become invalid
}
}
- (NSData *) valueAtIndex:(unsigned int)index
{
return [contentDictionary objectForKey:[self keyAtIndex:index]];
}
- (NSData *) keyAtIndex:(unsigned int) index
{
// check range
if ((index < 0) || (index >= [orderedKeys count])) {
return nil; // maybe raise an exception?
}
return [orderedKeys objectAtIndex:index];
}
- (BOOL) indexBeyondLastKey:(unsigned int) index
{
return (index >= [orderedKeys count]);
}
- (int)lastIndex
{
return ([orderedKeys count] - 1);
}
- (BOOL) isEmpty
{
return ([orderedKeys count] == 0);
}
- (void) dealloc
{
[self unregisterForTransactions];
[contentDictionary release];
[orderedKeys release];
[[NSNotificationCenter defaultCenter] removeObserver:nil name:SDBTreeIndexDidBecomeInvalid object:self];
[super dealloc];
}
- (void) setDirty:(BOOL) flag
{
dirty = flag;
}
- (BOOL) isDirty
{
return dirty;
}
- (int) blockNumber
{
return blockNumber;
}
@end
|
|