This is MiscSparseArray.m in view mode; [Download] [Up]
/* MiscSparseArray.m
Copyright 1995 Christopher J. Kane.
This notice may not be removed from this source code.
The use and distribution of this software is governed by the
terms of the MiscKit license agreement. Refer to the license
document included with the MiscKit distribution for the terms.
Version 1 (1 February 1995)
*/
#import <MiscSparseArray.h>
#import <MiscUtilities.h>
#import <Foundation/Foundation.h>
/**************** Enumerators ****************/
@interface _MiscSparseArrayUpEnumerator : NSEnumerator
{
MiscSparseArray *_sparseArray;
unsigned int _count;
unsigned int _currentIndex;
}
- (id)initWithSparseArray:(MiscSparseArray *)anArray;
@end
@implementation _MiscSparseArrayUpEnumerator
- (id)initWithSparseArray:(MiscSparseArray *)anArray {
NSParameterAssert(nil != anArray);
NSParameterAssert([anArray isKindOfClass:[MiscSparseArray class]]);
self = [super init];
NSAssert(nil != self, @"object super initialization failed");
_sparseArray = [anArray retain];
_count = [anArray count];
_currentIndex = 0;
return self;
}
- (id)nextObject {
id obj = nil;
if (0 == _count)
return nil;
while (_currentIndex < UINT_MAX) {
obj = [_sparseArray objectAtIndex:_currentIndex];
if (nil != obj)
break;
_currentIndex++;
}
if (UINT_MAX == _currentIndex) {
obj = [_sparseArray objectAtIndex:_currentIndex];
NSAssert(nil != obj, @"0 < _count, but no more objects in array");
NSAssert(1 == _count, @"_count too large");
}
if (nil != obj)
_count--;
return obj;
}
- (void)dealloc {
[_sparseArray autorelease];
[super dealloc];
}
@end
@interface _MiscSparseArrayDownEnumerator : NSEnumerator
{
MiscSparseArray *_sparseArray;
unsigned int _count;
unsigned int _currentIndex;
}
- (id)initWithSparseArray:(MiscSparseArray *)anArray;
@end
@implementation _MiscSparseArrayDownEnumerator
- (id)initWithSparseArray:(MiscSparseArray *)anArray {
NSParameterAssert(nil != anArray);
NSParameterAssert([anArray isKindOfClass:[MiscSparseArray class]]);
self = [super init];
NSAssert(nil != self, @"object super initialization failed");
_sparseArray = [anArray retain];
_count = [anArray count];
_currentIndex = UINT_MAX;
return self;
}
- (id)nextObject {
id obj = nil;
if (0 == _count)
return nil;
while (0 < _currentIndex) {
obj = [_sparseArray objectAtIndex:_currentIndex];
if (nil != obj)
break;
_currentIndex--;
}
if (0 == _currentIndex) {
obj = [_sparseArray objectAtIndex:_currentIndex];
NSAssert(nil != obj, @"0 < _count, but no more objects in array");
NSAssert(1 == _count, @"_count too large");
}
if (nil != obj)
_count--;
return obj;
}
- (void)dealloc {
[_sparseArray autorelease];
[super dealloc];
}
@end
/**************** Abstract implementation ****************/
@interface MiscConcreteSparseArray : MiscSparseArray
{
void *_index;
unsigned int _count;
}
@end
@implementation MiscSparseArray
+ (MiscSparseArray *)allocWithZone:(NSZone *)zone {
Class class = self;
if ([MiscSparseArray class] == class)
class = [MiscConcreteSparseArray class];
return (MiscSparseArray *)NSAllocateObject(class, 0, zone);
}
- (id)init {
MiscRequiresConcreteObject(self, _cmd);
return self;
}
- (unsigned int)count {
MiscRequiresConcreteImplementation(self, _cmd, [MiscSparseArray class]);
return 0;
}
- (id)objectAtIndex:(unsigned int)anIndex {
MiscRequiresConcreteImplementation(self, _cmd, [MiscSparseArray class]);
return nil;
}
- (void)putObject:(id)anObject atIndex:(unsigned int)anIndex {
MiscRequiresConcreteImplementation(self, _cmd, [MiscSparseArray class]);
}
- (BOOL)isEqual:(id)anObject {
NSParameterAssert(nil != anObject);
return (anObject == self) || [self isEqualToSparseArray:anObject];
}
- (id)copyWithZone:(NSZone *)zone {
unsigned int index = 0, count = [self count];
MiscSparseArray *newArray = [[isa allocWithZone:zone] init];
NSAssert(nil != newArray, @"could not create new array");
if (0 == count)
return newArray;
do {
id elem = [self objectAtIndex:index];
if (nil != elem) {
id newElem = [elem copyWithZone:zone];
NSAssert(nil != newElem, @"could not copy object");
[newArray putObject:newElem atIndex:index];
count--;
}
index++;
} while (0 < count && 0 != index);
NSAssert(0 != index, @"0 < count, but no more objects in array");
return newArray;
}
- (Class)classForCoder {
return [MiscSparseArray class];
}
- (void)encodeWithCoder:(NSCoder *)encoder {
unsigned int index = 0, count = [self count];
[encoder encodeValueOfObjCType:@encode(int) at:&count];
if (0 == count)
return;
do {
id obj = [self objectAtIndex:index];
if (nil != obj) {
[encoder encodeValueOfObjCType:@encode(int) at:&index];
[encoder encodeValueOfObjCType:@encode(id) at:&obj];
count--;
}
index++;
} while (0 < count && 0 != index);
NSAssert(0 != index, @"0 < count, but no more objects in array");
}
- (id)initWithCoder:(NSCoder *)decoder {
unsigned int index = 0, count;
[self init];
[decoder decodeValueOfObjCType:@encode(int) at:&count];
while (count--) {
id obj;
[decoder decodeValueOfObjCType:@encode(int) at:&index];
[decoder decodeValueOfObjCType:@encode(id) at:&obj];
[self putObject:obj atIndex:index];
[obj release];
}
return self;
}
@end
@interface NSString (MiscSparseArrayExtensionToQuietCompiler)
- (NSString *)quotedStringRepresentation;
@end
@implementation MiscSparseArray (MiscSparseArrayExtensions)
+ (MiscSparseArray *)sparseArray {
return [[[self alloc] init] autorelease];
}
- (BOOL)containsObject:(id)anObject {
return [self indexOfObject:anObject] != NSNotFound;
}
- (unsigned int)indexOfObject:(id)anObject {
unsigned int index = 0, count = [self count];
if (nil == anObject || 0 == count)
return NSNotFound;
do {
id elem = [self objectAtIndex:index];
if (elem == anObject || (nil != elem && [elem isEqual:anObject]))
return index;
if (nil != elem)
count--;
index++;
} while (0 < count && 0 != index);
NSAssert(0 != index, @"0 < count, but no more objects in array");
return NSNotFound;
}
- (unsigned int)indexOfObjectIdenticalTo:(id)anObject {
unsigned int index = 0, count = [self count];
if (nil == anObject || 0 == count)
return NSNotFound;
do {
id elem = [self objectAtIndex:index];
if (elem == anObject)
return index;
if (nil != elem)
count--;
index++;
} while (0 < count && 0 != index);
NSAssert(0 != index, @"0 < count, but no more objects in array");
return NSNotFound;
}
- (void)removeObjectAtIndex:(unsigned int)anIndex {
[self putObject:nil atIndex:anIndex];
}
- (void)removeObject:(id)anObject {
unsigned int index = 0, count = [self count];
if (nil == anObject || 0 == count)
return;
do {
id elem = [self objectAtIndex:index];
if (elem == anObject || (nil != elem && [elem isEqual:anObject])) {
[self removeObjectAtIndex:index];
count--;
}
index++;
} while (0 < count && 0 != index);
NSAssert(0 != index, @"0 < count, but no more objects in array");
}
- (void)removeObjectIdenticalTo:(id)anObject {
unsigned int index = 0, count = [self count];
if (nil == anObject || 0 == count)
return;
do {
id elem = [self objectAtIndex:index];
if (elem == anObject) {
[self removeObjectAtIndex:index];
count--;
}
index++;
} while (0 < count && 0 != index);
NSAssert(0 != index, @"0 < count, but no more objects in array");
}
- (void)removeAllObjects {
unsigned int index = 0, count = [self count];
if (0 == count)
return;
do {
id elem = [self objectAtIndex:index];
if (nil != elem) {
[self removeObjectAtIndex:index];
count--;
}
index++;
} while (0 < count && 0 != index);
NSAssert(0 != index, @"0 < count, but no more objects in array");
}
- (void)makeObjectsPerform:(SEL)aSelector {
unsigned int index = 0, count = [self count];
NSParameterAssert(aSelector != 0);
if (0 == count)
return;
do {
id elem = [self objectAtIndex:index];
if (nil != elem) {
[elem performSelector:aSelector];
count--;
}
index++;
} while (0 < count && 0 != index);
NSAssert(0 != index, @"0 < count, but no more objects in array");
}
- (void)makeObjectsPerform:(SEL)aSelector withObject:(id)anObject {
unsigned int index = 0, count = [self count];
NSParameterAssert(aSelector != 0);
if (0 == count)
return;
do {
id elem = [self objectAtIndex:index];
if (nil != elem) {
[elem performSelector:aSelector withObject:anObject];
count--;
}
index++;
} while (0 < count && 0 != index);
NSAssert(0 != index, @"0 < count, but no more objects in array");
}
- (NSEnumerator *)objectEnumerator {
return [[[_MiscSparseArrayUpEnumerator allocWithZone:[self zone]] initWithSparseArray:self] autorelease];
}
- (NSEnumerator *)reverseObjectEnumerator {
return [[[_MiscSparseArrayDownEnumerator allocWithZone:[self zone]] initWithSparseArray:self] autorelease];
}
- (BOOL)isEqualToSparseArray:(MiscSparseArray *)otherArray {
unsigned int index = 0, count = [self count];
if (![otherArray isKindOfClass:[MiscSparseArray class]] || [otherArray count] != count)
return NO;
if (0 == count)
return YES;
do {
id elem1 = [self objectAtIndex:index];
id elem2 = [otherArray objectAtIndex:index];
if ((nil == elem1 && nil != elem2) || (nil != elem1 && nil == elem2))
return NO;
if (nil != elem1) {
if (elem1 != elem2 && ![elem1 isEqual:elem2])
return NO;
count--;
}
index++;
} while (0 < count && 0 != index);
NSAssert(0 != index, @"0 < count, but no more objects in array");
return YES;
}
- (NSString *)description {
return [self descriptionWithLocale:nil];
}
- (NSString *)descriptionWithLocale:(NSDictionary *)aLocale {
unsigned int index = 0, count = [self count];
NSMutableString *result;
if (0 == count)
return [[[NSMutableString alloc] initWithString:@"()"] autorelease];
result = [[[NSMutableString alloc] init] autorelease];
[result appendString:@"(\n"];
do {
id obj = [self objectAtIndex:index];
if (nil != obj) {
count--;
[result appendFormat:@"%u : ", index];
if ([obj isKindOfClass:[NSString class]])
[result appendString:[obj quotedStringRepresentation]];
else if ([obj respondsToSelector:@selector(descriptionWithLocale:)])
[result appendString:[obj descriptionWithLocale:aLocale]];
else
[result appendString:[obj description]];
if (0 < count)
[result appendString:@",\n"];
}
index++;
} while (0 < count && 0 != index);
NSAssert(0 != index, @"0 < count, but no more objects in array");
[result appendString:@"\n)"];
return result;
}
@end
/**************** Concrete implementation ****************/
#if defined(NeXT) || defined(WIN32)
#define INDEX0BITS 11
#define INDEX1BITS 11
#define BUCKETBITS 10
#define BUCKETSPERPAGE 2
#else
#error BIT sizes not defined for operating system
#endif
typedef id bucket_t[1 << BUCKETBITS];
typedef bucket_t *index1_t[1 << INDEX1BITS];
typedef index1_t *index0_t[1 << INDEX0BITS];
#define IDX_IDX0(INDEX) (((INDEX) >> (BUCKETBITS + INDEX1BITS)) & ((1 << INDEX0BITS) - 1))
#define IDX_IDX1(INDEX) (((INDEX) >> BUCKETBITS) & ((1 << INDEX1BITS) - 1))
#define IDX_BUCKET(INDEX) ((INDEX) & ((1 << BUCKETBITS) - 1))
@implementation MiscConcreteSparseArray
- (id)init {
_index = NULL;
_count = 0;
return self;
}
- (void)dealloc {
int i, j, k;
if (_index != NULL) {
for (i = 0; i < (1 << INDEX0BITS); i++) {
index1_t *index1p = (*(index0_t *)_index)[i];
if (index1p == NULL)
continue;
for (j = 0; j < (1 << INDEX1BITS); j++) {
bucket_t *bktp = (*index1p)[j];
if (bktp == NULL)
continue;
for (k = 0; k < (1 << BUCKETBITS); k++)
if ((*bktp)[k] != nil)
[(*bktp)[k] autorelease];
}
for (j = 0; j < (1 << INDEX1BITS); j += BUCKETSPERPAGE)
NSDeallocateMemoryPages(index1p[j], NSPageSize());
NSDeallocateMemoryPages(index1p, sizeof(index1_t));
}
NSDeallocateMemoryPages(_index, sizeof(index0_t));
}
[super dealloc];
}
- (unsigned int)count {
return _count;
}
- (id)objectAtIndex:(unsigned int)anIndex {
index1_t *index1p;
bucket_t *bktp;
id object;
if (_count == 0 || _index == NULL)
return nil;
index1p = (*(index0_t *)_index)[IDX_IDX0(anIndex)];
if (index1p == NULL)
return nil;
bktp = (*index1p)[IDX_IDX1(anIndex)];
if (bktp == NULL)
return nil;
object = (*bktp)[IDX_BUCKET(anIndex)];
return [[object retain] autorelease];
}
- (void)putObject:(id)anObject atIndex:(unsigned int)anIndex {
unsigned int idx0 = IDX_IDX0(anIndex);
unsigned int idx1 = IDX_IDX1(anIndex);
unsigned int idxb = IDX_BUCKET(anIndex);
index1_t *index1p;
bucket_t *bktp;
if (_index == NULL) {
if (anObject == nil)
return;
_index = NSAllocateMemoryPages(sizeof(index0_t));
}
index1p = (*(index0_t *)_index)[idx0];
if (index1p == NULL) {
if (anObject == nil)
return;
index1p = (*(index0_t *)_index)[idx0] = NSAllocateMemoryPages(sizeof(index1_t));
}
bktp = (*index1p)[idx1];
if (bktp == NULL) {
unsigned int i, low;
bucket_t *new_bucket;
if (anObject == nil)
return;
new_bucket = NSAllocateMemoryPages(NSPageSize());
low = idx1 - idx1 & (BUCKETSPERPAGE - 1);
for (i = 0; i < BUCKETSPERPAGE; i++)
(*index1p)[low + i] = new_bucket + i * sizeof(bucket_t);
bktp = (*index1p)[idx1];
}
if ((*bktp)[idxb] != nil) {
[(*bktp)[idxb] autorelease];
(*bktp)[idxb] = nil;
_count--;
}
if (anObject != nil) {
(*bktp)[idxb] = [anObject retain];
_count++;
}
}
@end
These are the contents of the former NiCE NeXT User Group NeXTSTEP/OpenStep software archive, currently hosted by Netfuture.ch.