libkern/c++/OSOrderedSet.cpp

   1 /*
   2  * Copyright (c) 2000 Apple Computer, Inc. All rights reserved.
   3  *
   4  * @APPLE_LICENSE_HEADER_START@
   5  *
   6  * The contents of this file constitute Original Code as defined in and
   7  * are subject to the Apple Public Source License Version 1.1 (the
   8  * "License").  You may not use this file except in compliance with the
   9  * License.  Please obtain a copy of the License at
  10  * http://www.apple.com/publicsource and read it before using this file.
  11  *
  12  * This Original Code and all software distributed under the License are
  13  * distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  14  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  15  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  16  * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT.  Please see the
  17  * License for the specific language governing rights and limitations
  18  * under the License.
  19  *
  20  * @APPLE_LICENSE_HEADER_END@
  21  */
  22
  23 #include <libkern/c++/OSOrderedSet.h>
  24 #include <libkern/c++/OSLib.h>
  25
  26 #define super OSCollection
  27
  28 OSDefineMetaClassAndStructors(OSOrderedSet, OSCollection)
  29 OSMetaClassDefineReservedUnused(OSOrderedSet, 0);
  30 OSMetaClassDefineReservedUnused(OSOrderedSet, 1);
  31 OSMetaClassDefineReservedUnused(OSOrderedSet, 2);
  32 OSMetaClassDefineReservedUnused(OSOrderedSet, 3);
  33 OSMetaClassDefineReservedUnused(OSOrderedSet, 4);
  34 OSMetaClassDefineReservedUnused(OSOrderedSet, 5);
  35 OSMetaClassDefineReservedUnused(OSOrderedSet, 6);
  36 OSMetaClassDefineReservedUnused(OSOrderedSet, 7);
  37
  38 #if OSALLOCDEBUG
  39 extern "C" {
  40     extern int debug_container_malloc_size;
  41 };
  42 #define ACCUMSIZE(s) do { debug_container_malloc_size += (s); } while(0)
  43 #else
  44 #define ACCUMSIZE(s)
  45 #endif
  46
  47 struct _Element {
  48     const OSMetaClassBase *             obj;
  49 //    unsigned int      pri;
  50 };
  51
  52
  53 bool OSOrderedSet::
  54 initWithCapacity(unsigned int inCapacity,
  55                  OSOrderFunction inOrdering, void *inOrderingRef)
  56 {
  57     int size;
  58
  59     if (!super::init())
  60         return false;
  61
  62     size = sizeof(_Element) * inCapacity;
  63     array = (_Element *) kalloc(size);
  64     if (!array)
  65         return false;
  66
  67     count = 0;
  68     capacity = inCapacity;
  69     capacityIncrement = (inCapacity)? inCapacity : 16;
  70     ordering = inOrdering;
  71     orderingRef = inOrderingRef;
  72
  73     bzero(array, size);
  74     ACCUMSIZE(size);
  75
  76     return this;
  77 }
  78
  79 OSOrderedSet * OSOrderedSet::
  80 withCapacity(unsigned int capacity,
  81              OSOrderFunction ordering, void * orderingRef)
  82 {
  83     OSOrderedSet *me = new OSOrderedSet;
  84
  85     if (me && !me->initWithCapacity(capacity, ordering, orderingRef)) {
  86         me->free();
  87         me = 0;
  88     }
  89
  90     return me;
  91 }
  92
  93 void OSOrderedSet::free()
  94 {
  95     flushCollection();
  96
  97     if (array) {
  98         kfree((vm_offset_t)array, sizeof(_Element) * capacity);
  99         ACCUMSIZE( -(sizeof(_Element) * capacity) );
 100     }
 101
 102     super::free();
 103 }
 104
 105 unsigned int OSOrderedSet::getCount() const { return count; }
 106 unsigned int OSOrderedSet::getCapacity() const { return capacity; }
 107 unsigned int OSOrderedSet::getCapacityIncrement() const
 108         { return capacityIncrement; }
 109 unsigned int OSOrderedSet::setCapacityIncrement(unsigned int increment)
 110 {
 111     capacityIncrement = (increment)? increment : 16;
 112     return capacityIncrement;
 113 }
 114
 115 unsigned int OSOrderedSet::ensureCapacity(unsigned int newCapacity)
 116 {
 117     _Element *newArray;
 118     int oldSize, newSize;
 119
 120     if (newCapacity <= capacity)
 121         return capacity;
 122
 123     // round up
 124     newCapacity = (((newCapacity - 1) / capacityIncrement) + 1)
 125                 * capacityIncrement;
 126     newSize = sizeof(_Element) * newCapacity;
 127
 128     newArray = (_Element *) kalloc(newSize);
 129     if (newArray) {
 130         oldSize = sizeof(_Element) * capacity;
 131
 132         ACCUMSIZE(newSize - oldSize);
 133
 134         bcopy(array, newArray, oldSize);
 135         bzero(&newArray[capacity], newSize - oldSize);
 136         kfree((vm_offset_t)array, oldSize);
 137         array = newArray;
 138         capacity = newCapacity;
 139     }
 140
 141     return capacity;
 142 }
 143
 144 void OSOrderedSet::flushCollection()
 145 {
 146     unsigned int i;
 147
 148     haveUpdated();
 149
 150     for (i = 0; i < count; i++)
 151         array[i].obj->release();
 152
 153     count = 0;
 154 }
 155
 156 /* internal */
 157 bool OSOrderedSet::setObject(unsigned int index, const OSMetaClassBase *anObject)
 158 {
 159     unsigned int i;
 160     unsigned int newCount = count + 1;
 161
 162     if ((index > count) || !anObject)
 163         return false;
 164
 165     if (containsObject(anObject))
 166         return false;
 167
 168     // do we need more space?
 169     if (newCount > capacity && newCount > ensureCapacity(newCount))
 170         return false;
 171
 172     haveUpdated();
 173     if (index != count) {
 174         for (i = count; i > index; i--)
 175             array[i] = array[i-1];
 176     }
 177     array[index].obj = anObject;
 178 //    array[index].pri = pri;
 179     anObject->retain();
 180     count++;
 181
 182     return true;
 183 }
 184
 185
 186 bool OSOrderedSet::setFirstObject(const OSMetaClassBase *anObject)
 187 {
 188     return( setObject(0, anObject));
 189 }
 190
 191 bool OSOrderedSet::setLastObject(const OSMetaClassBase *anObject)
 192 {
 193     return( setObject( count, anObject));
 194 }
 195
 196
 197 #define ORDER(obj1,obj2) \
 198     (ordering ? ((*ordering)( (OSObject *) obj1, (OSObject *) obj2, orderingRef)) : 0)
 199
 200 bool OSOrderedSet::setObject(const OSMetaClassBase *anObject )
 201 {
 202     unsigned int i;
 203
 204     // queue it behind those with same priority
 205     for( i = 0;
 206         (i < count) && (ORDER(array[i].obj, anObject) >= 0);
 207         i++ ) {}
 208
 209     return( setObject(i, anObject));
 210 }
 211
 212 void OSOrderedSet::removeObject(const OSMetaClassBase *anObject)
 213 {
 214     bool                deleted = false;
 215     unsigned int        i;
 216
 217     for (i = 0; i < count; i++) {
 218
 219         if( deleted)
 220             array[i-1] = array[i];
 221         else if( (array[i].obj == anObject)) {
 222             array[i].obj->release();
 223             deleted = true;
 224         }
 225     }
 226
 227     if( deleted) {
 228         count--;
 229         haveUpdated();
 230     }
 231 }
 232
 233 bool OSOrderedSet::containsObject(const OSMetaClassBase *anObject) const
 234 {
 235     return anObject && member(anObject);
 236 }
 237
 238 bool OSOrderedSet::member(const OSMetaClassBase *anObject) const
 239 {
 240     unsigned int i;
 241
 242     for( i = 0;
 243         (i < count) && (array[i].obj != anObject);
 244         i++ ) {}
 245
 246     return( i < count);
 247 }
 248
 249 /* internal */
 250 OSObject *OSOrderedSet::getObject( unsigned int index ) const
 251 {
 252     if (index >= count)
 253         return 0;
 254
 255 //    if( pri)
 256 //      *pri = array[index].pri;
 257
 258     return( (OSObject *) array[index].obj );
 259 }
 260
 261 OSObject *OSOrderedSet::getFirstObject() const
 262 {
 263     if( count)
 264         return( (OSObject *) array[0].obj );
 265     else
 266         return( 0 );
 267 }
 268
 269 OSObject *OSOrderedSet::getLastObject() const
 270 {
 271     if( count)
 272         return( (OSObject *) array[count-1].obj );
 273     else
 274         return( 0 );
 275 }
 276
 277 SInt32 OSOrderedSet::orderObject( const OSMetaClassBase * anObject )
 278 {
 279     return( ORDER( anObject, 0 ));
 280 }
 281
 282 void *OSOrderedSet::getOrderingRef()
 283 {
 284     return orderingRef;
 285 }
 286
 287 bool OSOrderedSet::isEqualTo(const OSOrderedSet *anOrderedSet) const
 288 {
 289     unsigned int i;
 290
 291     if ( this == anOrderedSet )
 292         return true;
 293
 294     if ( count != anOrderedSet->getCount() )
 295         return false;
 296
 297     for ( i = 0; i < count; i++ ) {
 298         if ( !array[i].obj->isEqualTo(anOrderedSet->getObject(i)) )
 299             return false;
 300     }
 301
 302     return true;
 303 }
 304
 305 bool OSOrderedSet::isEqualTo(const OSMetaClassBase *anObject) const
 306 {
 307     OSOrderedSet *oSet;
 308
 309     oSet = OSDynamicCast(OSOrderedSet, anObject);
 310     if ( oSet )
 311         return isEqualTo(oSet);
 312     else
 313         return false;
 314 }
 315
 316 unsigned int OSOrderedSet::iteratorSize() const
 317 {
 318     return( sizeof(unsigned int));
 319 }
 320
 321 bool OSOrderedSet::initIterator(void *inIterator) const
 322 {
 323     unsigned int *iteratorP = (unsigned int *) inIterator;
 324
 325     *iteratorP = 0;
 326     return true;
 327 }
 328
 329 bool OSOrderedSet::
 330 getNextObjectForIterator(void *inIterator, OSObject **ret) const
 331 {
 332     unsigned int *iteratorP = (unsigned int *) inIterator;
 333     unsigned int index = (*iteratorP)++;
 334
 335     if (index < count)
 336         *ret = (OSObject *) array[index].obj;
 337     else
 338         *ret = 0;
 339
 340     return (*ret != 0);
 341 }
 342