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 #if OSALLOCDEBUG 46 extern "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 54 struct _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 62 bool OSOrderedSet:: 63 initWithCapacity(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 91 OSOrderedSet * OSOrderedSet:: 92 withCapacity(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 105 void 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 118 unsigned int OSOrderedSet::getCount() const { return count; } 119 unsigned int OSOrderedSet::getCapacity() const { return capacity; } 120 unsigned int OSOrderedSet::getCapacityIncrement() const 121 { return capacityIncrement; } 122 unsigned int OSOrderedSet::setCapacityIncrement(unsigned int increment) 123 { 124 capacityIncrement = (increment)? increment : 16; 125 return capacityIncrement; 126 } 127 128 unsigned 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 161 void 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 */ 174 bool 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 203 bool OSOrderedSet::setFirstObject(const OSMetaClassBase *anObject) 204 { 205 return( setObject(0, anObject)); 206 } 207 208 bool 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 217 bool 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 229 void 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 249 bool OSOrderedSet::containsObject(const OSMetaClassBase *anObject) const 250 { 251 return anObject && member(anObject); 252 } 253 254 bool 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 */ 266 OSObject *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 277 OSObject *OSOrderedSet::getFirstObject() const 278 { 279 if( count) 280 return( const_cast<OSObject *>((const OSObject *) array[0].obj) ); 281 else 282 return( 0 ); 283 } 284 285 OSObject *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 293 SInt32 OSOrderedSet::orderObject( const OSMetaClassBase * anObject ) 294 { 295 return( ORDER( anObject, 0 )); 296 } 297 298 void *OSOrderedSet::getOrderingRef() 299 { 300 return orderingRef; 301 } 302 303 bool 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 321 bool 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 332 unsigned int OSOrderedSet::iteratorSize() const 333 { 334 return( sizeof(unsigned int)); 335 } 336 337 bool OSOrderedSet::initIterator(void *inIterator) const 338 { 339 unsigned int *iteratorP = (unsigned int *) inIterator; 340 341 *iteratorP = 0; 342 return true; 343 } 344 345 bool OSOrderedSet:: 346 getNextObjectForIterator(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 360 unsigned 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 376 OSCollection * 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 425 abortCopy: 426 if (newSet) 427 newSet->release(); 428 429 if (allocDict) 430 cycleDict->release(); 431 432 return ret; 433 } 434