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