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