libkern/c++/OSSet.cpp

   1 /*
   2  * Copyright (c) 2000, 2014 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 /* IOSet.m created by rsulack on Thu 11-Jun-1998 */
  29
  30 #define IOKIT_ENABLE_SHARED_PTR
  31
  32 #include <libkern/c++/OSArray.h>
  33 #include <libkern/c++/OSDictionary.h>
  34 #include <libkern/c++/OSSerialize.h>
  35 #include <libkern/c++/OSSet.h>
  36 #include <libkern/c++/OSSharedPtr.h>
  37 #include <os/cpp_util.h>
  38 #include <kern/zalloc.h>
  39
  40 #define super OSCollection
  41
  42 OSDefineMetaClassAndStructorsWithZone(OSSet, OSCollection,
  43     ZC_ZFREE_CLEARMEM)
  44 OSMetaClassDefineReservedUnused(OSSet, 0);
  45 OSMetaClassDefineReservedUnused(OSSet, 1);
  46 OSMetaClassDefineReservedUnused(OSSet, 2);
  47 OSMetaClassDefineReservedUnused(OSSet, 3);
  48 OSMetaClassDefineReservedUnused(OSSet, 4);
  49 OSMetaClassDefineReservedUnused(OSSet, 5);
  50 OSMetaClassDefineReservedUnused(OSSet, 6);
  51 OSMetaClassDefineReservedUnused(OSSet, 7);
  52
  53 #define EXT_CAST(obj) \
  54     reinterpret_cast<OSObject *>(const_cast<OSMetaClassBase *>(obj))
  55
  56 bool
  57 OSSet::initWithCapacity(unsigned int inCapacity)
  58 {
  59         if (!super::init()) {
  60                 return false;
  61         }
  62
  63         members = OSArray::withCapacity(inCapacity);
  64         if (!members) {
  65                 return false;
  66         }
  67
  68         return true;
  69 }
  70
  71 bool
  72 OSSet::initWithObjects(const OSObject *inObjects[],
  73     unsigned int inCount,
  74     unsigned int inCapacity)
  75 {
  76         unsigned int capacity = inCount;
  77
  78         if (inCapacity) {
  79                 if (inCount > inCapacity) {
  80                         return false;
  81                 }
  82
  83                 capacity = inCapacity;
  84         }
  85
  86         if (!inObjects || !initWithCapacity(capacity)) {
  87                 return false;
  88         }
  89
  90         for (unsigned int i = 0; i < inCount; i++) {
  91 // xx-review: no test here for failure of setObject()
  92                 if (members->getCount() < capacity) {
  93                         setObject(inObjects[i]);
  94                 } else {
  95                         return false;
  96                 }
  97         }
  98
  99         return true;
 100 }
 101
 102 bool
 103 OSSet::initWithArray(const OSArray *inArray,
 104     unsigned int inCapacity)
 105 {
 106         if (!inArray) {
 107                 return false;
 108         }
 109
 110         return initWithObjects((const OSObject **) inArray->array,
 111                    inArray->count, inCapacity);
 112 }
 113
 114 bool
 115 OSSet::initWithSet(const OSSet *inSet,
 116     unsigned int inCapacity)
 117 {
 118         return initWithArray(inSet->members.get(), inCapacity);
 119 }
 120
 121 OSSharedPtr<OSSet>
 122 OSSet::withCapacity(unsigned int capacity)
 123 {
 124         OSSharedPtr<OSSet> me = OSMakeShared<OSSet>();
 125
 126         if (me && !me->initWithCapacity(capacity)) {
 127                 return nullptr;
 128         }
 129
 130         return me;
 131 }
 132
 133 OSSharedPtr<OSSet>
 134 OSSet::withObjects(const OSObject *objects[],
 135     unsigned int count,
 136     unsigned int capacity)
 137 {
 138         OSSharedPtr<OSSet> me = OSMakeShared<OSSet>();
 139
 140         if (me && !me->initWithObjects(objects, count, capacity)) {
 141                 return nullptr;
 142         }
 143
 144         return me;
 145 }
 146
 147 OSSharedPtr<OSSet>
 148 OSSet::withArray(const OSArray *array,
 149     unsigned int capacity)
 150 {
 151         OSSharedPtr<OSSet> me = OSMakeShared<OSSet>();
 152
 153         if (me && !me->initWithArray(array, capacity)) {
 154                 return nullptr;
 155         }
 156
 157         return me;
 158 }
 159
 160 OSSharedPtr<OSSet>
 161 OSSet::withSet(const OSSet *set,
 162     unsigned int capacity)
 163 {
 164         OSSharedPtr<OSSet> me = OSMakeShared<OSSet>();;
 165
 166         if (me && !me->initWithSet(set, capacity)) {
 167                 return nullptr;
 168         }
 169
 170         return me;
 171 }
 172
 173 void
 174 OSSet::free()
 175 {
 176         if (members) {
 177                 (void) members->super::setOptions(0, kImmutable);
 178         }
 179
 180         super::free();
 181 }
 182
 183 unsigned int
 184 OSSet::getCount() const
 185 {
 186         return members->count;
 187 }
 188
 189 unsigned int
 190 OSSet::getCapacity() const
 191 {
 192         return members->capacity;
 193 }
 194
 195 unsigned int
 196 OSSet::getCapacityIncrement() const
 197 {
 198         return members->capacityIncrement;
 199 }
 200
 201 unsigned int
 202 OSSet::setCapacityIncrement(unsigned int increment)
 203 {
 204         return members->setCapacityIncrement(increment);
 205 }
 206
 207 unsigned int
 208 OSSet::ensureCapacity(unsigned int newCapacity)
 209 {
 210         return members->ensureCapacity(newCapacity);
 211 }
 212
 213 void
 214 OSSet::flushCollection()
 215 {
 216         haveUpdated();
 217         members->flushCollection();
 218 }
 219
 220 bool
 221 OSSet::setObject(const OSMetaClassBase *anObject)
 222 {
 223         if (containsObject(anObject)) {
 224                 return false;
 225         } else {
 226                 haveUpdated();
 227                 return members->setObject(anObject);
 228         }
 229 }
 230
 231 bool
 232 OSSet::setObject(OSSharedPtr<const OSMetaClassBase> const& anObject)
 233 {
 234         return setObject(anObject.get());
 235 }
 236
 237 bool
 238 OSSet::merge(const OSArray * array)
 239 {
 240         const OSMetaClassBase * anObject = NULL;
 241         bool                    result   = true;
 242
 243         for (int i = 0; (anObject = array->getObject(i)); i++) {
 244                 /* setObject() returns false if the object is already in the set,
 245                  * so we have to check beforehand here with containsObject().
 246                  */
 247                 if (containsObject(anObject)) {
 248                         continue;
 249                 }
 250                 if (!setObject(anObject)) {
 251                         result = false;
 252                 }
 253         }
 254
 255         return result;
 256 }
 257
 258 bool
 259 OSSet::merge(const OSSet * set)
 260 {
 261         return merge(set->members.get());
 262 }
 263
 264 void
 265 OSSet::removeObject(const OSMetaClassBase *anObject)
 266 {
 267         const OSMetaClassBase *probeObject;
 268
 269         for (int i = 0; (probeObject = members->getObject(i)); i++) {
 270                 if (probeObject == anObject) {
 271                         haveUpdated();
 272                         members->removeObject(i);
 273                         return;
 274                 }
 275         }
 276 }
 277
 278 void
 279 OSSet::removeObject(OSSharedPtr<const OSMetaClassBase> const& anObject)
 280 {
 281         removeObject(anObject.get());
 282 }
 283
 284
 285 bool
 286 OSSet::containsObject(const OSMetaClassBase *anObject) const
 287 {
 288         return anObject && member(anObject);
 289 }
 290
 291 bool
 292 OSSet::member(const OSMetaClassBase *anObject) const
 293 {
 294         OSMetaClassBase *probeObject;
 295
 296         for (int i = 0; (probeObject = members->getObject(i)); i++) {
 297                 if (probeObject == anObject) {
 298                         return true;
 299                 }
 300         }
 301
 302         return false;
 303 }
 304
 305 OSObject *
 306 OSSet::getAnyObject() const
 307 {
 308         return members->getObject(0);
 309 }
 310
 311 bool
 312 OSSet::isEqualTo(const OSSet *aSet) const
 313 {
 314         unsigned int count;
 315         unsigned int i;
 316         const OSMetaClassBase *obj1;
 317         const OSMetaClassBase *obj2;
 318
 319         if (this == aSet) {
 320                 return true;
 321         }
 322
 323         count = members->count;
 324         if (count != aSet->getCount()) {
 325                 return false;
 326         }
 327
 328         for (i = 0; i < count; i++) {
 329                 obj1 = aSet->members->getObject(i);
 330                 if (containsObject(obj1)) {
 331                         continue;
 332                 }
 333                 obj2 = members->getObject(i);
 334                 if (!obj1 || !obj2) {
 335                         return false;
 336                 }
 337
 338                 if (!obj1->isEqualTo(obj2)) {
 339                         return false;
 340                 }
 341         }
 342
 343         return true;
 344 }
 345
 346 bool
 347 OSSet::isEqualTo(const OSMetaClassBase *anObject) const
 348 {
 349         OSSet *otherSet;
 350
 351         otherSet = OSDynamicCast(OSSet, anObject);
 352         if (otherSet) {
 353                 return isEqualTo(otherSet);
 354         } else {
 355                 return false;
 356         }
 357 }
 358
 359 unsigned int
 360 OSSet::iteratorSize() const
 361 {
 362         return sizeof(unsigned int);
 363 }
 364
 365 bool
 366 OSSet::initIterator(void *inIterator) const
 367 {
 368         unsigned int *iteratorP = (unsigned int *) inIterator;
 369
 370         *iteratorP = 0;
 371         return true;
 372 }
 373
 374 bool
 375 OSSet::getNextObjectForIterator(void *inIterator, OSObject **ret) const
 376 {
 377         unsigned int *iteratorP = (unsigned int *) inIterator;
 378         unsigned int index = (*iteratorP)++;
 379
 380         if (index < members->count) {
 381                 *ret = members->getObject(index);
 382         } else {
 383                 *ret = NULL;
 384         }
 385
 386         return *ret != NULL;
 387 }
 388
 389 bool
 390 OSSet::serialize(OSSerialize *s) const
 391 {
 392         const OSMetaClassBase *o;
 393
 394         if (s->previouslySerialized(this)) {
 395                 return true;
 396         }
 397
 398         if (!s->addXMLStartTag(this, "set")) {
 399                 return false;
 400         }
 401
 402         for (int i = 0; (o = members->getObject(i)); i++) {
 403                 if (!o->serialize(s)) {
 404                         return false;
 405                 }
 406         }
 407
 408         return s->addXMLEndTag("set");
 409 }
 410
 411 unsigned
 412 OSSet::setOptions(unsigned options, unsigned mask, void *)
 413 {
 414         unsigned old = super::setOptions(options, mask);
 415         if ((old ^ options) & mask) {
 416                 members->setOptions(options, mask);
 417         }
 418
 419         return old;
 420 }
 421
 422 OSSharedPtr<OSCollection>
 423 OSSet::copyCollection(OSDictionary *cycleDict)
 424 {
 425         OSSharedPtr<OSDictionary> ourCycleDict;
 426         OSSharedPtr<OSCollection> ret;
 427         OSSharedPtr<OSSet> newSet;
 428
 429         if (!cycleDict) {
 430                 ourCycleDict = OSDictionary::withCapacity(16);
 431                 if (!ourCycleDict) {
 432                         return nullptr;
 433                 }
 434                 cycleDict = ourCycleDict.get();
 435         }
 436
 437         do {
 438                 // Check for a cycle
 439                 ret = super::copyCollection(cycleDict);
 440                 if (ret) {
 441                         continue; // Found it
 442                 }
 443                 newSet = OSSet::withCapacity(members->capacity);
 444                 if (!newSet) {
 445                         continue; // Couldn't create new set abort
 446                 }
 447                 // Insert object into cycle Dictionary
 448                 cycleDict->setObject((const OSSymbol *) this, newSet.get());
 449
 450                 OSArray *newMembers = newSet->members.get();
 451                 newMembers->capacityIncrement = members->capacityIncrement;
 452
 453                 // Now copy over the contents into the new duplicate
 454                 for (unsigned int i = 0; i < members->count; i++) {
 455                         OSObject *obj = EXT_CAST(members->array[i].get());
 456                         OSCollection *coll = OSDynamicCast(OSCollection, obj);
 457                         if (coll) {
 458                                 OSSharedPtr<OSCollection> newColl = coll->copyCollection(cycleDict);
 459                                 if (newColl) {
 460                                         obj = newColl.get(); // Rely on cycleDict ref for a bit
 461                                 } else {
 462                                         return ret;
 463                                 }
 464                         }
 465                         newMembers->setObject(obj);
 466                 }
 467
 468                 ret = os::move(newSet);
 469         } while (false);
 470
 471         return ret;
 472 }