libkern/c++/OSOrderedSet.cpp

   1 /*
   2  * Copyright (c) 2000 Apple Computer, Inc. All rights reserved.
   3  *
   4  * @APPLE_LICENSE_HEADER_START@
   5  *
   6  * Copyright (c) 1999-2003 Apple Computer, Inc.  All Rights Reserved.
   7  *
   8  * This file contains Original Code and/or Modifications of Original Code
   9  * as defined in and that are subject to the Apple Public Source License
  10  * Version 2.0 (the 'License'). You may not use this file except in
  11  * compliance with the License. Please obtain a copy of the License at
  12  * http://www.opensource.apple.com/apsl/ and read it before using this
  13  * file.
  14  *
  15  * The Original Code and all software distributed under the License are
  16  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  17  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  18  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  19  * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
  20  * Please see the License for the specific language governing rights and
  21  * limitations under the License.
  22  *
  23  * @APPLE_LICENSE_HEADER_END@
  24  */
  25
  26 #include <libkern/c++/OSOrderedSet.h>
  27 #include <libkern/c++/OSLib.h>
  28
  29 #define super OSCollection
  30
  31 OSDefineMetaClassAndStructors(OSOrderedSet, OSCollection)
  32 OSMetaClassDefineReservedUnused(OSOrderedSet, 0);
  33 OSMetaClassDefineReservedUnused(OSOrderedSet, 1);
  34 OSMetaClassDefineReservedUnused(OSOrderedSet, 2);
  35 OSMetaClassDefineReservedUnused(OSOrderedSet, 3);
  36 OSMetaClassDefineReservedUnused(OSOrderedSet, 4);
  37 OSMetaClassDefineReservedUnused(OSOrderedSet, 5);
  38 OSMetaClassDefineReservedUnused(OSOrderedSet, 6);
  39 OSMetaClassDefineReservedUnused(OSOrderedSet, 7);
  40
  41 #if OSALLOCDEBUG
  42 extern "C" {
  43     extern int debug_container_malloc_size;
  44 };
  45 #define ACCUMSIZE(s) do { debug_container_malloc_size += (s); } while(0)
  46 #else
  47 #define ACCUMSIZE(s)
  48 #endif
  49
  50 struct _Element {
  51     const OSMetaClassBase *             obj;
  52 //    unsigned int      pri;
  53 };
  54
  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     flushCollection();
  99
 100     if (array) {
 101         kfree((vm_offset_t)array, sizeof(_Element) * capacity);
 102         ACCUMSIZE( -(sizeof(_Element) * capacity) );
 103     }
 104
 105     super::free();
 106 }
 107
 108 unsigned int OSOrderedSet::getCount() const { return count; }
 109 unsigned int OSOrderedSet::getCapacity() const { return capacity; }
 110 unsigned int OSOrderedSet::getCapacityIncrement() const
 111         { return capacityIncrement; }
 112 unsigned int OSOrderedSet::setCapacityIncrement(unsigned int increment)
 113 {
 114     capacityIncrement = (increment)? increment : 16;
 115     return capacityIncrement;
 116 }
 117
 118 unsigned int OSOrderedSet::ensureCapacity(unsigned int newCapacity)
 119 {
 120     _Element *newArray;
 121     int oldSize, newSize;
 122
 123     if (newCapacity <= capacity)
 124         return capacity;
 125
 126     // round up
 127     newCapacity = (((newCapacity - 1) / capacityIncrement) + 1)
 128                 * capacityIncrement;
 129     newSize = sizeof(_Element) * newCapacity;
 130
 131     newArray = (_Element *) kalloc(newSize);
 132     if (newArray) {
 133         oldSize = sizeof(_Element) * capacity;
 134
 135         ACCUMSIZE(newSize - oldSize);
 136
 137         bcopy(array, newArray, oldSize);
 138         bzero(&newArray[capacity], newSize - oldSize);
 139         kfree((vm_offset_t)array, oldSize);
 140         array = newArray;
 141         capacity = newCapacity;
 142     }
 143
 144     return capacity;
 145 }
 146
 147 void OSOrderedSet::flushCollection()
 148 {
 149     unsigned int i;
 150
 151     haveUpdated();
 152
 153     for (i = 0; i < count; i++)
 154         array[i].obj->taggedRelease(OSTypeID(OSCollection));
 155
 156     count = 0;
 157 }
 158
 159 /* internal */
 160 bool OSOrderedSet::setObject(unsigned int index, const OSMetaClassBase *anObject)
 161 {
 162     unsigned int i;
 163     unsigned int newCount = count + 1;
 164
 165     if ((index > count) || !anObject)
 166         return false;
 167
 168     if (containsObject(anObject))
 169         return false;
 170
 171     // do we need more space?
 172     if (newCount > capacity && newCount > ensureCapacity(newCount))
 173         return false;
 174
 175     haveUpdated();
 176     if (index != count) {
 177         for (i = count; i > index; i--)
 178             array[i] = array[i-1];
 179     }
 180     array[index].obj = anObject;
 181 //    array[index].pri = pri;
 182     anObject->taggedRetain(OSTypeID(OSCollection));
 183     count++;
 184
 185     return true;
 186 }
 187
 188
 189 bool OSOrderedSet::setFirstObject(const OSMetaClassBase *anObject)
 190 {
 191     return( setObject(0, anObject));
 192 }
 193
 194 bool OSOrderedSet::setLastObject(const OSMetaClassBase *anObject)
 195 {
 196     return( setObject( count, anObject));
 197 }
 198
 199
 200 #define ORDER(obj1,obj2) \
 201     (ordering ? ((*ordering)( (OSObject *) obj1, (OSObject *) obj2, orderingRef)) : 0)
 202
 203 bool OSOrderedSet::setObject(const OSMetaClassBase *anObject )
 204 {
 205     unsigned int i;
 206
 207     // queue it behind those with same priority
 208     for( i = 0;
 209         (i < count) && (ORDER(array[i].obj, anObject) >= 0);
 210         i++ ) {}
 211
 212     return( setObject(i, anObject));
 213 }
 214
 215 void OSOrderedSet::removeObject(const OSMetaClassBase *anObject)
 216 {
 217     bool                deleted = false;
 218     unsigned int        i;
 219
 220     for (i = 0; i < count; i++) {
 221
 222         if( deleted)
 223             array[i-1] = array[i];
 224         else if( (array[i].obj == anObject)) {
 225             array[i].obj->taggedRelease(OSTypeID(OSCollection));
 226             deleted = true;
 227         }
 228     }
 229
 230     if( deleted) {
 231         count--;
 232         haveUpdated();
 233     }
 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