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