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