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