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