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