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