libkern/c++/OSOrderedSet.cpp

   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((vm_offset_t)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((vm_offset_t)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 }