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