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