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