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 #if OSALLOCDEBUG
  53 extern "C" {
  54     extern int debug_container_malloc_size;
  55 };
  56 #define ACCUMSIZE(s) do { debug_container_malloc_size += (s); } while(0)
  57 #else
  58 #define ACCUMSIZE(s)
  59 #endif
  60
  61 #define EXT_CAST(obj) \
  62     reinterpret_cast<OSObject *>(const_cast<OSMetaClassBase *>(obj))
  63
  64 bool OSDictionary::initWithCapacity(unsigned int inCapacity)
  65 {
  66     if (!super::init())
  67         return false;
  68
  69     int size = inCapacity * sizeof(dictEntry);
  70
  71 //fOptions |= kSort;
  72
  73     dictionary = (dictEntry *) kalloc(size);
  74     if (!dictionary)
  75         return false;
  76
  77     bzero(dictionary, size);
  78     ACCUMSIZE(size);
  79
  80     count = 0;
  81     capacity = inCapacity;
  82     capacityIncrement = (inCapacity)? inCapacity : 16;
  83
  84     return true;
  85 }
  86
  87 bool OSDictionary::initWithObjects(const OSObject *objects[],
  88                                    const OSSymbol *keys[],
  89                                    unsigned int theCount,
  90                                    unsigned int theCapacity)
  91 {
  92     unsigned int newCapacity = theCount;
  93
  94     if (!objects || !keys)
  95         return false;
  96
  97     if ( theCapacity ) {
  98         if (theCount > theCapacity)
  99             return false;
 100
 101         newCapacity = theCapacity;
 102     }
 103
 104     if (!initWithCapacity(newCapacity))
 105         return false;
 106
 107     for (unsigned int i = 0; i < theCount; i++) {
 108         const OSMetaClassBase *newObject = *objects++;
 109
 110         if (!newObject || !keys[i] || !setObject(keys[i], newObject))
 111             return false;
 112     }
 113
 114     return true;
 115 }
 116
 117 bool OSDictionary::initWithObjects(const OSObject *objects[],
 118                                    const OSString *keys[],
 119                                    unsigned int theCount,
 120                                    unsigned int theCapacity)
 121 {
 122     unsigned int newCapacity = theCount;
 123
 124     if (!objects || !keys)
 125         return false;
 126
 127     if ( theCapacity ) {
 128         if (theCount > theCapacity)
 129             return false;
 130
 131         newCapacity = theCapacity;
 132     }
 133
 134     if (!initWithCapacity(newCapacity))
 135         return false;
 136
 137     for (unsigned int i = 0; i < theCount; i++) {
 138         const OSSymbol *key = OSSymbol::withString(*keys++);
 139         const OSMetaClassBase *newObject = *objects++;
 140
 141         if (!key)
 142             return false;
 143
 144         if (!newObject || !setObject(key, newObject)) {
 145             key->release();
 146             return false;
 147         }
 148
 149         key->release();
 150     }
 151
 152     return true;
 153 }
 154
 155 bool OSDictionary::initWithDictionary(const OSDictionary *dict,
 156                                       unsigned int theCapacity)
 157 {
 158     unsigned int newCapacity;
 159
 160     if ( !dict )
 161         return false;
 162
 163     newCapacity = dict->count;
 164
 165     if ( theCapacity ) {
 166         if ( dict->count > theCapacity )
 167             return false;
 168
 169         newCapacity = theCapacity;
 170     }
 171
 172     if (!initWithCapacity(newCapacity))
 173         return false;
 174
 175     if ((kSort & fOptions) && !(kSort & dict->fOptions)) {
 176         for (unsigned int i = 0; i < dict->count; i++) {
 177             if (!setObject(dict->dictionary[i].key, dict->dictionary[i].value)) {
 178                 return false;
 179             }
 180         }
 181         return true;
 182     }
 183
 184     count = dict->count;
 185     bcopy(dict->dictionary, dictionary, count * sizeof(dictEntry));
 186     for (unsigned int i = 0; i < count; i++) {
 187         dictionary[i].key->taggedRetain(OSTypeID(OSCollection));
 188         dictionary[i].value->taggedRetain(OSTypeID(OSCollection));
 189     }
 190
 191     return true;
 192 }
 193
 194 OSDictionary *OSDictionary::withCapacity(unsigned int capacity)
 195 {
 196     OSDictionary *me = new OSDictionary;
 197
 198     if (me && !me->initWithCapacity(capacity)) {
 199         me->release();
 200         return 0;
 201     }
 202
 203     return me;
 204 }
 205
 206 OSDictionary *OSDictionary::withObjects(const OSObject *objects[],
 207                                         const OSSymbol *keys[],
 208                                         unsigned int count,
 209                                         unsigned int capacity)
 210 {
 211     OSDictionary *me = new OSDictionary;
 212
 213     if (me && !me->initWithObjects(objects, keys, count, capacity)) {
 214         me->release();
 215         return 0;
 216     }
 217
 218     return me;
 219 }
 220
 221 OSDictionary *OSDictionary::withObjects(const OSObject *objects[],
 222                                         const OSString *keys[],
 223                                         unsigned int count,
 224                                         unsigned int capacity)
 225 {
 226     OSDictionary *me = new OSDictionary;
 227
 228     if (me && !me->initWithObjects(objects, keys, count, capacity)) {
 229         me->release();
 230         return 0;
 231     }
 232
 233     return me;
 234 }
 235
 236 OSDictionary *OSDictionary::withDictionary(const OSDictionary *dict,
 237                                            unsigned int capacity)
 238 {
 239     OSDictionary *me = new OSDictionary;
 240
 241     if (me && !me->initWithDictionary(dict, capacity)) {
 242         me->release();
 243         return 0;
 244     }
 245
 246     return me;
 247 }
 248
 249 void OSDictionary::free()
 250 {
 251     (void) super::setOptions(0, kImmutable);
 252     flushCollection();
 253     if (dictionary) {
 254         kfree(dictionary, capacity * sizeof(dictEntry));
 255         ACCUMSIZE( -(capacity * sizeof(dictEntry)) );
 256     }
 257
 258     super::free();
 259 }
 260
 261 unsigned int OSDictionary::getCount() const { return count; }
 262 unsigned int OSDictionary::getCapacity() const { return capacity; }
 263
 264 unsigned int OSDictionary::getCapacityIncrement() const
 265 {
 266     return capacityIncrement;
 267 }
 268
 269 unsigned int OSDictionary::setCapacityIncrement(unsigned int increment)
 270 {
 271     capacityIncrement = (increment)? increment : 16;
 272
 273     return capacityIncrement;
 274 }
 275
 276 unsigned int OSDictionary::ensureCapacity(unsigned int newCapacity)
 277 {
 278     dictEntry *newDict;
 279     int oldSize, newSize;
 280
 281     if (newCapacity <= capacity)
 282         return capacity;
 283
 284     // round up
 285     newCapacity = (((newCapacity - 1) / capacityIncrement) + 1)
 286                 * capacityIncrement;
 287     newSize = sizeof(dictEntry) * newCapacity;
 288
 289     newDict = (dictEntry *) kalloc(newSize);
 290     if (newDict) {
 291         oldSize = sizeof(dictEntry) * capacity;
 292
 293         bcopy(dictionary, newDict, oldSize);
 294         bzero(&newDict[capacity], newSize - oldSize);
 295
 296         ACCUMSIZE(newSize - oldSize);
 297         kfree(dictionary, oldSize);
 298
 299         dictionary = newDict;
 300         capacity = newCapacity;
 301     }
 302
 303     return capacity;
 304 }
 305
 306 void OSDictionary::flushCollection()
 307 {
 308     haveUpdated();
 309
 310     for (unsigned int i = 0; i < count; i++) {
 311         dictionary[i].key->taggedRelease(OSTypeID(OSCollection));
 312         dictionary[i].value->taggedRelease(OSTypeID(OSCollection));
 313     }
 314     count = 0;
 315 }
 316
 317 bool OSDictionary::
 318 setObject(const OSSymbol *aKey, const OSMetaClassBase *anObject)
 319 {
 320     unsigned int i;
 321     bool exists;
 322
 323     if (!anObject || !aKey)
 324         return false;
 325
 326     // if the key exists, replace the object
 327
 328     if (fOptions & kSort) {
 329         i = OSSymbol::bsearch(aKey, &dictionary[0], count, sizeof(dictionary[0]));
 330         exists = (i < count) && (aKey == dictionary[i].key);
 331     } else for (exists = false, i = 0; i < count; i++) {
 332         if ((exists = (aKey == dictionary[i].key))) break;
 333     }
 334
 335     if (exists) {
 336         const OSMetaClassBase *oldObject = dictionary[i].value;
 337
 338         haveUpdated();
 339
 340         anObject->taggedRetain(OSTypeID(OSCollection));
 341         dictionary[i].value = anObject;
 342
 343         oldObject->taggedRelease(OSTypeID(OSCollection));
 344         return true;
 345     }
 346
 347     // add new key, possibly extending our capacity
 348     if (count >= capacity && count >= ensureCapacity(count+1))
 349         return false;
 350
 351     haveUpdated();
 352
 353     bcopy(&dictionary[i], &dictionary[i+1], (count - i) * sizeof(dictionary[0]));
 354
 355     aKey->taggedRetain(OSTypeID(OSCollection));
 356     anObject->taggedRetain(OSTypeID(OSCollection));
 357     dictionary[i].key = aKey;
 358     dictionary[i].value = anObject;
 359     count++;
 360
 361     return true;
 362 }
 363
 364 void OSDictionary::removeObject(const OSSymbol *aKey)
 365 {
 366     unsigned int i;
 367     bool exists;
 368
 369     if (!aKey)
 370         return;
 371
 372     // if the key exists, remove the object
 373
 374     if (fOptions & kSort) {
 375         i = OSSymbol::bsearch(aKey, &dictionary[0], count, sizeof(dictionary[0]));
 376         exists = (i < count) && (aKey == dictionary[i].key);
 377     } else for (exists = false, i = 0; i < count; i++) {
 378         if ((exists = (aKey == dictionary[i].key))) break;
 379     }
 380
 381     if (exists) {
 382         dictEntry oldEntry = dictionary[i];
 383
 384         haveUpdated();
 385
 386         count--;
 387         bcopy(&dictionary[i+1], &dictionary[i], (count - i) * sizeof(dictionary[0]));
 388
 389         oldEntry.key->taggedRelease(OSTypeID(OSCollection));
 390         oldEntry.value->taggedRelease(OSTypeID(OSCollection));
 391         return;
 392     }
 393 }
 394
 395
 396 // Returns true on success, false on an error condition.
 397 bool OSDictionary::merge(const OSDictionary *srcDict)
 398 {
 399     const OSSymbol * sym;
 400     OSCollectionIterator * iter;
 401
 402     if ( !OSDynamicCast(OSDictionary, srcDict) )
 403         return false;
 404
 405     iter = OSCollectionIterator::withCollection(const_cast<OSDictionary *>(srcDict));
 406     if ( !iter )
 407         return false;
 408
 409     while ( (sym = (const OSSymbol *)iter->getNextObject()) ) {
 410         const OSMetaClassBase * obj;
 411
 412         obj = srcDict->getObject(sym);
 413         if ( !setObject(sym, obj) ) {
 414             iter->release();
 415             return false;
 416         }
 417     }
 418     iter->release();
 419
 420     return true;
 421 }
 422
 423 OSObject *OSDictionary::getObject(const OSSymbol *aKey) const
 424 {
 425     unsigned int i;
 426     bool exists;
 427
 428     if (!aKey)
 429         return 0;
 430
 431     // if the key exists, return the object
 432
 433     if (fOptions & kSort) {
 434         i = OSSymbol::bsearch(aKey, &dictionary[0], count, sizeof(dictionary[0]));
 435         exists = (i < count) && (aKey == dictionary[i].key);
 436     } else for (exists = false, i = 0; i < count; i++) {
 437         if ((exists = (aKey == dictionary[i].key))) break;
 438     }
 439
 440     if (exists) {
 441         return (const_cast<OSObject *> ((const OSObject *)dictionary[i].value));
 442     }
 443
 444     return 0;
 445 }
 446
 447 // Wrapper macros
 448 #define OBJECT_WRAP_1(cmd, k)                                           \
 449 {                                                                       \
 450     const OSSymbol *tmpKey = k;                                         \
 451     OSObject *retObj = cmd(tmpKey);                                     \
 452                                                                         \
 453     tmpKey->release();                                                  \
 454     return retObj;                                                      \
 455 }
 456
 457 #define OBJECT_WRAP_2(cmd, k, o)                                        \
 458 {                                                                       \
 459     const OSSymbol *tmpKey = k;                                         \
 460     bool ret = cmd(tmpKey, o);                                          \
 461                                                                         \
 462     tmpKey->release();                                                  \
 463     return ret;                                                         \
 464 }
 465
 466 #define OBJECT_WRAP_3(cmd, k)                                           \
 467 {                                                                       \
 468     const OSSymbol *tmpKey = k;                                         \
 469     cmd(tmpKey);                                                        \
 470     tmpKey->release();                                                  \
 471 }
 472
 473
 474 bool OSDictionary::setObject(const OSString *aKey, const OSMetaClassBase *anObject)
 475     OBJECT_WRAP_2(setObject, OSSymbol::withString(aKey), anObject)
 476 bool OSDictionary::setObject(const char *aKey, const OSMetaClassBase *anObject)
 477     OBJECT_WRAP_2(setObject, OSSymbol::withCString(aKey), anObject)
 478
 479 OSObject *OSDictionary::getObject(const OSString *aKey) const
 480     OBJECT_WRAP_1(getObject, OSSymbol::withString(aKey))
 481 OSObject *OSDictionary::getObject(const char *aKey) const
 482     OBJECT_WRAP_1(getObject, OSSymbol::withCString(aKey))
 483
 484 void OSDictionary::removeObject(const OSString *aKey)
 485     OBJECT_WRAP_3(removeObject, OSSymbol::withString(aKey))
 486 void OSDictionary::removeObject(const char *aKey)
 487     OBJECT_WRAP_3(removeObject, OSSymbol::withCString(aKey))
 488
 489 bool
 490 OSDictionary::isEqualTo(const OSDictionary *srcDict, const OSCollection *keys) const
 491 {
 492     OSCollectionIterator * iter;
 493     unsigned int keysCount;
 494     const OSMetaClassBase * obj1;
 495     const OSMetaClassBase * obj2;
 496     OSString * aKey;
 497     bool ret;
 498
 499     if ( this == srcDict )
 500         return true;
 501
 502     keysCount = keys->getCount();
 503     if ( (count < keysCount) || (srcDict->getCount() < keysCount) )
 504         return false;
 505
 506     iter = OSCollectionIterator::withCollection(keys);
 507     if ( !iter )
 508         return false;
 509
 510     ret = true;
 511     while ( (aKey = OSDynamicCast(OSString, iter->getNextObject())) ) {
 512         obj1 = getObject(aKey);
 513         obj2 = srcDict->getObject(aKey);
 514         if ( !obj1 || !obj2 ) {
 515             ret = false;
 516             break;
 517         }
 518
 519         if ( !obj1->isEqualTo(obj2) ) {
 520             ret = false;
 521             break;
 522         }
 523     }
 524     iter->release();
 525
 526     return ret;
 527 }
 528
 529 bool OSDictionary::isEqualTo(const OSDictionary *srcDict) const
 530 {
 531     unsigned int i;
 532     const OSMetaClassBase * obj;
 533
 534     if ( this == srcDict )
 535         return true;
 536
 537     if ( count != srcDict->getCount() )
 538         return false;
 539
 540     for ( i = 0; i < count; i++ ) {
 541         obj = srcDict->getObject(dictionary[i].key);
 542         if ( !obj )
 543             return false;
 544
 545         if ( !dictionary[i].value->isEqualTo(obj) )
 546             return false;
 547     }
 548
 549     return true;
 550 }
 551
 552 bool OSDictionary::isEqualTo(const OSMetaClassBase *anObject) const
 553 {
 554     OSDictionary *dict;
 555
 556     dict = OSDynamicCast(OSDictionary, anObject);
 557     if ( dict )
 558         return isEqualTo(dict);
 559     else
 560         return false;
 561 }
 562
 563 unsigned int OSDictionary::iteratorSize() const
 564 {
 565     return sizeof(unsigned int);
 566 }
 567
 568 bool OSDictionary::initIterator(void *inIterator) const
 569 {
 570     unsigned int *iteratorP = (unsigned int *) inIterator;
 571
 572     *iteratorP = 0;
 573     return true;
 574 }
 575
 576 bool OSDictionary::getNextObjectForIterator(void *inIterator, OSObject **ret) const
 577 {
 578     unsigned int *iteratorP = (unsigned int *) inIterator;
 579     unsigned int index = (*iteratorP)++;
 580
 581     if (index < count)
 582         *ret = (OSObject *) dictionary[index].key;
 583     else
 584         *ret = 0;
 585
 586     return (*ret != 0);
 587 }
 588
 589 bool OSDictionary::serialize(OSSerialize *s) const
 590 {
 591     if (s->previouslySerialized(this)) return true;
 592
 593     if (!s->addXMLStartTag(this, "dict")) return false;
 594
 595     for (unsigned i = 0; i < count; i++) {
 596         const OSSymbol *key = dictionary[i].key;
 597
 598         // due the nature of the XML syntax, this must be a symbol
 599         if (!key->metaCast("OSSymbol")) {
 600             return false;
 601         }
 602         if (!s->addString("<key>")) return false;
 603         const char *c = key->getCStringNoCopy();
 604         while (*c) {
 605             if (*c == '<') {
 606                 if (!s->addString("&lt;")) return false;
 607             } else if (*c == '>') {
 608                 if (!s->addString("&gt;")) return false;
 609             } else if (*c == '&') {
 610                 if (!s->addString("&amp;")) return false;
 611             } else {
 612                 if (!s->addChar(*c)) return false;
 613             }
 614             c++;
 615         }
 616         if (!s->addXMLEndTag("key")) return false;
 617
 618         if (!dictionary[i].value->serialize(s)) return false;
 619     }
 620
 621     return s->addXMLEndTag("dict");
 622 }
 623
 624 unsigned OSDictionary::setOptions(unsigned options, unsigned mask, void *)
 625 {
 626     unsigned old = super::setOptions(options, mask);
 627     if ((old ^ options) & mask) {
 628
 629         // Value changed need to recurse over all of the child collections
 630         for ( unsigned i = 0; i < count; i++ ) {
 631             OSCollection *v = OSDynamicCast(OSCollection, dictionary[i].value);
 632             if (v)
 633                 v->setOptions(options, mask);
 634         }
 635     }
 636
 637     return old;
 638 }
 639
 640 OSCollection * OSDictionary::copyCollection(OSDictionary *cycleDict)
 641 {
 642     bool allocDict = !cycleDict;
 643     OSCollection *ret = 0;
 644     OSDictionary *newDict = 0;
 645
 646     if (allocDict) {
 647         cycleDict = OSDictionary::withCapacity(16);
 648         if (!cycleDict)
 649             return 0;
 650     }
 651
 652     do {
 653         // Check for a cycle
 654         ret = super::copyCollection(cycleDict);
 655         if (ret)
 656             continue;
 657
 658         newDict = OSDictionary::withDictionary(this);
 659         if (!newDict)
 660             continue;
 661
 662         // Insert object into cycle Dictionary
 663         cycleDict->setObject((const OSSymbol *) this, newDict);
 664
 665         for (unsigned int i = 0; i < count; i++) {
 666             const OSMetaClassBase *obj = dictionary[i].value;
 667             OSCollection *coll = OSDynamicCast(OSCollection, EXT_CAST(obj));
 668
 669             if (coll) {
 670                 OSCollection *newColl = coll->copyCollection(cycleDict);
 671                 if (!newColl)
 672                     goto abortCopy;
 673
 674                 newDict->dictionary[i].value = newColl;
 675
 676                 coll->taggedRelease(OSTypeID(OSCollection));
 677                 newColl->taggedRetain(OSTypeID(OSCollection));
 678                 newColl->release();
 679             };
 680         }
 681
 682         ret = newDict;
 683         newDict = 0;
 684
 685     } while (false);
 686
 687 abortCopy:
 688     if (newDict)
 689         newDict->release();
 690
 691     if (allocDict)
 692         cycleDict->release();
 693
 694     return ret;
 695 }
 696