libkern/c++/OSOrderedSet.cpp

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