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     int size;
  64
  65     if (!super::init())
  66         return false;
  67
  68     size = sizeof(const OSMetaClassBase *) * inCapacity;
  69     array = (const OSMetaClassBase **) kalloc(size);
  70     if (!array)
  71         return false;
  72
  73     count = 0;
  74     capacity = inCapacity;
  75     capacityIncrement = (inCapacity)? inCapacity : 16;
  76
  77     bzero(array, size);
  78     ACCUMSIZE(size);
  79
  80     return true;
  81 }
  82
  83 bool OSArray::initWithObjects(const OSObject *objects[],
  84                               unsigned int theCount,
  85                               unsigned int theCapacity)
  86 {
  87     unsigned int initCapacity;
  88
  89     if (!theCapacity)
  90         initCapacity = theCount;
  91     else if (theCount > theCapacity)
  92         return false;
  93     else
  94         initCapacity = theCapacity;
  95
  96     if (!objects || !initWithCapacity(initCapacity))
  97         return false;
  98
  99     for ( unsigned int i = 0; i < theCount; i++ ) {
 100         const OSMetaClassBase *newObject = *objects++;
 101
 102         if (!newObject)
 103             return false;
 104
 105         array[count++] = newObject;
 106         newObject->taggedRetain(OSTypeID(OSCollection));
 107     }
 108
 109     return true;
 110 }
 111
 112 bool OSArray::initWithArray(const OSArray *anArray,
 113                             unsigned int theCapacity)
 114 {
 115     if ( !anArray )
 116         return false;
 117
 118     return initWithObjects((const OSObject **) anArray->array,
 119                            anArray->count, theCapacity);
 120 }
 121
 122 OSArray *OSArray::withCapacity(unsigned int capacity)
 123 {
 124     OSArray *me = new OSArray;
 125
 126     if (me && !me->initWithCapacity(capacity)) {
 127         me->release();
 128         return 0;
 129     }
 130
 131     return me;
 132 }
 133
 134 OSArray *OSArray::withObjects(const OSObject *objects[],
 135                               unsigned int count,
 136                               unsigned int capacity)
 137 {
 138     OSArray *me = new OSArray;
 139
 140     if (me && !me->initWithObjects(objects, count, capacity)) {
 141         me->release();
 142         return 0;
 143     }
 144
 145     return me;
 146 }
 147
 148 OSArray *OSArray::withArray(const OSArray *array,
 149                             unsigned int capacity)
 150 {
 151     OSArray *me = new OSArray;
 152
 153     if (me && !me->initWithArray(array, capacity)) {
 154         me->release();
 155         return 0;
 156     }
 157
 158     return me;
 159 }
 160
 161 void OSArray::free()
 162 {
 163     // Clear immutability - assumes the container is doing the right thing
 164     (void) super::setOptions(0, kImmutable);
 165
 166     flushCollection();
 167
 168     if (array) {
 169         kfree(array, sizeof(const OSMetaClassBase *) * capacity);
 170         ACCUMSIZE( -(sizeof(const OSMetaClassBase *) * capacity) );
 171     }
 172
 173     super::free();
 174 }
 175
 176
 177 unsigned int OSArray::getCount() const { return count; }
 178 unsigned int OSArray::getCapacity() const { return capacity; }
 179 unsigned int OSArray::getCapacityIncrement() const { return capacityIncrement; }
 180 unsigned int OSArray::setCapacityIncrement(unsigned int increment)
 181 {
 182     capacityIncrement = (increment)? increment : 16;
 183
 184     return capacityIncrement;
 185 }
 186
 187 unsigned int OSArray::ensureCapacity(unsigned int newCapacity)
 188 {
 189     const OSMetaClassBase **newArray;
 190     int oldSize, newSize;
 191
 192     if (newCapacity <= capacity)
 193         return capacity;
 194
 195     // round up
 196     newCapacity = (((newCapacity - 1) / capacityIncrement) + 1)
 197                 * capacityIncrement;
 198     newSize = sizeof(const OSMetaClassBase *) * newCapacity;
 199
 200     newArray = (const OSMetaClassBase **) kalloc(newSize);
 201     if (newArray) {
 202         oldSize = sizeof(const OSMetaClassBase *) * capacity;
 203
 204         ACCUMSIZE(newSize - oldSize);
 205
 206         bcopy(array, newArray, oldSize);
 207         bzero(&newArray[capacity], newSize - oldSize);
 208         kfree(array, oldSize);
 209         array = newArray;
 210         capacity = newCapacity;
 211     }
 212
 213     return capacity;
 214 }
 215
 216 void OSArray::flushCollection()
 217 {
 218     unsigned int i;
 219
 220     haveUpdated();
 221     for (i = 0; i < count; i++) {
 222         array[i]->taggedRelease(OSTypeID(OSCollection));
 223     }
 224     count = 0;
 225 }
 226
 227 bool OSArray::setObject(const OSMetaClassBase *anObject)
 228 {
 229     return setObject(count, anObject);
 230 }
 231
 232 bool OSArray::setObject(unsigned int index, const OSMetaClassBase *anObject)
 233 {
 234     unsigned int i;
 235     unsigned int newCount = count + 1;
 236
 237     if ((index > count) || !anObject)
 238         return false;
 239
 240     // do we need more space?
 241     if (newCount > capacity && newCount > ensureCapacity(newCount))
 242         return false;
 243
 244     haveUpdated();
 245     if (index != count) {
 246         for (i = count; i > index; i--)
 247             array[i] = array[i-1];
 248     }
 249     array[index] = anObject;
 250     anObject->taggedRetain(OSTypeID(OSCollection));
 251     count++;
 252
 253     return true;
 254 }
 255
 256 bool OSArray::merge(const OSArray * otherArray)
 257 {
 258     unsigned int otherCount = otherArray->getCount();
 259     unsigned int newCount = count + otherCount;
 260
 261     if (!otherCount)
 262         return true;
 263
 264     // do we need more space?
 265     if (newCount > capacity && newCount > ensureCapacity(newCount))
 266         return false;
 267
 268     haveUpdated();
 269     for (unsigned int i = 0; i < otherCount; i++) {
 270         const OSMetaClassBase *newObject = otherArray->getObject(i);
 271
 272         array[count++] = newObject;
 273         newObject->taggedRetain(OSTypeID(OSCollection));
 274     }
 275
 276     return true;
 277 }
 278
 279 void OSArray::
 280 replaceObject(unsigned int index, const OSMetaClassBase *anObject)
 281 {
 282     const OSMetaClassBase *oldObject;
 283
 284     if ((index >= count) || !anObject)
 285         return;
 286
 287     haveUpdated();
 288     oldObject = array[index];
 289     array[index] = anObject;
 290     anObject->taggedRetain(OSTypeID(OSCollection));
 291
 292     oldObject->taggedRelease(OSTypeID(OSCollection));
 293 }
 294
 295 void OSArray::removeObject(unsigned int index)
 296 {
 297     unsigned int i;
 298     const OSMetaClassBase *oldObject;
 299
 300     if (index >= count)
 301         return;
 302
 303     haveUpdated();
 304     oldObject = array[index];
 305
 306     count--;
 307     for (i = index; i < count; i++)
 308         array[i] = array[i+1];
 309
 310     oldObject->taggedRelease(OSTypeID(OSCollection));
 311 }
 312
 313 bool OSArray::isEqualTo(const OSArray *anArray) const
 314 {
 315     unsigned int i;
 316
 317     if ( this == anArray )
 318         return true;
 319
 320     if ( count != anArray->getCount() )
 321         return false;
 322
 323     for ( i = 0; i < count; i++ ) {
 324         if ( !array[i]->isEqualTo(anArray->getObject(i)) )
 325             return false;
 326     }
 327
 328     return true;
 329 }
 330
 331 bool OSArray::isEqualTo(const OSMetaClassBase *anObject) const
 332 {
 333     OSArray *otherArray;
 334
 335     otherArray = OSDynamicCast(OSArray, anObject);
 336     if ( otherArray )
 337         return isEqualTo(otherArray);
 338     else
 339         return false;
 340 }
 341
 342 OSObject *OSArray::getObject(unsigned int index) const
 343 {
 344     if (index >= count)
 345         return 0;
 346     else
 347         return (OSObject *) (const_cast<OSMetaClassBase *>(array[index]));
 348 }
 349
 350 OSObject *OSArray::getLastObject() const
 351 {
 352     if (count == 0)
 353         return 0;
 354     else
 355         return ( OSObject *) (const_cast<OSMetaClassBase *>(array[count - 1]));
 356 }
 357
 358 unsigned int OSArray::getNextIndexOfObject(const OSMetaClassBase * anObject,
 359                                             unsigned int index) const
 360 {
 361     while ((index < count) && (array[index] != anObject))
 362         index++;
 363     if (index >= count)
 364         index = (unsigned int)-1;
 365     return index;
 366 }
 367
 368 unsigned int OSArray::iteratorSize() const
 369 {
 370     return sizeof(unsigned int);
 371 }
 372
 373 bool OSArray::initIterator(void *inIterator) const
 374 {
 375     unsigned int *iteratorP = (unsigned int *) inIterator;
 376
 377     *iteratorP = 0;
 378     return true;
 379 }
 380
 381 bool OSArray::getNextObjectForIterator(void *inIterator, OSObject **ret) const
 382 {
 383     unsigned int *iteratorP = (unsigned int *) inIterator;
 384     unsigned int index = (*iteratorP)++;
 385
 386     if (index < count) {
 387         *ret = (OSObject *)(const_cast<OSMetaClassBase *> (array[index]));
 388         return true;
 389     }
 390     else {
 391         *ret = 0;
 392         return false;
 393     }
 394 }
 395
 396 bool OSArray::serialize(OSSerialize *s) const
 397 {
 398     if (s->previouslySerialized(this)) return true;
 399
 400     if (!s->addXMLStartTag(this, "array")) return false;
 401
 402     for (unsigned i = 0; i < count; i++) {
 403         if (!array[i]->serialize(s)) return false;
 404     }
 405
 406     return s->addXMLEndTag("array");
 407 }
 408
 409 unsigned OSArray::setOptions(unsigned options, unsigned mask, void *)
 410 {
 411     unsigned old = super::setOptions(options, mask);
 412     if ((old ^ options) & mask) {
 413
 414         // Value changed need to recurse over all of the child collections
 415         for ( unsigned i = 0; i < count; i++ ) {
 416             OSCollection *coll = OSDynamicCast(OSCollection, array[i]);
 417             if (coll)
 418                 coll->setOptions(options, mask);
 419         }
 420     }
 421
 422     return old;
 423 }
 424
 425 OSCollection * OSArray::copyCollection(OSDictionary *cycleDict)
 426 {
 427     bool allocDict = !cycleDict;
 428     OSCollection *ret = 0;
 429     OSArray *newArray = 0;
 430
 431     if (allocDict) {
 432         cycleDict = OSDictionary::withCapacity(16);
 433         if (!cycleDict)
 434             return 0;
 435     }
 436
 437     do {
 438         // Check for a cycle
 439         ret = super::copyCollection(cycleDict);
 440         if (ret)
 441             continue;
 442
 443         newArray = OSArray::withArray(this);
 444         if (!newArray)
 445             continue;
 446
 447         // Insert object into cycle Dictionary
 448         cycleDict->setObject((const OSSymbol *) this, newArray);
 449
 450         for (unsigned int i = 0; i < count; i++) {
 451             OSCollection *coll =
 452                 OSDynamicCast(OSCollection, EXT_CAST(newArray->array[i]));
 453
 454             if (coll) {
 455                 OSCollection *newColl = coll->copyCollection(cycleDict);
 456                 if (!newColl)
 457                     goto abortCopy;
 458
 459                 newArray->replaceObject(i, newColl);
 460                 newColl->release();
 461             };
 462         };
 463
 464         ret = newArray;
 465         newArray = 0;
 466
 467     } while (false);
 468
 469 abortCopy:
 470     if (newArray)
 471         newArray->release();
 472
 473     if (allocDict)
 474         cycleDict->release();
 475
 476     return ret;
 477 }
 478