1// 2// KTMutableMatrixSparseImp 3// KTMatrix collection class cluster 4// 5// KTMatrix class cluster mutable implementation subclass 6// Uses hash tables to reference on-the-fly allocated memory 7// Ideal for sparsely-populated matrices 8// Sacrifices some speed for a considerable potential memory saving 9// Sacrifices some of those memory savings for mutability 10// Same object retrieval time as any hash table-based storage 11// 12// Copyright (c) 2002 Chris Purcell. All rights reserved. 13// 14// You may use this code for whatever purposes you wish. 15// This code comes with no warranties, implied or otherwise. 16// Using it may damage your data. It shouldn't, but save a copy first. 17// That's a good idea anyway, actually. 18// 19 20#import "KTMutableMatrixSparseImp.h" 21#import "KTMatrixSparseEnumerator.h" 22 23static unsigned KTCallback_hash(NSHashTable *table, 24 const void *elem) 25{ return ((const struct KTMatrixSparseElement *)elem)->hashedLocation; } 26static BOOL KTCallback_isEqual(NSHashTable *table, const void *_1, 27 const void *_2) 28{ 29 return (((const struct KTMatrixSparseElement *)_1)->hashedLocation == 30 ((const struct KTMatrixSparseElement *)_2)->hashedLocation); 31} 32static void KTCallback_retain(NSHashTable *table, const void *elem) 33{ [(((const struct KTMatrixSparseElement *)elem)->object) retain]; } 34static void KTCallback_release(NSHashTable *table, void *elem) 35{ 36 [(((const struct KTMatrixSparseElement *)elem)->object) release]; 37 free(elem); 38} 39static NSString *KTCallback_describe(NSHashTable *table, const void *elem) 40{ return [(((const struct KTMatrixSparseElement *)elem)->object) description];} 41 42 43 44@implementation KTMutableMatrixSparseImp 45 46+ (id)matrixWithMatrix:(KTMatrix *)other 47{ 48 return [[[self alloc] initWithMatrix:other] autorelease]; 49} 50+ (id)matrixWithLocationHash:(id<KTLocationHash>)locationHash 51 objects:(NSArray *)objects 52 atLocations:(NSArray *)loc1s 53 byLocations:(NSArray *)loc2s 54{ 55 return [[[self alloc] initWithLocationHash:locationHash 56 objects:objects 57 atLocations:loc1s 58 byLocations:loc2s] autorelease]; 59} 60+ (id)matrixWithCapacity:(unsigned)numItems 61 locationHash:(id<KTLocationHash>)_hs 62{ 63 return [[[self alloc] initWithCapacity:numItems 64 locationHash:_hs] autorelease]; 65} 66- (id)initWithMatrix:(KTMatrix *)other 67{ 68 NSEnumerator<KTMatrixEnumerator> *j = [other objectEnumeratorRetained]; 69 if ([j conformsToProtocol:@protocol(KTMatrixEnumerator)]) 70 { 71 if ((self = [super init])) 72 { 73 struct KTMatrixSparseElement *element; 74 NSHashTableCallBacks callback; 75 id object; 76 77 callback.hash = KTCallback_hash; 78 callback.isEqual = KTCallback_isEqual; 79 callback.retain = KTCallback_retain; 80 callback.release = KTCallback_release; 81 callback.describe = KTCallback_describe; 82 83 // Deal with the hashing object 84 if (NSShouldRetainWithZone([other locationHash], [self zone])) 85 hash = [[other locationHash] retain]; 86 else 87 hash = [[other locationHash] copyWithZone:[self zone]]; 88 hashIsCoordinateOptimized = [hash conformsToProtocol: 89 @protocol(KTLocationHashCoordinatesOptimization)]; 90 91 // Allocate memory for the hashing table and cache 92 matrix = NSCreateHashTableWithZone(callback, 93 [other count], 94 [self zone]); 95 cache = NSZoneMalloc([self zone], 96 sizeof(struct KTMatrixSparseElement)); 97 98 // Fill the hashing table 99 while ((object = [j nextObject])) 100 { 101 element = NSZoneMalloc([self zone], 102 sizeof(struct KTMatrixSparseElement)); 103 element->hashedLocation = [j hashedLocation]; 104 element->object = object; 105 NSHashInsert(matrix, element); 106 } 107 } 108 } 109 else 110 { 111 self = [self initWithMatrixData:[other matrixData] 112 locationHash:[other locationHash]]; 113 } 114 [j release]; 115 return self; 116} 117- (id)initWithMatrixData:(NSDictionary *)matrixData 118 locationHash:(id<KTLocationHash>)locationHash 119{ // Same method: setMatrix 120 if ((self = [super init])) 121 { 122 struct KTMatrixSparseElement *element; 123 NSHashTableCallBacks callback; 124 NSNumber *key; 125 NSEnumerator *j = [matrixData keyEnumerator]; 126 127 callback.hash = KTCallback_hash; 128 callback.isEqual = KTCallback_isEqual; 129 callback.retain = KTCallback_retain; 130 callback.release = KTCallback_release; 131 callback.describe = KTCallback_describe; 132 133 // Deal with the hashing object 134 if (NSShouldRetainWithZone(locationHash, [self zone])) 135 hash = [locationHash retain]; 136 else 137 hash = [locationHash copyWithZone:[self zone]]; 138 hashIsCoordinateOptimized = [hash conformsToProtocol: 139 @protocol(KTLocationHashCoordinatesOptimization)]; 140 141 // Allocate memory for the hashing table and cache 142 matrix = NSCreateHashTableWithZone(callback, 143 [matrixData count], 144 [self zone]); 145 cache = NSZoneMalloc([self zone], 146 sizeof(struct KTMatrixSparseElement)); 147 148 // Fill the hashing table 149 while ((key = [j nextObject])) 150 { 151 element = NSZoneMalloc([self zone], 152 sizeof(struct KTMatrixSparseElement)); 153 element->hashedLocation = [key intValue]; 154 element->object = [matrixData objectForKey:key]; 155 NSHashInsert(matrix, element); 156 } 157 } 158 return self; 159} 160- (id)initWithLocationHash:(id<KTLocationHash>)locationHash 161{ 162 if ((self = [super init])) 163 { 164 NSHashTableCallBacks callback; 165 166 callback.hash = KTCallback_hash; 167 callback.isEqual = KTCallback_isEqual; 168 callback.retain = KTCallback_retain; 169 callback.release = KTCallback_release; 170 callback.describe = KTCallback_describe; 171 172 // Deal with the hashing object 173 if (NSShouldRetainWithZone(locationHash, [self zone])) 174 hash = [locationHash retain]; 175 else 176 hash = [locationHash copyWithZone:[self zone]]; 177 hashIsCoordinateOptimized = [hash conformsToProtocol: 178 @protocol(KTLocationHashCoordinatesOptimization)]; 179 180 // Allocate memory for the hashing table and cache 181 matrix = NSCreateHashTableWithZone(callback, 182 0, 183 [self zone]); 184 cache = NSZoneMalloc([self zone], 185 sizeof(struct KTMatrixSparseElement)); 186 } 187 return self; 188} 189- (id)initWithLocationHash:(id<KTLocationHash>)locationHash 190 objects:(NSArray *)objects 191 atLocations:(NSArray *)loc1s 192 byLocations:(NSArray *)loc2s 193{ 194 if ((self = [super init])) 195 { 196 struct KTMatrixSparseElement *element; 197 NSHashTableCallBacks callback; 198 unsigned i; 199 200 callback.hash = KTCallback_hash; 201 callback.isEqual = KTCallback_isEqual; 202 callback.retain = KTCallback_retain; 203 callback.release = KTCallback_release; 204 callback.describe = KTCallback_describe; 205 206 // Deal with the hashing object 207 if (NSShouldRetainWithZone(locationHash, [self zone])) 208 hash = [locationHash retain]; 209 else 210 hash = [locationHash copyWithZone:[self zone]]; 211 hashIsCoordinateOptimized = [hash conformsToProtocol: 212 @protocol(KTLocationHashCoordinatesOptimization)]; 213 214 // Check the parameters are sane 215 if ([objects count] != [loc1s count]) 216 [NSException raise:NSInvalidArgumentException 217 format: 218 @"Objects and locations arrays not of equal length"]; 219 if ([loc1s count] != [loc2s count]) 220 [NSException raise:NSInvalidArgumentException 221 format: 222 @"Locations arrays not of equal length"]; 223 224 // Allocate memory for the hashing table and cache 225 matrix = NSCreateHashTableWithZone(callback, 226 [objects count], 227 [self zone]); 228 cache = NSZoneMalloc([self zone], 229 sizeof(struct KTMatrixSparseElement)); 230 231 // Fill the cache and the hashing table 232 for (i = 0; i < [loc1s count]; i++) 233 { 234 element = NSZoneMalloc([self zone], 235 sizeof(struct KTMatrixSparseElement)); 236 element->hashedLocation = [hash 237 hashForLocation:[loc1s objectAtIndex:i] 238 byLocation:[loc2s objectAtIndex:i]]; 239 element->object = [objects objectAtIndex:i]; 240 NSHashInsert(matrix, element); 241 } 242 } 243 return self; 244} 245- (id)initWithCapacity:(unsigned)numItems 246 locationHash:(id<KTLocationHash>)locationHash 247{ 248 if ((self = [super init])) 249 { 250 NSHashTableCallBacks callback; 251 252 callback.hash = KTCallback_hash; 253 callback.isEqual = KTCallback_isEqual; 254 callback.retain = KTCallback_retain; 255 callback.release = KTCallback_release; 256 callback.describe = KTCallback_describe; 257 258 // Deal with the hashing object 259 if (NSShouldRetainWithZone(locationHash, [self zone])) 260 hash = [locationHash retain]; 261 else 262 hash = [locationHash copyWithZone:[self zone]]; 263 hashIsCoordinateOptimized = [hash conformsToProtocol: 264 @protocol(KTLocationHashCoordinatesOptimization)]; 265 266 // Allocate memory for the hashing table and cache 267 matrix = NSCreateHashTableWithZone(callback, 268 numItems, 269 [self zone]); 270 cache = NSZoneMalloc([self zone], 271 sizeof(struct KTMatrixSparseElement)); 272 } 273 return self; 274} 275 276//// Optimized versions 277- (id)initWithLocationHash:(id<KTLocationHash>)locationHash 278 object:(id)object 279 atHashedLocation:(unsigned)loc 280{ 281 if ((self = [super init])) 282 { 283 struct KTMatrixSparseElement *element; 284 NSHashTableCallBacks callback; 285 286 callback.hash = KTCallback_hash; 287 callback.isEqual = KTCallback_isEqual; 288 callback.retain = KTCallback_retain; 289 callback.release = KTCallback_release; 290 callback.describe = KTCallback_describe; 291 292 // Deal with the hashing object 293 if (NSShouldRetainWithZone(locationHash, [self zone])) 294 hash = [locationHash retain]; 295 else 296 hash = [locationHash copyWithZone:[self zone]]; 297 hashIsCoordinateOptimized = [hash 298 conformsToProtocol:@protocol(KTLocationHashCoordinatesOptimization)]; 299 300 // Allocate memory for the hashing table and cache 301 matrix = NSCreateHashTableWithZone(callback, 302 1, 303 [self zone]); 304 cache = NSZoneMalloc([self zone], 305 sizeof(struct KTMatrixSparseElement)); 306 307 // Fill the cache and the hashing table 308 element = NSZoneMalloc([self zone], 309 sizeof(struct KTMatrixSparseElement)); 310 element->hashedLocation = loc; 311 element->object = object; 312 NSHashInsert(matrix, element); 313 } 314 return self; 315} 316 317 318// Accessor methods 319- (id)objectAtLocation:(NSDictionary *)loc 320 byLocation:(NSDictionary *)loc2; 321{ 322 struct KTMatrixSparseElement *elem; 323 ((struct KTMatrixSparseElement *)cache)->hashedLocation = [hash 324 hashForLocation:loc byLocation:loc2]; 325 elem = (struct KTMatrixSparseElement *)NSHashGet(matrix, cache); 326 if (elem != NULL) 327 return (elem)->object; 328 else 329 return NULL; 330} 331 332//// Optimized algoritms 333- (id)objectAtCoordinates:(unsigned)x,... 334{ 335 va_list args; 336 337 va_start(args, x); 338 339 if (hashIsCoordinateOptimized) 340 { 341 struct KTMatrixSparseElement *elem; 342 ((struct KTMatrixSparseElement *)cache)->hashedLocation = 343 [(id)hash hashForCoordinatesList:x :&args]; 344 va_end(args); 345 346 elem = (struct KTMatrixSparseElement *)NSHashGet(matrix, cache); 347 if (elem != NULL) 348 return (elem)->object; 349 else 350 return NULL; 351 } 352 else 353 { 354 NSMutableArray *array 355 = [NSMutableArray arrayWithObject:[NSNumber numberWithInt:x]]; 356 unsigned axes = [self dimension]; 357 358 while ([array count] < axes) 359 [array addObject:[NSNumber numberWithInt:va_arg(args, unsigned)]]; 360 361 va_end(args); 362 363 return [self objectAtCoordinateArray:array]; 364 } 365} 366- (unsigned)dimension 367{ 368 if (hashIsCoordinateOptimized) return [(id)hash dimension]; 369 else return [[self axes] count]; 370} 371- (unsigned)lowerBoundForDimension:(unsigned)dim 372{ 373 if (hashIsCoordinateOptimized) return [(id)hash lowerBoundForDimension:dim]; 374 else return [self lowerBoundForAxis: [[self axes] objectAtIndex:dim]]; 375} 376- (unsigned)upperBoundForDimension:(unsigned)dim 377{ 378 if (hashIsCoordinateOptimized) return [(id)hash upperBoundForDimension:dim]; 379 else return [self upperBoundForAxis: [[self axes] objectAtIndex:dim]]; 380} 381 382- (id<KTLocationHash>)locationHash 383{ return hash; } 384- (NSDictionary *)matrixData 385{ 386 NSMutableDictionary *data = [NSMutableDictionary 387 dictionaryWithCapacity:[self count]]; 388 NSHashEnumerator i = NSEnumerateHashTable(matrix); 389 struct KTMatrixSparseElement *elem; 390 while ((elem = 391 (struct KTMatrixSparseElement *)NSNextHashEnumeratorItem(&i))) 392 [data setObject:elem->object 393 forKey:[NSNumber numberWithInt:elem->hashedLocation]]; 394 NSEndHashTableEnumeration(&i); 395 396 return data; 397} 398 399- (NSEnumerator *)objectEnumerator 400{ 401 return [[[KTMutableMatrixSparseEnumerator allocWithZone:[self zone]] 402 initWithHashEnumerator:NSEnumerateHashTable(matrix) 403 collection:self] autorelease]; 404} 405- (NSEnumerator *)objectEnumeratorRetained 406{ 407 return [[KTMutableMatrixSparseEnumerator allocWithZone:[self zone]] 408 initWithHashEnumerator:NSEnumerateHashTable(matrix) 409 collection:self]; 410} 411- (unsigned)count 412{ return NSCountHashTable(matrix); } 413 414 415 //// Mutator methods 416- (void)setMatrix:(KTMatrix *)other 417{ 418 struct KTMatrixSparseElement *element; 419 NSEnumerator<KTMatrixEnumerator> *j = [other objectEnumerator]; 420 NSHashTableCallBacks callback; 421 422 [hash release]; 423 NSFreeHashTable(matrix); 424 425 callback.hash = KTCallback_hash; 426 callback.isEqual = KTCallback_isEqual; 427 callback.retain = KTCallback_retain; 428 callback.release = KTCallback_release; 429 callback.describe = KTCallback_describe; 430 431 // Deal with the hashing object 432 if (NSShouldRetainWithZone([other locationHash], [self zone])) 433 hash = [[other locationHash] retain]; 434 else 435 hash = [[other locationHash] copyWithZone:[self zone]]; 436 hashIsCoordinateOptimized = 437 [hash conformsToProtocol:@protocol(KTLocationHashCoordinatesOptimization)]; 438 439 // Allocate memory for the hashing table 440 matrix = NSCreateHashTableWithZone(callback, 441 [other count], 442 [self zone]); 443 444 // Fill the hashing table 445 if ([j conformsToProtocol:@protocol(KTMatrixEnumerator)]) 446 { 447 id object; 448 while ((object = [j nextObject])) 449 { 450 element = NSZoneMalloc([self zone], 451 sizeof(struct KTMatrixSparseElement)); 452 element->hashedLocation = [j hashedLocation]; 453 element->object = object; 454 NSHashInsert(matrix, element); 455 } 456 } 457 else 458 { 459 NSDictionary *matrixData = [other matrixData]; 460 NSNumber *key; 461 NSEnumerator *k = [matrixData keyEnumerator]; 462 463 while ((key = [k nextObject])) 464 { 465 element = NSZoneMalloc([self zone], 466 sizeof(struct KTMatrixSparseElement)); 467 element->hashedLocation = [key intValue]; 468 element->object = [matrixData objectForKey:key]; 469 NSHashInsert(matrix, element); 470 } 471 } 472} 473- (void)setObject:(id)object 474 atLocation:(NSDictionary *)loc1 475 byLocation:(NSDictionary *)loc2 476{ 477 struct KTMatrixSparseElement *elem; 478 ((struct KTMatrixSparseElement *)cache)->hashedLocation = [hash 479 hashForLocation:loc1 byLocation:loc2]; 480 elem = (struct KTMatrixSparseElement *)NSHashGet(matrix, cache); 481 if (elem) 482 { // Just change object if the location is occupied 483 [elem->object release]; 484 elem->object = object; 485 } 486 else 487 { // Else allocate more memory 488 elem = NSZoneMalloc([self zone], 489 sizeof(struct KTMatrixSparseElement)); 490 elem->hashedLocation = 491 ((struct KTMatrixSparseElement *)cache)->hashedLocation; 492 elem->object = object; 493 NSHashInsertKnownAbsent(matrix, elem); 494 } 495} 496- (void) setObject:(id)object 497 atHashedLocation:(unsigned)loc 498{ 499 struct KTMatrixSparseElement *elem; 500 ((struct KTMatrixSparseElement *)cache)->hashedLocation = loc; 501 502 elem = (struct KTMatrixSparseElement *)NSHashGet(matrix, cache); 503 if (elem) 504 { // Just change object if the location is occupied 505 [elem->object release]; 506 elem->object = object; 507 } 508 else 509 { // Else allocate more memory 510 elem = NSZoneMalloc([self zone], 511 sizeof(struct KTMatrixSparseElement)); 512 elem->hashedLocation = 513 ((struct KTMatrixSparseElement *)cache)->hashedLocation; 514 elem->object = object; 515 NSHashInsertKnownAbsent(matrix, elem); 516 } 517} 518- (void)removeObjectAtLocation:(NSDictionary *)loc1 519 byLocation:(NSDictionary *)loc2; 520{ 521 ((struct KTMatrixSparseElement *)cache)->hashedLocation = [hash 522 hashForLocation:loc1 byLocation:loc2]; 523 NSHashRemove(matrix, cache); 524} 525- (void)removeAllObjects 526{ NSResetHashTable(matrix); } 527 528//// Optimized versions 529- (void) setObject:(id)object 530 atCoordinates:(unsigned)x,... 531{ 532 va_list args; 533 534 va_start(args, x); 535 536 if (hashIsCoordinateOptimized) 537 { 538 struct KTMatrixSparseElement *elem; 539 ((struct KTMatrixSparseElement *)cache)->hashedLocation = 540 [(id)hash hashForCoordinatesList:x :&args]; 541 542 elem = (struct KTMatrixSparseElement *)NSHashGet(matrix, cache); 543 if (elem) 544 { // Just change object if the location is occupied 545 [elem->object release]; 546 elem->object = object; 547 } 548 else 549 { // Else allocate more memory 550 elem = NSZoneMalloc([self zone], 551 sizeof(struct KTMatrixSparseElement)); 552 elem->hashedLocation = 553 ((struct KTMatrixSparseElement *)cache)->hashedLocation; 554 elem->object = object; 555 NSHashInsertKnownAbsent(matrix, elem); 556 } 557 } 558 else 559 { 560 NSMutableArray *array = [NSMutableArray arrayWithObject: 561 [NSNumber numberWithInt:x]]; 562 unsigned axes = [self dimension]; 563 564 while ([array count] < axes) 565 [array addObject:[NSNumber numberWithInt:va_arg(args, unsigned)]]; 566 567 va_end(args); 568 [self setObject:object 569 atCoordinateArray:array]; 570 return; 571 } 572} 573- (void)setObjectsAtCoordinates:(id)object1,... 574{ 575 id object = object1; 576 va_list args; 577 578 if (object1 != 0) 579 { 580 va_start(args, object1); 581 582 if (hashIsCoordinateOptimized) 583 { 584 // SELs/IMPs to speed up repeated method calls 585 SEL hashListSEL = @selector(hashForCoordinatesList:); 586 SEL setObjSEL = @selector(setObject:atHashedLocation:); 587 unsigned (*hashListIMP)(id, SEL, ...); 588 void (*setObjIMP)(id, SEL, ...); 589 590 hashListIMP = (unsigned (*)(id, SEL, ...)) 591 [(id)hash methodForSelector:hashListSEL]; 592 setObjIMP = (void (*)(id, SEL, ...)) 593 [self methodForSelector:setObjSEL]; 594 do 595 { 596 setObjIMP(self, setObjSEL, object, 597 hashListIMP(hash,hashListSEL,&args)); 598 } 599 while (object = va_arg(args, id)); 600 } 601 else 602 { 603 NSMutableArray *objects = [NSMutableArray array]; 604 NSMutableArray *coords = [NSMutableArray array]; 605 unsigned dimension = [self dimension]; 606 607 do 608 { 609 NSMutableArray *coord = [NSMutableArray arrayWithCapacity: 610 dimension]; 611 [objects addObject:object]; 612 while ([coord count] < dimension) 613 [coord addObject:[NSNumber numberWithInt: 614 va_arg(args, unsigned)]]; 615 [coords addObject:coord]; 616 } 617 while (object = va_arg(args, id)); 618 619 [self setObjects:objects 620 atCoordinateArrays:coords]; 621 } 622 } 623 624 va_end(args); 625} 626- (void)removeObjectAtCoordinates:(unsigned)x,... 627{ 628 va_list args; 629 630 va_start(args, x); 631 632 if (hashIsCoordinateOptimized) 633 { 634 ((struct KTMatrixSparseElement *)cache)->hashedLocation = [(id)hash 635 hashForCoordinatesList:x :&args]; 636 NSHashRemove(matrix, cache); 637 } 638 else 639 { 640 NSMutableArray *array = [NSMutableArray arrayWithObject: 641 [NSNumber numberWithInt:x]]; 642 unsigned axes = [self dimension]; 643 644 while ([array count] < axes) 645 [array addObject:[NSNumber numberWithInt:va_arg(args, unsigned)]]; 646 [self removeObjectAtCoordinateArray:array]; 647 } 648 649 va_end(args); 650} 651 652- (void)dealloc 653{ 654 [hash release]; 655 NSFreeHashTable(matrix); 656 NSZoneFree([self zone], cache); 657 [super dealloc]; 658} 659 660@end 661