libkern/c++/OSDictionary.cpp

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