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     count = 0;
 224 }
 225
 226 bool OSArray::setObject(const OSMetaClassBase *anObject)
 227 {
 228     return setObject(count, anObject);
 229 }
 230
 231 bool OSArray::setObject(unsigned int index, const OSMetaClassBase *anObject)
 232 {
 233     unsigned int i;
 234     unsigned int newCount = count + 1;
 235
 236     if ((index > count) || !anObject)
 237         return false;
 238
 239     // do we need more space?
 240     if (newCount > capacity && newCount > ensureCapacity(newCount))
 241         return false;
 242
 243     haveUpdated();
 244     if (index != count) {
 245         for (i = count; i > index; i--)
 246             array[i] = array[i-1];
 247     }
 248     array[index] = anObject;
 249     anObject->taggedRetain(OSTypeID(OSCollection));
 250     count++;
 251
 252     return true;
 253 }
 254
 255 bool OSArray::merge(const OSArray * otherArray)
 256 {
 257     unsigned int otherCount = otherArray->getCount();
 258     unsigned int newCount = count + otherCount;
 259
 260     if (!otherCount)
 261         return true;
 262
 263     // do we need more space?
 264     if (newCount > capacity && newCount > ensureCapacity(newCount))
 265         return false;
 266
 267     haveUpdated();
 268     for (unsigned int i = 0; i < otherCount; i++) {
 269         const OSMetaClassBase *newObject = otherArray->getObject(i);
 270
 271         array[count++] = newObject;
 272         newObject->taggedRetain(OSTypeID(OSCollection));
 273     }
 274
 275     return true;
 276 }
 277
 278 void OSArray::
 279 replaceObject(unsigned int index, const OSMetaClassBase *anObject)
 280 {
 281     const OSMetaClassBase *oldObject;
 282
 283     if ((index >= count) || !anObject)
 284         return;
 285
 286     haveUpdated();
 287     oldObject = array[index];
 288     array[index] = anObject;
 289     anObject->taggedRetain(OSTypeID(OSCollection));
 290
 291     oldObject->taggedRelease(OSTypeID(OSCollection));
 292 }
 293
 294 void OSArray::removeObject(unsigned int index)
 295 {
 296     unsigned int i;
 297     const OSMetaClassBase *oldObject;
 298
 299     if (index >= count)
 300         return;
 301
 302     haveUpdated();
 303     oldObject = array[index];
 304
 305     count--;
 306     for (i = index; i < count; i++)
 307         array[i] = array[i+1];
 308
 309     oldObject->taggedRelease(OSTypeID(OSCollection));
 310 }
 311
 312 bool OSArray::isEqualTo(const OSArray *anArray) const
 313 {
 314     unsigned int i;
 315
 316     if ( this == anArray )
 317         return true;
 318
 319     if ( count != anArray->getCount() )
 320         return false;
 321
 322     for ( i = 0; i < count; i++ ) {
 323         if ( !array[i]->isEqualTo(anArray->getObject(i)) )
 324             return false;
 325     }
 326
 327     return true;
 328 }
 329
 330 bool OSArray::isEqualTo(const OSMetaClassBase *anObject) const
 331 {
 332     OSArray *otherArray;
 333
 334     otherArray = OSDynamicCast(OSArray, anObject);
 335     if ( otherArray )
 336         return isEqualTo(otherArray);
 337     else
 338         return false;
 339 }
 340
 341 OSObject *OSArray::getObject(unsigned int index) const
 342 {
 343     if (index >= count)
 344         return 0;
 345     else
 346         return (OSObject *) (const_cast<OSMetaClassBase *>(array[index]));
 347 }
 348
 349 OSObject *OSArray::getLastObject() const
 350 {
 351     if (count == 0)
 352         return 0;
 353     else
 354         return ( OSObject *) (const_cast<OSMetaClassBase *>(array[count - 1]));
 355 }
 356
 357 unsigned int OSArray::getNextIndexOfObject(const OSMetaClassBase * anObject,
 358                                             unsigned int index) const
 359 {
 360     while ((index < count) && (array[index] != anObject))
 361         index++;
 362     if (index >= count)
 363         index = (unsigned int)-1;
 364     return index;
 365 }
 366
 367 unsigned int OSArray::iteratorSize() const
 368 {
 369     return sizeof(unsigned int);
 370 }
 371
 372 bool OSArray::initIterator(void *inIterator) const
 373 {
 374     unsigned int *iteratorP = (unsigned int *) inIterator;
 375
 376     *iteratorP = 0;
 377     return true;
 378 }
 379
 380 bool OSArray::getNextObjectForIterator(void *inIterator, OSObject **ret) const
 381 {
 382     unsigned int *iteratorP = (unsigned int *) inIterator;
 383     unsigned int index = (*iteratorP)++;
 384
 385     if (index < count) {
 386         *ret = (OSObject *)(const_cast<OSMetaClassBase *> (array[index]));
 387         return true;
 388     }
 389     else {
 390         *ret = 0;
 391         return false;
 392     }
 393 }
 394
 395 bool OSArray::serialize(OSSerialize *s) const
 396 {
 397     if (s->previouslySerialized(this)) return true;
 398
 399     if (!s->addXMLStartTag(this, "array")) return false;
 400
 401     for (unsigned i = 0; i < count; i++) {
 402         if (!array[i]->serialize(s)) return false;
 403     }
 404
 405     return s->addXMLEndTag("array");
 406 }
 407
 408 unsigned OSArray::setOptions(unsigned options, unsigned mask, void *)
 409 {
 410     unsigned old = super::setOptions(options, mask);
 411     if ((old ^ options) & mask) {
 412
 413         // Value changed need to recurse over all of the child collections
 414         for ( unsigned i = 0; i < count; i++ ) {
 415             OSCollection *coll = OSDynamicCast(OSCollection, array[i]);
 416             if (coll)
 417                 coll->setOptions(options, mask);
 418         }
 419     }
 420
 421     return old;
 422 }
 423
 424 OSCollection * OSArray::copyCollection(OSDictionary *cycleDict)
 425 {
 426     bool allocDict = !cycleDict;
 427     OSCollection *ret = 0;
 428     OSArray *newArray = 0;
 429
 430     if (allocDict) {
 431         cycleDict = OSDictionary::withCapacity(16);
 432         if (!cycleDict)
 433             return 0;
 434     }
 435
 436     do {
 437         // Check for a cycle
 438         ret = super::copyCollection(cycleDict);
 439         if (ret)
 440             continue;
 441
 442         newArray = OSArray::withArray(this);
 443         if (!newArray)
 444             continue;
 445
 446         // Insert object into cycle Dictionary
 447         cycleDict->setObject((const OSSymbol *) this, newArray);
 448
 449         for (unsigned int i = 0; i < count; i++) {
 450             OSCollection *coll =
 451                 OSDynamicCast(OSCollection, EXT_CAST(newArray->array[i]));
 452
 453             if (coll) {
 454                 OSCollection *newColl = coll->copyCollection(cycleDict);
 455                 if (!newColl)
 456                     goto abortCopy;
 457
 458                 newArray->replaceObject(i, newColl);
 459                 newColl->release();
 460             };
 461         };
 462
 463         ret = newArray;
 464         newArray = 0;
 465
 466     } while (false);
 467
 468 abortCopy:
 469     if (newArray)
 470         newArray->release();
 471
 472     if (allocDict)
 473         cycleDict->release();
 474
 475     return ret;
 476 }
 477