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