LXR darwin-xnu/libkern/c++/OSArray.cpp

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