libkern/c++/OSDictionary.cpp

   1 /*
   2  * Copyright (c) 2000 Apple Computer, Inc. All rights reserved.
   3  *
   4  * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
   5  *
   6  * This file contains Original Code and/or Modifications of Original Code
   7  * as defined in and that are subject to the Apple Public Source License
   8  * Version 2.0 (the 'License'). You may not use this file except in
   9  * compliance with the License. The rights granted to you under the License
  10  * may not be used to create, or enable the creation or redistribution of,
  11  * unlawful or unlicensed copies of an Apple operating system, or to
  12  * circumvent, violate, or enable the circumvention or violation of, any
  13  * terms of an Apple operating system software license agreement.
  14  *
  15  * Please obtain a copy of the License at
  16  * http://www.opensource.apple.com/apsl/ and read it before using this file.
  17  *
  18  * The Original Code and all software distributed under the License are
  19  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  20  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  21  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  22  * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
  23  * Please see the License for the specific language governing rights and
  24  * limitations under the License.
  25  *
  26  * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
  27  */
  28 /* OSDictionary.m created by rsulack on Fri 12-Sep-1997 */
  29 /* OSDictionary.cpp converted to C++ by gvdl on Fri 1998-10-30 */
  30 /* OSDictionary.cpp rewritten by gvdl on Fri 1998-10-30 */
  31
  32 #define IOKIT_ENABLE_SHARED_PTR
  33
  34 #include <libkern/c++/OSArray.h>
  35 #include <libkern/c++/OSCollectionIterator.h>
  36 #include <libkern/c++/OSDictionary.h>
  37 #include <libkern/c++/OSLib.h>
  38 #include <libkern/c++/OSSerialize.h>
  39 #include <libkern/c++/OSSharedPtr.h>
  40 #include <libkern/c++/OSSymbol.h>
  41 #include <os/cpp_util.h>
  42
  43 #define super OSCollection
  44
  45 OSDefineMetaClassAndStructorsWithZone(OSDictionary, OSCollection,
  46     (zone_create_flags_t) (ZC_CACHING | ZC_ZFREE_CLEARMEM))
  47 OSMetaClassDefineReservedUnused(OSDictionary, 0);
  48 OSMetaClassDefineReservedUnused(OSDictionary, 1);
  49 OSMetaClassDefineReservedUnused(OSDictionary, 2);
  50 OSMetaClassDefineReservedUnused(OSDictionary, 3);
  51 OSMetaClassDefineReservedUnused(OSDictionary, 4);
  52 OSMetaClassDefineReservedUnused(OSDictionary, 5);
  53 OSMetaClassDefineReservedUnused(OSDictionary, 6);
  54 OSMetaClassDefineReservedUnused(OSDictionary, 7);
  55
  56 #define EXT_CAST(obj) \
  57     reinterpret_cast<OSObject *>(const_cast<OSMetaClassBase *>(obj))
  58
  59 extern "C" {
  60 void qsort(void *, size_t, size_t, int (*)(const void *, const void *));
  61 }
  62
  63 int
  64 OSDictionary::dictEntry::compare(const void *_e1, const void *_e2)
  65 {
  66         const OSDictionary::dictEntry *e1 = (const OSDictionary::dictEntry *)_e1;
  67         const OSDictionary::dictEntry *e2 = (const OSDictionary::dictEntry *)_e2;
  68
  69         if ((uintptr_t)e1->key.get() == (uintptr_t)e2->key.get()) {
  70                 return 0;
  71         }
  72
  73         return (uintptr_t)e1->key.get() > (uintptr_t)e2->key.get() ? 1 : -1;
  74 }
  75
  76 void
  77 OSDictionary::sortBySymbol(void)
  78 {
  79         qsort(dictionary, count, sizeof(OSDictionary::dictEntry),
  80             &OSDictionary::dictEntry::compare);
  81 }
  82
  83 bool
  84 OSDictionary::initWithCapacity(unsigned int inCapacity)
  85 {
  86         if (!super::init()) {
  87                 return false;
  88         }
  89
  90         if (inCapacity > (UINT_MAX / sizeof(dictEntry))) {
  91                 return false;
  92         }
  93
  94         unsigned int size = inCapacity * sizeof(dictEntry);
  95 //fOptions |= kSort;
  96
  97         dictionary = (dictEntry *) kalloc_container(size);
  98         if (!dictionary) {
  99                 return false;
 100         }
 101
 102         os::uninitialized_value_construct(dictionary, dictionary + inCapacity);
 103         OSCONTAINER_ACCUMSIZE(size);
 104
 105         count = 0;
 106         capacity = inCapacity;
 107         capacityIncrement = (inCapacity)? inCapacity : 16;
 108
 109         return true;
 110 }
 111
 112 bool
 113 OSDictionary::initWithObjects(const OSObject *objects[],
 114     const OSSymbol *keys[],
 115     unsigned int theCount,
 116     unsigned int theCapacity)
 117 {
 118         unsigned int newCapacity = theCount;
 119
 120         if (!objects || !keys) {
 121                 return false;
 122         }
 123
 124         if (theCapacity) {
 125                 if (theCount > theCapacity) {
 126                         return false;
 127                 }
 128
 129                 newCapacity = theCapacity;
 130         }
 131
 132         if (!initWithCapacity(newCapacity)) {
 133                 return false;
 134         }
 135
 136         for (unsigned int i = 0; i < theCount; i++) {
 137                 const OSMetaClassBase *newObject = *objects++;
 138
 139                 if (!newObject || !keys[i] || !setObject(keys[i], newObject)) {
 140                         return false;
 141                 }
 142         }
 143
 144         return true;
 145 }
 146
 147 bool
 148 OSDictionary::initWithObjects(const OSObject *objects[],
 149     const OSString *keys[],
 150     unsigned int theCount,
 151     unsigned int theCapacity)
 152 {
 153         unsigned int newCapacity = theCount;
 154
 155         if (!objects || !keys) {
 156                 return false;
 157         }
 158
 159         if (theCapacity) {
 160                 if (theCount > theCapacity) {
 161                         return false;
 162                 }
 163
 164                 newCapacity = theCapacity;
 165         }
 166
 167         if (!initWithCapacity(newCapacity)) {
 168                 return false;
 169         }
 170
 171         for (unsigned int i = 0; i < theCount; i++) {
 172                 OSSharedPtr<const OSSymbol> key = OSSymbol::withString(*keys++);
 173                 const OSMetaClassBase *newObject = *objects++;
 174
 175                 if (!key) {
 176                         return false;
 177                 }
 178
 179                 if (!newObject || !setObject(key.get(), newObject)) {
 180                         return false;
 181                 }
 182         }
 183
 184         return true;
 185 }
 186
 187 bool
 188 OSDictionary::initWithDictionary(const OSDictionary *dict,
 189     unsigned int theCapacity)
 190 {
 191         unsigned int newCapacity;
 192
 193         if (!dict) {
 194                 return false;
 195         }
 196
 197         newCapacity = dict->count;
 198
 199         if (theCapacity) {
 200                 if (dict->count > theCapacity) {
 201                         return false;
 202                 }
 203
 204                 newCapacity = theCapacity;
 205         }
 206
 207         if (!initWithCapacity(newCapacity)) {
 208                 return false;
 209         }
 210
 211         count = dict->count;
 212         for (unsigned int i = 0; i < count; i++) {
 213                 dictionary[i].key = dict->dictionary[i].key;
 214                 dictionary[i].value = dict->dictionary[i].value;
 215         }
 216
 217         if ((kSort & fOptions) && !(kSort & dict->fOptions)) {
 218                 sortBySymbol();
 219         }
 220
 221         return true;
 222 }
 223
 224 OSSharedPtr<OSDictionary>
 225 OSDictionary::withCapacity(unsigned int capacity)
 226 {
 227         OSSharedPtr<OSDictionary> me = OSMakeShared<OSDictionary>();
 228
 229         if (me && !me->initWithCapacity(capacity)) {
 230                 return nullptr;
 231         }
 232
 233         return me;
 234 }
 235
 236 OSSharedPtr<OSDictionary>
 237 OSDictionary::withObjects(const OSObject *objects[],
 238     const OSSymbol *keys[],
 239     unsigned int count,
 240     unsigned int capacity)
 241 {
 242         OSSharedPtr<OSDictionary> me = OSMakeShared<OSDictionary>();
 243
 244         if (me && !me->initWithObjects(objects, keys, count, capacity)) {
 245                 return nullptr;
 246         }
 247
 248         return me;
 249 }
 250
 251 OSSharedPtr<OSDictionary>
 252 OSDictionary::withObjects(const OSObject *objects[],
 253     const OSString *keys[],
 254     unsigned int count,
 255     unsigned int capacity)
 256 {
 257         OSSharedPtr<OSDictionary> me = OSMakeShared<OSDictionary>();
 258
 259         if (me && !me->initWithObjects(objects, keys, count, capacity)) {
 260                 return nullptr;
 261         }
 262
 263         return me;
 264 }
 265
 266 OSSharedPtr<OSDictionary>
 267 OSDictionary::withDictionary(const OSDictionary *dict,
 268     unsigned int capacity)
 269 {
 270         OSSharedPtr<OSDictionary> me = OSMakeShared<OSDictionary>();
 271
 272         if (me && !me->initWithDictionary(dict, capacity)) {
 273                 return nullptr;
 274         }
 275
 276         return me;
 277 }
 278
 279 void
 280 OSDictionary::free()
 281 {
 282         (void) super::setOptions(0, kImmutable);
 283         flushCollection();
 284         if (dictionary) {
 285                 kfree(dictionary, capacity * sizeof(dictEntry));
 286                 OSCONTAINER_ACCUMSIZE( -(capacity * sizeof(dictEntry)));
 287         }
 288
 289         super::free();
 290 }
 291
 292 unsigned int
 293 OSDictionary::getCount() const
 294 {
 295         return count;
 296 }
 297 unsigned int
 298 OSDictionary::getCapacity() const
 299 {
 300         return capacity;
 301 }
 302
 303 unsigned int
 304 OSDictionary::getCapacityIncrement() const
 305 {
 306         return capacityIncrement;
 307 }
 308
 309 unsigned int
 310 OSDictionary::setCapacityIncrement(unsigned int increment)
 311 {
 312         capacityIncrement = (increment)? increment : 16;
 313
 314         return capacityIncrement;
 315 }
 316
 317 unsigned int
 318 OSDictionary::ensureCapacity(unsigned int newCapacity)
 319 {
 320         dictEntry *newDict;
 321         vm_size_t finalCapacity;
 322         vm_size_t oldSize, newSize;
 323
 324         if (newCapacity <= capacity) {
 325                 return capacity;
 326         }
 327
 328         // round up
 329         finalCapacity = (((newCapacity - 1) / capacityIncrement) + 1)
 330             * capacityIncrement;
 331
 332         // integer overflow check
 333         if (finalCapacity < newCapacity) {
 334                 return capacity;
 335         }
 336
 337         newSize = sizeof(dictEntry) * finalCapacity;
 338
 339         newDict = (dictEntry *) kallocp_container(&newSize);
 340         if (newDict) {
 341                 // use all of the actual allocation size
 342                 finalCapacity = (newSize / sizeof(dictEntry));
 343                 if (finalCapacity > UINT_MAX) {
 344                         // failure, too large
 345                         kfree(newDict, newSize);
 346                         return capacity;
 347                 }
 348
 349                 oldSize = sizeof(dictEntry) * capacity;
 350
 351                 os::uninitialized_move(dictionary, dictionary + capacity, newDict);
 352                 os::uninitialized_value_construct(newDict + capacity, newDict + finalCapacity);
 353                 os::destroy(dictionary, dictionary + capacity);
 354
 355                 OSCONTAINER_ACCUMSIZE(((size_t)newSize) - ((size_t)oldSize));
 356                 kfree(dictionary, oldSize);
 357
 358                 dictionary = newDict;
 359                 capacity = (unsigned int) finalCapacity;
 360         }
 361
 362         return capacity;
 363 }
 364
 365 void
 366 OSDictionary::flushCollection()
 367 {
 368         haveUpdated();
 369
 370         for (unsigned int i = 0; i < count; i++) {
 371                 dictionary[i].key->taggedRelease(OSTypeID(OSCollection));
 372                 dictionary[i].value->taggedRelease(OSTypeID(OSCollection));
 373         }
 374         count = 0;
 375 }
 376
 377 bool
 378 OSDictionary::
 379 setObject(const OSSymbol *aKey, const OSMetaClassBase *anObject, bool onlyAdd)
 380 {
 381         unsigned int i;
 382         bool exists;
 383
 384         if (!anObject || !aKey) {
 385                 return false;
 386         }
 387
 388         // if the key exists, replace the object
 389
 390         if (fOptions & kSort) {
 391                 i = OSSymbol::bsearch(aKey, &dictionary[0], count, sizeof(dictionary[0]));
 392                 exists = (i < count) && (aKey == dictionary[i].key);
 393         } else {
 394                 for (exists = false, i = 0; i < count; i++) {
 395                         if ((exists = (aKey == dictionary[i].key))) {
 396                                 break;
 397                         }
 398                 }
 399         }
 400
 401         if (exists) {
 402                 if (onlyAdd) {
 403                         return false;
 404                 }
 405
 406                 OSTaggedSharedPtr<const OSMetaClassBase, OSCollection> oldObject;
 407
 408                 haveUpdated();
 409
 410                 dictionary[i].value.reset(anObject, OSRetain);
 411                 return true;
 412         }
 413
 414         // add new key, possibly extending our capacity
 415         if (count >= capacity && count >= ensureCapacity(count + 1)) {
 416                 return false;
 417         }
 418
 419         haveUpdated();
 420
 421         new (&dictionary[count]) dictEntry();
 422         os::move_backward(&dictionary[i], &dictionary[count], &dictionary[count + 1]);
 423
 424         dictionary[i].key.reset(aKey, OSRetain);
 425         dictionary[i].value.reset(anObject, OSRetain);
 426         count++;
 427
 428         return true;
 429 }
 430
 431 bool
 432 OSDictionary::
 433 setObject(const OSSymbol *aKey, const OSMetaClassBase *anObject)
 434 {
 435         return setObject(aKey, anObject, false);
 436 }
 437
 438 bool
 439 OSDictionary::setObject(OSSharedPtr<const OSSymbol> const& aKey, OSSharedPtr<const OSMetaClassBase> const& anObject)
 440 {
 441         return setObject(aKey.get(), anObject.get());
 442 }
 443
 444 bool
 445 OSDictionary::setObject(const OSString* aKey, OSSharedPtr<const OSMetaClassBase> const& anObject)
 446 {
 447         return setObject(aKey, anObject.get());
 448 }
 449
 450 bool
 451 OSDictionary::setObject(const char* aKey, OSSharedPtr<const OSMetaClassBase> const& anObject)
 452 {
 453         return setObject(aKey, anObject.get());
 454 }
 455
 456 void
 457 OSDictionary::removeObject(const OSSymbol *aKey)
 458 {
 459         unsigned int i;
 460         bool exists;
 461
 462         if (!aKey) {
 463                 return;
 464         }
 465
 466         // if the key exists, remove the object
 467
 468         if (fOptions & kSort) {
 469                 i = OSSymbol::bsearch(aKey, &dictionary[0], count, sizeof(dictionary[0]));
 470                 exists = (i < count) && (aKey == dictionary[i].key);
 471         } else {
 472                 for (exists = false, i = 0; i < count; i++) {
 473                         if ((exists = (aKey == dictionary[i].key))) {
 474                                 break;
 475                         }
 476                 }
 477         }
 478
 479         if (exists) {
 480                 dictEntry oldEntry = dictionary[i];
 481
 482                 haveUpdated();
 483
 484                 count--;
 485                 bcopy(&dictionary[i + 1], &dictionary[i], (count - i) * sizeof(dictionary[0]));
 486
 487                 oldEntry.key->taggedRelease(OSTypeID(OSCollection));
 488                 oldEntry.value->taggedRelease(OSTypeID(OSCollection));
 489                 return;
 490         }
 491 }
 492
 493
 494 // Returns true on success, false on an error condition.
 495 bool
 496 OSDictionary::merge(const OSDictionary *srcDict)
 497 {
 498         const OSSymbol * sym;
 499         OSSharedPtr<OSCollectionIterator> iter;
 500
 501         if (!OSDynamicCast(OSDictionary, srcDict)) {
 502                 return false;
 503         }
 504
 505         iter = OSCollectionIterator::withCollection(const_cast<OSDictionary *>(srcDict));
 506         if (!iter) {
 507                 return false;
 508         }
 509
 510         while ((sym = (const OSSymbol *)iter->getNextObject())) {
 511                 const OSMetaClassBase * obj;
 512
 513                 obj = srcDict->getObject(sym);
 514                 if (!setObject(sym, obj)) {
 515                         return false;
 516                 }
 517         }
 518
 519         return true;
 520 }
 521
 522 OSObject *
 523 OSDictionary::getObject(const OSSymbol *aKey) const
 524 {
 525         unsigned int i, l = 0, r = count;
 526
 527         if (!aKey) {
 528                 return NULL;
 529         }
 530
 531         // if the key exists, return the object
 532         //
 533         // inline OSSymbol::bsearch in this performance critical codepath
 534         // for performance, the compiler can't do that due to the genericity
 535         // of OSSymbol::bsearch
 536         //
 537         // If we have less than 4 objects, scanning is faster.
 538         if (count > 4 && (fOptions & kSort)) {
 539                 while (l < r) {
 540                         i = (l + r) / 2;
 541                         if (aKey == dictionary[i].key) {
 542                                 return const_cast<OSObject *> ((const OSObject *)dictionary[i].value.get());
 543                         }
 544
 545                         if ((uintptr_t)aKey < (uintptr_t)dictionary[i].key.get()) {
 546                                 r = i;
 547                         } else {
 548                                 l = i + 1;
 549                         }
 550                 }
 551         } else {
 552                 for (i = l; i < r; i++) {
 553                         if (aKey == dictionary[i].key) {
 554                                 return const_cast<OSObject *> ((const OSObject *)dictionary[i].value.get());
 555                         }
 556                 }
 557         }
 558
 559         return NULL;
 560 }
 561
 562 // Wrapper macros
 563 #define OBJECT_WRAP_1(cmd, k)                                           \
 564 {                                                                       \
 565     OSSharedPtr<const OSSymbol> tmpKey = k;                                         \
 566     OSObject *retObj = NULL;                                            \
 567     if (tmpKey) {                                                       \
 568         retObj = cmd(tmpKey.get());                                           \
 569     }                                                                   \
 570     return retObj;                                                      \
 571 }
 572
 573 #define OBJECT_WRAP_2(cmd, k, o)                                        \
 574 {                                                                       \
 575     OSSharedPtr<const OSSymbol> tmpKey = k;                                         \
 576     bool ret = cmd(tmpKey.get(), o);                                          \
 577                                                                         \
 578     return ret;                                                         \
 579 }
 580
 581 #define OBJECT_WRAP_3(cmd, k)                                           \
 582 {                                                                       \
 583     OSSharedPtr<const OSSymbol> tmpKey = k;                                         \
 584     if (tmpKey) {                                                       \
 585         cmd(tmpKey.get());                                                    \
 586     }                                                                   \
 587 }
 588
 589
 590 bool
 591 OSDictionary::setObject(const OSString *aKey, const OSMetaClassBase *anObject)
 592 OBJECT_WRAP_2(setObject, OSSymbol::withString(aKey), anObject)
 593 bool
 594 OSDictionary::setObject(const char *aKey, const OSMetaClassBase *anObject)
 595 OBJECT_WRAP_2(setObject, OSSymbol::withCString(aKey), anObject)
 596
 597 OSObject *OSDictionary::getObject(const OSString * aKey) const
 598 OBJECT_WRAP_1(getObject, OSSymbol::existingSymbolForString(aKey))
 599 OSObject *OSDictionary::getObject(const char *aKey) const
 600 OBJECT_WRAP_1(getObject, OSSymbol::existingSymbolForCString(aKey))
 601
 602 void
 603 OSDictionary::removeObject(const OSString *aKey)
 604 OBJECT_WRAP_3(removeObject, OSSymbol::existingSymbolForString(aKey))
 605 void
 606 OSDictionary::removeObject(const char *aKey)
 607 OBJECT_WRAP_3(removeObject, OSSymbol::existingSymbolForCString(aKey))
 608
 609 bool
 610 OSDictionary::isEqualTo(const OSDictionary *srcDict, const OSCollection *keys) const
 611 {
 612         OSSharedPtr<OSCollectionIterator> iter;
 613         unsigned int keysCount;
 614         const OSMetaClassBase * obj1;
 615         const OSMetaClassBase * obj2;
 616         OSString * aKey;
 617         bool ret;
 618
 619         if (this == srcDict) {
 620                 return true;
 621         }
 622
 623         keysCount = keys->getCount();
 624         if ((count < keysCount) || (srcDict->getCount() < keysCount)) {
 625                 return false;
 626         }
 627
 628         iter = OSCollectionIterator::withCollection(keys);
 629         if (!iter) {
 630                 return false;
 631         }
 632
 633         ret = true;
 634         while ((aKey = OSDynamicCast(OSString, iter->getNextObject()))) {
 635                 obj1 = getObject(aKey);
 636                 obj2 = srcDict->getObject(aKey);
 637                 if (!obj1 || !obj2) {
 638                         ret = false;
 639                         break;
 640                 }
 641
 642                 if (!obj1->isEqualTo(obj2)) {
 643                         ret = false;
 644                         break;
 645                 }
 646         }
 647
 648         return ret;
 649 }
 650
 651 bool
 652 OSDictionary::isEqualTo(const OSDictionary *srcDict) const
 653 {
 654         unsigned int i;
 655         const OSMetaClassBase * obj;
 656
 657         if (this == srcDict) {
 658                 return true;
 659         }
 660
 661         if (count != srcDict->getCount()) {
 662                 return false;
 663         }
 664
 665         for (i = 0; i < count; i++) {
 666                 obj = srcDict->getObject(dictionary[i].key.get());
 667                 if (!obj) {
 668                         return false;
 669                 }
 670
 671                 if (!dictionary[i].value->isEqualTo(obj)) {
 672                         return false;
 673                 }
 674         }
 675
 676         return true;
 677 }
 678
 679 bool
 680 OSDictionary::isEqualTo(const OSMetaClassBase *anObject) const
 681 {
 682         OSDictionary *dict;
 683
 684         dict = OSDynamicCast(OSDictionary, anObject);
 685         if (dict) {
 686                 return isEqualTo(dict);
 687         } else {
 688                 return false;
 689         }
 690 }
 691
 692 unsigned int
 693 OSDictionary::iteratorSize() const
 694 {
 695         return sizeof(unsigned int);
 696 }
 697
 698 bool
 699 OSDictionary::initIterator(void *inIterator) const
 700 {
 701         unsigned int *iteratorP = (unsigned int *) inIterator;
 702
 703         *iteratorP = 0;
 704         return true;
 705 }
 706
 707 bool
 708 OSDictionary::getNextObjectForIterator(void *inIterator, OSObject **ret) const
 709 {
 710         unsigned int *iteratorP = (unsigned int *) inIterator;
 711         unsigned int index = (*iteratorP)++;
 712
 713         if (index < count) {
 714                 *ret = const_cast<OSSymbol*>(dictionary[index].key.get());
 715         } else {
 716                 *ret = NULL;
 717         }
 718
 719         return *ret != NULL;
 720 }
 721
 722 bool
 723 OSDictionary::serialize(OSSerialize *s) const
 724 {
 725         if (s->previouslySerialized(this)) {
 726                 return true;
 727         }
 728
 729         if (!s->addXMLStartTag(this, "dict")) {
 730                 return false;
 731         }
 732
 733         for (unsigned i = 0; i < count; i++) {
 734                 const OSSymbol *key = dictionary[i].key.get();
 735
 736                 // due the nature of the XML syntax, this must be a symbol
 737                 if (!key->metaCast("OSSymbol")) {
 738                         return false;
 739                 }
 740                 if (!s->addString("<key>")) {
 741                         return false;
 742                 }
 743                 const char *c = key->getCStringNoCopy();
 744                 while (*c) {
 745                         if (*c == '<') {
 746                                 if (!s->addString("&lt;")) {
 747                                         return false;
 748                                 }
 749                         } else if (*c == '>') {
 750                                 if (!s->addString("&gt;")) {
 751                                         return false;
 752                                 }
 753                         } else if (*c == '&') {
 754                                 if (!s->addString("&amp;")) {
 755                                         return false;
 756                                 }
 757                         } else {
 758                                 if (!s->addChar(*c)) {
 759                                         return false;
 760                                 }
 761                         }
 762                         c++;
 763                 }
 764                 if (!s->addXMLEndTag("key")) {
 765                         return false;
 766                 }
 767
 768                 if (!dictionary[i].value->serialize(s)) {
 769                         return false;
 770                 }
 771         }
 772
 773         return s->addXMLEndTag("dict");
 774 }
 775
 776 unsigned
 777 OSDictionary::setOptions(unsigned options, unsigned mask, void *)
 778 {
 779         unsigned old = super::setOptions(options, mask);
 780         if ((old ^ options) & mask) {
 781                 // Value changed need to recurse over all of the child collections
 782                 for (unsigned i = 0; i < count; i++) {
 783                         OSCollection *v = OSDynamicCast(OSCollection, dictionary[i].value.get());
 784                         if (v) {
 785                                 v->setOptions(options, mask);
 786                         }
 787                 }
 788         }
 789
 790         if (!(old & kSort) && (fOptions & kSort)) {
 791                 sortBySymbol();
 792         }
 793
 794         return old;
 795 }
 796
 797 OSSharedPtr<OSCollection>
 798 OSDictionary::copyCollection(OSDictionary *cycleDict)
 799 {
 800         OSSharedPtr<OSDictionary> ourCycleDict;
 801         OSSharedPtr<OSCollection> ret;
 802         OSSharedPtr<OSDictionary> newDict;
 803
 804         if (!cycleDict) {
 805                 ourCycleDict = OSDictionary::withCapacity(16);
 806                 if (!ourCycleDict) {
 807                         return nullptr;
 808                 }
 809                 cycleDict = ourCycleDict.get();
 810         }
 811
 812         do {
 813                 // Check for a cycle
 814                 ret = super::copyCollection(cycleDict);
 815                 if (ret) {
 816                         continue;
 817                 }
 818
 819                 newDict = OSDictionary::withDictionary(this);
 820                 if (!newDict) {
 821                         continue;
 822                 }
 823
 824                 // Insert object into cycle Dictionary
 825                 cycleDict->setObject((const OSSymbol *) this, newDict.get());
 826
 827                 for (unsigned int i = 0; i < count; i++) {
 828                         const OSMetaClassBase *obj = dictionary[i].value.get();
 829                         OSTaggedSharedPtr<OSCollection, OSCollection> coll(OSDynamicCast(OSCollection, EXT_CAST(obj)), OSNoRetain);
 830
 831                         if (coll) {
 832                                 OSSharedPtr<OSCollection> newColl = coll->copyCollection(cycleDict);
 833                                 if (!newColl) {
 834                                         return ret;
 835                                 }
 836                                 newDict->dictionary[i].value.detach();
 837                                 newDict->dictionary[i].value.reset(newColl.get(), OSRetain);
 838                         }
 839                 }
 840
 841                 ret = os::move(newDict);
 842         } while (false);
 843
 844         return ret;
 845 }
 846
 847 OSSharedPtr<OSArray>
 848 OSDictionary::copyKeys(void)
 849 {
 850         OSSharedPtr<OSArray> array;
 851
 852         array = OSArray::withCapacity(count);
 853         if (!array) {
 854                 return nullptr;
 855         }
 856
 857         for (unsigned int i = 0; i < count; i++) {
 858                 if (!array->setObject(i, dictionary[i].key.get())) {
 859                         return nullptr;
 860                 }
 861         }
 862         return array;
 863 }
 864
 865 bool
 866 OSDictionary::iterateObjects(void * refcon, bool (*callback)(void * refcon, const OSSymbol * key, OSObject * object))
 867 {
 868         unsigned int initialUpdateStamp;
 869         bool         done;
 870
 871         initialUpdateStamp = updateStamp;
 872         done = false;
 873         for (unsigned int i = 0; i < count; i++) {
 874                 done = callback(refcon, dictionary[i].key.get(), EXT_CAST(dictionary[i].value.get()));
 875                 if (done) {
 876                         break;
 877                 }
 878                 if (initialUpdateStamp != updateStamp) {
 879                         break;
 880                 }
 881         }
 882
 883         return initialUpdateStamp == updateStamp;
 884 }
 885
 886 static bool
 887 OSDictionaryIterateObjectsBlock(void * refcon, const OSSymbol * key, OSObject * object)
 888 {
 889         bool (^block)(const OSSymbol * key, OSObject * object) = (typeof(block))refcon;
 890         return block(key, object);
 891 }
 892
 893 bool
 894 OSDictionary::iterateObjects(bool (^block)(const OSSymbol * key, OSObject * object))
 895 {
 896         return iterateObjects((void *)block, &OSDictionaryIterateObjectsBlock);
 897 }