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 29 #define IOKIT_ENABLE_SHARED_PTR 30 31 #include <libkern/c++/OSDictionary.h> 32 #include <libkern/c++/OSLib.h> 33 #include <libkern/c++/OSOrderedSet.h> 34 #include <libkern/c++/OSSharedPtr.h> 35 #include <os/cpp_util.h> 36 37 #define super OSCollection 38 39 OSDefineMetaClassAndStructors(OSOrderedSet, OSCollection) 40 OSMetaClassDefineReservedUnused(OSOrderedSet, 0); 41 OSMetaClassDefineReservedUnused(OSOrderedSet, 1); 42 OSMetaClassDefineReservedUnused(OSOrderedSet, 2); 43 OSMetaClassDefineReservedUnused(OSOrderedSet, 3); 44 OSMetaClassDefineReservedUnused(OSOrderedSet, 4); 45 OSMetaClassDefineReservedUnused(OSOrderedSet, 5); 46 OSMetaClassDefineReservedUnused(OSOrderedSet, 6); 47 OSMetaClassDefineReservedUnused(OSOrderedSet, 7); 48 49 50 struct _Element { 51 OSTaggedPtr<const OSMetaClassBase> obj; 52 }; 53 54 #define EXT_CAST(obj) \ 55 reinterpret_cast<OSObject *>(const_cast<OSMetaClassBase *>(obj)) 56 57 bool 58 OSOrderedSet:: 59 initWithCapacity(unsigned int inCapacity, 60 OSOrderFunction inOrdering, void *inOrderingRef) 61 { 62 if (!super::init()) { 63 return false; 64 } 65 66 if (inCapacity > (UINT_MAX / sizeof(_Element))) { 67 return false; 68 } 69 70 array = kallocp_type_container(_Element, &inCapacity, Z_WAITOK_ZERO); 71 if (!array) { 72 return false; 73 } 74 75 count = 0; 76 capacity = inCapacity; 77 capacityIncrement = (inCapacity)? inCapacity : 16; 78 ordering = inOrdering; 79 orderingRef = inOrderingRef; 80 81 OSCONTAINER_ACCUMSIZE(sizeof(_Element) * inCapacity); 82 83 return true; 84 } 85 86 OSSharedPtr<OSOrderedSet> 87 OSOrderedSet:: 88 withCapacity(unsigned int capacity, 89 OSOrderFunction ordering, void * orderingRef) 90 { 91 auto me = OSMakeShared<OSOrderedSet>(); 92 93 if (me && !me->initWithCapacity(capacity, ordering, orderingRef)) { 94 return nullptr; 95 } 96 97 return me; 98 } 99 100 static SInt32 101 OSOrderedSetBlockToFunc(const OSMetaClassBase * obj1, 102 const OSMetaClassBase * obj2, 103 void * context) 104 { 105 OSOrderedSet::OSOrderBlock ordering = (typeof(ordering))context; 106 107 return ordering(obj1, obj2); 108 } 109 110 111 OSSharedPtr<OSOrderedSet> 112 OSOrderedSet::withCapacity(unsigned int capacity, OSOrderBlock ordering) 113 { 114 auto me = OSMakeShared<OSOrderedSet>(); 115 116 if (me && !me->initWithCapacity(capacity, &OSOrderedSetBlockToFunc, ordering)) { 117 return nullptr; 118 } 119 120 return me; 121 } 122 123 void 124 OSOrderedSet::free() 125 { 126 (void) super::setOptions(0, kImmutable); 127 flushCollection(); 128 129 if (array) { 130 kfree_type(_Element, capacity, array); 131 OSCONTAINER_ACCUMSIZE( -(sizeof(_Element) * capacity)); 132 } 133 134 super::free(); 135 } 136 137 unsigned int 138 OSOrderedSet::getCount() const 139 { 140 return count; 141 } 142 unsigned int 143 OSOrderedSet::getCapacity() const 144 { 145 return capacity; 146 } 147 unsigned int 148 OSOrderedSet::getCapacityIncrement() const 149 { 150 return capacityIncrement; 151 } 152 unsigned int 153 OSOrderedSet::setCapacityIncrement(unsigned int increment) 154 { 155 capacityIncrement = (increment)? increment : 16; 156 return capacityIncrement; 157 } 158 159 unsigned int 160 OSOrderedSet::ensureCapacity(unsigned int newCapacity) 161 { 162 _Element *newArray; 163 unsigned int finalCapacity; 164 165 if (newCapacity <= capacity) { 166 return capacity; 167 } 168 169 // round up 170 finalCapacity = (((newCapacity - 1) / capacityIncrement) + 1) 171 * capacityIncrement; 172 if (finalCapacity < newCapacity) { 173 return capacity; 174 } 175 176 newArray = kreallocp_type_container(_Element, array, 177 capacity, &finalCapacity, Z_WAITOK_ZERO); 178 if (newArray) { 179 OSCONTAINER_ACCUMSIZE(sizeof(_Element) * (finalCapacity - capacity)); 180 array = newArray; 181 capacity = finalCapacity; 182 } 183 184 return capacity; 185 } 186 187 void 188 OSOrderedSet::flushCollection() 189 { 190 unsigned int i; 191 192 haveUpdated(); 193 194 for (i = 0; i < count; i++) { 195 array[i].obj.reset(); 196 } 197 198 count = 0; 199 } 200 201 /* internal */ 202 bool 203 OSOrderedSet::setObject(unsigned int index, const OSMetaClassBase *anObject) 204 { 205 unsigned int i; 206 unsigned int newCount = count + 1; 207 208 if ((index > count) || !anObject) { 209 return false; 210 } 211 212 if (containsObject(anObject)) { 213 return false; 214 } 215 216 // do we need more space? 217 if (newCount > capacity && newCount > ensureCapacity(newCount)) { 218 return false; 219 } 220 221 haveUpdated(); 222 if (index != count) { 223 for (i = count; i > index; i--) { 224 array[i] = os::move(array[i - 1]); 225 } 226 } 227 array[index].obj.reset(anObject, OSRetain); 228 count++; 229 230 return true; 231 } 232 233 bool 234 OSOrderedSet::setObject(unsigned int index, OSSharedPtr<const OSMetaClassBase> const& anObject) 235 { 236 return setObject(index, anObject.get()); 237 } 238 239 bool 240 OSOrderedSet::setFirstObject(const OSMetaClassBase *anObject) 241 { 242 return setObject(0, anObject); 243 } 244 245 bool 246 OSOrderedSet::setFirstObject(OSSharedPtr<const OSMetaClassBase> const& anObject) 247 { 248 return setFirstObject(anObject.get()); 249 } 250 251 bool 252 OSOrderedSet::setLastObject(const OSMetaClassBase *anObject) 253 { 254 return setObject( count, anObject); 255 } 256 257 bool 258 OSOrderedSet::setLastObject(OSSharedPtr<const OSMetaClassBase> const& anObject) 259 { 260 return setLastObject(anObject.get()); 261 } 262 263 264 #define ORDER(obj1, obj2) \ 265 (ordering ? ((*ordering)( (const OSObject *) obj1, (const OSObject *) obj2, orderingRef)) : 0) 266 267 bool 268 OSOrderedSet::setObject(const OSMetaClassBase *anObject ) 269 { 270 unsigned int i; 271 272 // queue it behind those with same priority 273 for (i = 0; 274 (i < count) && (ORDER(array[i].obj.get(), anObject) >= 0); 275 i++) { 276 } 277 278 return setObject(i, anObject); 279 } 280 281 bool 282 OSOrderedSet::setObject(OSSharedPtr<const OSMetaClassBase> const& anObject) 283 { 284 return setObject(anObject.get()); 285 } 286 287 void 288 OSOrderedSet::removeObject(const OSMetaClassBase *anObject) 289 { 290 bool deleted = false; 291 unsigned int i; 292 293 for (i = 0; i < count; i++) { 294 if (deleted) { 295 array[i - 1] = os::move(array[i]); 296 } else if (array[i].obj == anObject) { 297 deleted = true; 298 haveUpdated(); // Pity we can't flush the log 299 array[i].obj.reset(); 300 } 301 } 302 303 if (deleted) { 304 count--; 305 } 306 } 307 308 void 309 OSOrderedSet::removeObject(OSSharedPtr<const OSMetaClassBase> const& anObject) 310 { 311 return removeObject(anObject.get()); 312 } 313 314 bool 315 OSOrderedSet::containsObject(const OSMetaClassBase *anObject) const 316 { 317 return anObject && member(anObject); 318 } 319 320 bool 321 OSOrderedSet::member(const OSMetaClassBase *anObject) const 322 { 323 unsigned int i; 324 325 for (i = 0; 326 (i < count) && (array[i].obj != anObject); 327 i++) { 328 } 329 330 return i < count; 331 } 332 333 /* internal */ 334 OSObject * 335 OSOrderedSet::getObject( unsigned int index ) const 336 { 337 if (index >= count) { 338 return NULL; 339 } 340 341 return const_cast<OSObject *>((const OSObject *) array[index].obj.get()); 342 } 343 344 OSObject * 345 OSOrderedSet::getFirstObject() const 346 { 347 if (count) { 348 return const_cast<OSObject *>((const OSObject *) array[0].obj.get()); 349 } else { 350 return NULL; 351 } 352 } 353 354 OSObject * 355 OSOrderedSet::getLastObject() const 356 { 357 if (count) { 358 return const_cast<OSObject *>((const OSObject *) array[count - 1].obj.get()); 359 } else { 360 return NULL; 361 } 362 } 363 364 SInt32 365 OSOrderedSet::orderObject( const OSMetaClassBase * anObject ) 366 { 367 return ORDER( anObject, NULL ); 368 } 369 370 void * 371 OSOrderedSet::getOrderingRef() 372 { 373 return orderingRef; 374 } 375 376 bool 377 OSOrderedSet::isEqualTo(const OSOrderedSet *anOrderedSet) const 378 { 379 unsigned int i; 380 381 if (this == anOrderedSet) { 382 return true; 383 } 384 385 if (count != anOrderedSet->getCount()) { 386 return false; 387 } 388 389 for (i = 0; i < count; i++) { 390 if (!array[i].obj->isEqualTo(anOrderedSet->getObject(i))) { 391 return false; 392 } 393 } 394 395 return true; 396 } 397 398 bool 399 OSOrderedSet::isEqualTo(const OSMetaClassBase *anObject) const 400 { 401 OSOrderedSet *oSet; 402 403 oSet = OSDynamicCast(OSOrderedSet, anObject); 404 if (oSet) { 405 return isEqualTo(oSet); 406 } else { 407 return false; 408 } 409 } 410 411 unsigned int 412 OSOrderedSet::iteratorSize() const 413 { 414 return sizeof(unsigned int); 415 } 416 417 bool 418 OSOrderedSet::initIterator(void *inIterator) const 419 { 420 unsigned int *iteratorP = (unsigned int *) inIterator; 421 422 *iteratorP = 0; 423 return true; 424 } 425 426 bool 427 OSOrderedSet:: 428 getNextObjectForIterator(void *inIterator, OSObject **ret) const 429 { 430 unsigned int *iteratorP = (unsigned int *) inIterator; 431 unsigned int index = (*iteratorP)++; 432 433 if (index < count) { 434 *ret = const_cast<OSObject *>((const OSObject *) array[index].obj.get()); 435 } else { 436 *ret = NULL; 437 } 438 439 return *ret != NULL; 440 } 441 442 443 unsigned 444 OSOrderedSet::setOptions(unsigned options, unsigned mask, void *) 445 { 446 unsigned old = super::setOptions(options, mask); 447 if ((old ^ options) & mask) { 448 // Value changed need to recurse over all of the child collections 449 for (unsigned i = 0; i < count; i++) { 450 OSCollection *coll = OSDynamicCast(OSCollection, array[i].obj.get()); 451 if (coll) { 452 coll->setOptions(options, mask); 453 } 454 } 455 } 456 457 return old; 458 } 459 460 OSSharedPtr<OSCollection> 461 OSOrderedSet::copyCollection(OSDictionary *cycleDict) 462 { 463 OSSharedPtr<OSDictionary> ourCycleDict; 464 OSSharedPtr<OSCollection> ret; 465 OSSharedPtr<OSOrderedSet> newSet; 466 467 if (!cycleDict) { 468 ourCycleDict = OSDictionary::withCapacity(16); 469 if (!ourCycleDict) { 470 return nullptr; 471 } 472 cycleDict = ourCycleDict.get(); 473 } 474 475 do { 476 // Check for a cycle 477 ret = super::copyCollection(cycleDict); 478 if (ret) { 479 continue; 480 } 481 482 // Duplicate the set with no contents 483 newSet = OSOrderedSet::withCapacity(capacity, ordering, orderingRef); 484 if (!newSet) { 485 continue; 486 } 487 488 // Insert object into cycle Dictionary 489 cycleDict->setObject((const OSSymbol *) this, newSet.get()); 490 491 newSet->capacityIncrement = capacityIncrement; 492 493 // Now copy over the contents to the new duplicate 494 for (unsigned int i = 0; i < count; i++) { 495 OSObject *obj = EXT_CAST(array[i].obj.get()); 496 OSCollection *coll = OSDynamicCast(OSCollection, obj); 497 if (coll) { 498 OSSharedPtr<OSCollection> newColl = coll->copyCollection(cycleDict); 499 if (newColl) { 500 obj = newColl.get(); // Rely on cycleDict ref for a bit 501 } else { 502 return ret; 503 } 504 } 505 506 newSet->setLastObject(obj); 507 } 508 509 ret = os::move(newSet); 510 } while (false); 511 512 return ret; 513 } 514