libkern/c++/OSArray.cpp

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