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