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