libkern/c++/OSOrderedSet.cpp

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