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
  33 OSDefineMetaClassAndStructors(OSArray, OSCollection)
  34 OSMetaClassDefineReservedUnused(OSArray, 0);
  35 OSMetaClassDefineReservedUnused(OSArray, 1);
  36 OSMetaClassDefineReservedUnused(OSArray, 2);
  37 OSMetaClassDefineReservedUnused(OSArray, 3);
  38 OSMetaClassDefineReservedUnused(OSArray, 4);
  39 OSMetaClassDefineReservedUnused(OSArray, 5);
  40 OSMetaClassDefineReservedUnused(OSArray, 6);
  41 OSMetaClassDefineReservedUnused(OSArray, 7);
  42
  43 #if OSALLOCDEBUG
  44 extern "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
  55 bool 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
  77 bool 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
 106 bool 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
 116 OSArray *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
 128 OSArray *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
 142 OSArray *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
 155 void 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
 171 unsigned int OSArray::getCount() const { return count; }
 172 unsigned int OSArray::getCapacity() const { return capacity; }
 173 unsigned int OSArray::getCapacityIncrement() const { return capacityIncrement; }
 174 unsigned int OSArray::setCapacityIncrement(unsigned int increment)
 175 {
 176     capacityIncrement = (increment)? increment : 16;
 177
 178     return capacityIncrement;
 179 }
 180
 181 unsigned 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
 210 void 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
 220 bool OSArray::setObject(const OSMetaClassBase *anObject)
 221 {
 222     return setObject(count, anObject);
 223 }
 224
 225 bool 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
 249 bool 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
 272 void OSArray::
 273 replaceObject(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
 288 void 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
 306 bool 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
 324 bool 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
 335 OSObject *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
 343 OSObject *OSArray::getLastObject() const
 344 {
 345     if (count == 0)
 346         return 0;
 347     else
 348         return ( OSObject *) (const_cast<OSMetaClassBase *>(array[count - 1]));
 349 }
 350
 351 unsigned 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
 361 unsigned int OSArray::iteratorSize() const
 362 {
 363     return sizeof(unsigned int);
 364 }
 365
 366 bool OSArray::initIterator(void *inIterator) const
 367 {
 368     unsigned int *iteratorP = (unsigned int *) inIterator;
 369
 370     *iteratorP = 0;
 371     return true;
 372 }
 373
 374 bool 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
 389 bool 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
 402 unsigned 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
 418 OSCollection * 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
 462 abortCopy:
 463     if (newArray)
 464         newArray->release();
 465
 466     if (allocDict)
 467         cycleDict->release();
 468
 469     return ret;
 470 }
 471