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 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 88 OSOrderedSet * OSOrderedSet:: 89 withCapacity(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 102 void 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 115 unsigned int OSOrderedSet::getCount() const { return count; } 116 unsigned int OSOrderedSet::getCapacity() const { return capacity; } 117 unsigned int OSOrderedSet::getCapacityIncrement() const 118 { return capacityIncrement; } 119 unsigned int OSOrderedSet::setCapacityIncrement(unsigned int increment) 120 { 121 capacityIncrement = (increment)? increment : 16; 122 return capacityIncrement; 123 } 124 125 unsigned 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 154 void 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 */ 167 bool 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 196 bool OSOrderedSet::setFirstObject(const OSMetaClassBase *anObject) 197 { 198 return( setObject(0, anObject)); 199 } 200 201 bool OSOrderedSet::setLastObject(const OSMetaClassBase *anObject) 202 { 203 return( setObject( count, anObject)); 204 } 205 206 207 #define ORDER(obj1,obj2) \ 208 (ordering ? ((*ordering)( (OSObject *) obj1, (OSObject *) obj2, orderingRef)) : 0) 209 210 bool 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 222 void 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 242 bool OSOrderedSet::containsObject(const OSMetaClassBase *anObject) const 243 { 244 return anObject && member(anObject); 245 } 246 247 bool 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 */ 259 OSObject *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( (OSObject *) array[index].obj ); 268 } 269 270 OSObject *OSOrderedSet::getFirstObject() const 271 { 272 if( count) 273 return( (OSObject *) array[0].obj ); 274 else 275 return( 0 ); 276 } 277 278 OSObject *OSOrderedSet::getLastObject() const 279 { 280 if( count) 281 return( (OSObject *) array[count-1].obj ); 282 else 283 return( 0 ); 284 } 285 286 SInt32 OSOrderedSet::orderObject( const OSMetaClassBase * anObject ) 287 { 288 return( ORDER( anObject, 0 )); 289 } 290 291 void *OSOrderedSet::getOrderingRef() 292 { 293 return orderingRef; 294 } 295 296 bool 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 314 bool 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 325 unsigned int OSOrderedSet::iteratorSize() const 326 { 327 return( sizeof(unsigned int)); 328 } 329 330 bool OSOrderedSet::initIterator(void *inIterator) const 331 { 332 unsigned int *iteratorP = (unsigned int *) inIterator; 333 334 *iteratorP = 0; 335 return true; 336 } 337 338 bool OSOrderedSet:: 339 getNextObjectForIterator(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 = (OSObject *) array[index].obj; 346 else 347 *ret = 0; 348 349 return (*ret != 0); 350 } 351 352 353 unsigned 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 369 OSCollection * 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 418 abortCopy: 419 if (newSet) 420 newSet->release(); 421 422 if (allocDict) 423 cycleDict->release(); 424 425 return ret; 426 } 427