libkern/c++/OSOrderedSet.cpp

   1 /*
   2  * Copyright (c) 2000 Apple Computer, Inc. All rights reserved.
   3  *
   4  * @APPLE_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. Please obtain a copy of the License at
  10  * http://www.opensource.apple.com/apsl/ and read it before using this
  11  * file.
  12  *
  13  * The Original Code and all software distributed under the License are
  14  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  15  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  16  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  17  * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
  18  * Please see the License for the specific language governing rights and
  19  * limitations under the License.
  20  *
  21  * @APPLE_LICENSE_HEADER_END@
  22  */
  23
  24 #include <libkern/c++/OSDictionary.h>
  25 #include <libkern/c++/OSOrderedSet.h>
  26 #include <libkern/c++/OSLib.h>
  27
  28 #define super OSCollection
  29
  30 OSDefineMetaClassAndStructors(OSOrderedSet, OSCollection)
  31 OSMetaClassDefineReservedUnused(OSOrderedSet, 0);
  32 OSMetaClassDefineReservedUnused(OSOrderedSet, 1);
  33 OSMetaClassDefineReservedUnused(OSOrderedSet, 2);
  34 OSMetaClassDefineReservedUnused(OSOrderedSet, 3);
  35 OSMetaClassDefineReservedUnused(OSOrderedSet, 4);
  36 OSMetaClassDefineReservedUnused(OSOrderedSet, 5);
  37 OSMetaClassDefineReservedUnused(OSOrderedSet, 6);
  38 OSMetaClassDefineReservedUnused(OSOrderedSet, 7);
  39
  40 #if OSALLOCDEBUG
  41 extern "C" {
  42     extern int debug_container_malloc_size;
  43 };
  44 #define ACCUMSIZE(s) do { debug_container_malloc_size += (s); } while(0)
  45 #else
  46 #define ACCUMSIZE(s)
  47 #endif
  48
  49 struct _Element {
  50     const OSMetaClassBase *             obj;
  51 //    unsigned int      pri;
  52 };
  53
  54 #define EXT_CAST(obj) \
  55     reinterpret_cast<OSObject *>(const_cast<OSMetaClassBase *>(obj))
  56
  57 bool OSOrderedSet::
  58 initWithCapacity(unsigned int inCapacity,
  59                  OSOrderFunction inOrdering, void *inOrderingRef)
  60 {
  61     int size;
  62
  63     if (!super::init())
  64         return false;
  65
  66     size = sizeof(_Element) * inCapacity;
  67     array = (_Element *) kalloc(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     ACCUMSIZE(size);
  79
  80     return this;
  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((vm_offset_t)array, sizeof(_Element) * capacity);
 104         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     int oldSize, newSize;
 124
 125     if (newCapacity <= capacity)
 126         return capacity;
 127
 128     // round up
 129     newCapacity = (((newCapacity - 1) / capacityIncrement) + 1)
 130                 * capacityIncrement;
 131     newSize = sizeof(_Element) * newCapacity;
 132
 133     newArray = (_Element *) kalloc(newSize);
 134     if (newArray) {
 135         oldSize = sizeof(_Element) * capacity;
 136
 137         ACCUMSIZE(newSize - oldSize);
 138
 139         bcopy(array, newArray, oldSize);
 140         bzero(&newArray[capacity], newSize - oldSize);
 141         kfree((vm_offset_t)array, oldSize);
 142         array = newArray;
 143         capacity = newCapacity;
 144     }
 145
 146     return capacity;
 147 }
 148
 149 void OSOrderedSet::flushCollection()
 150 {
 151     unsigned int i;
 152
 153     haveUpdated();
 154
 155     for (i = 0; i < count; i++)
 156         array[i].obj->taggedRelease(OSTypeID(OSCollection));
 157
 158     count = 0;
 159 }
 160
 161 /* internal */
 162 bool OSOrderedSet::setObject(unsigned int index, const OSMetaClassBase *anObject)
 163 {
 164     unsigned int i;
 165     unsigned int newCount = count + 1;
 166
 167     if ((index > count) || !anObject)
 168         return false;
 169
 170     if (containsObject(anObject))
 171         return false;
 172
 173     // do we need more space?
 174     if (newCount > capacity && newCount > ensureCapacity(newCount))
 175         return false;
 176
 177     haveUpdated();
 178     if (index != count) {
 179         for (i = count; i > index; i--)
 180             array[i] = array[i-1];
 181     }
 182     array[index].obj = anObject;
 183 //    array[index].pri = pri;
 184     anObject->taggedRetain(OSTypeID(OSCollection));
 185     count++;
 186
 187     return true;
 188 }
 189
 190
 191 bool OSOrderedSet::setFirstObject(const OSMetaClassBase *anObject)
 192 {
 193     return( setObject(0, anObject));
 194 }
 195
 196 bool OSOrderedSet::setLastObject(const OSMetaClassBase *anObject)
 197 {
 198     return( setObject( count, anObject));
 199 }
 200
 201
 202 #define ORDER(obj1,obj2) \
 203     (ordering ? ((*ordering)( (OSObject *) obj1, (OSObject *) obj2, orderingRef)) : 0)
 204
 205 bool OSOrderedSet::setObject(const OSMetaClassBase *anObject )
 206 {
 207     unsigned int i;
 208
 209     // queue it behind those with same priority
 210     for( i = 0;
 211         (i < count) && (ORDER(array[i].obj, anObject) >= 0);
 212         i++ ) {}
 213
 214     return( setObject(i, anObject));
 215 }
 216
 217 void OSOrderedSet::removeObject(const OSMetaClassBase *anObject)
 218 {
 219     bool                deleted = false;
 220     unsigned int        i;
 221
 222     for (i = 0; i < count; i++) {
 223
 224         if( deleted)
 225             array[i-1] = array[i];
 226         else if( (array[i].obj == anObject)) {
 227             deleted = true;
 228             haveUpdated();      // Pity we can't flush the log
 229             array[i].obj->taggedRelease(OSTypeID(OSCollection));
 230         }
 231     }
 232
 233     if (deleted)
 234         count--;
 235 }
 236
 237 bool OSOrderedSet::containsObject(const OSMetaClassBase *anObject) const
 238 {
 239     return anObject && member(anObject);
 240 }
 241
 242 bool OSOrderedSet::member(const OSMetaClassBase *anObject) const
 243 {
 244     unsigned int i;
 245
 246     for( i = 0;
 247         (i < count) && (array[i].obj != anObject);
 248         i++ ) {}
 249
 250     return( i < count);
 251 }
 252
 253 /* internal */
 254 OSObject *OSOrderedSet::getObject( unsigned int index ) const
 255 {
 256     if (index >= count)
 257         return 0;
 258
 259 //    if( pri)
 260 //      *pri = array[index].pri;
 261
 262     return( (OSObject *) array[index].obj );
 263 }
 264
 265 OSObject *OSOrderedSet::getFirstObject() const
 266 {
 267     if( count)
 268         return( (OSObject *) array[0].obj );
 269     else
 270         return( 0 );
 271 }
 272
 273 OSObject *OSOrderedSet::getLastObject() const
 274 {
 275     if( count)
 276         return( (OSObject *) array[count-1].obj );
 277     else
 278         return( 0 );
 279 }
 280
 281 SInt32 OSOrderedSet::orderObject( const OSMetaClassBase * anObject )
 282 {
 283     return( ORDER( anObject, 0 ));
 284 }
 285
 286 void *OSOrderedSet::getOrderingRef()
 287 {
 288     return orderingRef;
 289 }
 290
 291 bool OSOrderedSet::isEqualTo(const OSOrderedSet *anOrderedSet) const
 292 {
 293     unsigned int i;
 294
 295     if ( this == anOrderedSet )
 296         return true;
 297
 298     if ( count != anOrderedSet->getCount() )
 299         return false;
 300
 301     for ( i = 0; i < count; i++ ) {
 302         if ( !array[i].obj->isEqualTo(anOrderedSet->getObject(i)) )
 303             return false;
 304     }
 305
 306     return true;
 307 }
 308
 309 bool OSOrderedSet::isEqualTo(const OSMetaClassBase *anObject) const
 310 {
 311     OSOrderedSet *oSet;
 312
 313     oSet = OSDynamicCast(OSOrderedSet, anObject);
 314     if ( oSet )
 315         return isEqualTo(oSet);
 316     else
 317         return false;
 318 }
 319
 320 unsigned int OSOrderedSet::iteratorSize() const
 321 {
 322     return( sizeof(unsigned int));
 323 }
 324
 325 bool OSOrderedSet::initIterator(void *inIterator) const
 326 {
 327     unsigned int *iteratorP = (unsigned int *) inIterator;
 328
 329     *iteratorP = 0;
 330     return true;
 331 }
 332
 333 bool OSOrderedSet::
 334 getNextObjectForIterator(void *inIterator, OSObject **ret) const
 335 {
 336     unsigned int *iteratorP = (unsigned int *) inIterator;
 337     unsigned int index = (*iteratorP)++;
 338
 339     if (index < count)
 340         *ret = (OSObject *) array[index].obj;
 341     else
 342         *ret = 0;
 343
 344     return (*ret != 0);
 345 }
 346
 347
 348 unsigned OSOrderedSet::setOptions(unsigned options, unsigned mask, void *)
 349 {
 350     unsigned old = super::setOptions(options, mask);
 351     if ((old ^ options) & mask) {
 352
 353         // Value changed need to recurse over all of the child collections
 354         for ( unsigned i = 0; i < count; i++ ) {
 355             OSCollection *coll = OSDynamicCast(OSCollection, array[i].obj);
 356             if (coll)
 357                 coll->setOptions(options, mask);
 358         }
 359     }
 360
 361     return old;
 362 }
 363
 364 OSCollection * OSOrderedSet::copyCollection(OSDictionary *cycleDict)
 365 {
 366     bool allocDict = !cycleDict;
 367     OSCollection *ret = 0;
 368     OSOrderedSet *newSet = 0;
 369
 370     if (allocDict) {
 371         cycleDict = OSDictionary::withCapacity(16);
 372         if (!cycleDict)
 373             return 0;
 374     }
 375
 376     do {
 377         // Check for a cycle
 378         ret = super::copyCollection(cycleDict);
 379         if (ret)
 380             continue;
 381
 382         // Duplicate the set with no contents
 383         newSet = OSOrderedSet::withCapacity(capacity, ordering, orderingRef);
 384         if (!newSet)
 385             continue;
 386
 387         // Insert object into cycle Dictionary
 388         cycleDict->setObject((const OSSymbol *) this, newSet);
 389
 390         newSet->capacityIncrement = capacityIncrement;
 391
 392         // Now copy over the contents to the new duplicate
 393         for (unsigned int i = 0; i < count; i++) {
 394             OSObject *obj = EXT_CAST(array[i].obj);
 395             OSCollection *coll = OSDynamicCast(OSCollection, obj);
 396             if (coll) {
 397                 OSCollection *newColl = coll->copyCollection(cycleDict);
 398                 if (newColl) {
 399                     obj = newColl;      // Rely on cycleDict ref for a bit
 400                     newColl->release();
 401                 }
 402                 else
 403                     goto abortCopy;
 404             };
 405             newSet->setLastObject(obj);
 406         };
 407
 408         ret = newSet;
 409         newSet = 0;
 410
 411     } while (false);
 412
 413 abortCopy:
 414     if (newSet)
 415         newSet->release();
 416
 417     if (allocDict)
 418         cycleDict->release();
 419
 420     return ret;
 421 }