libkern/c++/OSDictionary.cpp

   1 /*
   2  * Copyright (c) 2000 Apple Computer, Inc. All rights reserved.
   3  *
   4  * @APPLE_LICENSE_HEADER_START@
   5  *
   6  * Copyright (c) 1999-2003 Apple Computer, Inc.  All Rights Reserved.
   7  *
   8  * This file contains Original Code and/or Modifications of Original Code
   9  * as defined in and that are subject to the Apple Public Source License
  10  * Version 2.0 (the 'License'). You may not use this file except in
  11  * compliance with the License. Please obtain a copy of the License at
  12  * http://www.opensource.apple.com/apsl/ and read it before using this
  13  * file.
  14  *
  15  * The Original Code and all software distributed under the License are
  16  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  17  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  18  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  19  * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
  20  * Please see the License for the specific language governing rights and
  21  * limitations under the License.
  22  *
  23  * @APPLE_LICENSE_HEADER_END@
  24  */
  25 /* OSDictionary.m created by rsulack on Fri 12-Sep-1997 */
  26 /* OSDictionary.cpp converted to C++ by gvdl on Fri 1998-10-30 */
  27 /* OSDictionary.cpp rewritten by gvdl on Fri 1998-10-30 */
  28
  29
  30 #include <libkern/c++/OSDictionary.h>
  31 #include <libkern/c++/OSArray.h>
  32 #include <libkern/c++/OSSymbol.h>
  33 #include <libkern/c++/OSSerialize.h>
  34 #include <libkern/c++/OSLib.h>
  35 #include <libkern/c++/OSCollectionIterator.h>
  36
  37 #define super OSCollection
  38
  39 OSDefineMetaClassAndStructors(OSDictionary, OSCollection)
  40 OSMetaClassDefineReservedUnused(OSDictionary, 0);
  41 OSMetaClassDefineReservedUnused(OSDictionary, 1);
  42 OSMetaClassDefineReservedUnused(OSDictionary, 2);
  43 OSMetaClassDefineReservedUnused(OSDictionary, 3);
  44 OSMetaClassDefineReservedUnused(OSDictionary, 4);
  45 OSMetaClassDefineReservedUnused(OSDictionary, 5);
  46 OSMetaClassDefineReservedUnused(OSDictionary, 6);
  47 OSMetaClassDefineReservedUnused(OSDictionary, 7);
  48
  49 #if OSALLOCDEBUG
  50 extern "C" {
  51     extern int debug_container_malloc_size;
  52 };
  53 #define ACCUMSIZE(s) do { debug_container_malloc_size += (s); } while(0)
  54 #else
  55 #define ACCUMSIZE(s)
  56 #endif
  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     flushCollection();
 235     if (dictionary) {
 236         kfree((vm_offset_t)dictionary, capacity * sizeof(dictEntry));
 237         ACCUMSIZE( -(capacity * sizeof(dictEntry)) );
 238     }
 239
 240     super::free();
 241 }
 242
 243 unsigned int OSDictionary::getCount() const { return count; }
 244 unsigned int OSDictionary::getCapacity() const { return capacity; }
 245
 246 unsigned int OSDictionary::getCapacityIncrement() const
 247 {
 248     return capacityIncrement;
 249 }
 250
 251 unsigned int OSDictionary::setCapacityIncrement(unsigned int increment)
 252 {
 253     capacityIncrement = (increment)? increment : 16;
 254
 255     return capacityIncrement;
 256 }
 257
 258 unsigned int OSDictionary::ensureCapacity(unsigned int newCapacity)
 259 {
 260     dictEntry *newDict;
 261     int oldSize, newSize;
 262
 263     if (newCapacity <= capacity)
 264         return capacity;
 265
 266     // round up
 267     newCapacity = (((newCapacity - 1) / capacityIncrement) + 1)
 268                 * capacityIncrement;
 269     newSize = sizeof(dictEntry) * newCapacity;
 270
 271     newDict = (dictEntry *) kalloc(newSize);
 272     if (newDict) {
 273         oldSize = sizeof(dictEntry) * capacity;
 274
 275         bcopy(dictionary, newDict, oldSize);
 276         bzero(&newDict[capacity], newSize - oldSize);
 277
 278         ACCUMSIZE(newSize - oldSize);
 279         kfree((vm_offset_t)dictionary, oldSize);
 280
 281         dictionary = newDict;
 282         capacity = newCapacity;
 283     }
 284
 285     return capacity;
 286 }
 287
 288 void OSDictionary::flushCollection()
 289 {
 290     haveUpdated();
 291
 292     for (unsigned int i = 0; i < count; i++) {
 293         dictionary[i].key->taggedRelease(OSTypeID(OSCollection));
 294         dictionary[i].value->taggedRelease(OSTypeID(OSCollection));
 295     }
 296     count = 0;
 297 }
 298
 299 bool OSDictionary::
 300 setObject(const OSSymbol *aKey, const OSMetaClassBase *anObject)
 301 {
 302     if (!anObject || !aKey)
 303         return false;
 304
 305     // if the key exists, replace the object
 306     for (unsigned int i = 0; i < count; i++) {
 307         if (aKey == dictionary[i].key) {
 308             const OSMetaClassBase *oldObject = dictionary[i].value;
 309
 310             anObject->taggedRetain(OSTypeID(OSCollection));
 311             dictionary[i].value = anObject;
 312
 313             haveUpdated();
 314
 315             oldObject->taggedRelease(OSTypeID(OSCollection));
 316             return true;
 317         }
 318     }
 319
 320     // add new key, possibly extending our capacity
 321     if (count >= capacity && count >= ensureCapacity(count+1))
 322         return 0;
 323
 324     aKey->taggedRetain(OSTypeID(OSCollection));
 325     anObject->taggedRetain(OSTypeID(OSCollection));
 326     dictionary[count].key = aKey;
 327     dictionary[count].value = anObject;
 328     count++;
 329
 330     haveUpdated();
 331
 332     return true;
 333 }
 334
 335 void OSDictionary::removeObject(const OSSymbol *aKey)
 336 {
 337     if (!aKey)
 338         return;
 339
 340     // if the key exists, remove the object
 341     for (unsigned int i = 0; i < count; i++)
 342         if (aKey == dictionary[i].key) {
 343             dictEntry oldEntry = dictionary[i];
 344
 345             haveUpdated();
 346
 347             count--;
 348             for (; i < count; i++)
 349                 dictionary[i] = dictionary[i+1];
 350
 351             oldEntry.key->taggedRelease(OSTypeID(OSCollection));
 352             oldEntry.value->taggedRelease(OSTypeID(OSCollection));
 353             return;
 354         }
 355 }
 356
 357
 358 // Returns true on success, false on an error condition.
 359 bool OSDictionary::merge(const OSDictionary *srcDict)
 360 {
 361     const OSSymbol * sym;
 362     OSCollectionIterator * iter;
 363
 364     if ( !OSDynamicCast(OSDictionary, srcDict) )
 365         return false;
 366
 367     iter = OSCollectionIterator::withCollection((OSDictionary *)srcDict);
 368     if ( !iter )
 369         return false;
 370
 371     while ( (sym = (const OSSymbol *)iter->getNextObject()) ) {
 372         const OSMetaClassBase * obj;
 373
 374         obj = srcDict->getObject(sym);
 375         if ( !setObject(sym, obj) ) {
 376             iter->release();
 377             return false;
 378         }
 379     }
 380     iter->release();
 381
 382     return true;
 383 }
 384
 385 OSObject *OSDictionary::getObject(const OSSymbol *aKey) const
 386 {
 387     if (!aKey)
 388         return 0;
 389
 390     // if the key exists, remove the object
 391     for (unsigned int i = 0; i < count; i++)
 392         if (aKey == dictionary[i].key)
 393             return (OSObject *) dictionary[i].value;
 394
 395     return 0;
 396 }
 397
 398 // Wrapper macros
 399 #define OBJECT_WRAP_1(cmd, k)                                           \
 400 {                                                                       \
 401     const OSSymbol *tmpKey = k;                                         \
 402     OSObject *retObj = cmd(tmpKey);                                     \
 403                                                                         \
 404     tmpKey->release();                                                  \
 405     return retObj;                                                      \
 406 }
 407
 408 #define OBJECT_WRAP_2(cmd, k, o)                                        \
 409 {                                                                       \
 410     const OSSymbol *tmpKey = k;                                         \
 411     bool ret = cmd(tmpKey, o);                                          \
 412                                                                         \
 413     tmpKey->release();                                                  \
 414     return ret;                                                         \
 415 }
 416
 417 #define OBJECT_WRAP_3(cmd, k)                                           \
 418 {                                                                       \
 419     const OSSymbol *tmpKey = k;                                         \
 420     cmd(tmpKey);                                                        \
 421     tmpKey->release();                                                  \
 422 }
 423
 424
 425 bool OSDictionary::setObject(const OSString *aKey, const OSMetaClassBase *anObject)
 426     OBJECT_WRAP_2(setObject, OSSymbol::withString(aKey), anObject)
 427 bool OSDictionary::setObject(const char *aKey, const OSMetaClassBase *anObject)
 428     OBJECT_WRAP_2(setObject, OSSymbol::withCString(aKey), anObject)
 429
 430 OSObject *OSDictionary::getObject(const OSString *aKey) const
 431     OBJECT_WRAP_1(getObject, OSSymbol::withString(aKey))
 432 OSObject *OSDictionary::getObject(const char *aKey) const
 433     OBJECT_WRAP_1(getObject, OSSymbol::withCString(aKey))
 434
 435 void OSDictionary::removeObject(const OSString *aKey)
 436     OBJECT_WRAP_3(removeObject, OSSymbol::withString(aKey))
 437 void OSDictionary::removeObject(const char *aKey)
 438     OBJECT_WRAP_3(removeObject, OSSymbol::withCString(aKey))
 439
 440 bool
 441 OSDictionary::isEqualTo(const OSDictionary *srcDict, const OSCollection *keys) const
 442 {
 443     OSCollectionIterator * iter;
 444     unsigned int keysCount;
 445     const OSMetaClassBase * obj1;
 446     const OSMetaClassBase * obj2;
 447     OSString * aKey;
 448     bool ret;
 449
 450     if ( this == srcDict )
 451         return true;
 452
 453     keysCount = keys->getCount();
 454     if ( (count < keysCount) || (srcDict->getCount() < keysCount) )
 455         return false;
 456
 457     iter = OSCollectionIterator::withCollection(keys);
 458     if ( !iter )
 459         return false;
 460
 461     ret = true;
 462     while ( (aKey = OSDynamicCast(OSString, iter->getNextObject())) ) {
 463         obj1 = getObject(aKey);
 464         obj2 = srcDict->getObject(aKey);
 465         if ( !obj1 || !obj2 ) {
 466             ret = false;
 467             break;
 468         }
 469
 470         if ( !obj1->isEqualTo(obj2) ) {
 471             ret = false;
 472             break;
 473         }
 474     }
 475     iter->release();
 476
 477     return ret;
 478 }
 479
 480 bool OSDictionary::isEqualTo(const OSDictionary *srcDict) const
 481 {
 482     unsigned int i;
 483     const OSMetaClassBase * obj;
 484
 485     if ( this == srcDict )
 486         return true;
 487
 488     if ( count != srcDict->getCount() )
 489         return false;
 490
 491     for ( i = 0; i < count; i++ ) {
 492         obj = srcDict->getObject(dictionary[i].key);
 493         if ( !obj )
 494             return false;
 495
 496         if ( !dictionary[i].value->isEqualTo(obj) )
 497             return false;
 498     }
 499
 500     return true;
 501 }
 502
 503 bool OSDictionary::isEqualTo(const OSMetaClassBase *anObject) const
 504 {
 505     OSDictionary *dict;
 506
 507     dict = OSDynamicCast(OSDictionary, anObject);
 508     if ( dict )
 509         return isEqualTo(dict);
 510     else
 511         return false;
 512 }
 513
 514 unsigned int OSDictionary::iteratorSize() const
 515 {
 516     return sizeof(unsigned int);
 517 }
 518
 519 bool OSDictionary::initIterator(void *inIterator) const
 520 {
 521     unsigned int *iteratorP = (unsigned int *) inIterator;
 522
 523     *iteratorP = 0;
 524     return true;
 525 }
 526
 527 bool OSDictionary::getNextObjectForIterator(void *inIterator, OSObject **ret) const
 528 {
 529     unsigned int *iteratorP = (unsigned int *) inIterator;
 530     unsigned int index = (*iteratorP)++;
 531
 532     if (index < count)
 533         *ret = (OSObject *) dictionary[index].key;
 534     else
 535         *ret = 0;
 536
 537     return (*ret != 0);
 538 }
 539
 540 bool OSDictionary::serialize(OSSerialize *s) const
 541 {
 542     if (s->previouslySerialized(this)) return true;
 543
 544     if (!s->addXMLStartTag(this, "dict")) return false;
 545
 546     for (unsigned i = 0; i < count; i++) {
 547         const OSSymbol *key = dictionary[i].key;
 548
 549         // due the nature of the XML syntax, this must be a symbol
 550         if (!key->metaCast("OSSymbol")) {
 551             return false;
 552         }
 553         if (!s->addString("<key>")) return false;
 554         const char *c = key->getCStringNoCopy();
 555         while (*c) {
 556             if (*c == '<') {
 557                 if (!s->addString("&lt;")) return false;
 558             } else if (*c == '>') {
 559                 if (!s->addString("&gt;")) return false;
 560             } else if (*c == '&') {
 561                 if (!s->addString("&amp;")) return false;
 562             } else {
 563                 if (!s->addChar(*c)) return false;
 564             }
 565             c++;
 566         }
 567         if (!s->addXMLEndTag("key")) return false;
 568
 569         if (!dictionary[i].value->serialize(s)) return false;
 570     }
 571
 572     return s->addXMLEndTag("dict");
 573 }