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