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++/OSSerialize.h> 28 #include <libkern/c++/OSLib.h> 29 30 #define super OSCollection 31 32 OSDefineMetaClassAndStructors(OSArray, OSCollection) 33 OSMetaClassDefineReservedUnused(OSArray, 0); 34 OSMetaClassDefineReservedUnused(OSArray, 1); 35 OSMetaClassDefineReservedUnused(OSArray, 2); 36 OSMetaClassDefineReservedUnused(OSArray, 3); 37 OSMetaClassDefineReservedUnused(OSArray, 4); 38 OSMetaClassDefineReservedUnused(OSArray, 5); 39 OSMetaClassDefineReservedUnused(OSArray, 6); 40 OSMetaClassDefineReservedUnused(OSArray, 7); 41 42 #if OSALLOCDEBUG 43 extern "C" { 44 extern int debug_container_malloc_size; 45 }; 46 #define ACCUMSIZE(s) do { debug_container_malloc_size += (s); } while(0) 47 #else 48 #define ACCUMSIZE(s) 49 #endif 50 51 bool OSArray::initWithCapacity(unsigned int inCapacity) 52 { 53 int size; 54 55 if (!super::init()) 56 return false; 57 58 size = sizeof(const OSMetaClassBase *) * inCapacity; 59 array = (const OSMetaClassBase **) kalloc(size); 60 if (!array) 61 return false; 62 63 count = 0; 64 capacity = inCapacity; 65 capacityIncrement = (inCapacity)? inCapacity : 16; 66 67 bzero(array, size); 68 ACCUMSIZE(size); 69 70 return this; 71 } 72 73 bool OSArray::initWithObjects(const OSObject *objects[], 74 unsigned int theCount, 75 unsigned int theCapacity = 0) 76 { 77 unsigned int capacity; 78 79 if (!theCapacity) 80 capacity = theCount; 81 else if (theCount > theCapacity) 82 return false; 83 else 84 capacity = theCapacity; 85 86 if (!objects || !initWithCapacity(capacity)) 87 return false; 88 89 for ( unsigned int i = 0; i < theCount; i++ ) { 90 const OSMetaClassBase *newObject = *objects++; 91 92 if (!newObject) 93 return false; 94 95 array[count++] = newObject; 96 newObject->taggedRetain(OSTypeID(OSCollection)); 97 } 98 99 return true; 100 } 101 102 bool OSArray::initWithArray(const OSArray *anArray, 103 unsigned int theCapacity = 0) 104 { 105 if ( !anArray ) 106 return false; 107 108 return initWithObjects((const OSObject **) anArray->array, 109 anArray->count, theCapacity); 110 } 111 112 OSArray *OSArray::withCapacity(unsigned int capacity) 113 { 114 OSArray *me = new OSArray; 115 116 if (me && !me->initWithCapacity(capacity)) { 117 me->free(); 118 return 0; 119 } 120 121 return me; 122 } 123 124 OSArray *OSArray::withObjects(const OSObject *objects[], 125 unsigned int count, 126 unsigned int capacity = 0) 127 { 128 OSArray *me = new OSArray; 129 130 if (me && !me->initWithObjects(objects, count, capacity)) { 131 me->free(); 132 return 0; 133 } 134 135 return me; 136 } 137 138 OSArray *OSArray::withArray(const OSArray *array, 139 unsigned int capacity = 0) 140 { 141 OSArray *me = new OSArray; 142 143 if (me && !me->initWithArray(array, capacity)) { 144 me->free(); 145 return 0; 146 } 147 148 return me; 149 } 150 151 void OSArray::free() 152 { 153 flushCollection(); 154 155 if (array) { 156 kfree((vm_offset_t)array, sizeof(const OSMetaClassBase *) * capacity); 157 ACCUMSIZE( -(sizeof(const OSMetaClassBase *) * capacity) ); 158 } 159 160 super::free(); 161 } 162 163 164 unsigned int OSArray::getCount() const { return count; } 165 unsigned int OSArray::getCapacity() const { return capacity; } 166 unsigned int OSArray::getCapacityIncrement() const { return capacityIncrement; } 167 unsigned int OSArray::setCapacityIncrement(unsigned int increment) 168 { 169 capacityIncrement = (increment)? increment : 16; 170 171 return capacityIncrement; 172 } 173 174 unsigned int OSArray::ensureCapacity(unsigned int newCapacity) 175 { 176 const OSMetaClassBase **newArray; 177 int oldSize, newSize; 178 179 if (newCapacity <= capacity) 180 return capacity; 181 182 // round up 183 newCapacity = (((newCapacity - 1) / capacityIncrement) + 1) 184 * capacityIncrement; 185 newSize = sizeof(const OSMetaClassBase *) * newCapacity; 186 187 newArray = (const OSMetaClassBase **) kalloc(newSize); 188 if (newArray) { 189 oldSize = sizeof(const OSMetaClassBase *) * capacity; 190 191 ACCUMSIZE(newSize - oldSize); 192 193 bcopy(array, newArray, oldSize); 194 bzero(&newArray[capacity], newSize - oldSize); 195 kfree((vm_offset_t)array, oldSize); 196 array = newArray; 197 capacity = newCapacity; 198 } 199 200 return capacity; 201 } 202 203 void OSArray::flushCollection() 204 { 205 unsigned int i; 206 207 haveUpdated(); 208 for (i = 0; i < count; i++) 209 array[i]->taggedRelease(OSTypeID(OSCollection)); 210 count = 0; 211 } 212 213 bool OSArray::setObject(const OSMetaClassBase *anObject) 214 { 215 return setObject(count, anObject); 216 } 217 218 bool OSArray::setObject(unsigned int index, const OSMetaClassBase *anObject) 219 { 220 unsigned int i; 221 unsigned int newCount = count + 1; 222 223 if ((index > count) || !anObject) 224 return false; 225 226 // do we need more space? 227 if (newCount > capacity && newCount > ensureCapacity(newCount)) 228 return false; 229 230 haveUpdated(); 231 if (index != count) { 232 for (i = count; i > index; i--) 233 array[i] = array[i-1]; 234 } 235 array[index] = anObject; 236 anObject->taggedRetain(OSTypeID(OSCollection)); 237 count++; 238 239 return true; 240 } 241 242 bool OSArray::merge(const OSArray * otherArray) 243 { 244 unsigned int otherCount = otherArray->getCount(); 245 unsigned int newCount = count + otherCount; 246 247 if (!otherCount) 248 return true; 249 250 // do we need more space? 251 if (newCount > capacity && newCount > ensureCapacity(newCount)) 252 return false; 253 254 haveUpdated(); 255 for (unsigned int i = 0; i < otherCount; i++) { 256 const OSMetaClassBase *newObject = otherArray->getObject(i); 257 258 array[count++] = newObject; 259 newObject->taggedRetain(OSTypeID(OSCollection)); 260 } 261 262 return true; 263 } 264 265 void OSArray:: 266 replaceObject(unsigned int index, const OSMetaClassBase *anObject) 267 { 268 const OSMetaClassBase *oldObject; 269 270 if ((index >= count) || !anObject) 271 return; 272 273 haveUpdated(); 274 oldObject = array[index]; 275 array[index] = anObject; 276 anObject->taggedRetain(OSTypeID(OSCollection)); 277 278 oldObject->taggedRelease(OSTypeID(OSCollection)); 279 } 280 281 void OSArray::removeObject(unsigned int index) 282 { 283 unsigned int i; 284 const OSMetaClassBase *oldObject; 285 286 if (index >= count) 287 return; 288 289 haveUpdated(); 290 oldObject = array[index]; 291 292 count--; 293 for (i = index; i < count; i++) 294 array[i] = array[i+1]; 295 296 oldObject->taggedRelease(OSTypeID(OSCollection)); 297 } 298 299 bool OSArray::isEqualTo(const OSArray *anArray) const 300 { 301 unsigned int i; 302 303 if ( this == anArray ) 304 return true; 305 306 if ( count != anArray->getCount() ) 307 return false; 308 309 for ( i = 0; i < count; i++ ) { 310 if ( !array[i]->isEqualTo(anArray->getObject(i)) ) 311 return false; 312 } 313 314 return true; 315 } 316 317 bool OSArray::isEqualTo(const OSMetaClassBase *anObject) const 318 { 319 OSArray *otherArray; 320 321 otherArray = OSDynamicCast(OSArray, anObject); 322 if ( otherArray ) 323 return isEqualTo(otherArray); 324 else 325 return false; 326 } 327 328 OSObject *OSArray::getObject(unsigned int index) const 329 { 330 if (index >= count) 331 return 0; 332 else 333 return (OSObject *) array[index]; 334 } 335 336 OSObject *OSArray::getLastObject() const 337 { 338 if (count == 0) 339 return 0; 340 else 341 return (OSObject *) array[count - 1]; 342 } 343 344 unsigned int OSArray::getNextIndexOfObject(const OSMetaClassBase * anObject, 345 unsigned int index) const 346 { 347 while ((index < count) && (array[index] != anObject)) 348 index++; 349 if (index >= count) 350 index = (unsigned int)-1; 351 return index; 352 } 353 354 unsigned int OSArray::iteratorSize() const 355 { 356 return sizeof(unsigned int); 357 } 358 359 bool OSArray::initIterator(void *inIterator) const 360 { 361 unsigned int *iteratorP = (unsigned int *) inIterator; 362 363 *iteratorP = 0; 364 return true; 365 } 366 367 bool OSArray::getNextObjectForIterator(void *inIterator, OSObject **ret) const 368 { 369 unsigned int *iteratorP = (unsigned int *) inIterator; 370 unsigned int index = (*iteratorP)++; 371 372 if (index < count) { 373 *ret = (OSObject *) array[index]; 374 return true; 375 } 376 else { 377 *ret = 0; 378 return false; 379 } 380 } 381 382 bool OSArray::serialize(OSSerialize *s) const 383 { 384 if (s->previouslySerialized(this)) return true; 385 386 if (!s->addXMLStartTag(this, "array")) return false; 387 388 for (unsigned i = 0; i < count; i++) { 389 if (!array[i]->serialize(s)) return false; 390 } 391 392 return s->addXMLEndTag("array"); 393 } 394