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 = kallocp_type_container(_Element, &finalCapacity, Z_WAITOK_ZERO); 177 if (newArray) { 178 OSCONTAINER_ACCUMSIZE(sizeof(_Element) * (finalCapacity - capacity)); 179 180 bcopy(array, newArray, capacity * sizeof(_Element)); 181 kfree_type(_Element, capacity, array); 182 array = newArray; 183 capacity = finalCapacity; 184 } 185 186 return capacity; 187 } 188 189 void 190 OSOrderedSet::flushCollection() 191 { 192 unsigned int i; 193 194 haveUpdated(); 195 196 for (i = 0; i < count; i++) { 197 array[i].obj.reset(); 198 } 199 200 count = 0; 201 } 202 203 /* internal */ 204 bool 205 OSOrderedSet::setObject(unsigned int index, const OSMetaClassBase *anObject) 206 { 207 unsigned int i; 208 unsigned int newCount = count + 1; 209 210 if ((index > count) || !anObject) { 211 return false; 212 } 213 214 if (containsObject(anObject)) { 215 return false; 216 } 217 218 // do we need more space? 219 if (newCount > capacity && newCount > ensureCapacity(newCount)) { 220 return false; 221 } 222 223 haveUpdated(); 224 if (index != count) { 225 for (i = count; i > index; i--) { 226 array[i] = os::move(array[i - 1]); 227 } 228 } 229 array[index].obj.reset(anObject, OSRetain); 230 count++; 231 232 return true; 233 } 234 235 bool 236 OSOrderedSet::setObject(unsigned int index, OSSharedPtr<const OSMetaClassBase> const& anObject) 237 { 238 return setObject(index, anObject.get()); 239 } 240 241 bool 242 OSOrderedSet::setFirstObject(const OSMetaClassBase *anObject) 243 { 244 return setObject(0, anObject); 245 } 246 247 bool 248 OSOrderedSet::setFirstObject(OSSharedPtr<const OSMetaClassBase> const& anObject) 249 { 250 return setFirstObject(anObject.get()); 251 } 252 253 bool 254 OSOrderedSet::setLastObject(const OSMetaClassBase *anObject) 255 { 256 return setObject( count, anObject); 257 } 258 259 bool 260 OSOrderedSet::setLastObject(OSSharedPtr<const OSMetaClassBase> const& anObject) 261 { 262 return setLastObject(anObject.get()); 263 } 264 265 266 #define ORDER(obj1, obj2) \ 267 (ordering ? ((*ordering)( (const OSObject *) obj1, (const OSObject *) obj2, orderingRef)) : 0) 268 269 bool 270 OSOrderedSet::setObject(const OSMetaClassBase *anObject ) 271 { 272 unsigned int i; 273 274 // queue it behind those with same priority 275 for (i = 0; 276 (i < count) && (ORDER(array[i].obj.get(), anObject) >= 0); 277 i++) { 278 } 279 280 return setObject(i, anObject); 281 } 282 283 bool 284 OSOrderedSet::setObject(OSSharedPtr<const OSMetaClassBase> const& anObject) 285 { 286 return setObject(anObject.get()); 287 } 288 289 void 290 OSOrderedSet::removeObject(const OSMetaClassBase *anObject) 291 { 292 bool deleted = false; 293 unsigned int i; 294 295 for (i = 0; i < count; i++) { 296 if (deleted) { 297 array[i - 1] = os::move(array[i]); 298 } else if (array[i].obj == anObject) { 299 deleted = true; 300 haveUpdated(); // Pity we can't flush the log 301 array[i].obj.reset(); 302 } 303 } 304 305 if (deleted) { 306 count--; 307 } 308 } 309 310 void 311 OSOrderedSet::removeObject(OSSharedPtr<const OSMetaClassBase> const& anObject) 312 { 313 return removeObject(anObject.get()); 314 } 315 316 bool 317 OSOrderedSet::containsObject(const OSMetaClassBase *anObject) const 318 { 319 return anObject && member(anObject); 320 } 321 322 bool 323 OSOrderedSet::member(const OSMetaClassBase *anObject) const 324 { 325 unsigned int i; 326 327 for (i = 0; 328 (i < count) && (array[i].obj != anObject); 329 i++) { 330 } 331 332 return i < count; 333 } 334 335 /* internal */ 336 OSObject * 337 OSOrderedSet::getObject( unsigned int index ) const 338 { 339 if (index >= count) { 340 return NULL; 341 } 342 343 return const_cast<OSObject *>((const OSObject *) array[index].obj.get()); 344 } 345 346 OSObject * 347 OSOrderedSet::getFirstObject() const 348 { 349 if (count) { 350 return const_cast<OSObject *>((const OSObject *) array[0].obj.get()); 351 } else { 352 return NULL; 353 } 354 } 355 356 OSObject * 357 OSOrderedSet::getLastObject() const 358 { 359 if (count) { 360 return const_cast<OSObject *>((const OSObject *) array[count - 1].obj.get()); 361 } else { 362 return NULL; 363 } 364 } 365 366 SInt32 367 OSOrderedSet::orderObject( const OSMetaClassBase * anObject ) 368 { 369 return ORDER( anObject, NULL ); 370 } 371 372 void * 373 OSOrderedSet::getOrderingRef() 374 { 375 return orderingRef; 376 } 377 378 bool 379 OSOrderedSet::isEqualTo(const OSOrderedSet *anOrderedSet) const 380 { 381 unsigned int i; 382 383 if (this == anOrderedSet) { 384 return true; 385 } 386 387 if (count != anOrderedSet->getCount()) { 388 return false; 389 } 390 391 for (i = 0; i < count; i++) { 392 if (!array[i].obj->isEqualTo(anOrderedSet->getObject(i))) { 393 return false; 394 } 395 } 396 397 return true; 398 } 399 400 bool 401 OSOrderedSet::isEqualTo(const OSMetaClassBase *anObject) const 402 { 403 OSOrderedSet *oSet; 404 405 oSet = OSDynamicCast(OSOrderedSet, anObject); 406 if (oSet) { 407 return isEqualTo(oSet); 408 } else { 409 return false; 410 } 411 } 412 413 unsigned int 414 OSOrderedSet::iteratorSize() const 415 { 416 return sizeof(unsigned int); 417 } 418 419 bool 420 OSOrderedSet::initIterator(void *inIterator) const 421 { 422 unsigned int *iteratorP = (unsigned int *) inIterator; 423 424 *iteratorP = 0; 425 return true; 426 } 427 428 bool 429 OSOrderedSet:: 430 getNextObjectForIterator(void *inIterator, OSObject **ret) const 431 { 432 unsigned int *iteratorP = (unsigned int *) inIterator; 433 unsigned int index = (*iteratorP)++; 434 435 if (index < count) { 436 *ret = const_cast<OSObject *>((const OSObject *) array[index].obj.get()); 437 } else { 438 *ret = NULL; 439 } 440 441 return *ret != NULL; 442 } 443 444 445 unsigned 446 OSOrderedSet::setOptions(unsigned options, unsigned mask, void *) 447 { 448 unsigned old = super::setOptions(options, mask); 449 if ((old ^ options) & mask) { 450 // Value changed need to recurse over all of the child collections 451 for (unsigned i = 0; i < count; i++) { 452 OSCollection *coll = OSDynamicCast(OSCollection, array[i].obj.get()); 453 if (coll) { 454 coll->setOptions(options, mask); 455 } 456 } 457 } 458 459 return old; 460 } 461 462 OSSharedPtr<OSCollection> 463 OSOrderedSet::copyCollection(OSDictionary *cycleDict) 464 { 465 OSSharedPtr<OSDictionary> ourCycleDict; 466 OSSharedPtr<OSCollection> ret; 467 OSSharedPtr<OSOrderedSet> newSet; 468 469 if (!cycleDict) { 470 ourCycleDict = OSDictionary::withCapacity(16); 471 if (!ourCycleDict) { 472 return nullptr; 473 } 474 cycleDict = ourCycleDict.get(); 475 } 476 477 do { 478 // Check for a cycle 479 ret = super::copyCollection(cycleDict); 480 if (ret) { 481 continue; 482 } 483 484 // Duplicate the set with no contents 485 newSet = OSOrderedSet::withCapacity(capacity, ordering, orderingRef); 486 if (!newSet) { 487 continue; 488 } 489 490 // Insert object into cycle Dictionary 491 cycleDict->setObject((const OSSymbol *) this, newSet.get()); 492 493 newSet->capacityIncrement = capacityIncrement; 494 495 // Now copy over the contents to the new duplicate 496 for (unsigned int i = 0; i < count; i++) { 497 OSObject *obj = EXT_CAST(array[i].obj.get()); 498 OSCollection *coll = OSDynamicCast(OSCollection, obj); 499 if (coll) { 500 OSSharedPtr<OSCollection> newColl = coll->copyCollection(cycleDict); 501 if (newColl) { 502 obj = newColl.get(); // Rely on cycleDict ref for a bit 503 } else { 504 return ret; 505 } 506 } 507 508 newSet->setLastObject(obj); 509 } 510 511 ret = os::move(newSet); 512 } while (false); 513 514 return ret; 515 } 516