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