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