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