1/** Implementation for NSIndexSet, NSMutableIndexSet for GNUStep 2 Copyright (C) 2004 Free Software Foundation, Inc. 3 4 Written by: Richard Frith-Macdonald <rfm@gnu.org> 5 Created: Feb 2004 6 7 This file is part of the GNUstep Base Library. 8 9 This library is free software; you can redistribute it and/or 10 modify it under the terms of the GNU Lesser General Public 11 License as published by the Free Software Foundation; either 12 version 2 of the License, or (at your option) any later version. 13 14 This library is distributed in the hope that it will be useful, 15 but WITHOUT ANY WARRANTY; without even the implied warranty of 16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 17 Lesser General Public License for more details. 18 19 You should have received a copy of the GNU Lesser General Public 20 License along with this library; if not, write to the Free 21 Software Foundation, Inc., 51 Franklin Street, Fifth Floor, 22 Boston, MA 02110 USA. 23 24 */ 25 26#import "common.h" 27#define EXPOSE_NSIndexSet_IVARS 1 28#import "Foundation/NSCoder.h" 29#import "Foundation/NSData.h" 30#import "Foundation/NSIndexSet.h" 31#import "Foundation/NSException.h" 32#import "GSDispatch.h" 33 34#define GSI_ARRAY_TYPE NSRange 35 36#define GSI_ARRAY_NO_RELEASE 1 37#define GSI_ARRAY_NO_RETAIN 1 38 39#include "GNUstepBase/GSIArray.h" 40 41#define _array ((GSIArray)(self->_data)) 42#define _other ((GSIArray)(aSet->_data)) 43 44#ifdef SANITY_CHECKS 45static void sanity(GSIArray array) 46{ 47 if (array != 0) 48 49 { 50 NSUInteger c = GSIArrayCount(array); 51 NSUInteger i; 52 NSUInteger last = 0; 53 54 for (i = 0; i < c; i++) 55 { 56 NSRange r = GSIArrayItemAtIndex(array, i).ext; 57 58 if (i > 0) 59 { 60 NSCAssert(r.location > last, @"Overlap or touching ranges"); 61 } 62 else 63 { 64 NSCAssert(r.location >= last, @"Overlap ranges"); 65 } 66 NSCAssert(NSMaxRange(r) > r.location, @"Bad range length"); 67 last = NSMaxRange(r); 68 } 69 } 70} 71#define SANITY() sanity(_array) 72#else 73#define SANITY() 74#endif 75 76/* 77 * Returns the position in the array at which the index should be inserted. 78 * This may be the position of a range containing the index if it is already 79 * present, otherwise it is the position of the first range containing an 80 * index greater than the argument (or a position beyond the end of the 81 * array). 82 */ 83static NSUInteger posForIndex(GSIArray array, NSUInteger index) 84{ 85 NSUInteger upper = GSIArrayCount(array); 86 NSUInteger lower = 0; 87 NSUInteger pos; 88 89 /* 90 * Binary search for an item equal to the one to be inserted. 91 */ 92 for (pos = upper/2; upper != lower; pos = (upper+lower)/2) 93 { 94 NSRange r = GSIArrayItemAtIndex(array, pos).ext; 95 96 if (index < r.location) 97 { 98 upper = pos; 99 } 100 else if (index > NSMaxRange(r)) 101 { 102 lower = pos + 1; 103 } 104 else 105 { 106 break; 107 } 108 } 109 /* 110 * Now skip past any item containing no values as high as the index. 111 */ 112 while (pos < GSIArrayCount(array) 113 && index >= NSMaxRange(GSIArrayItemAtIndex(array, pos).ext)) 114 { 115 pos++; 116 } 117 return pos; 118} 119 120@implementation NSIndexSet 121+ (id) indexSet 122{ 123 id o = [self allocWithZone: NSDefaultMallocZone()]; 124 125 o = [o init]; 126 return AUTORELEASE(o); 127} 128 129+ (id) indexSetWithIndex: (NSUInteger)anIndex 130{ 131 id o = [self allocWithZone: NSDefaultMallocZone()]; 132 133 o = [o initWithIndex: anIndex]; 134 return AUTORELEASE(o); 135} 136 137+ (id) indexSetWithIndexesInRange: (NSRange)aRange 138{ 139 id o = [self allocWithZone: NSDefaultMallocZone()]; 140 141 o = [o initWithIndexesInRange: aRange]; 142 return AUTORELEASE(o); 143} 144 145- (BOOL) containsIndex: (NSUInteger)anIndex 146{ 147 NSUInteger pos; 148 NSRange r; 149 150 if (_array == 0 || GSIArrayCount(_array) == 0 151 || (pos = posForIndex(_array, anIndex)) >= GSIArrayCount(_array)) 152 { 153 return NO; 154 } 155 r = GSIArrayItemAtIndex(_array, pos).ext; 156 return NSLocationInRange(anIndex, r); 157} 158 159- (BOOL) containsIndexes: (NSIndexSet*)aSet 160{ 161 NSUInteger count = _other ? GSIArrayCount(_other) : 0; 162 163 if (count > 0) 164 { 165 NSUInteger i; 166 167 for (i = 0; i < count; i++) 168 { 169 NSRange r = GSIArrayItemAtIndex(_other, i).ext; 170 171 if ([self containsIndexesInRange: r] == NO) 172 { 173 return NO; 174 } 175 } 176 } 177 return YES; 178} 179 180- (BOOL) containsIndexesInRange: (NSRange)aRange 181{ 182 NSUInteger pos; 183 NSRange r; 184 185 if (NSNotFound - aRange.length < aRange.location) 186 { 187 [NSException raise: NSInvalidArgumentException 188 format: @"[%@-%@]: Bad range", 189 NSStringFromClass([self class]), NSStringFromSelector(_cmd)]; 190 } 191 if (_array == 0 || GSIArrayCount(_array) == 0 192 || (pos = posForIndex(_array, aRange.location)) >= GSIArrayCount(_array)) 193 { 194 return NO; // Empty ... contains no indexes. 195 } 196 if (aRange.length == 0) 197 { 198 return YES; // No indexes needed. 199 } 200 r = GSIArrayItemAtIndex(_array, pos).ext; 201 if (NSLocationInRange(aRange.location, r) 202 && NSLocationInRange(NSMaxRange(aRange)-1, r)) 203 { 204 return YES; 205 } 206 return NO; 207} 208 209- (id) copyWithZone: (NSZone*)aZone 210{ 211 if (NSShouldRetainWithZone(self, aZone)) 212 { 213 return RETAIN(self); 214 } 215 else 216 { 217 NSIndexSet *c = [NSIndexSet allocWithZone: aZone]; 218 219 return [c initWithIndexSet: self]; 220 } 221} 222 223- (NSUInteger) count 224{ 225 if (_array == 0 || GSIArrayCount(_array) == 0) 226 { 227 return 0; 228 } 229 else 230 { 231 NSUInteger count = GSIArrayCount(_array); 232 NSUInteger total = 0; 233 NSUInteger i = 0; 234 235 while (i < count) 236 { 237 total += GSIArrayItemAtIndex(_array, i).ext.length; 238 i++; 239 } 240 return total; 241 } 242} 243 244- (NSUInteger) countOfIndexesInRange: (NSRange)range 245{ 246 if (_array == 0 || GSIArrayCount(_array) == 0) 247 { 248 return 0; 249 } 250 else 251 { 252 NSUInteger count = GSIArrayCount(_array); 253 NSUInteger total = 0; 254 NSUInteger i = 0; 255 256 while (i < count) 257 { 258 NSRange r = GSIArrayItemAtIndex(_array, i).ext; 259 260 r = NSIntersectionRange(r, range); 261 total += r.length; 262 i++; 263 } 264 return total; 265 } 266} 267 268- (void) dealloc 269{ 270 if (_array != 0) 271 { 272 GSIArrayClear(_array); 273 NSZoneFree([self zone], _array); 274 _data = 0; 275 } 276 [super dealloc]; 277} 278 279- (NSString*) description 280{ 281 NSMutableString *m; 282 NSUInteger c = (_array == 0) ? 0 : GSIArrayCount(_array); 283 NSUInteger i; 284 285 if (c == 0) 286 { 287 return [NSString stringWithFormat: @"%@(no indexes)", 288 [super description]]; 289 } 290 m = [NSMutableString stringWithFormat: 291 @"%@[number of indexes: %"PRIuPTR" (in %"PRIuPTR" ranges), indexes:", 292 [super description], [self count], c]; 293 for (i = 0; i < c; i++) 294 { 295 NSRange r = GSIArrayItemAtIndex(_array, i).ext; 296 297 if (r.length > 1) 298 { 299 [m appendFormat: @" (%"PRIuPTR"-%"PRIuPTR")", 300 r.location, NSMaxRange(r) - 1]; 301 } 302 else 303 { 304 [m appendFormat: @" %"PRIuPTR, r.location]; 305 } 306 } 307 [m appendString: @"]"]; 308 return m; 309} 310 311- (void) encodeWithCoder: (NSCoder*)aCoder 312{ 313 NSUInteger rangeCount = 0; 314 315 if (_array != 0) 316 { 317 rangeCount = GSIArrayCount(_array); 318 } 319 320 if ([aCoder allowsKeyedCoding]) 321 { 322 [aCoder encodeInt: rangeCount forKey: @"NSRangeCount"]; 323 } 324 else 325 { 326 [aCoder encodeValueOfObjCType: @encode(NSUInteger) 327 at: &rangeCount]; 328 } 329 330 if (rangeCount == 0) 331 { 332 // Do nothing 333 } 334 else if (rangeCount == 1) 335 { 336 NSRange r; 337 338 r = GSIArrayItemAtIndex(_array, 0).ext; 339 if ([aCoder allowsKeyedCoding]) 340 { 341 [aCoder encodeInt: r.location forKey: @"NSLocation"]; 342 [aCoder encodeInt: r.length forKey: @"NSLength"]; 343 } 344 else 345 { 346 [aCoder encodeValueOfObjCType: @encode(NSUInteger) 347 at: &r.location]; 348 [aCoder encodeValueOfObjCType: @encode(NSUInteger) 349 at: &r.length]; 350 } 351 } 352 else 353 { 354 NSMutableData *m = [NSMutableData dataWithCapacity: rangeCount*2]; 355 NSUInteger i; 356 357 for (i = 0; i < rangeCount; i++) 358 { 359 NSRange r; 360 NSUInteger v; 361 uint8_t b; 362 363 r = GSIArrayItemAtIndex(_array, i).ext; 364 v = r.location; 365 do 366 { 367 if (v > 0x7f) 368 { 369 b = (v & 0x7f) | 0x80; 370 } 371 else 372 { 373 b = v; 374 } 375 v >>= 7; 376 [m appendBytes: &b length: 1]; 377 } 378 while (v > 0); 379 v = r.length; 380 do 381 { 382 if (v > 0x7f) 383 { 384 b = (v & 0x7f) | 0x80; 385 } 386 else 387 { 388 b = v; 389 } 390 v >>= 7; 391 [m appendBytes: &b length: 1]; 392 } 393 while (v > 0); 394 } 395 if ([aCoder allowsKeyedCoding]) 396 { 397 [aCoder encodeObject: m forKey: @"NSRangeData"]; 398 } 399 else 400 { 401 [aCoder encodeObject: m]; 402 } 403 } 404} 405 406- (NSUInteger) firstIndex 407{ 408 if (_array == 0 || GSIArrayCount(_array) == 0) 409 { 410 return NSNotFound; 411 } 412 return GSIArrayItemAtIndex(_array, 0).ext.location; 413} 414 415- (NSUInteger) getIndexes: (NSUInteger*)aBuffer 416 maxCount: (NSUInteger)aCount 417 inIndexRange: (NSRangePointer)aRange 418{ 419 NSUInteger pos; 420 NSUInteger i = 0; 421 NSRange r; 422 NSRange fullRange; 423 424 if (aBuffer == 0) 425 { 426 [NSException raise: NSInvalidArgumentException 427 format: @"[%@-%@]: nul pointer argument", 428 NSStringFromClass([self class]), NSStringFromSelector(_cmd)]; 429 } 430 if (aRange == 0) 431 { 432 fullRange = (NSRange){0, NSNotFound}; 433 aRange = &fullRange; 434 } 435 else if (NSNotFound - aRange->length < aRange->location) 436 { 437 [NSException raise: NSInvalidArgumentException 438 format: @"[%@-%@]: Bad range", 439 NSStringFromClass([self class]), NSStringFromSelector(_cmd)]; 440 } 441 if (_array == 0 || GSIArrayCount(_array) == 0 442 || (pos = posForIndex(_array, aRange->location)) >= GSIArrayCount(_array)) 443 { 444 *aRange = NSMakeRange(NSMaxRange(*aRange), 0); 445 return 0; 446 } 447 448 while (aRange->length > 0 && i < aCount && pos < GSIArrayCount(_array)) 449 { 450 r = GSIArrayItemAtIndex(_array, pos).ext; 451 if (aRange->location < r.location) 452 { 453 NSUInteger skip = r.location - aRange->location; 454 455 if (skip > aRange->length) 456 { 457 skip = aRange->length; 458 } 459 aRange->location += skip; 460 aRange->length -= skip; 461 } 462 if (NSLocationInRange(aRange->location, r)) 463 { 464 while (aRange->length > 0 && i < aCount 465 && aRange->location < NSMaxRange(r)) 466 { 467 aBuffer[i++] = aRange->location++; 468 aRange->length--; 469 } 470 } 471 else 472 { 473 } 474 pos++; 475 } 476 return i; 477} 478 479- (NSUInteger) hash 480{ 481 return [self count]; 482} 483 484- (NSUInteger) indexGreaterThanIndex: (NSUInteger)anIndex 485{ 486 NSUInteger pos; 487 NSRange r; 488 489 if (anIndex++ == NSNotFound) 490 { 491 return NSNotFound; 492 } 493 if (_array == 0 || GSIArrayCount(_array) == 0 494 || (pos = posForIndex(_array, anIndex)) >= GSIArrayCount(_array)) 495 { 496 return NSNotFound; 497 } 498 r = GSIArrayItemAtIndex(_array, pos).ext; 499 if (NSLocationInRange(anIndex, r)) 500 { 501 return anIndex; 502 } 503 return r.location; 504} 505 506- (NSUInteger) indexGreaterThanOrEqualToIndex: (NSUInteger)anIndex 507{ 508 NSUInteger pos; 509 NSRange r; 510 511 if (anIndex == NSNotFound) 512 { 513 return NSNotFound; 514 } 515 if (_array == 0 || GSIArrayCount(_array) == 0 516 || (pos = posForIndex(_array, anIndex)) >= GSIArrayCount(_array)) 517 { 518 return NSNotFound; 519 } 520 r = GSIArrayItemAtIndex(_array, pos).ext; 521 if (NSLocationInRange(anIndex, r)) 522 { 523 return anIndex; 524 } 525 return r.location; 526} 527 528- (NSUInteger) indexLessThanIndex: (NSUInteger)anIndex 529{ 530 NSUInteger pos; 531 NSRange r; 532 533 if (anIndex-- == 0) 534 { 535 return NSNotFound; 536 } 537 if (_array == 0 || GSIArrayCount(_array) == 0 538 || (pos = posForIndex(_array, anIndex)) >= GSIArrayCount(_array)) 539 { 540 return NSNotFound; 541 } 542 r = GSIArrayItemAtIndex(_array, pos).ext; 543 if (NSLocationInRange(anIndex, r)) 544 { 545 return anIndex; 546 } 547 if (pos-- == 0) 548 { 549 return NSNotFound; 550 } 551 r = GSIArrayItemAtIndex(_array, pos).ext; 552 return NSMaxRange(r) - 1; 553} 554 555- (NSUInteger) indexLessThanOrEqualToIndex: (NSUInteger)anIndex 556{ 557 NSUInteger pos; 558 NSRange r; 559 560 if (_array == 0 || GSIArrayCount(_array) == 0 561 || (pos = posForIndex(_array, anIndex)) >= GSIArrayCount(_array)) 562 { 563 return NSNotFound; 564 } 565 r = GSIArrayItemAtIndex(_array, pos).ext; 566 if (NSLocationInRange(anIndex, r)) 567 { 568 return anIndex; 569 } 570 if (pos-- == 0) 571 { 572 return NSNotFound; 573 } 574 r = GSIArrayItemAtIndex(_array, pos).ext; 575 return NSMaxRange(r) - 1; 576} 577 578- (id) init 579{ 580 return self; 581} 582 583- (id) initWithCoder: (NSCoder*)aCoder 584{ 585 NSUInteger rangeCount = 0; 586 587 if ([aCoder allowsKeyedCoding]) 588 { 589 if ([aCoder containsValueForKey: @"NSRangeCount"]) 590 { 591 rangeCount = [aCoder decodeIntForKey: @"NSRangeCount"]; 592 } 593 } 594 else 595 { 596 [aCoder decodeValueOfObjCType: @encode(NSUInteger) 597 at: &rangeCount]; 598 } 599 600 if (rangeCount == 0) 601 { 602 // Do nothing 603 } 604 else if (rangeCount == 1) 605 { 606 NSUInteger len = 0; 607 NSUInteger loc = 0; 608 609 if ([aCoder allowsKeyedCoding]) 610 { 611 if ([aCoder containsValueForKey: @"NSLocation"]) 612 { 613 loc = [aCoder decodeIntForKey: @"NSLocation"]; 614 } 615 if ([aCoder containsValueForKey: @"NSLength"]) 616 { 617 len = [aCoder decodeIntForKey: @"NSLength"]; 618 } 619 } 620 else 621 { 622 [aCoder decodeValueOfObjCType: @encode(NSUInteger) 623 at: &loc]; 624 [aCoder decodeValueOfObjCType: @encode(NSUInteger) 625 at: &len]; 626 } 627 self = [self initWithIndexesInRange: NSMakeRange(loc, len)]; 628 } 629 else 630 { 631 NSMutableIndexSet *other = [NSMutableIndexSet new]; 632 NSData *data = nil; 633 const uint8_t *bytes; 634 NSUInteger length; 635 NSUInteger index = 0; 636 637 if ([aCoder allowsKeyedCoding]) 638 { 639 if ([aCoder containsValueForKey: @"NSRangeData"]) 640 { 641 data = [aCoder decodeObjectForKey: @"NSRangeData"]; 642 } 643 } 644 else 645 { 646 data = [aCoder decodeObject]; 647 } 648 bytes = (const uint8_t*)[data bytes]; 649 length = [data length]; 650 while (index < length) 651 { 652 NSRange range; 653 NSUInteger offset; 654 NSUInteger value; 655 NSUInteger next; 656 657 for (offset = 0; index + offset < length; offset++) 658 { 659 if (bytes[index + offset] < 0x80) 660 { 661 break; 662 } 663 } 664 NSAssert(index + offset < length && bytes[index + offset] < 0x80, 665 NSInternalInconsistencyException); 666 next = index + offset + 1; 667 value = bytes[index + offset]; 668 while (offset-- > 0) 669 { 670 value <<= 7; 671 value += (bytes[index + offset] & 0x7f); 672 } 673 range.location = value; 674 index = next; 675 for (offset = 0; index + offset < length; offset++) 676 { 677 if (bytes[index + offset] < 0x80) 678 { 679 break; 680 } 681 } 682 NSAssert(index + offset < length && bytes[index + offset] < 0x80, 683 NSInternalInconsistencyException); 684 next = index + offset + 1; 685 value = bytes[index + offset]; 686 while (offset-- > 0) 687 { 688 value <<= 7; 689 value += (bytes[index + offset] & 0x7f); 690 } 691 range.length = value; 692 index = next; 693 [other addIndexesInRange: range]; 694 } 695 self = [self initWithIndexSet: other]; 696 RELEASE(other); 697 /* 698 FIXME: 699 NSLog(@"Decoded count %d, data %@", rangeCount, data); 700 This is a very strange format: 701 702 5 + 6 + 9 gives <05020901> 703 5 + 6 + 23 gives <05021701> 704 155 + 156 + 223 gives <9b0102df 0101> 705 */ 706 } 707 708 return self; 709} 710 711- (id) initWithIndex: (NSUInteger)anIndex 712{ 713 if (anIndex == NSNotFound) 714 { 715 DESTROY(self); // NSNotFound is not legal 716 } 717 else 718 { 719 self = [self initWithIndexesInRange: NSMakeRange(anIndex, 1)]; 720 } 721 return self; 722} 723 724- (id) initWithIndexesInRange: (NSRange)aRange 725{ 726 if (aRange.length > 0) 727 { 728 if (NSMaxRange(aRange) == NSNotFound) 729 { 730 DESTROY(self); // NSNotFound is not legal 731 } 732 else 733 { 734 _data = (GSIArray)NSZoneMalloc([self zone], sizeof(GSIArray_t)); 735 GSIArrayInitWithZoneAndCapacity(_array, [self zone], 1); 736 GSIArrayAddItem(_array, (GSIArrayItem)aRange); 737 } 738 } 739 return self; 740} 741 742- (id) initWithIndexSet: (NSIndexSet*)aSet 743{ 744 if (aSet == nil || [aSet isKindOfClass: [NSIndexSet class]] == NO) 745 { 746 DESTROY(self); 747 } 748 else 749 { 750 NSUInteger count = _other ? GSIArrayCount(_other) : 0; 751 752 if (count > 0) 753 { 754 NSUInteger i; 755 756 _data = (GSIArray)NSZoneMalloc([self zone], sizeof(GSIArray_t)); 757 GSIArrayInitWithZoneAndCapacity(_array, [self zone], count); 758 for (i = 0; i < count; i++) 759 { 760 GSIArrayAddItem(_array, GSIArrayItemAtIndex(_other, i)); 761 } 762 } 763 } 764 return self; 765} 766 767- (BOOL) intersectsIndexesInRange: (NSRange)aRange 768{ 769 NSUInteger p1; 770 NSUInteger p2; 771 772 if (NSNotFound - aRange.length < aRange.location) 773 { 774 [NSException raise: NSInvalidArgumentException 775 format: @"[%@-%@]: Bad range", 776 NSStringFromClass([self class]), NSStringFromSelector(_cmd)]; 777 } 778 if (aRange.length == 0 || _array == 0 || GSIArrayCount(_array) == 0) 779 { 780 return NO; // Empty 781 } 782 p1 = posForIndex(_array, aRange.location); 783 p2 = posForIndex(_array, NSMaxRange(aRange) - 1); 784 if (p1 != p2) 785 { 786 return YES; 787 } 788 if (p1 >= GSIArrayCount(_array)) 789 { 790 return NO; 791 } 792 if (NSLocationInRange(aRange.location, GSIArrayItemAtIndex(_array, p1).ext)) 793 { 794 return YES; 795 } 796 if (NSLocationInRange(NSMaxRange(aRange)-1, 797 GSIArrayItemAtIndex(_array, p1).ext)) 798 { 799 return YES; 800 } 801 return NO; 802} 803 804- (BOOL) isEqual: (id)aSet 805{ 806 if ([aSet isKindOfClass: [NSIndexSet class]] == YES) 807 { 808 return [self isEqualToIndexSet: aSet]; 809 } 810 return NO; 811} 812 813- (BOOL) isEqualToIndexSet: (NSIndexSet*)aSet 814{ 815 NSUInteger count = _other ? GSIArrayCount(_other) : 0; 816 817 if (count != (_array ? GSIArrayCount(_array) : 0)) 818 { 819 return NO; 820 } 821 if (count > 0) 822 { 823 NSUInteger i; 824 825 for (i = 0; i < count; i++) 826 { 827 NSRange rself = GSIArrayItemAtIndex(_array, i).ext; 828 NSRange rother = GSIArrayItemAtIndex(_other, i).ext; 829 830 if (NSEqualRanges(rself, rother) == NO) 831 { 832 return NO; 833 } 834 } 835 } 836 return YES; 837} 838 839- (NSUInteger) lastIndex 840{ 841 if (_array == 0 || GSIArrayCount(_array) == 0) 842 { 843 return NSNotFound; 844 } 845 return NSMaxRange(GSIArrayItemAtIndex(_array, GSIArrayCount(_array)-1).ext)-1; 846} 847 848- (id) mutableCopyWithZone: (NSZone*)aZone 849{ 850 NSMutableIndexSet *c = [NSMutableIndexSet allocWithZone: aZone]; 851 852 return [c initWithIndexSet: self]; 853} 854 855 856- (void) enumerateIndexesInRange: (NSRange)range 857 options: (NSEnumerationOptions)opts 858 usingBlock: (GSIndexSetEnumerationBlock)aBlock 859{ 860 NSUInteger lastInRange; 861 NSUInteger startArrayIndex; 862 NSUInteger endArrayIndex; 863 NSUInteger i; 864 NSUInteger c; 865 BOOL isReverse = opts & NSEnumerationReverse; 866 BLOCK_SCOPE BOOL shouldStop = NO; 867 868 if ((0 == [self count]) || (NSNotFound == range.location)) 869 { 870 return; 871 } 872 873 startArrayIndex = posForIndex(_array, range.location); 874 if (NSNotFound == startArrayIndex) 875 { 876 startArrayIndex = 0; 877 } 878 879 lastInRange = (NSMaxRange(range) - 1); 880 endArrayIndex = MIN(posForIndex(_array, lastInRange), 881 (GSIArrayCount(_array) - 1)); 882 if (NSNotFound == endArrayIndex) 883 { 884 endArrayIndex = GSIArrayCount(_array) - 1; 885 } 886 887 if (isReverse) 888 { 889 i = endArrayIndex; 890 c = startArrayIndex; 891 } 892 else 893 { 894 i = startArrayIndex; 895 c = endArrayIndex; 896 } 897 898 GS_DISPATCH_CREATE_QUEUE_AND_GROUP_FOR_ENUMERATION(enumQueue, opts) 899 while (isReverse ? i >= c : i <= c) 900 { 901 NSRange r = GSIArrayItemAtIndex(_array, i).ext; 902 NSUInteger innerI; 903 NSUInteger innerC; 904 905 if (isReverse) 906 { 907 innerI = NSMaxRange(r) - 1; 908 innerC = r.location; 909 } 910 else 911 { 912 innerI = r.location; 913 innerC = NSMaxRange(r) - 1; 914 } 915 while (isReverse ? innerI >= innerC : innerI <= innerC) 916 { 917 if ((innerI <= lastInRange) && (innerI >= range.location)) 918 { 919 GS_DISPATCH_SUBMIT_BLOCK(enumQueueGroup, enumQueue, 920 if (shouldStop == NO) {, }, 921 aBlock, innerI, &shouldStop); 922 } 923 if (shouldStop) 924 { 925 break; 926 } 927 if (isReverse) 928 { 929 if (0 == innerI) 930 { 931 break; 932 } 933 innerI--; 934 } 935 else 936 { 937 innerI++; 938 } 939 } 940 941 if (shouldStop) 942 { 943 break; 944 } 945 if (isReverse) 946 { 947 if (0 == i) 948 { 949 break; 950 } 951 i--; 952 } 953 else 954 { 955 i++; 956 } 957 } 958 GS_DISPATCH_TEARDOWN_QUEUE_AND_GROUP_FOR_ENUMERATION(enumQueue, opts) 959 960} 961 962- (void) enumerateIndexesWithOptions: (NSEnumerationOptions)opts 963 usingBlock: (GSIndexSetEnumerationBlock)aBlock 964{ 965 NSUInteger firstIndex; 966 NSUInteger lastIndex; 967 NSRange range; 968 969 firstIndex = [self firstIndex]; 970 if (NSNotFound == firstIndex) 971 { 972 return; 973 } 974 975 lastIndex = [self lastIndex]; 976 range = NSMakeRange(firstIndex, ((lastIndex - firstIndex) + 1)); 977 978 [self enumerateIndexesInRange: range 979 options: opts 980 usingBlock: aBlock]; 981} 982 983- (void) enumerateIndexesUsingBlock: (GSIndexSetEnumerationBlock)aBlock 984{ 985 [self enumerateIndexesWithOptions: 0 986 usingBlock: aBlock]; 987} 988@end 989 990 991@implementation NSMutableIndexSet 992 993#undef _other 994#define _other ((GSIArray)(((NSMutableIndexSet*)aSet)->_data)) 995 996- (void) addIndex: (NSUInteger)anIndex 997{ 998 [self addIndexesInRange: NSMakeRange(anIndex, 1)]; 999} 1000 1001- (void) addIndexes: (NSIndexSet*)aSet 1002{ 1003 NSUInteger count = _other ? GSIArrayCount(_other) : 0; 1004 1005 if (count > 0) 1006 { 1007 NSUInteger i; 1008 1009 for (i = 0; i < count; i++) 1010 { 1011 NSRange r = GSIArrayItemAtIndex(_other, i).ext; 1012 1013 [self addIndexesInRange: r]; 1014 } 1015 } 1016} 1017 1018- (void) addIndexesInRange: (NSRange)aRange 1019{ 1020 NSUInteger pos; 1021 1022 if (NSNotFound - aRange.length < aRange.location) 1023 { 1024 [NSException raise: NSInvalidArgumentException 1025 format: @"[%@-%@]: Bad range", 1026 NSStringFromClass([self class]), NSStringFromSelector(_cmd)]; 1027 } 1028 if (aRange.length == 0) 1029 { 1030 return; 1031 } 1032 if (_array == 0) 1033 { 1034 _data = (GSIArray)NSZoneMalloc([self zone], sizeof(GSIArray_t)); 1035 GSIArrayInitWithZoneAndCapacity(_array, [self zone], 1); 1036 } 1037 1038 pos = posForIndex(_array, aRange.location); 1039 if (pos >= GSIArrayCount(_array)) 1040 { 1041 /* 1042 * The start of the range to add lies beyond the existing 1043 * ranges, so we can simply append it. 1044 */ 1045 GSIArrayAddItem(_array, (GSIArrayItem)aRange); 1046 } 1047 else 1048 { 1049 NSRange r = GSIArrayItemAtIndex(_array, pos).ext; 1050 1051 if (NSLocationInRange(aRange.location, r)) 1052 { 1053 pos++; 1054 } 1055 GSIArrayInsertItem(_array, (GSIArrayItem)aRange, pos); 1056 } 1057 1058 /* 1059 * Combine with the preceding ranges if possible. 1060 */ 1061 while (pos > 0) 1062 { 1063 NSRange r = GSIArrayItemAtIndex(_array, pos-1).ext; 1064 1065 if (NSMaxRange(r) < aRange.location) 1066 { 1067 break; 1068 } 1069 if (NSMaxRange(r) >= NSMaxRange(aRange)) 1070 { 1071 GSIArrayRemoveItemAtIndex(_array, pos--); 1072 } 1073 else 1074 { 1075 r.length += (NSMaxRange(aRange) - NSMaxRange(r)); 1076 GSIArrayRemoveItemAtIndex(_array, pos--); 1077 GSIArraySetItemAtIndex(_array, (GSIArrayItem)r, pos); 1078 } 1079 } 1080 1081 /* 1082 * Combine with any following ranges where possible. 1083 */ 1084 while (pos + 1 < GSIArrayCount(_array)) 1085 { 1086 NSRange r = GSIArrayItemAtIndex(_array, pos+1).ext; 1087 1088 if (NSMaxRange(aRange) < r.location) 1089 { 1090 break; 1091 } 1092 GSIArrayRemoveItemAtIndex(_array, pos + 1); 1093 if (NSMaxRange(r) > NSMaxRange(aRange)) 1094 { 1095 int offset = NSMaxRange(r) - NSMaxRange(aRange); 1096 1097 r = GSIArrayItemAtIndex(_array, pos).ext; 1098 r.length += offset; 1099 GSIArraySetItemAtIndex(_array, (GSIArrayItem)r, pos); 1100 } 1101 } 1102 SANITY(); 1103} 1104 1105- (id) copyWithZone: (NSZone*)aZone 1106{ 1107 NSIndexSet *c = [NSIndexSet allocWithZone: aZone]; 1108 1109 return [c initWithIndexSet: self]; 1110} 1111 1112- (void) removeAllIndexes 1113{ 1114 if (_array != 0) 1115 { 1116 GSIArrayRemoveAllItems(_array); 1117 } 1118} 1119 1120- (void) removeIndex: (NSUInteger)anIndex 1121{ 1122 [self removeIndexesInRange: NSMakeRange(anIndex, 1)]; 1123} 1124 1125- (void) removeIndexes: (NSIndexSet*)aSet 1126{ 1127 NSUInteger count = _other ? GSIArrayCount(_other) : 0; 1128 1129 if (count > 0) 1130 { 1131 NSUInteger i; 1132 1133 for (i = 0; i < count; i++) 1134 { 1135 NSRange r = GSIArrayItemAtIndex(_other, i).ext; 1136 1137 [self removeIndexesInRange: r]; 1138 } 1139 } 1140} 1141 1142- (void) removeIndexesInRange: (NSRange)aRange 1143{ 1144 NSUInteger pos; 1145 NSRange r; 1146 1147 if (NSNotFound - aRange.length < aRange.location) 1148 { 1149 [NSException raise: NSInvalidArgumentException 1150 format: @"[%@-%@]: Bad range", 1151 NSStringFromClass([self class]), NSStringFromSelector(_cmd)]; 1152 } 1153 if (aRange.length == 0 || _array == 0 1154 || (pos = posForIndex(_array, aRange.location)) >= GSIArrayCount(_array)) 1155 { 1156 return; // Already empty 1157 } 1158 1159 r = GSIArrayItemAtIndex(_array, pos).ext; 1160 if (r.location <= aRange.location) 1161 { 1162 if (r.location == aRange.location) 1163 { 1164 if (NSMaxRange(r) <= NSMaxRange(aRange)) 1165 { 1166 /* 1167 * Found range is entirely within range to remove, 1168 * leaving next range to check at current position. 1169 */ 1170 GSIArrayRemoveItemAtIndex(_array, pos); 1171 } 1172 else 1173 { 1174 /* 1175 * Range to remove is entirely within found range and 1176 * overlaps the start of the found range ... shrink it 1177 * and then we are finished. 1178 */ 1179 r.location += aRange.length; 1180 r.length -= aRange.length; 1181 GSIArraySetItemAtIndex(_array, (GSIArrayItem)r, pos); 1182 pos++; 1183 } 1184 } 1185 else 1186 { 1187 if (NSMaxRange(r) <= NSMaxRange(aRange)) 1188 { 1189 /* 1190 * Range to remove overlaps the end of the found range. 1191 * May also overlap next range ... so shorten found 1192 * range and move on. 1193 */ 1194 r.length = aRange.location - r.location; 1195 GSIArraySetItemAtIndex(_array, (GSIArrayItem)r, pos); 1196 pos++; 1197 } 1198 else 1199 { 1200 NSRange next = r; 1201 1202 /* 1203 * Range to remove is entirely within found range and 1204 * overlaps the middle of the found range ... split it. 1205 * Then we are finished. 1206 */ 1207 next.location = NSMaxRange(aRange); 1208 next.length = NSMaxRange(r) - next.location; 1209 r.length = aRange.location - r.location; 1210 GSIArraySetItemAtIndex(_array, (GSIArrayItem)r, pos); 1211 pos++; 1212 GSIArrayInsertItem(_array, (GSIArrayItem)next, pos); 1213 pos++; 1214 } 1215 } 1216 } 1217 1218 /* 1219 * At this point we are guaranteed that, if there is a range at pos, 1220 * it does not start before aRange.location 1221 */ 1222 while (pos < GSIArrayCount(_array)) 1223 { 1224 NSRange r = GSIArrayItemAtIndex(_array, pos).ext; 1225 1226 if (NSMaxRange(r) <= NSMaxRange(aRange)) 1227 { 1228 /* 1229 * Found range is entirely within range to remove ... 1230 * delete it. 1231 */ 1232 GSIArrayRemoveItemAtIndex(_array, pos); 1233 } 1234 else 1235 { 1236 if (r.location < NSMaxRange(aRange)) 1237 { 1238 /* 1239 * Range to remove overlaps start of found range ... 1240 * shorten it. 1241 */ 1242 r.length = NSMaxRange(r) - NSMaxRange(aRange); 1243 r.location = NSMaxRange(aRange); 1244 GSIArraySetItemAtIndex(_array, (GSIArrayItem)r, pos); 1245 } 1246 /* 1247 * Found range extends beyond range to remove ... finished. 1248 */ 1249 break; 1250 } 1251 } 1252 SANITY(); 1253} 1254 1255- (void) shiftIndexesStartingAtIndex: (NSUInteger)anIndex by: (NSInteger)amount 1256{ 1257 if (amount != 0 && _array != 0 && GSIArrayCount(_array) > 0) 1258 { 1259 NSUInteger c; 1260 NSUInteger pos; 1261 1262 if (amount > 0) 1263 { 1264 c = GSIArrayCount(_array); 1265 pos = posForIndex(_array, anIndex); 1266 1267 if (pos < c) 1268 { 1269 NSRange r = GSIArrayItemAtIndex(_array, pos).ext; 1270 1271 /* 1272 * If anIndex is within an existing range, we split 1273 * that range so we have one starting at anIndex. 1274 */ 1275 if (r.location < anIndex) 1276 { 1277 NSRange t; 1278 1279 /* 1280 * Split the range. 1281 */ 1282 t = NSMakeRange(r.location, anIndex - r.location); 1283 GSIArrayInsertItem(_array, (GSIArrayItem)t, pos); 1284 c++; 1285 r.length = NSMaxRange(r) - anIndex; 1286 r.location = anIndex; 1287 GSIArraySetItemAtIndex(_array, (GSIArrayItem)r, ++pos); 1288 } 1289 1290 /* 1291 * Shift all higher ranges to the right. 1292 */ 1293 while (c > pos) 1294 { 1295 NSRange r = GSIArrayItemAtIndex(_array, --c).ext; 1296 1297 if (NSNotFound - amount <= r.location) 1298 { 1299 GSIArrayRemoveItemAtIndex(_array, c); 1300 } 1301 else if (NSNotFound - amount < NSMaxRange(r)) 1302 { 1303 r.location += amount; 1304 r.length = NSNotFound - r.location; 1305 GSIArraySetItemAtIndex(_array, (GSIArrayItem)r, c); 1306 } 1307 else 1308 { 1309 r.location += amount; 1310 GSIArraySetItemAtIndex(_array, (GSIArrayItem)r, c); 1311 } 1312 } 1313 } 1314 } 1315 else 1316 { 1317 amount = -amount; 1318 1319 /* 1320 * Delete range which will be overwritten. 1321 */ 1322 if (amount >= anIndex) 1323 { 1324 [self removeIndexesInRange: NSMakeRange(0, anIndex)]; 1325 } 1326 else 1327 { 1328 [self removeIndexesInRange: 1329 NSMakeRange(anIndex - amount, amount)]; 1330 } 1331 pos = posForIndex(_array, anIndex); 1332 1333 /* 1334 * Now shift everything left into the hole we made. 1335 */ 1336 c = GSIArrayCount(_array); 1337 while (c > pos) 1338 { 1339 NSRange r = GSIArrayItemAtIndex(_array, --c).ext; 1340 1341 if (NSMaxRange(r) <= amount) 1342 { 1343 GSIArrayRemoveItemAtIndex(_array, c); 1344 } 1345 else if (r.location <= amount) 1346 { 1347 r.length += (r.location - amount); 1348 r.location = 0; 1349 GSIArraySetItemAtIndex(_array, (GSIArrayItem)r, c); 1350 } 1351 else 1352 { 1353 r.location -= amount; 1354 GSIArraySetItemAtIndex(_array, (GSIArrayItem)r, c); 1355 } 1356 } 1357 if (pos > 0) 1358 { 1359 c = GSIArrayCount(_array); 1360 if (pos < c) 1361 { 1362 NSRange r0 = GSIArrayItemAtIndex(_array, pos - 1).ext; 1363 NSRange r1 = GSIArrayItemAtIndex(_array, pos).ext; 1364 1365 if (NSMaxRange(r0) == r1.location) 1366 { 1367 r0.length += r1.length; 1368 GSIArraySetItemAtIndex(_array, (GSIArrayItem)r0, pos - 1); 1369 GSIArrayRemoveItemAtIndex(_array, pos); 1370 } 1371 } 1372 } 1373 } 1374 } 1375 SANITY(); 1376} 1377 1378@end 1379 1380@implementation NSIndexSet (NSCharacterSet) 1381/* Extra method to let NSCharacterSet play with index sets more efficiently. 1382 */ 1383- (NSUInteger) _gapGreaterThanIndex: (NSUInteger)anIndex 1384{ 1385 NSUInteger pos; 1386 NSRange r; 1387 1388 if (anIndex++ == NSNotFound) 1389 { 1390 return NSNotFound; 1391 } 1392 if (_array == 0 || GSIArrayCount(_array) == 0) 1393 { 1394 return NSNotFound; 1395 } 1396 1397 if ((pos = posForIndex(_array, anIndex)) >= GSIArrayCount(_array)) 1398 { 1399 r = GSIArrayItemAtIndex(_array, pos-1).ext; 1400 if (anIndex > NSMaxRange(r)) 1401 { 1402 return NSNotFound; 1403 } 1404 return anIndex; // anIndex is the gap after the last index. 1405 } 1406 r = GSIArrayItemAtIndex(_array, pos).ext; 1407 if (r.location > anIndex) 1408 { 1409 return anIndex; // anIndex is in a gap between index ranges. 1410 } 1411 return NSMaxRange(r); // Return start of gap after the index range. 1412} 1413 1414@end 1415 1416/* A subclass used to access a pre-generated table of information on the 1417 * stack or in other non-heap allocated memory. 1418 */ 1419@interface _GSStaticIndexSet : NSIndexSet 1420@end 1421 1422@implementation _GSStaticIndexSet 1423- (void) dealloc 1424{ 1425 if (_array != 0) 1426 { 1427 /* Free the array without freeing its static content. 1428 */ 1429 NSZoneFree([self zone], _array); 1430 _data = 0; 1431 } 1432 [super dealloc]; 1433} 1434 1435- (id) _initWithBytes: (const void*)bytes length: (NSUInteger)length 1436{ 1437 NSAssert(length % sizeof(GSIArrayItem) == 0, NSInvalidArgumentException); 1438 NSAssert(length % __alignof__(GSIArrayItem) == 0, NSInvalidArgumentException); 1439 length /= sizeof(NSRange); 1440 _data = NSZoneMalloc([self zone], sizeof(GSIArray_t)); 1441 _array->ptr = (GSIArrayItem*)bytes; 1442 _array->count = length; 1443 _array->cap = length; 1444 _array->old = length; 1445 _array->zone = 0; 1446 return self; 1447} 1448 1449- (id) init 1450{ 1451 return [self _initWithBytes: 0 length: 0]; 1452} 1453@end 1454 1455