libkern/c++/OSOrderedSet.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
  29 #define IOKIT_ENABLE_SHARED_PTR
  30
  31 #include <libkern/c++/OSDictionary.h>
  32 #include <libkern/c++/OSLib.h>
  33 #include <libkern/c++/OSOrderedSet.h>
  34 #include <libkern/c++/OSSharedPtr.h>
  35 #include <os/cpp_util.h>
  36
  37 #define super OSCollection
  38
  39 OSDefineMetaClassAndStructors(OSOrderedSet, OSCollection)
  40 OSMetaClassDefineReservedUnused(OSOrderedSet, 0);
  41 OSMetaClassDefineReservedUnused(OSOrderedSet, 1);
  42 OSMetaClassDefineReservedUnused(OSOrderedSet, 2);
  43 OSMetaClassDefineReservedUnused(OSOrderedSet, 3);
  44 OSMetaClassDefineReservedUnused(OSOrderedSet, 4);
  45 OSMetaClassDefineReservedUnused(OSOrderedSet, 5);
  46 OSMetaClassDefineReservedUnused(OSOrderedSet, 6);
  47 OSMetaClassDefineReservedUnused(OSOrderedSet, 7);
  48
  49
  50 struct _Element {
  51         OSTaggedPtr<const OSMetaClassBase> obj;
  52 };
  53
  54 #define EXT_CAST(obj) \
  55     reinterpret_cast<OSObject *>(const_cast<OSMetaClassBase *>(obj))
  56
  57 bool
  58 OSOrderedSet::
  59 initWithCapacity(unsigned int inCapacity,
  60     OSOrderFunction inOrdering, void *inOrderingRef)
  61 {
  62         unsigned int size;
  63
  64         if (!super::init()) {
  65                 return false;
  66         }
  67
  68         if (inCapacity > (UINT_MAX / sizeof(_Element))) {
  69                 return false;
  70         }
  71
  72         size = sizeof(_Element) * inCapacity;
  73         array = (_Element *) kalloc_container(size);
  74         if (!array) {
  75                 return false;
  76         }
  77
  78         count = 0;
  79         capacity = inCapacity;
  80         capacityIncrement = (inCapacity)? inCapacity : 16;
  81         ordering = inOrdering;
  82         orderingRef = inOrderingRef;
  83
  84         bzero(array, size);
  85         OSCONTAINER_ACCUMSIZE(size);
  86
  87         return true;
  88 }
  89
  90 OSSharedPtr<OSOrderedSet>
  91 OSOrderedSet::
  92 withCapacity(unsigned int capacity,
  93     OSOrderFunction ordering, void * orderingRef)
  94 {
  95         auto me = OSMakeShared<OSOrderedSet>();
  96
  97         if (me && !me->initWithCapacity(capacity, ordering, orderingRef)) {
  98                 return nullptr;
  99         }
 100
 101         return me;
 102 }
 103
 104 void
 105 OSOrderedSet::free()
 106 {
 107         (void) super::setOptions(0, kImmutable);
 108         flushCollection();
 109
 110         if (array) {
 111                 kfree(array, sizeof(_Element) * capacity);
 112                 OSCONTAINER_ACCUMSIZE( -(sizeof(_Element) * capacity));
 113         }
 114
 115         super::free();
 116 }
 117
 118 unsigned int
 119 OSOrderedSet::getCount() const
 120 {
 121         return count;
 122 }
 123 unsigned int
 124 OSOrderedSet::getCapacity() const
 125 {
 126         return capacity;
 127 }
 128 unsigned int
 129 OSOrderedSet::getCapacityIncrement() const
 130 {
 131         return capacityIncrement;
 132 }
 133 unsigned int
 134 OSOrderedSet::setCapacityIncrement(unsigned int increment)
 135 {
 136         capacityIncrement = (increment)? increment : 16;
 137         return capacityIncrement;
 138 }
 139
 140 unsigned int
 141 OSOrderedSet::ensureCapacity(unsigned int newCapacity)
 142 {
 143         _Element *newArray;
 144         vm_size_t finalCapacity;
 145         vm_size_t oldSize, newSize;
 146
 147         if (newCapacity <= capacity) {
 148                 return capacity;
 149         }
 150
 151         // round up
 152         finalCapacity = (((newCapacity - 1) / capacityIncrement) + 1)
 153             * capacityIncrement;
 154         if (finalCapacity < newCapacity) {
 155                 return capacity;
 156         }
 157         newSize = sizeof(_Element) * finalCapacity;
 158
 159         newArray = (_Element *) kallocp_container(&newSize);
 160         if (newArray) {
 161                 // use all of the actual allocation size
 162                 finalCapacity = (newSize / sizeof(_Element));
 163                 if (finalCapacity > UINT_MAX) {
 164                         // failure, too large
 165                         kfree(newArray, newSize);
 166                         return capacity;
 167                 }
 168
 169                 oldSize = sizeof(_Element) * capacity;
 170
 171                 OSCONTAINER_ACCUMSIZE(((size_t)newSize) - ((size_t)oldSize));
 172
 173                 bcopy(array, newArray, oldSize);
 174                 bzero(&newArray[capacity], newSize - oldSize);
 175                 kfree(array, oldSize);
 176                 array = newArray;
 177                 capacity = (unsigned int) finalCapacity;
 178         }
 179
 180         return capacity;
 181 }
 182
 183 void
 184 OSOrderedSet::flushCollection()
 185 {
 186         unsigned int i;
 187
 188         haveUpdated();
 189
 190         for (i = 0; i < count; i++) {
 191                 array[i].obj.reset();
 192         }
 193
 194         count = 0;
 195 }
 196
 197 /* internal */
 198 bool
 199 OSOrderedSet::setObject(unsigned int index, const OSMetaClassBase *anObject)
 200 {
 201         unsigned int i;
 202         unsigned int newCount = count + 1;
 203
 204         if ((index > count) || !anObject) {
 205                 return false;
 206         }
 207
 208         if (containsObject(anObject)) {
 209                 return false;
 210         }
 211
 212         // do we need more space?
 213         if (newCount > capacity && newCount > ensureCapacity(newCount)) {
 214                 return false;
 215         }
 216
 217         haveUpdated();
 218         if (index != count) {
 219                 for (i = count; i > index; i--) {
 220                         array[i] = os::move(array[i - 1]);
 221                 }
 222         }
 223         array[index].obj.reset(anObject, OSRetain);
 224         count++;
 225
 226         return true;
 227 }
 228
 229 bool
 230 OSOrderedSet::setObject(unsigned int index, OSSharedPtr<const OSMetaClassBase> const& anObject)
 231 {
 232         return setObject(index, anObject.get());
 233 }
 234
 235 bool
 236 OSOrderedSet::setFirstObject(const OSMetaClassBase *anObject)
 237 {
 238         return setObject(0, anObject);
 239 }
 240
 241 bool
 242 OSOrderedSet::setFirstObject(OSSharedPtr<const OSMetaClassBase> const& anObject)
 243 {
 244         return setFirstObject(anObject.get());
 245 }
 246
 247 bool
 248 OSOrderedSet::setLastObject(const OSMetaClassBase *anObject)
 249 {
 250         return setObject( count, anObject);
 251 }
 252
 253 bool
 254 OSOrderedSet::setLastObject(OSSharedPtr<const OSMetaClassBase> const& anObject)
 255 {
 256         return setLastObject(anObject.get());
 257 }
 258
 259
 260 #define ORDER(obj1, obj2) \
 261     (ordering ? ((*ordering)( (const OSObject *) obj1, (const OSObject *) obj2, orderingRef)) : 0)
 262
 263 bool
 264 OSOrderedSet::setObject(const OSMetaClassBase *anObject )
 265 {
 266         unsigned int i;
 267
 268         // queue it behind those with same priority
 269         for (i = 0;
 270             (i < count) && (ORDER(array[i].obj.get(), anObject) >= 0);
 271             i++) {
 272         }
 273
 274         return setObject(i, anObject);
 275 }
 276
 277 bool
 278 OSOrderedSet::setObject(OSSharedPtr<const OSMetaClassBase> const& anObject)
 279 {
 280         return setObject(anObject.get());
 281 }
 282
 283 void
 284 OSOrderedSet::removeObject(const OSMetaClassBase *anObject)
 285 {
 286         bool                deleted = false;
 287         unsigned int        i;
 288
 289         for (i = 0; i < count; i++) {
 290                 if (deleted) {
 291                         array[i - 1] = os::move(array[i]);
 292                 } else if (array[i].obj == anObject) {
 293                         deleted = true;
 294                         haveUpdated(); // Pity we can't flush the log
 295                         array[i].obj.reset();
 296                 }
 297         }
 298
 299         if (deleted) {
 300                 count--;
 301         }
 302 }
 303
 304 void
 305 OSOrderedSet::removeObject(OSSharedPtr<const OSMetaClassBase> const& anObject)
 306 {
 307         return removeObject(anObject.get());
 308 }
 309
 310 bool
 311 OSOrderedSet::containsObject(const OSMetaClassBase *anObject) const
 312 {
 313         return anObject && member(anObject);
 314 }
 315
 316 bool
 317 OSOrderedSet::member(const OSMetaClassBase *anObject) const
 318 {
 319         unsigned int i;
 320
 321         for (i = 0;
 322             (i < count) && (array[i].obj != anObject);
 323             i++) {
 324         }
 325
 326         return i < count;
 327 }
 328
 329 /* internal */
 330 OSObject *
 331 OSOrderedSet::getObject( unsigned int index ) const
 332 {
 333         if (index >= count) {
 334                 return NULL;
 335         }
 336
 337         return const_cast<OSObject *>((const OSObject *) array[index].obj.get());
 338 }
 339
 340 OSObject *
 341 OSOrderedSet::getFirstObject() const
 342 {
 343         if (count) {
 344                 return const_cast<OSObject *>((const OSObject *) array[0].obj.get());
 345         } else {
 346                 return NULL;
 347         }
 348 }
 349
 350 OSObject *
 351 OSOrderedSet::getLastObject() const
 352 {
 353         if (count) {
 354                 return const_cast<OSObject *>((const OSObject *) array[count - 1].obj.get());
 355         } else {
 356                 return NULL;
 357         }
 358 }
 359
 360 SInt32
 361 OSOrderedSet::orderObject( const OSMetaClassBase * anObject )
 362 {
 363         return ORDER( anObject, NULL );
 364 }
 365
 366 void *
 367 OSOrderedSet::getOrderingRef()
 368 {
 369         return orderingRef;
 370 }
 371
 372 bool
 373 OSOrderedSet::isEqualTo(const OSOrderedSet *anOrderedSet) const
 374 {
 375         unsigned int i;
 376
 377         if (this == anOrderedSet) {
 378                 return true;
 379         }
 380
 381         if (count != anOrderedSet->getCount()) {
 382                 return false;
 383         }
 384
 385         for (i = 0; i < count; i++) {
 386                 if (!array[i].obj->isEqualTo(anOrderedSet->getObject(i))) {
 387                         return false;
 388                 }
 389         }
 390
 391         return true;
 392 }
 393
 394 bool
 395 OSOrderedSet::isEqualTo(const OSMetaClassBase *anObject) const
 396 {
 397         OSOrderedSet *oSet;
 398
 399         oSet = OSDynamicCast(OSOrderedSet, anObject);
 400         if (oSet) {
 401                 return isEqualTo(oSet);
 402         } else {
 403                 return false;
 404         }
 405 }
 406
 407 unsigned int
 408 OSOrderedSet::iteratorSize() const
 409 {
 410         return sizeof(unsigned int);
 411 }
 412
 413 bool
 414 OSOrderedSet::initIterator(void *inIterator) const
 415 {
 416         unsigned int *iteratorP = (unsigned int *) inIterator;
 417
 418         *iteratorP = 0;
 419         return true;
 420 }
 421
 422 bool
 423 OSOrderedSet::
 424 getNextObjectForIterator(void *inIterator, OSObject **ret) const
 425 {
 426         unsigned int *iteratorP = (unsigned int *) inIterator;
 427         unsigned int index = (*iteratorP)++;
 428
 429         if (index < count) {
 430                 *ret = const_cast<OSObject *>((const OSObject *) array[index].obj.get());
 431         } else {
 432                 *ret = NULL;
 433         }
 434
 435         return *ret != NULL;
 436 }
 437
 438
 439 unsigned
 440 OSOrderedSet::setOptions(unsigned options, unsigned mask, void *)
 441 {
 442         unsigned old = super::setOptions(options, mask);
 443         if ((old ^ options) & mask) {
 444                 // Value changed need to recurse over all of the child collections
 445                 for (unsigned i = 0; i < count; i++) {
 446                         OSCollection *coll = OSDynamicCast(OSCollection, array[i].obj.get());
 447                         if (coll) {
 448                                 coll->setOptions(options, mask);
 449                         }
 450                 }
 451         }
 452
 453         return old;
 454 }
 455
 456 OSSharedPtr<OSCollection>
 457 OSOrderedSet::copyCollection(OSDictionary *cycleDict)
 458 {
 459         OSSharedPtr<OSDictionary> ourCycleDict;
 460         OSSharedPtr<OSCollection> ret;
 461         OSSharedPtr<OSOrderedSet> newSet;
 462
 463         if (!cycleDict) {
 464                 ourCycleDict = OSDictionary::withCapacity(16);
 465                 if (!ourCycleDict) {
 466                         return nullptr;
 467                 }
 468                 cycleDict = ourCycleDict.get();
 469         }
 470
 471         do {
 472                 // Check for a cycle
 473                 ret = super::copyCollection(cycleDict);
 474                 if (ret) {
 475                         continue;
 476                 }
 477
 478                 // Duplicate the set with no contents
 479                 newSet = OSOrderedSet::withCapacity(capacity, ordering, orderingRef);
 480                 if (!newSet) {
 481                         continue;
 482                 }
 483
 484                 // Insert object into cycle Dictionary
 485                 cycleDict->setObject((const OSSymbol *) this, newSet.get());
 486
 487                 newSet->capacityIncrement = capacityIncrement;
 488
 489                 // Now copy over the contents to the new duplicate
 490                 for (unsigned int i = 0; i < count; i++) {
 491                         OSObject *obj = EXT_CAST(array[i].obj.get());
 492                         OSCollection *coll = OSDynamicCast(OSCollection, obj);
 493                         if (coll) {
 494                                 OSSharedPtr<OSCollection> newColl = coll->copyCollection(cycleDict);
 495                                 if (newColl) {
 496                                         obj = newColl.get(); // Rely on cycleDict ref for a bit
 497                                 } else {
 498                                         return ret;
 499                                 }
 500                         }
 501
 502                         newSet->setLastObject(obj);
 503                 }
 504
 505                 ret = os::move(newSet);
 506         } while (false);
 507
 508         return ret;
 509 }