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