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