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