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