libkern/c++/OSDictionary.cpp

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