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