libkern/c++/OSArray.cpp

   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