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