 |
*************************** SDBTreeCursor.h ********************************
@interface SDBTreeCursor:NSObject
{
SDBTree *btree; //implemented as an NSDictionary and NSArray
unsigned int index; //current position in array
NSData *currentKey;
BOOL currentKeyFoundInBTree;
BOOL validIndex;
BOOL isRegistered;
}
- (id)initWithBTree: (SDBTree *)aBTree ;
- (void) setKeyForIndex:(unsigned int) newIndex;
- (BOOL) writeValue: (void *)aValue andLength: (unsigned int)length;
- (void) writeData:(NSData *)data;
- (void) writeRange:(const void *)aRange ofLength:(unsigned int)aLength atOffset:(unsigned int)anOffset;
- (void) removeValue;
- (NSData *)readData;
- (unsigned int) readValue: (void **)buffer;
- (BOOL) setLast;
- (BOOL) setFirst;
- (BOOL) setNext;
- (BOOL) setPrevious;
- (BOOL) setKey: (NSData *)aKey;
- (void) resetKey;
- (BOOL) setKey:(const void *)aKey andLength:(unsigned int) length;
- (BOOL)setKey:(const void *)aKey andLength:(unsigned int)aLength withHint:(unsigned int)aHint;
- (BOOL) setKey:(NSData *)newKey withHint:(HINT_TYPE)aHint;
- (NSData *) getKey;
- (BOOL) getKeyData:(NSData **)aKey withHint:(HINT_TYPE *)aHint;
- (BOOL) getKey:(const void **)aKey andLength:(unsigned int *) length;
- (BOOL)getKey:(const void **)aKey andLength:(unsigned int *)aLength withHint:(HINT_TYPE *)aHint;
- (BOOL) isMatch;
- (unsigned long) currentPosition;
- (void)invalidateIndex:(NSNotification *)aNotification;
- (SDBTree *)btree;
@end
*************************** SDBTreeCursor.m ********************************
#import "ixCover.h"
@implementation SDBTreeCursor:NSObject
- (void) registerCursor
{
[[NSNotificationCenter defaultCenter] addObserver:self selector:@selector(invalidateIndex:) name: SDBTreeIndexDidBecomeInvalid object:btree];
isRegistered = YES;
}
- (void) unregisterCursor
{
isRegistered = NO;
[[NSNotificationCenter defaultCenter]removeObserver:self name:SDBTreeIndexDidBecomeInvalid object:btree];
}
// bug with NSData; data passed to it must be freeable (see Release Notes bug #58127)
- (NSData *) makeData:(const void *)aValue length:(int)length
{
void *freeableData;
freeableData = NSZoneMalloc([self zone],length);
bcopy(aValue,freeableData,length);
return [NSData dataWithBytes:freeableData length:length];
}
- (id) initWithBTree: (SDBTree *)aBTree
{
btree = aBTree;
[self registerCursor]; // so btree can invalidate index
index = NSNotFound; // uninitialized;
validIndex = NO;
return self;
}
- (void) setKeyForNewKey:(NSData *)newKey andIndex:(unsigned int) newIndex
{
NSData *oldKey = currentKey;
currentKey = [newKey retain];
[oldKey release];
index = newIndex;
validIndex = YES;
currentKeyFoundInBTree = YES;
}
- (void) setKeyForIndex:(unsigned int) newIndex
{
NSData *newKey = [btree keyAtIndex:newIndex];
[self setKeyForNewKey:newKey andIndex:newIndex];
}
///////////////////////////////////////////////////////////////////////////
//
// writeValue:andLength:
//
// Writes aLength bytes from aValue as the value in the IXBTree
// at the IXBTreeCursor's position, possibly overwriting a
// previously stored value. Returns YES if the write resulted
// in an insertion, and NO if the write overwrote a previously
// stored value.
//
///////////////////////////////////////////////////////////////////////////
- (BOOL) writeValue: (void *)aValue andLength: (unsigned int)length
{
// key is currentKey
// make NSData out of aValue
NSData *value;
if (length == 0) {
// empty value
value = [NSData data];
} else {
value = [self makeData:aValue length:length];
}
return [btree insertValue:value andKey:currentKey atIndex:index];
}
- (void) writeData:(NSData *)data
{
[btree insertValue:data andKey:currentKey atIndex:index];
}
///////////////////////////////////////////////////////////////////////////
//
// writeRange
//
// Writes aRange over a portion of the value in the IXBTree at the IXBTreeCursor's
// position. Data starting at anOffset within the IXBTree's value
// is overwritten for aLength bytes. If the range would extend past
// the end of the value, the value is enlarged to hold the new amount.
//
// If there is no key/value pair at the IXBTreeCursor's position,
// this method raises IX_NotFoundError.
//
///////////////////////////////////////////////////////////////////////////
- (void) writeRange:(const void *)aRange ofLength:(unsigned int)aLength atOffset:(unsigned int)anOffset
{
NSData *theData;
NSMutableData *changeData;
if (!currentKeyFoundInBTree) {
return;
// raise an exception or something
}
// retrieve the data
theData = [btree valueAtIndex:index];
changeData = [[theData mutableCopyWithZone:[self zone]]autorelease];
[changeData replaceBytesInRange:(NSMakeRange(anOffset,aLength))withBytes:aRange];
[btree insertValue:changeData andKey:currentKey atIndex:index];
}
///////////////////////////////////////////////////////////////////////////
//
// removeValue
//
// Removes the key and the associated value at the IXBTreeCursor's
// position. This method raises IX_NotFoundError if there is no key
// at the IXBTreeCursor's position. Returns self.
//
///////////////////////////////////////////////////////////////////////////
- (void) removeValue
{
if (!validIndex) [self resetKey];
if (!currentKeyFoundInBTree) {
// raise exception
return;
}
[btree removeValueAtIndex:index withKey:currentKey];
}
- (NSData *)readData
{
if (!validIndex) [self resetKey];
if (!currentKeyFoundInBTree) {
if (![btree indexBeyondLastKey:index]) {
// we need to update the key to reflect the current position
[self setKeyForIndex:index];
} else {
// we need to raise an exception
return nil;
}
}
return [btree valueAtIndex:index];
}
///////////////////////////////////////////////////////////////////////////
//
// readValue:
//
// Copies the value in the IXBTree at the IXBTreeCursor's position,
// and returns the length of the value. If there is no key/value pair
// at the IXBTreeCursor's position, the IXBTreeCursor moves to the
// next higher position if possible. If the IXBTreeCursor is at
// the end of the key space, IX_NotFoundError is raised.
//
// If *aValue is NULL, then a buffer will be allocated from the
// IXBTreeCursor's zone, and the data will be copied into that buffer.
// Your code is responsible for freeing the memory allocated.
// If a non-NULL value is provided in *aValue,
// then it is assumed to be the address of a valid buffer,
// and the value stored in the IXBTree will be copied into it.
// Your code is responsible for making sure the buffer is
// large enough to hold the value. This is useful for
// fixed-length values, or values with a known maximum length.
//
// Important: Using the address of an uninitialized pointer variable
// as aValue is incorrect, and will result in data being copied
// into a random location in the application's address space.
// Your code should always allocate memory for the pointer variable
// or set it to NULL before passing its address to this method.
//
// This method may be used to determine the size of the buffer needed:
// invoke it first with NULL as aValue to get the buffer length without
// copying the data, then a second time with the length to copy the
// data.
///////////////////////////////////////////////////////////////////////////
- (unsigned int) readValue: (void **)buffer
// if buffer is nil, return length
// if *buffer is nil, allocate space here
{
NSData *tmpData;
void *tmpbuffer;
unsigned int length;
tmpData = [self readData];
length = [tmpData length];
if (buffer == NULL) return length;
if (*buffer == NULL) {
tmpbuffer = NSZoneMalloc([self zone],length);
if (!tmpbuffer) ; // raise an exception or something
[tmpData getBytes:tmpbuffer];
*buffer = tmpbuffer;
return length;
}
[tmpData getBytes:*buffer];
return length;
}
///////////////////////////////////////////////////////////////////////////
//
// setLast
//
// If there is at least one value associated with a key,
// this method positions the cursor at the last element's
// key and returns YES. Otherwise it returns NO, and any
// attempt to remove or read a value at the cursor's position
// will raise IX_ArgumentError.
//
///////////////////////////////////////////////////////////////////////////
- (BOOL) setLast
{
if ([btree isEmpty]) return NO;
[self setKeyForIndex:[btree lastIndex]];
return YES;
}
///////////////////////////////////////////////////////////////////////////
//
// setFirst
//
// If there is at least one value associated with a key,
// this method positions the cursor at the first element's
// key and returns YES. Otherwise it returns NO, and
// any attempt to remove or read a value at the cursor's
// position will raise IX_ArgumentError.
//
///////////////////////////////////////////////////////////////////////////
- (BOOL) setFirst
{
if ([btree isEmpty]) return NO;
[self setKeyForIndex:0];
return YES;
}
///////////////////////////////////////////////////////////////////////////
//
// setNext
//
// Sets the cursor's position to the next key with an
// associated value. Returns YES if there is a next element,
// and NO if the cursor is already positioned at the end of
// the key space. If this method returns NO, then
// any attempt to remove or read a value at the cursor's
// position will raise IX_ArgumentError.
//
///////////////////////////////////////////////////////////////////////////
- (BOOL) setNext
{
if ([btree isEmpty]) return NO;
if (index > [btree lastIndex]) return NO;
index = index + 1;
if (index > [btree lastIndex]) return NO;
[self setKeyForIndex:index];
return YES;
}
///////////////////////////////////////////////////////////////////////////
//
// setPrevious
//
// Sets the cursor's position to the previous key with an
// associated value. Returns YES if there is a previous
// element, and NO if the cursor was positioned at the beginning
// of the key space and has moved to a position before the first key.
// If this method returns NO, then any attempt to read a value
// will cause the cursor to move to the next key with a value,
// or raise IX_ArgumentError if the cursor can't move
// (because it's at the end of the key space).
//
///////////////////////////////////////////////////////////////////////////
- (BOOL) setPrevious
{
if ([btree isEmpty]) return NO;
if (index == 0) return NO;
index = index - 1;
[self setKeyForIndex:index];
return YES;
}
- (BOOL) setToPositionNumber:(unsigned long) position
{
if ([btree isEmpty]) return NO;
if (position > [btree lastIndex]) return NO;
index = position;
[self setKeyForIndex:index];
return YES;
}
- (BOOL) setKey: (NSData *)aKey
{
BOOL exactMatch;
NSData *tmp;
tmp = currentKey;
currentKey = [aKey retain];
[tmp release];
index = [btree indexForKey:aKey exactMatch:&exactMatch];
currentKeyFoundInBTree = exactMatch;
validIndex = YES;
return currentKeyFoundInBTree;
}
// uses currentKey
- (void) resetKey
{
BOOL exactMatch;
index = [btree indexForKey:currentKey exactMatch:&exactMatch];
currentKeyFoundInBTree = exactMatch;
validIndex = YES;
}
///////////////////////////////////////////////////////////////////////////
//
// setKey:andLength:
//
// Sets the current position of the cursor to that specified
// by aKey and aLength.
//
// If a value is associated with aKey, returns YES. Otherwise
// returns NO. If there is no value with a key before aKey,
// this method positions the cursor before the first value.
// If there is no value with a key after aKey,
// his method positions the cursor beyond the last values.
// If this method returns NO, then any attempt to write into
// or remove a value at the cursor's position will raise
// IX_ArgumentError, and any attempt to read a key or value
// will cause the cursor to move to the key for the next value
// before reading the key or value, or raise IX_ArgumentError
// if the cursor can't move (because it's at the end
// of the key space).
//
///////////////////////////////////////////////////////////////////////////
- (BOOL) setKey:(const void *)aKey andLength:(unsigned int) length
{
// make an NSData
NSData *tmpKey = [self makeData:aKey length:length];
return [self setKey:tmpKey];
}
///////////////////////////////////////////////////////////////////////////
//
// setKey:andLength:withHint:
//
// Sets the current position of the cursor to that specified
// by aKey and aLength.
//
// If a value is associated with aKey, returns YES. Otherwise
// returns NO. If there is no value with a key before aKey,
// this method positions the cursor before the first value.
// If there is no value with a key after aKey,
// his method positions the cursor beyond the last values.
// If this method returns NO, then any attempt to write into
// or remove a value at the cursor's position will raise
// IX_ArgumentError, and any attempt to read a key or value
// will cause the cursor to move to the key for the next value
// before reading the key or value, or raise IX_ArgumentError
// if the cursor can't move (because it's at the end
// of the key space).
//
// This method uses a hint as returned by getKey:andLength:withHint:
// to find aKey quickly. A hint is like a bookmark; it defines a
// physical position in the IXBTree, so the IXBTreeCursor can just
// go there and check if aKey is still there.
//
///////////////////////////////////////////////////////////////////////////
- (BOOL) setKey:(NSData *)newKey withHint:(HINT_TYPE)aHint
{
NSData *tmpKey = [btree keyAtIndex:aHint];
if ([tmpKey isEqualToData:newKey]) {
[self setKeyForNewKey:newKey andIndex:aHint];
return YES;
} else {
return [self setKey:newKey];
}
}
- (BOOL)setKey:(const void *)aKey andLength:(unsigned int)aLength withHint:(unsigned int)aHint
{
NSData *newKey = [self makeData:aKey length:aLength];
return [self setKey:newKey withHint:aHint];
}
///////////////////////////////////////////////////////////////////////////
//
// getKey:andLength:
//
// // kaj 7/4/97 use NSData instead of void **
//
// Returns by reference the key defining the cursor's position
// in its key space, along with the key's length.
//
// If the cursor is at a key which has a value associated with it,
// this method returns YES. If the cursor is between two values
// or before the first one, this method advances the cursor to
// the key for the next value, returns that key by reference,
// and returns YES. If the cursor is beyond the last key,
// this method returns NO, and the contents of aKey and aLength
// aren't set.
//
///////////////////////////////////////////////////////////////////////////
- (NSData *) getKey
{
BOOL beyondLastKey = [btree indexBeyondLastKey:index];
NSData *tmpKey;
if (beyondLastKey) return nil;
tmpKey = [btree keyAtIndex:index];
// move cursor to key for next value and make that key our current key
if (![tmpKey isEqual:currentKey]) [self setKey:tmpKey];
return currentKey;
}
- (BOOL) getKeyData:(NSData **)aKey withHint:(HINT_TYPE *)aHint
{
*aKey = [self getKey];
if (!*aKey) return NO;
*aHint = index;
return YES;
}
- (BOOL) getKey:(const void **)aKey andLength:(unsigned int *) length
{
NSData *theKey = [self getKey]; // this is also the currentKey
if (!theKey) return NO;
*aKey = (void *)[theKey bytes];
*length = [theKey length];
return YES;
}
///////////////////////////////////////////////////////////////////////////
//
// getKey:andLength:withHint:
//
// kaj 7/4/97 replaced with getKey: (NSData **)aKey withHint:
//
// Returns by reference the key defining the cursor's position
// in its key space, along with the key's length and a hint that
// your code can use to speed up a subsequent key search for
// the same key using setKey:andLength:withHint:.
// The hint is guaranteed to remain useful as long as no insertions
// or removals are performed; however, the more the IXBTree changes,
// the less useful the hint becomes.
//
// If the cursor is at a key which has a value associated with it,
// this method returns YES. If the cursor is between two values
// or before the first one, this method advances the cursor to
// the key for the next value, returns that key by reference,
// and returns YES. If the cursor is beyond the last key,
// this method returns NO, and the contents of aKey, aLength, and aHint
// aren't set.
//
///////////////////////////////////////////////////////////////////////////
- (BOOL)getKey:(const void **)aKey andLength:(unsigned int *)aLength withHint:(HINT_TYPE *)aHint
{
BOOL result = [self getKey:aKey andLength:aLength];
*aHint = index;
return result;
}
///////////////////////////////////////////////////////////////////////////
//
// isMatch
//
// Returns YES if the cursor is on a key with an associated value,
// NO if the cursor is between two values or past
// either end of the set of values.
//
// If the cursor isn't on a key with a value, then trying
// to get a key or read a value can cause the cursor to move
// forward to the next key with a value before reading the key
// or value, or raise IX_ArgumentError if the cursor can't
// move (because it's at the end of the key space).
// Any attempt to write into or remove a nonexistent value will raise
// IX_ArgumentError.
//
///////////////////////////////////////////////////////////////////////////
- (BOOL) isMatch
{
return currentKeyFoundInBTree;
}
- (unsigned long) currentPosition
{
return index;
}
- (SDBTree *)btree
{
return btree;
}
- (void)invalidateIndex:(NSNotification *)aNotification
{
if ([aNotification object] == btree)
validIndex = NO;
}
- (void) dealloc
{
[self unregisterCursor];
[currentKey release];
[super dealloc];
}
@end
|
|