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