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->retain(); 168 dictionary[i].value->retain(); 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->release(); 291 dictionary[i].value->release(); 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->retain(); 308 dictionary[i].value = anObject; 309 310 haveUpdated(); 311 312 oldObject->release(); 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->retain(); 322 anObject->retain(); 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->release(); 349 oldEntry.value->release(); 350 return; 351 } 352 } 353 354 355 // Returns true on success, false on an error condition. 356 bool OSDictionary::merge(const OSDictionary *aDictionary) 357 { 358 const OSSymbol * sym; 359 OSCollectionIterator * iter; 360 361 if ( !OSDynamicCast(OSDictionary, (OSDictionary *) aDictionary) ) 362 return false; 363 364 iter = OSCollectionIterator::withCollection((OSDictionary *)aDictionary); 365 if ( !iter ) 366 return false; 367 368 while ( (sym = (const OSSymbol *)iter->getNextObject()) ) { 369 const OSMetaClassBase * obj; 370 371 obj = aDictionary->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 *aDictionary, 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 == aDictionary ) 448 return true; 449 450 keysCount = keys->getCount(); 451 if ( (count < keysCount) || (aDictionary->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 = aDictionary->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 *aDictionary) const 478 { 479 unsigned int i; 480 const OSMetaClassBase * obj; 481 482 if ( this == aDictionary ) 483 return true; 484 485 if ( count != aDictionary->getCount() ) 486 return false; 487 488 for ( i = 0; i < count; i++ ) { 489 obj = aDictionary->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("<")) return false; 555 } else if (*c == '>') { 556 if (!s->addString(">")) return false; 557 } else if (*c == '&') { 558 if (!s->addString("&")) 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 } 571