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     unsigned int size;
  67
  68     if (!super::init())
  69         return false;
  70
  71     if (inCapacity > (UINT_MAX / sizeof(_Element)))
  72         return false;
  73
  74     size = sizeof(_Element) * inCapacity;
  75     array = (_Element *) kalloc(size);
  76     if (!array)
  77         return false;
  78
  79     count = 0;
  80     capacity = inCapacity;
  81     capacityIncrement = (inCapacity)? inCapacity : 16;
  82     ordering = inOrdering;
  83     orderingRef = inOrderingRef;
  84
  85     bzero(array, size);
  86     ACCUMSIZE(size);
  87
  88     return this;
  89 }
  90
  91 OSOrderedSet * OSOrderedSet::
  92 withCapacity(unsigned int capacity,
  93              OSOrderFunction ordering, void * orderingRef)
  94 {
  95     OSOrderedSet *me = new OSOrderedSet;
  96
  97     if (me && !me->initWithCapacity(capacity, ordering, orderingRef)) {
  98         me->release();
  99         me = 0;
 100     }
 101
 102     return me;
 103 }
 104
 105 void OSOrderedSet::free()
 106 {
 107     (void) super::setOptions(0, kImmutable);
 108     flushCollection();
 109
 110     if (array) {
 111         kfree(array, sizeof(_Element) * capacity);
 112         ACCUMSIZE( -(sizeof(_Element) * capacity) );
 113     }
 114
 115     super::free();
 116 }
 117
 118 unsigned int OSOrderedSet::getCount() const { return count; }
 119 unsigned int OSOrderedSet::getCapacity() const { return capacity; }
 120 unsigned int OSOrderedSet::getCapacityIncrement() const
 121         { return capacityIncrement; }
 122 unsigned int OSOrderedSet::setCapacityIncrement(unsigned int increment)
 123 {
 124     capacityIncrement = (increment)? increment : 16;
 125     return capacityIncrement;
 126 }
 127
 128 unsigned int OSOrderedSet::ensureCapacity(unsigned int newCapacity)
 129 {
 130     _Element *newArray;
 131     unsigned int finalCapacity, oldSize, newSize;
 132
 133     if (newCapacity <= capacity)
 134         return capacity;
 135
 136     // round up
 137     finalCapacity = (((newCapacity - 1) / capacityIncrement) + 1)
 138                 * capacityIncrement;
 139     if ((finalCapacity < newCapacity) ||
 140         (finalCapacity > (UINT_MAX / sizeof(_Element)))) {
 141         return capacity;
 142     }
 143     newSize = sizeof(_Element) * finalCapacity;
 144
 145     newArray = (_Element *) kalloc(newSize);
 146     if (newArray) {
 147         oldSize = sizeof(_Element) * capacity;
 148
 149         ACCUMSIZE(newSize - oldSize);
 150
 151         bcopy(array, newArray, oldSize);
 152         bzero(&newArray[capacity], newSize - oldSize);
 153         kfree(array, oldSize);
 154         array = newArray;
 155         capacity = finalCapacity;
 156     }
 157
 158     return capacity;
 159 }
 160
 161 void OSOrderedSet::flushCollection()
 162 {
 163     unsigned int i;
 164
 165     haveUpdated();
 166
 167     for (i = 0; i < count; i++)
 168         array[i].obj->taggedRelease(OSTypeID(OSCollection));
 169
 170     count = 0;
 171 }
 172
 173 /* internal */
 174 bool OSOrderedSet::setObject(unsigned int index, const OSMetaClassBase *anObject)
 175 {
 176     unsigned int i;
 177     unsigned int newCount = count + 1;
 178
 179     if ((index > count) || !anObject)
 180         return false;
 181
 182     if (containsObject(anObject))
 183         return false;
 184
 185     // do we need more space?
 186     if (newCount > capacity && newCount > ensureCapacity(newCount))
 187         return false;
 188
 189     haveUpdated();
 190     if (index != count) {
 191         for (i = count; i > index; i--)
 192             array[i] = array[i-1];
 193     }
 194     array[index].obj = anObject;
 195 //    array[index].pri = pri;
 196     anObject->taggedRetain(OSTypeID(OSCollection));
 197     count++;
 198
 199     return true;
 200 }
 201
 202
 203 bool OSOrderedSet::setFirstObject(const OSMetaClassBase *anObject)
 204 {
 205     return( setObject(0, anObject));
 206 }
 207
 208 bool OSOrderedSet::setLastObject(const OSMetaClassBase *anObject)
 209 {
 210     return( setObject( count, anObject));
 211 }
 212
 213
 214 #define ORDER(obj1,obj2) \
 215     (ordering ? ((*ordering)( (const OSObject *) obj1, (const OSObject *) obj2, orderingRef)) : 0)
 216
 217 bool OSOrderedSet::setObject(const OSMetaClassBase *anObject )
 218 {
 219     unsigned int i;
 220
 221     // queue it behind those with same priority
 222     for( i = 0;
 223         (i < count) && (ORDER(array[i].obj, anObject) >= 0);
 224         i++ ) {}
 225
 226     return( setObject(i, anObject));
 227 }
 228
 229 void OSOrderedSet::removeObject(const OSMetaClassBase *anObject)
 230 {
 231     bool                deleted = false;
 232     unsigned int        i;
 233
 234     for (i = 0; i < count; i++) {
 235
 236         if (deleted)
 237             array[i-1] = array[i];
 238         else if (array[i].obj == anObject) {
 239             deleted = true;
 240             haveUpdated();      // Pity we can't flush the log
 241             array[i].obj->taggedRelease(OSTypeID(OSCollection));
 242         }
 243     }
 244
 245     if (deleted)
 246         count--;
 247 }
 248
 249 bool OSOrderedSet::containsObject(const OSMetaClassBase *anObject) const
 250 {
 251     return anObject && member(anObject);
 252 }
 253
 254 bool OSOrderedSet::member(const OSMetaClassBase *anObject) const
 255 {
 256     unsigned int i;
 257
 258     for( i = 0;
 259         (i < count) && (array[i].obj != anObject);
 260         i++ ) {}
 261
 262     return( i < count);
 263 }
 264
 265 /* internal */
 266 OSObject *OSOrderedSet::getObject( unsigned int index ) const
 267 {
 268     if (index >= count)
 269         return 0;
 270
 271 //    if( pri)
 272 //      *pri = array[index].pri;
 273
 274     return( const_cast<OSObject *>((const OSObject *) array[index].obj) );
 275 }
 276
 277 OSObject *OSOrderedSet::getFirstObject() const
 278 {
 279     if( count)
 280         return( const_cast<OSObject *>((const OSObject *) array[0].obj) );
 281     else
 282         return( 0 );
 283 }
 284
 285 OSObject *OSOrderedSet::getLastObject() const
 286 {
 287     if( count)
 288         return( const_cast<OSObject *>((const OSObject *) array[count-1].obj) );
 289     else
 290         return( 0 );
 291 }
 292
 293 SInt32 OSOrderedSet::orderObject( const OSMetaClassBase * anObject )
 294 {
 295     return( ORDER( anObject, 0 ));
 296 }
 297
 298 void *OSOrderedSet::getOrderingRef()
 299 {
 300     return orderingRef;
 301 }
 302
 303 bool OSOrderedSet::isEqualTo(const OSOrderedSet *anOrderedSet) const
 304 {
 305     unsigned int i;
 306
 307     if ( this == anOrderedSet )
 308         return true;
 309
 310     if ( count != anOrderedSet->getCount() )
 311         return false;
 312
 313     for ( i = 0; i < count; i++ ) {
 314         if ( !array[i].obj->isEqualTo(anOrderedSet->getObject(i)) )
 315             return false;
 316     }
 317
 318     return true;
 319 }
 320
 321 bool OSOrderedSet::isEqualTo(const OSMetaClassBase *anObject) const
 322 {
 323     OSOrderedSet *oSet;
 324
 325     oSet = OSDynamicCast(OSOrderedSet, anObject);
 326     if ( oSet )
 327         return isEqualTo(oSet);
 328     else
 329         return false;
 330 }
 331
 332 unsigned int OSOrderedSet::iteratorSize() const
 333 {
 334     return( sizeof(unsigned int));
 335 }
 336
 337 bool OSOrderedSet::initIterator(void *inIterator) const
 338 {
 339     unsigned int *iteratorP = (unsigned int *) inIterator;
 340
 341     *iteratorP = 0;
 342     return true;
 343 }
 344
 345 bool OSOrderedSet::
 346 getNextObjectForIterator(void *inIterator, OSObject **ret) const
 347 {
 348     unsigned int *iteratorP = (unsigned int *) inIterator;
 349     unsigned int index = (*iteratorP)++;
 350
 351     if (index < count)
 352         *ret = const_cast<OSObject *>((const OSObject *) array[index].obj);
 353     else
 354         *ret = 0;
 355
 356     return (*ret != 0);
 357 }
 358
 359
 360 unsigned OSOrderedSet::setOptions(unsigned options, unsigned mask, void *)
 361 {
 362     unsigned old = super::setOptions(options, mask);
 363     if ((old ^ options) & mask) {
 364
 365         // Value changed need to recurse over all of the child collections
 366         for ( unsigned i = 0; i < count; i++ ) {
 367             OSCollection *coll = OSDynamicCast(OSCollection, array[i].obj);
 368             if (coll)
 369                 coll->setOptions(options, mask);
 370         }
 371     }
 372
 373     return old;
 374 }
 375
 376 OSCollection * OSOrderedSet::copyCollection(OSDictionary *cycleDict)
 377 {
 378     bool allocDict = !cycleDict;
 379     OSCollection *ret = 0;
 380     OSOrderedSet *newSet = 0;
 381
 382     if (allocDict) {
 383         cycleDict = OSDictionary::withCapacity(16);
 384         if (!cycleDict)
 385             return 0;
 386     }
 387
 388     do {
 389         // Check for a cycle
 390         ret = super::copyCollection(cycleDict);
 391         if (ret)
 392             continue;
 393
 394         // Duplicate the set with no contents
 395         newSet = OSOrderedSet::withCapacity(capacity, ordering, orderingRef);
 396         if (!newSet)
 397             continue;
 398
 399         // Insert object into cycle Dictionary
 400         cycleDict->setObject((const OSSymbol *) this, newSet);
 401
 402         newSet->capacityIncrement = capacityIncrement;
 403
 404         // Now copy over the contents to the new duplicate
 405         for (unsigned int i = 0; i < count; i++) {
 406             OSObject *obj = EXT_CAST(array[i].obj);
 407             OSCollection *coll = OSDynamicCast(OSCollection, obj);
 408             if (coll) {
 409                 OSCollection *newColl = coll->copyCollection(cycleDict);
 410                 if (newColl) {
 411                     obj = newColl;      // Rely on cycleDict ref for a bit
 412                     newColl->release();
 413                 }
 414                 else
 415                     goto abortCopy;
 416             };
 417             newSet->setLastObject(obj);
 418         };
 419
 420         ret = newSet;
 421         newSet = 0;
 422
 423     } while (false);
 424
 425 abortCopy:
 426     if (newSet)
 427         newSet->release();
 428
 429     if (allocDict)
 430         cycleDict->release();
 431
 432     return ret;
 433 }