1  //
   2  //  NSDictionary.m
   3  //  CoreFoundation
   4  //
   5  //  Copyright (c) 2014 Apportable. All rights reserved.
   6  //
   7  
   8  #import <Foundation/NSDictionary.h>
   9  
  10  #import <CoreFoundation/CFData.h>
  11  #import <CoreFoundation/CFPropertyList.h>
  12  #import <Foundation/NSArray.h>
  13  #import <Foundation/NSSet.h>
  14  #import <Foundation/NSURL.h>
  15  #include <Foundation/NSError.h>
  16  
  17  #import "CFInternal.h"
  18  #import "CFSortFunctions.h"
  19  #import "NSFastEnumerationEnumerator.h"
  20  #import <Foundation/NSKeyValueObserving.h>
  21  #import "NSObjectInternal.h"
  22  #import "NSStringInternal.h"
  23  
  24  CF_EXPORT Boolean _CFDictionaryIsMutable(CFDictionaryRef ref);
  25  CF_EXPORT void _CFDictionarySetKVOBit(CFDictionaryRef hc, CFIndex bit);
  26  CF_EXPORT NSUInteger _CFDictionaryFastEnumeration(CFDictionaryRef hc, NSFastEnumerationState *state, id __unsafe_unretained stackbuffer[], NSUInteger count);
  27  CF_EXPORT CFDataRef _CFPropertyListCreateXMLData(CFAllocatorRef allocator, CFPropertyListRef propertyList, Boolean checkValidPlist);
  28  
  29  @interface NSDictionary (Internal)
  30  + (id)newWithContentsOf:(id)source immutable:(BOOL)immutable;
  31  @end
  32  
  33  CF_PRIVATE
  34  @interface __NSPlaceholderDictionary : NSMutableDictionary
  35  + (id)mutablePlaceholder;
  36  + (id)immutablePlaceholder;
  37  @end
  38  
  39  CF_PRIVATE
  40  @interface __NSDictionaryObjectEnumerator : __NSFastEnumerationEnumerator
  41  @end
  42  
  43  CF_PRIVATE
  44  @interface __NSCFDictionary : NSMutableDictionary {
  45      unsigned char _cfinfo[4];
  46      unsigned int _bits[4];
  47      void *_callbacks;
  48      id *_values;
  49      id *_keys;
  50  }
  51  @end
  52  
  53  CF_PRIVATE
  54  @interface __NSDictionaryI : NSDictionary {
  55      unsigned int _used:26;
  56      unsigned int _szidx:6;
  57  }
  58  @end
  59  
  60  @implementation __NSDictionaryObjectEnumerator : __NSFastEnumerationEnumerator
  61  
  62  - (id)nextObject
  63  {
  64      return [(NSDictionary *)_obj objectForKey:[super nextObject]];
  65  }
  66  
  67  @end
  68  
  69  @implementation NSDictionary
  70  
  71  + (id)allocWithZone:(NSZone *)zone
  72  {
  73      NSDictionary *dictionary = nil;
  74  
  75      if (self == [NSDictionary class])
  76      {
  77          dictionary = [__NSPlaceholderDictionary immutablePlaceholder];
  78      }
  79      else if (self == [NSMutableDictionary class] || self == [__NSCFDictionary class])
  80      {
  81          // we check for `[__NSCFDictionary class]` because Xcode has a convenience class method defined on NSMutableDictionary
  82          // that returns `self` as the mutable version of the class (as it should). however, since our `__NSCFDictionary` inherits
  83          // from NSMutableDictionary, it also inherits this cateogry class method. `__NSCFDictionary` itself can be either,
  84          // but we err on the side of caution and return a mutable placeholder.
  85          dictionary = [__NSPlaceholderDictionary mutablePlaceholder];
  86      }
  87      else
  88      {
  89          dictionary = [super allocWithZone:zone];
  90      }
  91  
  92      return dictionary;
  93  }
  94  
  95  - (NSUInteger)count
  96  {
  97      NSRequestConcreteImplementation();
  98      return 0;
  99  }
 100  
 101  - (id)objectForKey:(id)aKey
 102  {
 103      NSRequestConcreteImplementation();
 104      return nil;
 105  }
 106  
 107  - (NSEnumerator *)keyEnumerator
 108  {
 109      NSRequestConcreteImplementation();
 110      return nil;
 111  }
 112  
 113  - (NSEnumerator *)objectEnumerator
 114  {
 115      return [[[__NSDictionaryObjectEnumerator alloc] initWithObject:self] autorelease];
 116  }
 117  
 118  - (id)copyWithZone:(NSZone *)zone
 119  {
 120      return [[NSDictionary allocWithZone:zone] initWithDictionary:self copyItems:NO];
 121  }
 122  
 123  - (id)mutableCopyWithZone:(NSZone *)zone
 124  {
 125      return [[NSMutableDictionary allocWithZone:zone] initWithDictionary:self copyItems:NO];
 126  }
 127  
 128  + (BOOL)supportsSecureCoding
 129  {
 130      return YES;
 131  }
 132  
 133  - (NSUInteger)countByEnumeratingWithState:(NSFastEnumerationState *)state objects:(id __unsafe_unretained [])buffer count:(NSUInteger)len
 134  {
 135      // this is technically incorrect and should be refactored to use [self keyEnumerator] instead and manage it's own state
 136      return [[self allKeys] countByEnumeratingWithState:state objects:buffer count:len];
 137  }
 138  
 139  - (CFTypeID)_cfTypeID
 140  {
 141      return CFDictionaryGetTypeID();
 142  }
 143  
 144  - (BOOL)isNSDictionary__
 145  {
 146      return YES;
 147  }
 148  
 149  @end
 150  
 151  @implementation NSMutableDictionary
 152  
 153  + (id)dictionaryWithCapacity:(NSUInteger)numItems
 154  {
 155      return [[(NSMutableDictionary *)[self alloc] initWithCapacity:numItems] autorelease];
 156  }
 157  
 158  - (id)initWithObjects:(const id [])objects forKeys:(const id <NSCopying> [])keys count:(NSUInteger)cnt
 159  {
 160      if ((self = [self initWithCapacity:cnt]))
 161      {
 162          for (NSUInteger i=0; i<cnt; ++i)
 163          {
 164              [self setObject:objects[i] forKey:keys[i]];
 165          }
 166      }
 167      return self;
 168  }
 169  
 170  - (id)initWithCapacity:(NSUInteger)capacity
 171  {
 172      NSRequestConcreteImplementation();
 173      [self release];
 174      return nil;
 175  }
 176  
 177  - (void)removeObjectForKey:(id)aKey
 178  {
 179      NSRequestConcreteImplementation();
 180  }
 181  
 182  - (void)setObject:(id)anObject forKey:(id <NSCopying>)aKey
 183  {
 184      NSRequestConcreteImplementation();
 185  }
 186  
 187  @end
 188  
 189  static CFDictionaryKeyCallBacks sNSCFDictionaryKeyCallBacks = {
 190      0,
 191      &_NSCFRetain2,
 192      &_NSCFRelease2,
 193      &_NSCFCopyDescription,
 194      &_NSCFEqual,
 195      &_NSCFHash
 196  };
 197  
 198  static CFDictionaryValueCallBacks sNSCFDictionaryValueCallBacks = {
 199      0,
 200      &_NSCFRetain2,
 201      &_NSCFRelease2,
 202      &_NSCFCopyDescription,
 203      &_NSCFEqual
 204  };
 205  
 206  static __NSPlaceholderDictionary *mutablePlaceholder = nil;
 207  static __NSPlaceholderDictionary *immutablePlaceholder = nil;
 208  
 209  @implementation __NSPlaceholderDictionary
 210  
 211  + (void)initialize
 212  {
 213  
 214  }
 215  
 216  - (void)removeObjectForKey:(id)key
 217  {
 218      NSRequestConcreteImplementation();
 219  }
 220  
 221  - (void)setObject:(id)obj forKey:(id)key
 222  {
 223      NSRequestConcreteImplementation();
 224  }
 225  
 226  - (NSEnumerator *)keyEnumerator
 227  {
 228      NSRequestConcreteImplementation();
 229      return nil;
 230  }
 231  
 232  - (id)objectForKey:(id)key
 233  {
 234      NSRequestConcreteImplementation();
 235      return nil;
 236  }
 237  
 238  - (NSUInteger)count
 239  {
 240      NSRequestConcreteImplementation();
 241      return 0;
 242  }
 243  
 244  + (id)immutablePlaceholder
 245  {
 246      static dispatch_once_t once = 0L;
 247      dispatch_once(&once, ^{
 248          immutablePlaceholder = [__NSPlaceholderDictionary allocWithZone:nil];
 249      });
 250      return immutablePlaceholder;
 251  }
 252  
 253  + (id)mutablePlaceholder
 254  {
 255      static dispatch_once_t once = 0L;
 256      dispatch_once(&once, ^{
 257          mutablePlaceholder = [__NSPlaceholderDictionary allocWithZone:nil];
 258      });
 259      return mutablePlaceholder;
 260  }
 261  
 262  SINGLETON_RR()
 263  
 264  - (id)initWithContentsOfURL:(NSURL *)url
 265  {
 266      if (url != nil && [url isNSString__])
 267      {
 268          @throw [NSException exceptionWithName:NSInvalidArgumentException reason:@"sent NSString to initWithContentsOfURL - please send a URL" userInfo:nil];
 269          return nil;
 270      }
 271  
 272      return (id)[NSDictionary newWithContentsOf:url immutable:(self == immutablePlaceholder)];
 273  }
 274  
 275  - (id)initWithContentsOfFile:(NSString *)path
 276  {
 277      return (id)[NSDictionary newWithContentsOf:path immutable:(self == immutablePlaceholder)];
 278  }
 279  
 280  - (id)init
 281  {
 282      if (self == mutablePlaceholder)
 283      {
 284          return [self initWithCapacity:0];
 285      }
 286      else
 287      {
 288          return [self initWithObjects:NULL forKeys:NULL count:0];
 289      }
 290  }
 291  
 292  - (id)initWithCapacity:(NSUInteger)capacity
 293  {
 294      if (self == mutablePlaceholder)
 295      {
 296          NSCapacityCheck(capacity, 0x40000000, @"Please rethink the size of the capacity of the dictionary you are creating: %d seems a bit exessive", capacity);
 297          return (id)CFDictionaryCreateMutable(kCFAllocatorDefault, capacity, &sNSCFDictionaryKeyCallBacks, &sNSCFDictionaryValueCallBacks);
 298      }
 299      else
 300      {
 301          [self doesNotRecognizeSelector:_cmd];
 302          return nil;
 303      }
 304  }
 305  
 306  - (id)initWithObjects:(const id [])objects forKeys:(const id <NSCopying> [])keys count:(NSUInteger)cnt
 307  {
 308      if (cnt != 0)
 309      {
 310          if (objects == NULL)
 311          {
 312              [self release];
 313              [NSException raise:NSInvalidArgumentException format:@"Tried to init dictionary with nonzero count but NULL object array"];
 314              return nil;
 315          }
 316          if (keys == NULL)
 317          {
 318              [self release];
 319              [NSException raise:NSInvalidArgumentException format:@"Tried to init dictionary with nonzero count but NULL key array"];
 320              return nil;
 321          }
 322      }
 323  
 324      for (NSUInteger idx = 0; idx < cnt; idx++)
 325      {
 326          if (objects[idx] == nil)
 327          {
 328              [self release];
 329              [NSException raise:NSInvalidArgumentException format:@"Tried to init dictionary with nil object"];
 330              return nil;
 331          }
 332          if (keys[idx] == nil)
 333          {
 334              [self release];
 335              [NSException raise:NSInvalidArgumentException format:@"Tried to init dictionary with nil key"];
 336              return nil;
 337          }
 338      }
 339  
 340      if (self == mutablePlaceholder)
 341      {
 342          CFMutableDictionaryRef dict = CFDictionaryCreateMutable(kCFAllocatorDefault, cnt, &sNSCFDictionaryKeyCallBacks, &sNSCFDictionaryValueCallBacks);
 343          for (NSUInteger idx = 0; idx < cnt; idx++)
 344          {
 345              if ([(NSObject *)keys[idx] respondsToSelector:@selector(copyWithZone:)])
 346              {
 347                  CFDictionarySetValue(dict, keys[idx], objects[idx]);
 348              }
 349              else
 350              {
 351                  CFRelease(dict);
 352                  dict = NULL;
 353                  @throw [NSException exceptionWithName:NSInvalidArgumentException reason:@"" userInfo:@{}];
 354              }
 355          }
 356  
 357          return (id)dict;
 358      }
 359      else
 360      {
 361          return (id)CFDictionaryCreate(kCFAllocatorDefault, (const void **)keys, (const void **)objects, cnt, &sNSCFDictionaryKeyCallBacks, &sNSCFDictionaryValueCallBacks);
 362      }
 363  }
 364  
 365  @end
 366  
 367  @implementation NSDictionary (NSDictionaryCreation)
 368  
 369  + (id)dictionary
 370  {
 371      return [[[self alloc] initWithObjects:NULL forKeys:NULL count:0] autorelease];
 372  }
 373  
 374  + (id)dictionaryWithObject:(id)object forKey:(id <NSCopying>)key
 375  {
 376      return [[[self alloc] initWithObjects:&object forKeys:&key count:1] autorelease];
 377  }
 378  
 379  + (id)dictionaryWithObjects:(const id [])objects forKeys:(const id <NSCopying> [])keys count:(NSUInteger)count
 380  {
 381      return [[[self alloc] initWithObjects:objects forKeys:keys count:count] autorelease];
 382  }
 383  
 384  + (id)dictionaryWithObjectsAndKeys:(id)firstObject, ...
 385  {
 386      va_list args;
 387      va_start(args, firstObject);
 388      id value = firstObject;
 389      id key = va_arg(args, id);
 390      size_t size = 32;
 391      size_t count = 0;
 392      id *objects = malloc(sizeof(id) * size);
 393  
 394      if (UNLIKELY(objects == NULL))
 395      {
 396          return nil;
 397      }
 398  
 399      id *keys = malloc(sizeof(id) * size);
 400  
 401      if (UNLIKELY(keys == NULL))
 402      {
 403          free(objects);
 404          return nil;
 405      }
 406  
 407      while(value != NULL && key != NULL)
 408      {
 409          count++;
 410  
 411          if (count > size)
 412          {
 413              size += 32;
 414              objects = (id *)realloc(objects, sizeof(id) * size);
 415  
 416              if (UNLIKELY(objects == NULL))
 417              {
 418                  free(keys);
 419                  return nil;
 420              }
 421  
 422              keys = (id *)realloc(keys, sizeof(id) * size);
 423  
 424              if (UNLIKELY(keys == NULL))
 425              {
 426                  free(objects);
 427                  return nil;
 428              }
 429          }
 430          objects[count - 1] = value;
 431          keys[count - 1] = key;
 432          value = va_arg(args, id);
 433  
 434          if (value == nil)
 435          {
 436              break;
 437          }
 438  
 439          key = va_arg(args, id);
 440      }
 441  
 442      id dict = [[self alloc] initWithObjects:objects forKeys:keys count:count];
 443      free(objects);
 444      free(keys);
 445      return [dict autorelease];
 446  }
 447  
 448  + (id)dictionaryWithDictionary:(NSDictionary *)dict
 449  {
 450      size_t count = [dict count];
 451      id *objects = NULL;
 452      id *keys = NULL;
 453  
 454      if (count > 0)
 455      {
 456          objects = malloc(sizeof(id) * count);
 457  
 458          if (UNLIKELY(objects == NULL))
 459          {
 460              return NULL;
 461          }
 462  
 463          keys = malloc(sizeof(id) * count);
 464  
 465          if (UNLIKELY(keys == NULL))
 466          {
 467              free(objects);
 468              return NULL;
 469          }
 470      }
 471      [dict getObjects:objects andKeys:keys];
 472      id obj = [[self alloc] initWithObjects:objects forKeys:keys count:count];
 473  
 474      if (objects != NULL)
 475      {
 476          free(objects);
 477      }
 478  
 479      if (keys != NULL)
 480      {
 481          free(keys);
 482      }
 483  
 484      return [obj autorelease];
 485  }
 486  
 487  + (id)dictionaryWithObjects:(NSArray *)objectArray forKeys:(NSArray *)keyArray
 488  {
 489      return [[[self alloc] initWithObjects:objectArray forKeys:keyArray] autorelease];
 490  }
 491  
 492  + (id)dictionaryWithContentsOfFile:(NSString *)path
 493  {
 494      if (path == nil)
 495      {
 496          return nil;
 497      }
 498      
 499      return [[[self alloc] initWithContentsOfURL:[NSURL fileURLWithPath:path]] autorelease];
 500  }
 501  
 502  + (id)dictionaryWithContentsOfURL:(NSURL *)url
 503  {
 504      return [[[self alloc] initWithContentsOfURL:url] autorelease];
 505  }
 506  
 507  + (instancetype)dictionaryWithContentsOfURL:(NSURL *)url error:(NSError **)error
 508  {
 509      // TODO: we should actually pass along any error we get to the user so they have more info
 510      // this is just a quick and dirty implementation
 511      NSDictionary* tmp = [self dictionaryWithContentsOfURL:url];
 512      if (tmp == nil) {
 513          *error = [NSError errorWithDomain:@"NSDictionaryErrorDomain" code:-1 userInfo:nil];
 514      }
 515      return tmp;
 516  }
 517  
 518  - (id)initWithObjectsAndKeys:(id)firstObject, ...
 519  {
 520      va_list args;
 521      va_start(args, firstObject);
 522      id value = firstObject;
 523      id key = va_arg(args, id);
 524      size_t size = 32;
 525      size_t count = 0;
 526      id *values = (id *)malloc(sizeof(id) * size);
 527  
 528      if (UNLIKELY(values == NULL))
 529      {
 530          [self release];
 531          return nil;
 532      }
 533  
 534      id *keys = (id *)malloc(sizeof(id) * size);
 535  
 536      if (UNLIKELY(keys == NULL))
 537      {
 538          free(values);
 539          [self release];
 540          return nil;
 541      }
 542  
 543      while(value != NULL && key != NULL)
 544      {
 545          count++;
 546  
 547          if (count > size)
 548          {
 549              size += 32;
 550              values = (id *)realloc(values, sizeof(id) * size);
 551  
 552              if (UNLIKELY(values == NULL))
 553              {
 554                  free(keys);
 555                  [self release];
 556                  return nil;
 557              }
 558  
 559              keys = (id *)realloc(keys, sizeof(id) * size);
 560              if (UNLIKELY(keys == NULL))
 561              {
 562                  free(values);
 563                  [self release];
 564                  return nil;
 565              }
 566          }
 567          values[count - 1] = value;
 568          keys[count - 1] = key;
 569          value = va_arg(args, id);
 570          key = va_arg(args, id);
 571      }
 572  
 573      id dict = [self initWithObjects:values forKeys:keys count:count];
 574      free(values);
 575      free(keys);
 576      return dict;
 577  }
 578  
 579  - (id)initWithDictionary:(NSDictionary *)otherDictionary
 580  {
 581      size_t count = [otherDictionary count];
 582      id *objects = NULL;
 583      id *keys = NULL;
 584  
 585      if (count > 0)
 586      {
 587          objects = malloc(sizeof(id) * count);
 588  
 589          if (UNLIKELY(objects == NULL))
 590          {
 591              [self release];
 592              return NULL;
 593          }
 594  
 595          keys = malloc(sizeof(id) * count);
 596  
 597          if (UNLIKELY(keys == NULL))
 598          {
 599              [self release];
 600              free(objects);
 601              return NULL;
 602          }
 603      }
 604      [otherDictionary getObjects:objects andKeys:keys];
 605      id dict = [self initWithObjects:objects forKeys:keys count:count];
 606  
 607      if (objects != NULL)
 608      {
 609          free(objects);
 610      }
 611  
 612      if (keys != NULL)
 613      {
 614          free(keys);
 615      }
 616  
 617      return dict;
 618  }
 619  
 620  - (id)initWithDictionary:(NSDictionary *)otherDictionary copyItems:(BOOL)flag
 621  {
 622      size_t count = [otherDictionary count];
 623      id *objects = NULL;
 624      id *keys = NULL;
 625  
 626      if (count > 0)
 627      {
 628          objects = malloc(sizeof(id) * count);
 629  
 630          if (UNLIKELY(objects == NULL))
 631          {
 632              [self release];
 633              return NULL;
 634          }
 635  
 636          keys = malloc(sizeof(id) * count);
 637  
 638          if (UNLIKELY(keys == NULL))
 639          {
 640              free(objects);
 641              [self release];
 642              return NULL;
 643          }
 644      }
 645  
 646      [otherDictionary getObjects:objects andKeys:keys];
 647  
 648      for (int i = 0 ; i < count; i++)
 649      {
 650          if (flag && [objects[i] respondsToSelector:@selector(copyWithZone:)])
 651          {
 652              objects[i] = [objects[i] copy];
 653          }
 654          else
 655          {
 656              objects[i] = [objects[i] retain];
 657          }
 658      }
 659  
 660      id dict = [self initWithObjects:objects forKeys:keys count:count];
 661  
 662      if (objects != NULL)
 663      {
 664          free(objects);
 665      }
 666  
 667      if (keys != NULL)
 668      {
 669          free(keys);
 670      }
 671  
 672      return dict;
 673  }
 674  
 675  - (id)initWithObjects:(NSArray *)objectArray forKeys:(NSArray *)keyArray
 676  {
 677      NSUInteger objectCount = [objectArray count];
 678      NSUInteger keyCount = [keyArray count];
 679  
 680      if (objectCount != keyCount)
 681      {
 682          [NSException raise:NSInvalidArgumentException format:@"Object and key arrays have different number of elements (%d and %d)", objectCount, keyCount];
 683          return nil;
 684      }
 685  
 686      id *objects = malloc(sizeof(id) * objectCount);
 687  
 688      if (UNLIKELY(objects == NULL))
 689      {
 690          [self release];
 691          return nil;
 692      }
 693  
 694      id *keys = malloc(sizeof(id) * keyCount);
 695  
 696      if (UNLIKELY(keys == NULL))
 697      {
 698          [self release];
 699          free(objects);
 700          return nil;
 701      }
 702  
 703      [objectArray getObjects:objects range:NSMakeRange(0, objectCount)];
 704      [keyArray getObjects:keys range:NSMakeRange(0, keyCount)];
 705      id dict = [self initWithObjects:objects forKeys:keys count:objectCount];
 706      free(objects);
 707      free(keys);
 708      return dict;
 709  }
 710  
 711  - (instancetype)initWithObjects:(const id [])objects forKeys:(const id <NSCopying> [])keys count:(NSUInteger)cnt
 712  {
 713      NSRequestConcreteImplementation();
 714      [self release];
 715      return nil;
 716  }
 717  
 718  - (id)initWithContentsOfFile:(NSString *)path
 719  {
 720      BOOL immutable = ![self isKindOfClass:[NSMutableDictionary class]];
 721      [self release];
 722      return [NSDictionary newWithContentsOf:path immutable:immutable];
 723  }
 724  
 725  - (id)initWithContentsOfURL:(NSURL *)url
 726  {
 727      BOOL immutable = ![self isKindOfClass:[NSMutableDictionary class]];
 728      [self release];
 729      return [NSDictionary newWithContentsOf:url immutable:immutable];
 730  }
 731  
 732  - (id)initWithContentsOfURL:(NSURL *)url error:(NSError **)error
 733  {
 734      NSDictionary* tmp = [self initWithContentsOfURL:url];
 735      if (tmp == nil) {
 736          *error = [NSError errorWithDomain:@"NSDictionaryErrorDomain" code:-1 userInfo:nil];
 737      }
 738      return tmp;
 739  }
 740  
 741  @end
 742  
 743  
 744  @implementation NSDictionary (NSExtendedDictionary)
 745  
 746  - (void)__apply:(void (*)(const void *, const void *, void *))applier context:(void *)context
 747  {
 748      for (id<NSCopying> key in self)
 749      {
 750          id value = [self objectForKey:key];
 751          applier(key, value, context);
 752      }
 753  }
 754  
 755  - (NSArray *)allKeys
 756  {
 757      NSUInteger count = [self count];
 758      NSMutableArray *keys = [[NSMutableArray alloc] initWithCapacity:count];
 759      NSEnumerator *enumerator = [self keyEnumerator];
 760      id key = nil;
 761  
 762      while (key = [enumerator nextObject])
 763      {
 764          [keys addObject:key];
 765      }
 766  
 767      NSArray *retval = [keys copy];
 768      [keys release];
 769      return [retval autorelease];
 770  }
 771  
 772  - (NSArray *)allKeysForObject:(id)anObject
 773  {
 774      NSUInteger count = [self count];
 775      NSMutableArray *keys = [[NSMutableArray alloc] initWithCapacity:count];
 776      NSEnumerator *enumerator = [self keyEnumerator];
 777      id key = nil;
 778  
 779      while (key = [enumerator nextObject])
 780      {
 781          if ([[self objectForKey:key] isEqual:anObject])
 782          {
 783              [keys addObject:key];
 784          }
 785      }
 786  
 787      NSArray *retval = [keys copy];
 788      [keys release];
 789      return [retval autorelease];
 790  }
 791  
 792  - (NSArray *)allValues
 793  {
 794      NSArray *keys = [self allKeys];
 795      NSMutableArray *values = [[NSMutableArray alloc] initWithCapacity:[keys count]];
 796  
 797      for (id key in keys)
 798      {
 799          id value = [self objectForKey:key];
 800          [values addObject:value];
 801      }
 802  
 803      NSArray *retval = [values copy];
 804      [values release];
 805      return [retval autorelease];
 806  }
 807  
 808  - (NSString *)description
 809  {
 810      return [self descriptionWithLocale:nil indent:0];
 811  }
 812  
 813  - (NSString *)descriptionWithLocale:(id)locale
 814  {
 815      return [self descriptionWithLocale:locale indent:0];
 816  }
 817  
 818  static NSString *_getDescription(id obj, id locale, int level)
 819  {
 820      if ([obj isKindOfClass:[NSDictionary class]] || [obj isKindOfClass:[NSArray class]])
 821      {
 822          return [obj descriptionWithLocale:locale indent:level + 1];
 823      }
 824      else if ([obj respondsToSelector:@selector(descriptionWithLocale:)])
 825      {
 826          return [obj descriptionWithLocale:locale];
 827      }
 828      else
 829      {
 830          return [obj description];
 831      }
 832  }
 833  
 834  - (NSString *)descriptionWithLocale:(id)locale indent:(NSUInteger)level
 835  {
 836      CFMutableStringRef description = CFStringCreateMutable(kCFAllocatorDefault, 0);
 837      CFStringAppendFormat(description, NULL, CFSTR("%*s{\n"), (int)level * strlen(INDENT), "");
 838      int count = [self count];
 839      id *keys = (id *)malloc(sizeof(id) * count);
 840      [self getObjects:nil andKeys:keys];
 841  
 842      Class checkKeyClass = nil;
 843  
 844      for (int i = 0; i < count; i++)
 845      {
 846          if (checkKeyClass == nil)
 847          {
 848              checkKeyClass = object_getClass(keys[i]);
 849          }
 850          else if (checkKeyClass != object_getClass(keys[i]))
 851          {
 852              checkKeyClass = nil;
 853              break;
 854          }
 855      }
 856  
 857      if (checkKeyClass && [keys[0] respondsToSelector: @selector(compare:)]) // homogeneous, sortable NSDictionary's should be sorted
 858      {
 859          CFIndex *indexes = (CFIndex *)malloc(count * sizeof(CFIndex));
 860          CFSortIndexes(indexes, count, 0, ^(CFIndex i1, CFIndex i2) {
 861              return (CFComparisonResult)[keys[i1] compare: keys[i2]];
 862          });
 863  
 864          for (int i = 0; i < count; i++)
 865          {
 866              id key = keys[indexes[i]];
 867              id value = [self objectForKey:key];
 868              NSString *valueDescription = _getDescription(value, locale, level);
 869              NSString *keyDescription = _getDescription(key, locale, level);
 870              CFStringAppendFormat(description, NULL, CFSTR("%*s%@ = %@;\n"), ((int)level + 1)  * strlen(INDENT), "", keyDescription, valueDescription);
 871          }
 872  
 873          free(indexes);
 874      }
 875      else {
 876          NSEnumerator *enumerator = [self keyEnumerator];
 877  
 878          for (id key  = [enumerator nextObject]; key != nil; key = [enumerator nextObject])
 879          {
 880              id value = [self objectForKey:key];
 881              NSString *valueDescription = _getDescription(value, locale, level);
 882              NSString *keyDescription = _getDescription(key, locale, level);
 883              CFStringAppendFormat(description, NULL, CFSTR("%*s%@ = %@;\n"), ((int)level + 1)  * strlen(INDENT), "", keyDescription, valueDescription);
 884          }
 885      }
 886      CFStringAppendFormat(description, NULL, CFSTR("%*s}"), (int)level * strlen(INDENT), "");
 887      CFStringRef desc = CFStringCreateCopy(kCFAllocatorDefault, description);
 888      CFRelease(description);
 889      free(keys);
 890      return [(NSString *)desc autorelease];
 891  }
 892  
 893  - (NSUInteger)hash
 894  {
 895      return [self count];
 896  }
 897  
 898  - (BOOL)isEqual:(id)other
 899  {
 900      if (![other isNSDictionary__])
 901      {
 902          return NO;
 903      }
 904  
 905      return [self isEqualToDictionary:other];
 906  }
 907  
 908  - (BOOL)isEqualToDictionary:(NSDictionary *)otherDictionary
 909  {
 910      if (self == otherDictionary)
 911      {
 912          return YES;
 913      }
 914  
 915      if (![otherDictionary isKindOfClass:[NSDictionary class]])
 916      {
 917          // @throw [NSException exceptionWithName:NSInvalidArgumentException reason:@"Second argument is not a dictionary" userInfo:nil];
 918          return NO;
 919      }
 920  
 921      if ([self count] != [otherDictionary count])
 922      {
 923          return NO;
 924      }
 925  
 926      for (NSString* key in [self allKeys]) 
 927      {
 928          id val = [self objectForKey:key];
 929          id otherVal = [otherDictionary objectForKey:key];
 930          if (val == otherVal)
 931          {
 932              continue;
 933          }
 934  
 935          if (![val isEqual:otherVal])
 936          {
 937              return NO;
 938          }
 939      }
 940  
 941      return YES;
 942  }
 943  
 944  - (NSEnumerator *)objectEnumerator
 945  {
 946      return [[self allValues] objectEnumerator];
 947  }
 948  
 949  - (NSArray *)objectsForKeys:(NSArray *)keys notFoundMarker:(id)marker
 950  {
 951      NSMutableArray *objects = [[NSMutableArray alloc] initWithCapacity:[keys count]];
 952  
 953      for (id key in keys)
 954      {
 955          id obj = [self objectForKey:key];
 956  
 957          if (obj == nil)
 958          {
 959              obj = marker;
 960          }
 961  
 962          if (obj != nil)
 963          {
 964              [objects addObject:obj];
 965          }
 966      }
 967  
 968      NSArray *objs = [objects copy];
 969      [objects release];
 970      return [objs autorelease];
 971  }
 972  
 973  - (BOOL)writeToFile:(NSString *)path atomically:(BOOL)atomically
 974  {
 975      NSData *data = (NSData *)_CFPropertyListCreateXMLData(kCFAllocatorDefault, (CFPropertyListRef)self, true);
 976      BOOL success = [data writeToFile:path atomically:atomically];
 977      [data release];
 978      return success;
 979  }
 980  
 981  - (BOOL)writeToURL:(NSURL *)url atomically:(BOOL)atomically
 982  {
 983      NSData *data = (NSData *)_CFPropertyListCreateXMLData(kCFAllocatorDefault, (CFPropertyListRef)self, true);
 984      BOOL success = [data writeToURL:url atomically:atomically];
 985      [data release];
 986      return success;
 987  }
 988  
 989  - (NSArray *)keysSortedByValueUsingSelector:(SEL)comparator
 990  {
 991      return [[self allKeys] sortedArrayUsingComparator:^NSComparisonResult(id obj1, id obj2) {
 992          id val1 = [self objectForKey:obj1];
 993          id val2 = [self objectForKey:obj2];
 994          return (NSComparisonResult)[val1 performSelector:comparator withObject:val2];
 995      }];
 996  }
 997  
 998  - (void)getObjects:(id __unsafe_unretained [])objects andKeys:(id __unsafe_unretained [])keys count:(NSUInteger)count
 999  {
1000      if (objects == NULL && keys == NULL)
1001      {
1002          // nothing to do here... move along.
1003          return;
1004      }
1005  
1006      NSEnumerator *enumerator = [self keyEnumerator];
1007      id key = nil;
1008      NSUInteger idx = 0;
1009      while (key = [enumerator nextObject])
1010      {
1011          if (idx >= count) {
1012              break;
1013          }
1014  
1015          if (keys != NULL)
1016          {
1017              keys[idx] = key;
1018          }
1019  
1020          if (objects != NULL)
1021          {
1022              objects[idx] = [self objectForKey:key];
1023          }
1024  
1025          idx++;
1026      }
1027  }
1028  
1029  - (void)getObjects:(id __unsafe_unretained [])objects andKeys:(id __unsafe_unretained [])keys
1030  {
1031      return [self getObjects: objects andKeys: keys count: [self count]];
1032  }
1033  
1034  - (id)objectForKeyedSubscript:(id)key
1035  {
1036      return [self objectForKey:key];
1037  }
1038  
1039  - (void)enumerateKeysAndObjectsUsingBlock:(void (^)(id key, id obj, BOOL *stop))block
1040  {
1041      [self enumerateKeysAndObjectsWithOptions:0 usingBlock:block];
1042  }
1043  
1044  - (void)enumerateKeysAndObjectsWithOptions:(NSEnumerationOptions)opts usingBlock:(void (^)(id key, id obj, BOOL *stop))block
1045  {
1046      NSArray *keys = nil;
1047      if (opts & NSEnumerationReverse)
1048      {
1049          keys = [[[self allKeys] reverseObjectEnumerator] allObjects];
1050      }
1051      else
1052      {
1053          keys = [self allKeys];
1054      }
1055  
1056      if (opts & NSEnumerationConcurrent)
1057      {
1058          __block BOOL stop = NO;
1059          dispatch_apply([keys count], dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_DEFAULT, 0), ^(size_t iter){
1060              if (!stop)
1061              {
1062                  id key = [keys objectAtIndex:iter];
1063                  id obj = [self objectForKey:key];
1064                  block(key, obj, &stop);
1065              }
1066          });
1067      }
1068      else
1069      {
1070          id key = NULL;
1071          BOOL stop = NO;
1072          NSUInteger idx = 0;
1073          NSUInteger count = [self count];
1074  
1075          while(idx < count && (key = [keys objectAtIndex:idx]) && !stop)
1076          {
1077              id obj = [self objectForKey:key];
1078              block(key, obj, &stop);
1079              idx++;
1080          }
1081      }
1082  }
1083  
1084  - (NSArray *)keysSortedByValueUsingComparator:(NSComparator)cmptr
1085  {
1086      return [self keysSortedByValueWithOptions:NSSortStable usingComparator:cmptr];
1087  
1088  }
1089  
1090  - (NSArray *)keysSortedByValueWithOptions:(NSSortOptions)opts usingComparator:(NSComparator)cmptr
1091  {
1092      return [[self allKeys] sortedArrayWithOptions:opts usingComparator:^NSComparisonResult(id obj1, id obj2) {
1093          id val1 = [self objectForKey:obj1];
1094          id val2 = [self objectForKey:obj2];
1095          return cmptr(val1, val2);
1096      }];
1097  }
1098  
1099  - (NSSet *)keysOfEntriesPassingTest:(BOOL (^)(id key, id obj, BOOL *stop))predicate
1100  {
1101      return [self keysOfEntriesWithOptions:0 passingTest:predicate];
1102  }
1103  
1104  - (NSSet *)keysOfEntriesWithOptions:(NSEnumerationOptions)opts passingTest:(BOOL (^)(id key, id obj, BOOL *stop))predicate
1105  {
1106      NSArray *keys = nil;
1107      if (opts & NSEnumerationReverse)
1108      {
1109          keys = [[[self allKeys] reverseObjectEnumerator] allObjects];
1110      }
1111      else
1112      {
1113          keys = [self allKeys];
1114      }
1115  
1116      __block NSMutableSet *found = [[NSMutableSet alloc] initWithCapacity:[keys count]];
1117  
1118      if (opts & NSEnumerationConcurrent)
1119      {
1120          __block BOOL stop = NO;
1121          dispatch_apply([keys count], dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_DEFAULT, 0), ^(size_t iter){
1122              if (!stop)
1123              {
1124                  id key = [keys objectAtIndex:iter];
1125                  id obj = [self objectForKey:key];
1126  
1127                  if (predicate(key, obj, &stop))
1128                  {
1129                      [found addObject:key];
1130                  }
1131              }
1132          });
1133      }
1134      else
1135      {
1136          BOOL stop = NO;
1137          NSUInteger idx = 0;
1138          NSUInteger count = [keys count];
1139  
1140          while (!stop && idx < count)
1141          {
1142              id key = [keys objectAtIndex:idx];
1143              id obj = [self objectForKey:key];
1144  
1145              if (predicate(key, obj, &stop))
1146              {
1147                  [found addObject:key];
1148              }
1149  
1150              idx++;
1151          }
1152      }
1153  
1154      NSSet *set = [found copy];
1155      [found release];
1156      return [set autorelease];
1157  }
1158  
1159  @end
1160  
1161  
1162  @implementation NSMutableDictionary (NSExtendedMutableDictionary)
1163  
1164  - (void)addEntriesFromDictionary:(NSDictionary *)otherDictionary
1165  {
1166      NSEnumerator *enumerator = [otherDictionary keyEnumerator];
1167      id key = nil;
1168  
1169      while (key = [enumerator nextObject])
1170      {
1171          [self setObject:[otherDictionary objectForKey:key] forKey:key];
1172      }
1173  }
1174  
1175  - (void)removeAllObjects
1176  {
1177      NSEnumerator *enumerator = [self keyEnumerator];
1178      id key = nil;
1179  
1180      while (key = [enumerator nextObject])
1181      {
1182          [self removeObjectForKey:key];
1183      }
1184  }
1185  
1186  - (void)removeObjectsForKeys:(NSArray *)keyArray
1187  {
1188      for (id key in keyArray)
1189      {
1190          [self removeObjectForKey:key];
1191      }
1192  }
1193  
1194  - (void)setDictionary:(NSDictionary *)otherDictionary
1195  {
1196      [self removeAllObjects];
1197      [self addEntriesFromDictionary:otherDictionary];
1198  }
1199  
1200  - (void)setObject:(id)obj forKeyedSubscript:(id <NSCopying>)key
1201  {
1202      [self setObject:obj forKey:key];
1203  }
1204  
1205  @end
1206  
1207  @implementation __NSCFDictionary
1208  
1209  + (BOOL)automaticallyNotifiesObserversForKey:(NSString *)key
1210  {
1211      return NO;
1212  }
1213  
1214  - (void)setObservationInfo:(void *)info
1215  {
1216      _CFDictionarySetKVOBit((CFDictionaryRef)self, (CFIndex)info);
1217      [super setObservationInfo:info];
1218  }
1219  
1220  - (void)removeAllObjects
1221  {
1222      if (_CFDictionaryIsMutable((CFDictionaryRef)self))
1223      {
1224          CFDictionaryRemoveAllValues((CFMutableDictionaryRef)self);
1225      }
1226      else
1227      {
1228          NSInvalidMutation();
1229      }
1230  }
1231  
1232  - (void)removeObjectForKey:(id)key
1233  {
1234      if (_CFDictionaryIsMutable((CFDictionaryRef)self))
1235      {
1236          if (key == nil)
1237          {
1238              @throw [NSException exceptionWithName:NSInvalidArgumentException reason:@"Cannot remove a nil key" userInfo:nil];
1239              return;
1240          }
1241  
1242          CFDictionaryRemoveValue((CFMutableDictionaryRef)self, (const void *)key);
1243      }
1244      else
1245      {
1246          NSInvalidMutation();
1247      }
1248  }
1249  
1250  - (void)setObject:(id)obj forKey:(id)key
1251  {
1252      if (_CFDictionaryIsMutable((CFDictionaryRef)self))
1253      {
1254          if ((obj == nil) || (key == nil))
1255          {
1256              @throw [NSException exceptionWithName:NSInvalidArgumentException reason:@"Cannot set nil objects nor nil keys" userInfo:nil];
1257              return;
1258          }
1259  
1260          [self willChangeValueForKey:key];
1261          CFDictionarySetValue((CFMutableDictionaryRef)self, (const void *)key, (const void *)obj);
1262          [self didChangeValueForKey:key];
1263      }
1264      else
1265      {
1266          NSInvalidMutation();
1267      }
1268  }
1269  
1270  - (NSEnumerator *)keyEnumerator
1271  {
1272      return [[[__NSFastEnumerationEnumerator alloc] initWithObject:self] autorelease];
1273  }
1274  
1275  - (NSUInteger)countByEnumeratingWithState:(NSFastEnumerationState *)state objects:(id __unsafe_unretained [])buffer count:(NSUInteger)len
1276  {
1277      return _CFDictionaryFastEnumeration((CFDictionaryRef)self, state, buffer, len);
1278  }
1279  
1280  - (id)objectForKey:(id)key
1281  {
1282      if (key == nil)
1283      {
1284          return nil;
1285      }
1286      return (id)CFDictionaryGetValue((CFDictionaryRef)self, (const void *)key);
1287  }
1288  
1289  - (NSUInteger)count
1290  {
1291      return CFDictionaryGetCount((CFDictionaryRef)self);
1292  }
1293  
1294  - (void)getObjects:(id [])objects andKeys:(id [])keys count:(NSUInteger)count
1295  {
1296      // fastpath: if the provided buffers are large enough, just defer to CFDictionary
1297      if (count >= self.count) {
1298          return [self getObjects: objects andKeys: keys];
1299      }
1300  
1301      // otherwise, do it ourselves
1302      NSUInteger index = 0;
1303      for (id key in self) {
1304          if (index >= count) {
1305              break;
1306          }
1307  
1308          keys[index] = key;
1309          objects[index] = [self objectForKey: key];
1310          ++index;
1311      }
1312  }
1313  
1314  - (void)getObjects:(id [])objects andKeys:(id [])keys
1315  {
1316      CFDictionaryGetKeysAndValues((CFDictionaryRef)self, (const void **)keys, (const void **)objects);
1317  }
1318  
1319  - (id)mutableCopyWithZone:(NSZone *)zone
1320  {
1321      return (id)CFDictionaryCreateMutableCopy(kCFAllocatorDefault, 0, (CFDictionaryRef)self);
1322  }
1323  
1324  - (id)copyWithZone:(NSZone *)zone
1325  {
1326      return (id)CFDictionaryCreateCopy(kCFAllocatorDefault, (CFDictionaryRef)self);
1327  }
1328  
1329  - (Class)classForCoder
1330  {
1331      if (_CFDictionaryIsMutable((CFDictionaryRef)self))
1332      {
1333          return [NSMutableDictionary class];
1334      }
1335      else
1336      {
1337          return [NSDictionary class];
1338      }
1339  }
1340  
1341  - (NSUInteger)retainCount
1342  {
1343      return CFGetRetainCount((CFTypeRef)self);
1344  }
1345  
1346  - (BOOL)_isDeallocating
1347  {
1348      return _CFIsDeallocating((CFTypeRef)self);
1349  }
1350  
1351  - (BOOL)_tryRetain
1352  {
1353      return _CFTryRetain((CFTypeRef)self) != NULL;
1354  }
1355  
1356  - (oneway void)release
1357  {
1358      CFRelease((CFTypeRef)self);
1359  }
1360  
1361  - (id)retain
1362  {
1363      return (id)CFRetain((CFTypeRef)self);
1364  }
1365  
1366  - (NSUInteger)hash
1367  {
1368      return CFHash((CFTypeRef)self);
1369  }
1370  
1371  - (BOOL)isEqual:(id)obj
1372  {
1373      if (obj == nil)
1374      {
1375          return NO;
1376      }
1377  
1378      return CFEqual((CFTypeRef)self, (CFTypeRef)obj);
1379  }
1380  
1381  @end
1382  
1383  @implementation __NSDictionaryI
1384  
1385  + (id)allocWithZone:(NSZone *)zone
1386  {
1387      return (id)[__NSPlaceholderDictionary allocWithZone:zone];
1388  }
1389  
1390  + (BOOL)automaticallyNotifiesObserversForKey:(NSString *)key
1391  {
1392      return NO;
1393  }
1394  
1395  + (id)__new:(const id *)objects :(const id *)keys :(NSUInteger)count :(BOOL)immutable :(BOOL)copyKeys
1396  {
1397      NSUInteger sz = count * sizeof(id);
1398      __NSDictionaryI *dict = ___CFAllocateObject2(self, sz * 2);
1399      dict->_used = count;
1400      id *keysAndObjects = (id *)object_getIndexedIvars(dict);
1401  
1402      for (NSUInteger idx = 0; idx < count * 2; idx += 2)
1403      {
1404          keysAndObjects[idx] = [keys[idx / 2] copy];
1405          keysAndObjects[idx + 1] = [objects[idx / 2] retain];
1406      }
1407  
1408      return dict;
1409  }
1410  
1411  /*
1412  // add this in when __NSDictionaryM is implemented
1413  - (id)mutableCopyWithZone:(NSZone *)zone
1414  {
1415  
1416  }
1417  */
1418  
1419  - (void)dealloc
1420  {
1421      id *keysAndObjects = (id *)object_getIndexedIvars(self);
1422  
1423      for (NSUInteger idx = 0; idx < _used * 2; idx += 2)
1424      {
1425          [keysAndObjects[idx] release];
1426          [keysAndObjects[idx + 1] release];
1427      }
1428  
1429      [super dealloc];
1430  }
1431  
1432  - (id)copyWithZone:(NSZone *)zone
1433  {
1434      return [self retain];
1435  }
1436  
1437  - (NSUInteger)countByEnumeratingWithState:(NSFastEnumerationState *)state objects:(id __unsafe_unretained [])buffer count:(NSUInteger)len
1438  {
1439      id *keysAndObjects = NULL;
1440      state->extra[0] = [self count];
1441  
1442      if (state->state >= state->extra[0])
1443      {
1444          return 0;
1445      }
1446      
1447      if (state->extra[1] == 0)
1448      {
1449          state->extra[1] = (unsigned long)object_getIndexedIvars(self);
1450      }
1451  
1452      keysAndObjects = (id *)state->extra[1];
1453      
1454      if (state->mutationsPtr == NULL)
1455      {
1456          state->mutationsPtr = &state->extra[0];
1457      }
1458      
1459      id key = keysAndObjects[0];
1460      NSUInteger idx = 0;
1461      
1462      while (key != nil && idx < len && idx < state->extra[0])
1463      {
1464          buffer[idx] = key;
1465          key = keysAndObjects[idx * 2];
1466          idx++;
1467      }
1468  
1469      state->state += idx;
1470      state->extra[1] += sizeof(id) * idx * 2;
1471      state->itemsPtr = buffer;
1472      return idx;
1473  }
1474  
1475  - (void)getObjects:(id __unsafe_unretained [])objects andKeys:(id __unsafe_unretained [])keys count: (NSUInteger)count
1476  {
1477      id *keysAndObjects = (id *)object_getIndexedIvars(self);
1478  
1479      for (NSUInteger idx = 0; idx < _used * 2 && idx < count * 2; idx += 2)
1480      {
1481          keys[idx] = keysAndObjects[idx];
1482          objects[idx] = keysAndObjects[idx + 1];
1483      }
1484  }
1485  
1486  - (void)getObjects:(id __unsafe_unretained [])objects andKeys:(id __unsafe_unretained [])keys
1487  {
1488      return [self getObjects: objects andKeys: keys count: _used];
1489  }
1490  
1491  - (NSEnumerator *)keyEnumerator
1492  {
1493      return [[[__NSFastEnumerationEnumerator alloc] initWithObject:self] autorelease];
1494  }
1495  
1496  - (id)objectForKey:(id)key
1497  {
1498      id *keysAndObjects = (id *)object_getIndexedIvars(self);
1499      // NOTE: This is probably ineffecient and should be refactored somewhat for speed
1500      // thankfully NSDictionaryI should only be used for small dictionaries so the perf
1501      // hit should be relatively small
1502  
1503      for (NSUInteger idx = 0; idx < _used * 2; idx += 2)
1504      {
1505          if ([keysAndObjects[idx] hash] == [key hash])
1506          {
1507              if ([keysAndObjects[idx] isEqual:key])
1508              {
1509                  return keysAndObjects[idx + 1];
1510              }
1511          }
1512      }
1513      return nil;
1514  }
1515  
1516  - (NSUInteger)count
1517  {
1518      return _used;
1519  }
1520  
1521  @end