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 /* IOArray.m created by rsulack on Fri 12-Sep-1997 */ 29 /* IOArray.cpp converted to C++ by gvdl on Fri 1998-10-30 */ 30 31 32 #define IOKIT_ENABLE_SHARED_PTR 33 34 #include <libkern/c++/OSArray.h> 35 #include <libkern/c++/OSDictionary.h> 36 #include <libkern/c++/OSLib.h> 37 #include <libkern/c++/OSSerialize.h> 38 #include <libkern/c++/OSSharedPtr.h> 39 #include <libkern/OSDebug.h> 40 #include <os/cpp_util.h> 41 42 #define super OSCollection 43 44 OSDefineMetaClassAndStructorsWithZone(OSArray, OSCollection, 45 (zone_create_flags_t) (ZC_CACHING | ZC_ZFREE_CLEARMEM)) 46 OSMetaClassDefineReservedUnused(OSArray, 0); 47 OSMetaClassDefineReservedUnused(OSArray, 1); 48 OSMetaClassDefineReservedUnused(OSArray, 2); 49 OSMetaClassDefineReservedUnused(OSArray, 3); 50 OSMetaClassDefineReservedUnused(OSArray, 4); 51 OSMetaClassDefineReservedUnused(OSArray, 5); 52 OSMetaClassDefineReservedUnused(OSArray, 6); 53 OSMetaClassDefineReservedUnused(OSArray, 7); 54 55 bool 56 OSArray::initWithCapacity(unsigned int inCapacity) 57 { 58 unsigned int size; 59 60 if (!super::init()) { 61 return false; 62 } 63 64 // integer overflow check 65 if (inCapacity > (UINT_MAX / sizeof(*array))) { 66 return false; 67 } 68 69 size = sizeof(*array) * inCapacity; 70 array = (ArraySharedPtrType *)kalloc_container(size); 71 if (!array) { 72 return false; 73 } 74 75 count = 0; 76 capacity = inCapacity; 77 capacityIncrement = (inCapacity)? inCapacity : 16; 78 79 os::uninitialized_value_construct(array, array + capacity); 80 OSCONTAINER_ACCUMSIZE(size); 81 82 return true; 83 } 84 85 bool 86 OSArray::initWithObjects(const OSObject *objects[], 87 unsigned int theCount, 88 unsigned int theCapacity) 89 { 90 unsigned int initCapacity; 91 92 if (!theCapacity) { 93 initCapacity = theCount; 94 } else if (theCount > theCapacity) { 95 return false; 96 } else { 97 initCapacity = theCapacity; 98 } 99 100 if (!objects || !initWithCapacity(initCapacity)) { 101 return false; 102 } 103 104 for (unsigned int i = 0; i < theCount; i++) { 105 const OSMetaClassBase *newObject = *objects++; 106 107 if (!newObject) { 108 return false; 109 } 110 111 array[count++].reset(newObject, OSRetain); 112 } 113 114 return true; 115 } 116 117 bool 118 OSArray::initWithArray(const OSArray *anArray, 119 unsigned int theCapacity) 120 { 121 if (!anArray) { 122 return false; 123 } 124 125 return initWithObjects((const OSObject **) anArray->array, 126 anArray->count, theCapacity); 127 } 128 129 OSSharedPtr<OSArray> 130 OSArray::withCapacity(unsigned int capacity) 131 { 132 OSSharedPtr<OSArray> me = OSMakeShared<OSArray>(); 133 134 if (me && !me->initWithCapacity(capacity)) { 135 return nullptr; 136 } 137 138 return me; 139 } 140 141 OSSharedPtr<OSArray> 142 OSArray::withObjects(const OSObject *objects[], 143 unsigned int count, 144 unsigned int capacity) 145 { 146 OSSharedPtr<OSArray> me = OSMakeShared<OSArray>(); 147 148 if (me && !me->initWithObjects(objects, count, capacity)) { 149 return nullptr; 150 } 151 152 return me; 153 } 154 155 OSSharedPtr<OSArray> 156 OSArray::withArray(const OSArray *array, 157 unsigned int capacity) 158 { 159 OSSharedPtr<OSArray> me = OSMakeShared<OSArray>(); 160 161 if (me && !me->initWithArray(array, capacity)) { 162 return nullptr; 163 } 164 165 return me; 166 } 167 168 void 169 OSArray::free() 170 { 171 // Clear immutability - assumes the container is doing the right thing 172 (void) super::setOptions(0, kImmutable); 173 174 flushCollection(); 175 176 if (array) { 177 os::destroy(array, array + capacity); 178 kfree(array, sizeof(*array) * capacity); 179 OSCONTAINER_ACCUMSIZE( -(sizeof(*array) * capacity)); 180 } 181 182 super::free(); 183 } 184 185 186 unsigned int 187 OSArray::getCount() const 188 { 189 return count; 190 } 191 unsigned int 192 OSArray::getCapacity() const 193 { 194 return capacity; 195 } 196 unsigned int 197 OSArray::getCapacityIncrement() const 198 { 199 return capacityIncrement; 200 } 201 unsigned int 202 OSArray::setCapacityIncrement(unsigned int increment) 203 { 204 capacityIncrement = (increment)? increment : 16; 205 206 return capacityIncrement; 207 } 208 209 unsigned int 210 OSArray::ensureCapacity(unsigned int newCapacity) 211 { 212 ArraySharedPtrType *newArray; 213 vm_size_t finalCapacity; 214 vm_size_t oldSize, newSize; 215 216 if (newCapacity <= capacity) { 217 return capacity; 218 } 219 220 // round up 221 finalCapacity = (((newCapacity - 1) / capacityIncrement) + 1) 222 * capacityIncrement; 223 224 // integer overflow check 225 if (finalCapacity < newCapacity) { 226 return capacity; 227 } 228 229 newSize = sizeof(*newArray) * finalCapacity; 230 231 newArray = (decltype(newArray))kallocp_container(&newSize); 232 if (newArray) { 233 // use all of the actual allocation size 234 finalCapacity = (newSize / sizeof(*newArray)); 235 if (finalCapacity > UINT_MAX) { 236 // failure, too large 237 kfree(newArray, newSize); 238 return capacity; 239 } 240 241 oldSize = sizeof(*array) * capacity; 242 243 OSCONTAINER_ACCUMSIZE(((size_t)newSize) - ((size_t)oldSize)); 244 245 os::uninitialized_move(array, array + capacity, newArray); 246 os::uninitialized_value_construct(newArray + capacity, newArray + finalCapacity); 247 os::destroy(array, array + capacity); 248 kfree(array, oldSize); 249 array = newArray; 250 capacity = (unsigned int) finalCapacity; 251 } 252 253 return capacity; 254 } 255 256 void 257 OSArray::flushCollection() 258 { 259 unsigned int i; 260 261 haveUpdated(); 262 for (i = 0; i < count; i++) { 263 array[i].reset(); 264 } 265 count = 0; 266 } 267 268 bool 269 OSArray::setObject(const OSMetaClassBase *anObject) 270 { 271 return setObject(count, anObject); 272 } 273 274 bool 275 OSArray::setObject(OSSharedPtr<const OSMetaClassBase> const& anObject) 276 { 277 return setObject(count, anObject); 278 } 279 280 bool 281 OSArray::setObject(unsigned int index, const OSMetaClassBase *anObject) 282 { 283 unsigned int i; 284 unsigned int newCount = count + 1; 285 286 if ((index > count) || !anObject) { 287 return false; 288 } 289 290 // do we need more space? 291 if (newCount > capacity && newCount > ensureCapacity(newCount)) { 292 return false; 293 } 294 295 haveUpdated(); 296 if (index != count) { 297 for (i = count; i > index; i--) { 298 array[i] = os::move(array[i - 1]); 299 } 300 } 301 array[index].reset(anObject, OSRetain); 302 count++; 303 304 return true; 305 } 306 307 bool 308 OSArray::setObject(unsigned int index, OSSharedPtr<const OSMetaClassBase> const& anObject) 309 { 310 return setObject(index, anObject.get()); 311 } 312 313 bool 314 OSArray::merge(const OSArray * otherArray) 315 { 316 unsigned int otherCount = otherArray->getCount(); 317 unsigned int newCount = count + otherCount; 318 319 if (!otherCount) { 320 return true; 321 } 322 323 if (newCount < count) { 324 return false; 325 } 326 327 // do we need more space? 328 if (newCount > capacity && newCount > ensureCapacity(newCount)) { 329 return false; 330 } 331 332 haveUpdated(); 333 for (unsigned int i = 0; i < otherCount; i++) { 334 const OSMetaClassBase *newObject = otherArray->getObject(i); 335 336 array[count++].reset(newObject, OSRetain); 337 } 338 339 return true; 340 } 341 342 void 343 OSArray:: 344 replaceObject(unsigned int index, const OSMetaClassBase *anObject) 345 { 346 if ((index >= count) || !anObject) { 347 return; 348 } 349 350 haveUpdated(); 351 352 array[index].reset(anObject, OSRetain); 353 } 354 355 void 356 OSArray::replaceObject(unsigned int index, OSSharedPtr<const OSMetaClassBase> const& anObject) 357 { 358 return replaceObject(index, anObject.get()); 359 } 360 361 void 362 OSArray::removeObject(unsigned int index) 363 { 364 unsigned int i; 365 ArraySharedPtrType oldObject; 366 367 if (index >= count) { 368 return; 369 } 370 371 haveUpdated(); 372 oldObject = os::move(array[index]); 373 374 count--; 375 for (i = index; i < count; i++) { 376 array[i] = os::move(array[i + 1]); 377 } 378 } 379 380 bool 381 OSArray::isEqualTo(const OSArray *anArray) const 382 { 383 unsigned int i; 384 385 if (this == anArray) { 386 return true; 387 } 388 389 if (count != anArray->getCount()) { 390 return false; 391 } 392 393 for (i = 0; i < count; i++) { 394 if (!array[i]->isEqualTo(anArray->getObject(i))) { 395 return false; 396 } 397 } 398 399 return true; 400 } 401 402 bool 403 OSArray::isEqualTo(const OSMetaClassBase *anObject) const 404 { 405 OSArray *otherArray; 406 407 otherArray = OSDynamicCast(OSArray, anObject); 408 if (otherArray) { 409 return isEqualTo(otherArray); 410 } else { 411 return false; 412 } 413 } 414 415 OSObject * 416 OSArray::getObject(unsigned int index) const 417 { 418 if (index >= count) { 419 return NULL; 420 } else { 421 return static_cast<OSObject *>(const_cast<OSMetaClassBase *>(array[index].get())); 422 } 423 } 424 425 OSObject * 426 OSArray::getLastObject() const 427 { 428 if (count == 0) { 429 return NULL; 430 } else { 431 return static_cast<OSObject *>(const_cast<OSMetaClassBase *>(array[count - 1].get())); 432 } 433 } 434 435 unsigned int 436 OSArray::getNextIndexOfObject(const OSMetaClassBase * anObject, 437 unsigned int index) const 438 { 439 while ((index < count) && (array[index] != anObject)) { 440 index++; 441 } 442 if (index >= count) { 443 index = (unsigned int)-1; 444 } 445 return index; 446 } 447 448 unsigned int 449 OSArray::iteratorSize() const 450 { 451 return sizeof(unsigned int); 452 } 453 454 bool 455 OSArray::initIterator(void *inIterator) const 456 { 457 unsigned int *iteratorP = (unsigned int *) inIterator; 458 459 *iteratorP = 0; 460 return true; 461 } 462 463 bool 464 OSArray::getNextObjectForIterator(void *inIterator, OSObject **ret) const 465 { 466 unsigned int *iteratorP = (unsigned int *) inIterator; 467 unsigned int index = (*iteratorP)++; 468 469 if (index < count) { 470 *ret = static_cast<OSObject *>(const_cast<OSMetaClassBase *>(array[index].get())); 471 return true; 472 } else { 473 *ret = NULL; 474 return false; 475 } 476 } 477 478 bool 479 OSArray::serialize(OSSerialize *s) const 480 { 481 if (s->previouslySerialized(this)) { 482 return true; 483 } 484 485 if (!s->addXMLStartTag(this, "array")) { 486 return false; 487 } 488 489 for (unsigned i = 0; i < count; i++) { 490 if (array[i] == NULL || !array[i]->serialize(s)) { 491 return false; 492 } 493 } 494 495 return s->addXMLEndTag("array"); 496 } 497 498 unsigned 499 OSArray::setOptions(unsigned options, unsigned mask, void *) 500 { 501 unsigned old = super::setOptions(options, mask); 502 if ((old ^ options) & mask) { 503 // Value changed need to recurse over all of the child collections 504 for (unsigned i = 0; i < count; i++) { 505 OSCollection *coll = OSDynamicCast(OSCollection, array[i].get()); 506 if (coll) { 507 coll->setOptions(options, mask); 508 } 509 } 510 } 511 512 return old; 513 } 514 515 OSSharedPtr<OSCollection> 516 OSArray::copyCollection(OSDictionary *cycleDict) 517 { 518 OSSharedPtr<OSDictionary> ourCycleDict; 519 OSSharedPtr<OSCollection> ret; 520 OSSharedPtr<OSArray> newArray; 521 522 if (!cycleDict) { 523 ourCycleDict = OSDictionary::withCapacity(16); 524 if (!ourCycleDict) { 525 return nullptr; 526 } 527 cycleDict = ourCycleDict.get(); 528 } 529 530 do { 531 // Check for a cycle 532 ret = super::copyCollection(cycleDict); 533 if (ret) { 534 continue; 535 } 536 537 newArray = OSArray::withArray(this); 538 if (!newArray) { 539 continue; 540 } 541 542 // Insert object into cycle Dictionary 543 cycleDict->setObject((const OSSymbol *) this, newArray.get()); 544 545 for (unsigned int i = 0; i < count; i++) { 546 OSCollection *coll = 547 OSDynamicCast(OSCollection, static_cast<OSObject *>( 548 const_cast<OSMetaClassBase *>( 549 newArray->array[i].get()))); 550 551 if (coll) { 552 OSSharedPtr<OSCollection> newColl = coll->copyCollection(cycleDict); 553 if (!newColl) { 554 return ret; 555 } 556 557 newArray->replaceObject(i, newColl.get()); 558 } 559 } 560 561 ret = os::move(newArray); 562 } while (false); 563 564 return ret; 565 } 566