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