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