libkern/c++/OSArray.cpp

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