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