1 /* 2 * Copyright (c) 2000 Apple Computer, Inc. All rights reserved. 3 * 4 * @APPLE_LICENSE_HEADER_START@ 5 * 6 * The contents of this file constitute Original Code as defined in and 7 * are subject to the Apple Public Source License Version 1.1 (the 8 * "License"). You may not use this file except in compliance with the 9 * License. Please obtain a copy of the License at 10 * http://www.apple.com/publicsource and read it before using this file. 11 * 12 * This Original Code and all software distributed under the License are 13 * distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER 14 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, 15 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, 16 * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT. Please see the 17 * License for the specific language governing rights and limitations 18 * under the License. 19 * 20 * @APPLE_LICENSE_HEADER_END@ 21 */ 22 /* IOArray.m created by rsulack on Fri 12-Sep-1997 */ 23 /* IOArray.cpp converted to C++ by gvdl on Fri 1998-10-30 */ 24 25 26 #include <libkern/c++/OSArray.h> 27 #include <libkern/c++/OSDictionary.h> 28 #include <libkern/c++/OSSerialize.h> 29 #include <libkern/c++/OSLib.h> 30 31 #define super OSCollection 32 33 OSDefineMetaClassAndStructors(OSArray, OSCollection) 34 OSMetaClassDefineReservedUnused(OSArray, 0); 35 OSMetaClassDefineReservedUnused(OSArray, 1); 36 OSMetaClassDefineReservedUnused(OSArray, 2); 37 OSMetaClassDefineReservedUnused(OSArray, 3); 38 OSMetaClassDefineReservedUnused(OSArray, 4); 39 OSMetaClassDefineReservedUnused(OSArray, 5); 40 OSMetaClassDefineReservedUnused(OSArray, 6); 41 OSMetaClassDefineReservedUnused(OSArray, 7); 42 43 #if OSALLOCDEBUG 44 extern "C" { 45 extern int debug_container_malloc_size; 46 }; 47 #define ACCUMSIZE(s) do { debug_container_malloc_size += (s); } while(0) 48 #else 49 #define ACCUMSIZE(s) 50 #endif 51 52 #define EXT_CAST(obj) \ 53 reinterpret_cast<OSObject *>(const_cast<OSMetaClassBase *>(obj)) 54 55 bool OSArray::initWithCapacity(unsigned int inCapacity) 56 { 57 int size; 58 59 if (!super::init()) 60 return false; 61 62 size = sizeof(const OSMetaClassBase *) * inCapacity; 63 array = (const OSMetaClassBase **) kalloc(size); 64 if (!array) 65 return false; 66 67 count = 0; 68 capacity = inCapacity; 69 capacityIncrement = (inCapacity)? inCapacity : 16; 70 71 bzero(array, size); 72 ACCUMSIZE(size); 73 74 return true; 75 } 76 77 bool OSArray::initWithObjects(const OSObject *objects[], 78 unsigned int theCount, 79 unsigned int theCapacity) 80 { 81 unsigned int initCapacity; 82 83 if (!theCapacity) 84 initCapacity = theCount; 85 else if (theCount > theCapacity) 86 return false; 87 else 88 initCapacity = theCapacity; 89 90 if (!objects || !initWithCapacity(initCapacity)) 91 return false; 92 93 for ( unsigned int i = 0; i < theCount; i++ ) { 94 const OSMetaClassBase *newObject = *objects++; 95 96 if (!newObject) 97 return false; 98 99 array[count++] = newObject; 100 newObject->taggedRetain(OSTypeID(OSCollection)); 101 } 102 103 return true; 104 } 105 106 bool OSArray::initWithArray(const OSArray *anArray, 107 unsigned int theCapacity) 108 { 109 if ( !anArray ) 110 return false; 111 112 return initWithObjects((const OSObject **) anArray->array, 113 anArray->count, theCapacity); 114 } 115 116 OSArray *OSArray::withCapacity(unsigned int capacity) 117 { 118 OSArray *me = new OSArray; 119 120 if (me && !me->initWithCapacity(capacity)) { 121 me->release(); 122 return 0; 123 } 124 125 return me; 126 } 127 128 OSArray *OSArray::withObjects(const OSObject *objects[], 129 unsigned int count, 130 unsigned int capacity) 131 { 132 OSArray *me = new OSArray; 133 134 if (me && !me->initWithObjects(objects, count, capacity)) { 135 me->release(); 136 return 0; 137 } 138 139 return me; 140 } 141 142 OSArray *OSArray::withArray(const OSArray *array, 143 unsigned int capacity) 144 { 145 OSArray *me = new OSArray; 146 147 if (me && !me->initWithArray(array, capacity)) { 148 me->release(); 149 return 0; 150 } 151 152 return me; 153 } 154 155 void OSArray::free() 156 { 157 // Clear immutability - assumes the container is doing the right thing 158 (void) super::setOptions(0, kImmutable); 159 160 flushCollection(); 161 162 if (array) { 163 kfree(array, sizeof(const OSMetaClassBase *) * capacity); 164 ACCUMSIZE( -(sizeof(const OSMetaClassBase *) * capacity) ); 165 } 166 167 super::free(); 168 } 169 170 171 unsigned int OSArray::getCount() const { return count; } 172 unsigned int OSArray::getCapacity() const { return capacity; } 173 unsigned int OSArray::getCapacityIncrement() const { return capacityIncrement; } 174 unsigned int OSArray::setCapacityIncrement(unsigned int increment) 175 { 176 capacityIncrement = (increment)? increment : 16; 177 178 return capacityIncrement; 179 } 180 181 unsigned int OSArray::ensureCapacity(unsigned int newCapacity) 182 { 183 const OSMetaClassBase **newArray; 184 int oldSize, newSize; 185 186 if (newCapacity <= capacity) 187 return capacity; 188 189 // round up 190 newCapacity = (((newCapacity - 1) / capacityIncrement) + 1) 191 * capacityIncrement; 192 newSize = sizeof(const OSMetaClassBase *) * newCapacity; 193 194 newArray = (const OSMetaClassBase **) kalloc(newSize); 195 if (newArray) { 196 oldSize = sizeof(const OSMetaClassBase *) * capacity; 197 198 ACCUMSIZE(newSize - oldSize); 199 200 bcopy(array, newArray, oldSize); 201 bzero(&newArray[capacity], newSize - oldSize); 202 kfree(array, oldSize); 203 array = newArray; 204 capacity = newCapacity; 205 } 206 207 return capacity; 208 } 209 210 void OSArray::flushCollection() 211 { 212 unsigned int i; 213 214 haveUpdated(); 215 for (i = 0; i < count; i++) 216 array[i]->taggedRelease(OSTypeID(OSCollection)); 217 count = 0; 218 } 219 220 bool OSArray::setObject(const OSMetaClassBase *anObject) 221 { 222 return setObject(count, anObject); 223 } 224 225 bool OSArray::setObject(unsigned int index, const OSMetaClassBase *anObject) 226 { 227 unsigned int i; 228 unsigned int newCount = count + 1; 229 230 if ((index > count) || !anObject) 231 return false; 232 233 // do we need more space? 234 if (newCount > capacity && newCount > ensureCapacity(newCount)) 235 return false; 236 237 haveUpdated(); 238 if (index != count) { 239 for (i = count; i > index; i--) 240 array[i] = array[i-1]; 241 } 242 array[index] = anObject; 243 anObject->taggedRetain(OSTypeID(OSCollection)); 244 count++; 245 246 return true; 247 } 248 249 bool OSArray::merge(const OSArray * otherArray) 250 { 251 unsigned int otherCount = otherArray->getCount(); 252 unsigned int newCount = count + otherCount; 253 254 if (!otherCount) 255 return true; 256 257 // do we need more space? 258 if (newCount > capacity && newCount > ensureCapacity(newCount)) 259 return false; 260 261 haveUpdated(); 262 for (unsigned int i = 0; i < otherCount; i++) { 263 const OSMetaClassBase *newObject = otherArray->getObject(i); 264 265 array[count++] = newObject; 266 newObject->taggedRetain(OSTypeID(OSCollection)); 267 } 268 269 return true; 270 } 271 272 void OSArray:: 273 replaceObject(unsigned int index, const OSMetaClassBase *anObject) 274 { 275 const OSMetaClassBase *oldObject; 276 277 if ((index >= count) || !anObject) 278 return; 279 280 haveUpdated(); 281 oldObject = array[index]; 282 array[index] = anObject; 283 anObject->taggedRetain(OSTypeID(OSCollection)); 284 285 oldObject->taggedRelease(OSTypeID(OSCollection)); 286 } 287 288 void OSArray::removeObject(unsigned int index) 289 { 290 unsigned int i; 291 const OSMetaClassBase *oldObject; 292 293 if (index >= count) 294 return; 295 296 haveUpdated(); 297 oldObject = array[index]; 298 299 count--; 300 for (i = index; i < count; i++) 301 array[i] = array[i+1]; 302 303 oldObject->taggedRelease(OSTypeID(OSCollection)); 304 } 305 306 bool OSArray::isEqualTo(const OSArray *anArray) const 307 { 308 unsigned int i; 309 310 if ( this == anArray ) 311 return true; 312 313 if ( count != anArray->getCount() ) 314 return false; 315 316 for ( i = 0; i < count; i++ ) { 317 if ( !array[i]->isEqualTo(anArray->getObject(i)) ) 318 return false; 319 } 320 321 return true; 322 } 323 324 bool OSArray::isEqualTo(const OSMetaClassBase *anObject) const 325 { 326 OSArray *otherArray; 327 328 otherArray = OSDynamicCast(OSArray, anObject); 329 if ( otherArray ) 330 return isEqualTo(otherArray); 331 else 332 return false; 333 } 334 335 OSObject *OSArray::getObject(unsigned int index) const 336 { 337 if (index >= count) 338 return 0; 339 else 340 return (OSObject *) (const_cast<OSMetaClassBase *>(array[index])); 341 } 342 343 OSObject *OSArray::getLastObject() const 344 { 345 if (count == 0) 346 return 0; 347 else 348 return ( OSObject *) (const_cast<OSMetaClassBase *>(array[count - 1])); 349 } 350 351 unsigned int OSArray::getNextIndexOfObject(const OSMetaClassBase * anObject, 352 unsigned int index) const 353 { 354 while ((index < count) && (array[index] != anObject)) 355 index++; 356 if (index >= count) 357 index = (unsigned int)-1; 358 return index; 359 } 360 361 unsigned int OSArray::iteratorSize() const 362 { 363 return sizeof(unsigned int); 364 } 365 366 bool OSArray::initIterator(void *inIterator) const 367 { 368 unsigned int *iteratorP = (unsigned int *) inIterator; 369 370 *iteratorP = 0; 371 return true; 372 } 373 374 bool OSArray::getNextObjectForIterator(void *inIterator, OSObject **ret) const 375 { 376 unsigned int *iteratorP = (unsigned int *) inIterator; 377 unsigned int index = (*iteratorP)++; 378 379 if (index < count) { 380 *ret = (OSObject *)(const_cast<OSMetaClassBase *> (array[index])); 381 return true; 382 } 383 else { 384 *ret = 0; 385 return false; 386 } 387 } 388 389 bool OSArray::serialize(OSSerialize *s) const 390 { 391 if (s->previouslySerialized(this)) return true; 392 393 if (!s->addXMLStartTag(this, "array")) return false; 394 395 for (unsigned i = 0; i < count; i++) { 396 if (!array[i]->serialize(s)) return false; 397 } 398 399 return s->addXMLEndTag("array"); 400 } 401 402 unsigned OSArray::setOptions(unsigned options, unsigned mask, void *) 403 { 404 unsigned old = super::setOptions(options, mask); 405 if ((old ^ options) & mask) { 406 407 // Value changed need to recurse over all of the child collections 408 for ( unsigned i = 0; i < count; i++ ) { 409 OSCollection *coll = OSDynamicCast(OSCollection, array[i]); 410 if (coll) 411 coll->setOptions(options, mask); 412 } 413 } 414 415 return old; 416 } 417 418 OSCollection * OSArray::copyCollection(OSDictionary *cycleDict) 419 { 420 bool allocDict = !cycleDict; 421 OSCollection *ret = 0; 422 OSArray *newArray = 0; 423 424 if (allocDict) { 425 cycleDict = OSDictionary::withCapacity(16); 426 if (!cycleDict) 427 return 0; 428 } 429 430 do { 431 // Check for a cycle 432 ret = super::copyCollection(cycleDict); 433 if (ret) 434 continue; 435 436 newArray = OSArray::withArray(this); 437 if (!newArray) 438 continue; 439 440 // Insert object into cycle Dictionary 441 cycleDict->setObject((const OSSymbol *) this, newArray); 442 443 for (unsigned int i = 0; i < count; i++) { 444 OSCollection *coll = 445 OSDynamicCast(OSCollection, EXT_CAST(newArray->array[i])); 446 447 if (coll) { 448 OSCollection *newColl = coll->copyCollection(cycleDict); 449 if (!newColl) 450 goto abortCopy; 451 452 newArray->replaceObject(i, newColl); 453 newColl->release(); 454 }; 455 }; 456 457 ret = newArray; 458 newArray = 0; 459 460 } while (false); 461 462 abortCopy: 463 if (newArray) 464 newArray->release(); 465 466 if (allocDict) 467 cycleDict->release(); 468 469 return ret; 470 } 471 472