libkern/c++/OSDictionary.cpp

   1 /*
   2  * Copyright (c) 2000 Apple Computer, Inc. All rights reserved.
   3  *
   4  * @APPLE_LICENSE_OSREFERENCE_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
  10  * License may not be used to create, or enable the creation or
  11  * redistribution of, unlawful or unlicensed copies of an Apple operating
  12  * system, or to circumvent, violate, or enable the circumvention or
  13  * violation of, any terms of an Apple operating system software license
  14  * agreement.
  15  *
  16  * Please obtain a copy of the License at
  17  * http://www.opensource.apple.com/apsl/ and read it before using this
  18  * file.
  19  *
  20  * The Original Code and all software distributed under the License are
  21  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  22  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  23  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  24  * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
  25  * Please see the License for the specific language governing rights and
  26  * limitations under the License.
  27  *
  28  * @APPLE_LICENSE_OSREFERENCE_HEADER_END@
  29  */
  30 /* OSDictionary.m created by rsulack on Fri 12-Sep-1997 */
  31 /* OSDictionary.cpp converted to C++ by gvdl on Fri 1998-10-30 */
  32 /* OSDictionary.cpp rewritten by gvdl on Fri 1998-10-30 */
  33
  34
  35 #include <libkern/c++/OSDictionary.h>
  36 #include <libkern/c++/OSArray.h>
  37 #include <libkern/c++/OSSymbol.h>
  38 #include <libkern/c++/OSSerialize.h>
  39 #include <libkern/c++/OSLib.h>
  40 #include <libkern/c++/OSCollectionIterator.h>
  41
  42 #define super OSCollection
  43
  44 OSDefineMetaClassAndStructors(OSDictionary, OSCollection)
  45 OSMetaClassDefineReservedUnused(OSDictionary, 0);
  46 OSMetaClassDefineReservedUnused(OSDictionary, 1);
  47 OSMetaClassDefineReservedUnused(OSDictionary, 2);
  48 OSMetaClassDefineReservedUnused(OSDictionary, 3);
  49 OSMetaClassDefineReservedUnused(OSDictionary, 4);
  50 OSMetaClassDefineReservedUnused(OSDictionary, 5);
  51 OSMetaClassDefineReservedUnused(OSDictionary, 6);
  52 OSMetaClassDefineReservedUnused(OSDictionary, 7);
  53
  54 #if OSALLOCDEBUG
  55 extern "C" {
  56     extern int debug_container_malloc_size;
  57 };
  58 #define ACCUMSIZE(s) do { debug_container_malloc_size += (s); } while(0)
  59 #else
  60 #define ACCUMSIZE(s)
  61 #endif
  62
  63 #define EXT_CAST(obj) \
  64     reinterpret_cast<OSObject *>(const_cast<OSMetaClassBase *>(obj))
  65
  66 bool OSDictionary::initWithCapacity(unsigned int inCapacity)
  67 {
  68     if (!super::init())
  69         return false;
  70
  71     int size = inCapacity * sizeof(dictEntry);
  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 capacity = theCount;
  93
  94     if (!objects || !keys)
  95         return false;
  96
  97     if ( theCapacity ) {
  98         if (theCount > theCapacity)
  99             return false;
 100
 101         capacity = theCapacity;
 102     }
 103
 104     if (!initWithCapacity(capacity))
 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 capacity = theCount;
 123
 124     if (!objects || !keys)
 125         return false;
 126
 127     if ( theCapacity ) {
 128         if (theCount > theCapacity)
 129             return false;
 130
 131         capacity = theCapacity;
 132     }
 133
 134     if (!initWithCapacity(capacity))
 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 capacity;
 159
 160     if ( !dict )
 161         return false;
 162
 163     capacity = dict->count;
 164
 165     if ( theCapacity ) {
 166         if ( dict->count > theCapacity )
 167             return false;
 168
 169         capacity = theCapacity;
 170     }
 171
 172     if (!initWithCapacity(capacity))
 173         return false;
 174
 175     count = dict->count;
 176     bcopy(dict->dictionary, dictionary, count * sizeof(dictEntry));
 177     for (unsigned int i = 0; i < count; i++) {
 178         dictionary[i].key->taggedRetain(OSTypeID(OSCollection));
 179         dictionary[i].value->taggedRetain(OSTypeID(OSCollection));
 180     }
 181
 182     return true;
 183 }
 184
 185 OSDictionary *OSDictionary::withCapacity(unsigned int capacity)
 186 {
 187     OSDictionary *me = new OSDictionary;
 188
 189     if (me && !me->initWithCapacity(capacity)) {
 190         me->release();
 191         return 0;
 192     }
 193
 194     return me;
 195 }
 196
 197 OSDictionary *OSDictionary::withObjects(const OSObject *objects[],
 198                                         const OSSymbol *keys[],
 199                                         unsigned int count,
 200                                         unsigned int capacity)
 201 {
 202     OSDictionary *me = new OSDictionary;
 203
 204     if (me && !me->initWithObjects(objects, keys, count, capacity)) {
 205         me->release();
 206         return 0;
 207     }
 208
 209     return me;
 210 }
 211
 212 OSDictionary *OSDictionary::withObjects(const OSObject *objects[],
 213                                         const OSString *keys[],
 214                                         unsigned int count,
 215                                         unsigned int capacity)
 216 {
 217     OSDictionary *me = new OSDictionary;
 218
 219     if (me && !me->initWithObjects(objects, keys, count, capacity)) {
 220         me->release();
 221         return 0;
 222     }
 223
 224     return me;
 225 }
 226
 227 OSDictionary *OSDictionary::withDictionary(const OSDictionary *dict,
 228                                            unsigned int capacity)
 229 {
 230     OSDictionary *me = new OSDictionary;
 231
 232     if (me && !me->initWithDictionary(dict, capacity)) {
 233         me->release();
 234         return 0;
 235     }
 236
 237     return me;
 238 }
 239
 240 void OSDictionary::free()
 241 {
 242     (void) super::setOptions(0, kImmutable);
 243     flushCollection();
 244     if (dictionary) {
 245         kfree(dictionary, capacity * sizeof(dictEntry));
 246         ACCUMSIZE( -(capacity * sizeof(dictEntry)) );
 247     }
 248
 249     super::free();
 250 }
 251
 252 unsigned int OSDictionary::getCount() const { return count; }
 253 unsigned int OSDictionary::getCapacity() const { return capacity; }
 254
 255 unsigned int OSDictionary::getCapacityIncrement() const
 256 {
 257     return capacityIncrement;
 258 }
 259
 260 unsigned int OSDictionary::setCapacityIncrement(unsigned int increment)
 261 {
 262     capacityIncrement = (increment)? increment : 16;
 263
 264     return capacityIncrement;
 265 }
 266
 267 unsigned int OSDictionary::ensureCapacity(unsigned int newCapacity)
 268 {
 269     dictEntry *newDict;
 270     int oldSize, newSize;
 271
 272     if (newCapacity <= capacity)
 273         return capacity;
 274
 275     // round up
 276     newCapacity = (((newCapacity - 1) / capacityIncrement) + 1)
 277                 * capacityIncrement;
 278     newSize = sizeof(dictEntry) * newCapacity;
 279
 280     newDict = (dictEntry *) kalloc(newSize);
 281     if (newDict) {
 282         oldSize = sizeof(dictEntry) * capacity;
 283
 284         bcopy(dictionary, newDict, oldSize);
 285         bzero(&newDict[capacity], newSize - oldSize);
 286
 287         ACCUMSIZE(newSize - oldSize);
 288         kfree(dictionary, oldSize);
 289
 290         dictionary = newDict;
 291         capacity = newCapacity;
 292     }
 293
 294     return capacity;
 295 }
 296
 297 void OSDictionary::flushCollection()
 298 {
 299     haveUpdated();
 300
 301     for (unsigned int i = 0; i < count; i++) {
 302         dictionary[i].key->taggedRelease(OSTypeID(OSCollection));
 303         dictionary[i].value->taggedRelease(OSTypeID(OSCollection));
 304     }
 305     count = 0;
 306 }
 307
 308 bool OSDictionary::
 309 setObject(const OSSymbol *aKey, const OSMetaClassBase *anObject)
 310 {
 311     if (!anObject || !aKey)
 312         return false;
 313
 314     // if the key exists, replace the object
 315     for (unsigned int i = 0; i < count; i++) {
 316         if (aKey == dictionary[i].key) {
 317             const OSMetaClassBase *oldObject = dictionary[i].value;
 318
 319             haveUpdated();
 320
 321             anObject->taggedRetain(OSTypeID(OSCollection));
 322             dictionary[i].value = anObject;
 323
 324             oldObject->taggedRelease(OSTypeID(OSCollection));
 325             return true;
 326         }
 327     }
 328
 329     // add new key, possibly extending our capacity
 330     if (count >= capacity && count >= ensureCapacity(count+1))
 331         return 0;
 332
 333     haveUpdated();
 334
 335     aKey->taggedRetain(OSTypeID(OSCollection));
 336     anObject->taggedRetain(OSTypeID(OSCollection));
 337     dictionary[count].key = aKey;
 338     dictionary[count].value = anObject;
 339     count++;
 340
 341     return true;
 342 }
 343
 344 void OSDictionary::removeObject(const OSSymbol *aKey)
 345 {
 346     if (!aKey)
 347         return;
 348
 349     // if the key exists, remove the object
 350     for (unsigned int i = 0; i < count; i++)
 351         if (aKey == dictionary[i].key) {
 352             dictEntry oldEntry = dictionary[i];
 353
 354             haveUpdated();
 355
 356             count--;
 357             for (; i < count; i++)
 358                 dictionary[i] = dictionary[i+1];
 359
 360             oldEntry.key->taggedRelease(OSTypeID(OSCollection));
 361             oldEntry.value->taggedRelease(OSTypeID(OSCollection));
 362             return;
 363         }
 364 }
 365
 366
 367 // Returns true on success, false on an error condition.
 368 bool OSDictionary::merge(const OSDictionary *srcDict)
 369 {
 370     const OSSymbol * sym;
 371     OSCollectionIterator * iter;
 372
 373     if ( !OSDynamicCast(OSDictionary, srcDict) )
 374         return false;
 375
 376     iter = OSCollectionIterator::withCollection((OSDictionary *)srcDict);
 377     if ( !iter )
 378         return false;
 379
 380     while ( (sym = (const OSSymbol *)iter->getNextObject()) ) {
 381         const OSMetaClassBase * obj;
 382
 383         obj = srcDict->getObject(sym);
 384         if ( !setObject(sym, obj) ) {
 385             iter->release();
 386             return false;
 387         }
 388     }
 389     iter->release();
 390
 391     return true;
 392 }
 393
 394 OSObject *OSDictionary::getObject(const OSSymbol *aKey) const
 395 {
 396     if (!aKey)
 397         return 0;
 398
 399     // if the key exists, remove the object
 400     for (unsigned int i = 0; i < count; i++)
 401         if (aKey == dictionary[i].key)
 402             return (OSObject *) dictionary[i].value;
 403
 404     return 0;
 405 }
 406
 407 // Wrapper macros
 408 #define OBJECT_WRAP_1(cmd, k)                                           \
 409 {                                                                       \
 410     const OSSymbol *tmpKey = k;                                         \
 411     OSObject *retObj = cmd(tmpKey);                                     \
 412                                                                         \
 413     tmpKey->release();                                                  \
 414     return retObj;                                                      \
 415 }
 416
 417 #define OBJECT_WRAP_2(cmd, k, o)                                        \
 418 {                                                                       \
 419     const OSSymbol *tmpKey = k;                                         \
 420     bool ret = cmd(tmpKey, o);                                          \
 421                                                                         \
 422     tmpKey->release();                                                  \
 423     return ret;                                                         \
 424 }
 425
 426 #define OBJECT_WRAP_3(cmd, k)                                           \
 427 {                                                                       \
 428     const OSSymbol *tmpKey = k;                                         \
 429     cmd(tmpKey);                                                        \
 430     tmpKey->release();                                                  \
 431 }
 432
 433
 434 bool OSDictionary::setObject(const OSString *aKey, const OSMetaClassBase *anObject)
 435     OBJECT_WRAP_2(setObject, OSSymbol::withString(aKey), anObject)
 436 bool OSDictionary::setObject(const char *aKey, const OSMetaClassBase *anObject)
 437     OBJECT_WRAP_2(setObject, OSSymbol::withCString(aKey), anObject)
 438
 439 OSObject *OSDictionary::getObject(const OSString *aKey) const
 440     OBJECT_WRAP_1(getObject, OSSymbol::withString(aKey))
 441 OSObject *OSDictionary::getObject(const char *aKey) const
 442     OBJECT_WRAP_1(getObject, OSSymbol::withCString(aKey))
 443
 444 void OSDictionary::removeObject(const OSString *aKey)
 445     OBJECT_WRAP_3(removeObject, OSSymbol::withString(aKey))
 446 void OSDictionary::removeObject(const char *aKey)
 447     OBJECT_WRAP_3(removeObject, OSSymbol::withCString(aKey))
 448
 449 bool
 450 OSDictionary::isEqualTo(const OSDictionary *srcDict, const OSCollection *keys) const
 451 {
 452     OSCollectionIterator * iter;
 453     unsigned int keysCount;
 454     const OSMetaClassBase * obj1;
 455     const OSMetaClassBase * obj2;
 456     OSString * aKey;
 457     bool ret;
 458
 459     if ( this == srcDict )
 460         return true;
 461
 462     keysCount = keys->getCount();
 463     if ( (count < keysCount) || (srcDict->getCount() < keysCount) )
 464         return false;
 465
 466     iter = OSCollectionIterator::withCollection(keys);
 467     if ( !iter )
 468         return false;
 469
 470     ret = true;
 471     while ( (aKey = OSDynamicCast(OSString, iter->getNextObject())) ) {
 472         obj1 = getObject(aKey);
 473         obj2 = srcDict->getObject(aKey);
 474         if ( !obj1 || !obj2 ) {
 475             ret = false;
 476             break;
 477         }
 478
 479         if ( !obj1->isEqualTo(obj2) ) {
 480             ret = false;
 481             break;
 482         }
 483     }
 484     iter->release();
 485
 486     return ret;
 487 }
 488
 489 bool OSDictionary::isEqualTo(const OSDictionary *srcDict) const
 490 {
 491     unsigned int i;
 492     const OSMetaClassBase * obj;
 493
 494     if ( this == srcDict )
 495         return true;
 496
 497     if ( count != srcDict->getCount() )
 498         return false;
 499
 500     for ( i = 0; i < count; i++ ) {
 501         obj = srcDict->getObject(dictionary[i].key);
 502         if ( !obj )
 503             return false;
 504
 505         if ( !dictionary[i].value->isEqualTo(obj) )
 506             return false;
 507     }
 508
 509     return true;
 510 }
 511
 512 bool OSDictionary::isEqualTo(const OSMetaClassBase *anObject) const
 513 {
 514     OSDictionary *dict;
 515
 516     dict = OSDynamicCast(OSDictionary, anObject);
 517     if ( dict )
 518         return isEqualTo(dict);
 519     else
 520         return false;
 521 }
 522
 523 unsigned int OSDictionary::iteratorSize() const
 524 {
 525     return sizeof(unsigned int);
 526 }
 527
 528 bool OSDictionary::initIterator(void *inIterator) const
 529 {
 530     unsigned int *iteratorP = (unsigned int *) inIterator;
 531
 532     *iteratorP = 0;
 533     return true;
 534 }
 535
 536 bool OSDictionary::getNextObjectForIterator(void *inIterator, OSObject **ret) const
 537 {
 538     unsigned int *iteratorP = (unsigned int *) inIterator;
 539     unsigned int index = (*iteratorP)++;
 540
 541     if (index < count)
 542         *ret = (OSObject *) dictionary[index].key;
 543     else
 544         *ret = 0;
 545
 546     return (*ret != 0);
 547 }
 548
 549 bool OSDictionary::serialize(OSSerialize *s) const
 550 {
 551     if (s->previouslySerialized(this)) return true;
 552
 553     if (!s->addXMLStartTag(this, "dict")) return false;
 554
 555     for (unsigned i = 0; i < count; i++) {
 556         const OSSymbol *key = dictionary[i].key;
 557
 558         // due the nature of the XML syntax, this must be a symbol
 559         if (!key->metaCast("OSSymbol")) {
 560             return false;
 561         }
 562         if (!s->addString("<key>")) return false;
 563         const char *c = key->getCStringNoCopy();
 564         while (*c) {
 565             if (*c == '<') {
 566                 if (!s->addString("&lt;")) return false;
 567             } else if (*c == '>') {
 568                 if (!s->addString("&gt;")) return false;
 569             } else if (*c == '&') {
 570                 if (!s->addString("&amp;")) return false;
 571             } else {
 572                 if (!s->addChar(*c)) return false;
 573             }
 574             c++;
 575         }
 576         if (!s->addXMLEndTag("key")) return false;
 577
 578         if (!dictionary[i].value->serialize(s)) return false;
 579     }
 580
 581     return s->addXMLEndTag("dict");
 582 }
 583
 584 unsigned OSDictionary::setOptions(unsigned options, unsigned mask, void *)
 585 {
 586     unsigned old = super::setOptions(options, mask);
 587     if ((old ^ options) & mask) {
 588
 589         // Value changed need to recurse over all of the child collections
 590         for ( unsigned i = 0; i < count; i++ ) {
 591             OSCollection *v = OSDynamicCast(OSCollection, dictionary[i].value);
 592             if (v)
 593                 v->setOptions(options, mask);
 594         }
 595     }
 596
 597     return old;
 598 }
 599
 600 OSCollection * OSDictionary::copyCollection(OSDictionary *cycleDict)
 601 {
 602     bool allocDict = !cycleDict;
 603     OSCollection *ret = 0;
 604     OSDictionary *newDict = 0;
 605
 606     if (allocDict) {
 607         cycleDict = OSDictionary::withCapacity(16);
 608         if (!cycleDict)
 609             return 0;
 610     }
 611
 612     do {
 613         // Check for a cycle
 614         ret = super::copyCollection(cycleDict);
 615         if (ret)
 616             continue;
 617
 618         newDict = OSDictionary::withDictionary(this);
 619         if (!newDict)
 620             continue;
 621
 622         // Insert object into cycle Dictionary
 623         cycleDict->setObject((const OSSymbol *) this, newDict);
 624
 625         for (unsigned int i = 0; i < count; i++) {
 626             const OSMetaClassBase *obj = dictionary[i].value;
 627             OSCollection *coll = OSDynamicCast(OSCollection, EXT_CAST(obj));
 628
 629             if (coll) {
 630                 OSCollection *newColl = coll->copyCollection(cycleDict);
 631                 if (!newColl)
 632                     goto abortCopy;
 633
 634                 newDict->dictionary[i].value = newColl;
 635
 636                 coll->taggedRelease(OSTypeID(OSCollection));
 637                 newColl->taggedRetain(OSTypeID(OSCollection));
 638                 newColl->release();
 639             };
 640         }
 641
 642         ret = newDict;
 643         newDict = 0;
 644
 645     } while (false);
 646
 647 abortCopy:
 648     if (newDict)
 649         newDict->release();
 650
 651     if (allocDict)
 652         cycleDict->release();
 653
 654     return ret;
 655 }
 656