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