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 NULL; 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 NULL; 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 NULL; 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 NULL; 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 = NULL; 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 = NULL; 371 } 372 373 return *ret != NULL; 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 = NULL; 414 OSSet *newSet = NULL; 415 416 if (allocDict) { 417 cycleDict = OSDictionary::withCapacity(16); 418 if (!cycleDict) { 419 return NULL; 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 = NULL; 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 } 472