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