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         if (containsObject(obj1))
 284                 continue;
 285         obj2 = members->getObject(i);
 286         if ( !obj1 || !obj2 )
 287                 return false;
 288
 289         if ( !obj1->isEqualTo(obj2) )
 290             return false;
 291     }
 292
 293     return true;
 294 }
 295
 296 bool OSSet::isEqualTo(const OSMetaClassBase *anObject) const
 297 {
 298     OSSet *otherSet;
 299
 300     otherSet = OSDynamicCast(OSSet, anObject);
 301     if ( otherSet )
 302         return isEqualTo(otherSet);
 303     else
 304         return false;
 305 }
 306
 307 unsigned int OSSet::iteratorSize() const
 308 {
 309     return sizeof(unsigned int);
 310 }
 311
 312 bool OSSet::initIterator(void *inIterator) const
 313 {
 314     unsigned int *iteratorP = (unsigned int *) inIterator;
 315
 316     *iteratorP = 0;
 317     return true;
 318 }
 319
 320 bool OSSet::getNextObjectForIterator(void *inIterator, OSObject **ret) const
 321 {
 322     unsigned int *iteratorP = (unsigned int *) inIterator;
 323     unsigned int index = (*iteratorP)++;
 324
 325     if (index < members->count)
 326         *ret = members->getObject(index);
 327     else
 328         *ret = 0;
 329
 330     return (*ret != 0);
 331 }
 332
 333 bool OSSet::serialize(OSSerialize *s) const
 334 {
 335     const OSMetaClassBase *o;
 336
 337     if (s->previouslySerialized(this)) return true;
 338
 339     if (!s->addXMLStartTag(this, "set")) return false;
 340
 341     for (int i = 0; (o = members->getObject(i)); i++) {
 342         if (!o->serialize(s)) return false;
 343     }
 344
 345     return s->addXMLEndTag("set");
 346 }
 347
 348 unsigned OSSet::setOptions(unsigned options, unsigned mask, void *)
 349 {
 350     unsigned old = super::setOptions(options, mask);
 351     if ((old ^ options) & mask)
 352         members->setOptions(options, mask);
 353
 354     return old;
 355 }
 356
 357 OSCollection * OSSet::copyCollection(OSDictionary *cycleDict)
 358 {
 359     bool allocDict = !cycleDict;
 360     OSCollection *ret = 0;
 361     OSSet *newSet = 0;
 362
 363     if (allocDict) {
 364         cycleDict = OSDictionary::withCapacity(16);
 365         if (!cycleDict)
 366             return 0;
 367     }
 368
 369     do {
 370         // Check for a cycle
 371         ret = super::copyCollection(cycleDict);
 372         if (ret)
 373             continue;   // Found it
 374
 375         newSet = OSSet::withCapacity(members->capacity);
 376         if (!newSet)
 377             continue;   // Couldn't create new set abort
 378
 379         // Insert object into cycle Dictionary
 380         cycleDict->setObject((const OSSymbol *) this, newSet);
 381
 382         OSArray *newMembers = newSet->members;
 383         newMembers->capacityIncrement = members->capacityIncrement;
 384
 385         // Now copy over the contents into the new duplicate
 386         for (unsigned int i = 0; i < members->count; i++) {
 387             OSObject *obj = EXT_CAST(members->array[i]);
 388             OSCollection *coll = OSDynamicCast(OSCollection, obj);
 389             if (coll) {
 390                 OSCollection *newColl = coll->copyCollection(cycleDict);
 391                 if (newColl) {
 392                     obj = newColl;      // Rely on cycleDict ref for a bit
 393                     newColl->release();
 394                 }
 395                 else
 396                     goto abortCopy;
 397             };
 398             newMembers->setObject(obj);
 399         };
 400
 401         ret = newSet;
 402         newSet = 0;
 403
 404     } while(false);
 405
 406 abortCopy:
 407     if (newSet)
 408         newSet->release();
 409
 410     if (allocDict)
 411         cycleDict->release();
 412
 413     return ret;
 414 }