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