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 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() < capacity) 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 if (members) { 160 (void) members->super::setOptions(0, kImmutable); 161 members->release(); 162 } 163 164 super::free(); 165 } 166 167 unsigned int OSSet::getCount() const 168 { 169 return members->count; 170 } 171 172 unsigned int OSSet::getCapacity() const 173 { 174 return members->capacity; 175 } 176 177 unsigned int OSSet::getCapacityIncrement() const 178 { 179 return members->capacityIncrement; 180 } 181 182 unsigned int OSSet::setCapacityIncrement(unsigned int increment) 183 { 184 return members->setCapacityIncrement(increment); 185 } 186 187 unsigned int OSSet::ensureCapacity(unsigned int newCapacity) 188 { 189 return members->ensureCapacity(newCapacity); 190 } 191 192 void OSSet::flushCollection() 193 { 194 haveUpdated(); 195 members->flushCollection(); 196 } 197 198 bool OSSet::setObject(const OSMetaClassBase *anObject) 199 { 200 if (containsObject(anObject)) { 201 return false; 202 } else { 203 haveUpdated(); 204 return members->setObject(anObject); 205 } 206 } 207 208 bool OSSet::merge(const OSArray * array) 209 { 210 const OSMetaClassBase * anObject = 0; 211 bool result = true; 212 213 for (int i = 0; (anObject = array->getObject(i)); i++) { 214 215 /* setObject() returns false if the object is already in the set, 216 * so we have to check beforehand here with containsObject(). 217 */ 218 if (containsObject(anObject)) { 219 continue; 220 } 221 if (!setObject(anObject)) { 222 result = false; 223 } 224 } 225 226 return result; 227 } 228 229 bool OSSet::merge(const OSSet * set) 230 { 231 return merge(set->members); 232 } 233 234 void OSSet::removeObject(const OSMetaClassBase *anObject) 235 { 236 const OSMetaClassBase *probeObject; 237 238 for (int i = 0; (probeObject = members->getObject(i)); i++) 239 if (probeObject == anObject) { 240 haveUpdated(); 241 members->removeObject(i); 242 return; 243 } 244 } 245 246 247 bool OSSet::containsObject(const OSMetaClassBase *anObject) const 248 { 249 return anObject && member(anObject); 250 } 251 252 bool OSSet::member(const OSMetaClassBase *anObject) const 253 { 254 OSMetaClassBase *probeObject; 255 256 for (int i = 0; (probeObject = members->getObject(i)); i++) 257 if (probeObject == anObject) 258 return true; 259 260 return false; 261 } 262 263 OSObject *OSSet::getAnyObject() const 264 { 265 return members->getObject(0); 266 } 267 268 bool OSSet::isEqualTo(const OSSet *aSet) const 269 { 270 unsigned int count; 271 unsigned int i; 272 const OSMetaClassBase *obj1; 273 const OSMetaClassBase *obj2; 274 275 if ( this == aSet ) 276 return true; 277 278 count = members->count; 279 if ( count != aSet->getCount() ) 280 return false; 281 282 for ( i = 0; i < count; i++ ) { 283 obj1 = aSet->members->getObject(i); 284 if (containsObject(obj1)) 285 continue; 286 obj2 = members->getObject(i); 287 if ( !obj1 || !obj2 ) 288 return false; 289 290 if ( !obj1->isEqualTo(obj2) ) 291 return false; 292 } 293 294 return true; 295 } 296 297 bool OSSet::isEqualTo(const OSMetaClassBase *anObject) const 298 { 299 OSSet *otherSet; 300 301 otherSet = OSDynamicCast(OSSet, anObject); 302 if ( otherSet ) 303 return isEqualTo(otherSet); 304 else 305 return false; 306 } 307 308 unsigned int OSSet::iteratorSize() const 309 { 310 return sizeof(unsigned int); 311 } 312 313 bool OSSet::initIterator(void *inIterator) const 314 { 315 unsigned int *iteratorP = (unsigned int *) inIterator; 316 317 *iteratorP = 0; 318 return true; 319 } 320 321 bool OSSet::getNextObjectForIterator(void *inIterator, OSObject **ret) const 322 { 323 unsigned int *iteratorP = (unsigned int *) inIterator; 324 unsigned int index = (*iteratorP)++; 325 326 if (index < members->count) 327 *ret = members->getObject(index); 328 else 329 *ret = 0; 330 331 return (*ret != 0); 332 } 333 334 bool OSSet::serialize(OSSerialize *s) const 335 { 336 const OSMetaClassBase *o; 337 338 if (s->previouslySerialized(this)) return true; 339 340 if (!s->addXMLStartTag(this, "set")) return false; 341 342 for (int i = 0; (o = members->getObject(i)); i++) { 343 if (!o->serialize(s)) return false; 344 } 345 346 return s->addXMLEndTag("set"); 347 } 348 349 unsigned OSSet::setOptions(unsigned options, unsigned mask, void *) 350 { 351 unsigned old = super::setOptions(options, mask); 352 if ((old ^ options) & mask) 353 members->setOptions(options, mask); 354 355 return old; 356 } 357 358 OSCollection * OSSet::copyCollection(OSDictionary *cycleDict) 359 { 360 bool allocDict = !cycleDict; 361 OSCollection *ret = 0; 362 OSSet *newSet = 0; 363 364 if (allocDict) { 365 cycleDict = OSDictionary::withCapacity(16); 366 if (!cycleDict) 367 return 0; 368 } 369 370 do { 371 // Check for a cycle 372 ret = super::copyCollection(cycleDict); 373 if (ret) 374 continue; // Found it 375 376 newSet = OSSet::withCapacity(members->capacity); 377 if (!newSet) 378 continue; // Couldn't create new set abort 379 380 // Insert object into cycle Dictionary 381 cycleDict->setObject((const OSSymbol *) this, newSet); 382 383 OSArray *newMembers = newSet->members; 384 newMembers->capacityIncrement = members->capacityIncrement; 385 386 // Now copy over the contents into the new duplicate 387 for (unsigned int i = 0; i < members->count; i++) { 388 OSObject *obj = EXT_CAST(members->array[i]); 389 OSCollection *coll = OSDynamicCast(OSCollection, obj); 390 if (coll) { 391 OSCollection *newColl = coll->copyCollection(cycleDict); 392 if (newColl) { 393 obj = newColl; // Rely on cycleDict ref for a bit 394 newColl->release(); 395 } 396 else 397 goto abortCopy; 398 }; 399 newMembers->setObject(obj); 400 }; 401 402 ret = newSet; 403 newSet = 0; 404 405 } while(false); 406 407 abortCopy: 408 if (newSet) 409 newSet->release(); 410 411 if (allocDict) 412 cycleDict->release(); 413 414 return ret; 415 } 416