libkern/c++/OSArray.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 /* IOArray.m created by rsulack on Fri 12-Sep-1997 */
  26 /* IOArray.cpp converted to C++ by gvdl on Fri 1998-10-30 */
  27
  28
  29 #include <libkern/c++/OSArray.h>
  30 #include <libkern/c++/OSSerialize.h>
  31 #include <libkern/c++/OSLib.h>
  32
  33 #define super OSCollection
  34
  35 OSDefineMetaClassAndStructors(OSArray, OSCollection)
  36 OSMetaClassDefineReservedUnused(OSArray, 0);
  37 OSMetaClassDefineReservedUnused(OSArray, 1);
  38 OSMetaClassDefineReservedUnused(OSArray, 2);
  39 OSMetaClassDefineReservedUnused(OSArray, 3);
  40 OSMetaClassDefineReservedUnused(OSArray, 4);
  41 OSMetaClassDefineReservedUnused(OSArray, 5);
  42 OSMetaClassDefineReservedUnused(OSArray, 6);
  43 OSMetaClassDefineReservedUnused(OSArray, 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 bool OSArray::initWithCapacity(unsigned int inCapacity)
  55 {
  56     int size;
  57
  58     if (!super::init())
  59         return false;
  60
  61     size = sizeof(const OSMetaClassBase *) * inCapacity;
  62     array = (const OSMetaClassBase **) kalloc(size);
  63     if (!array)
  64         return false;
  65
  66     count = 0;
  67     capacity = inCapacity;
  68     capacityIncrement = (inCapacity)? inCapacity : 16;
  69
  70     bzero(array, size);
  71     ACCUMSIZE(size);
  72
  73     return this;
  74 }
  75
  76 bool OSArray::initWithObjects(const OSObject *objects[],
  77                               unsigned int theCount,
  78                               unsigned int theCapacity)
  79 {
  80     unsigned int capacity;
  81
  82     if (!theCapacity)
  83         capacity = theCount;
  84     else if (theCount > theCapacity)
  85         return false;
  86     else
  87         capacity = theCapacity;
  88
  89     if (!objects || !initWithCapacity(capacity))
  90         return false;
  91
  92     for ( unsigned int i = 0; i < theCount; i++ ) {
  93         const OSMetaClassBase *newObject = *objects++;
  94
  95         if (!newObject)
  96             return false;
  97
  98         array[count++] = newObject;
  99         newObject->taggedRetain(OSTypeID(OSCollection));
 100     }
 101
 102     return true;
 103 }
 104
 105 bool OSArray::initWithArray(const OSArray *anArray,
 106                             unsigned int theCapacity)
 107 {
 108     if ( !anArray )
 109         return false;
 110
 111     return initWithObjects((const OSObject **) anArray->array,
 112                            anArray->count, theCapacity);
 113 }
 114
 115 OSArray *OSArray::withCapacity(unsigned int capacity)
 116 {
 117     OSArray *me = new OSArray;
 118
 119     if (me && !me->initWithCapacity(capacity)) {
 120         me->release();
 121         return 0;
 122     }
 123
 124     return me;
 125 }
 126
 127 OSArray *OSArray::withObjects(const OSObject *objects[],
 128                               unsigned int count,
 129                               unsigned int capacity)
 130 {
 131     OSArray *me = new OSArray;
 132
 133     if (me && !me->initWithObjects(objects, count, capacity)) {
 134         me->release();
 135         return 0;
 136     }
 137
 138     return me;
 139 }
 140
 141 OSArray *OSArray::withArray(const OSArray *array,
 142                             unsigned int capacity)
 143 {
 144     OSArray *me = new OSArray;
 145
 146     if (me && !me->initWithArray(array, capacity)) {
 147         me->release();
 148         return 0;
 149     }
 150
 151     return me;
 152 }
 153
 154 void OSArray::free()
 155 {
 156     flushCollection();
 157
 158     if (array) {
 159         kfree((vm_offset_t)array, sizeof(const OSMetaClassBase *) * capacity);
 160         ACCUMSIZE( -(sizeof(const OSMetaClassBase *) * capacity) );
 161     }
 162
 163     super::free();
 164 }
 165
 166
 167 unsigned int OSArray::getCount() const { return count; }
 168 unsigned int OSArray::getCapacity() const { return capacity; }
 169 unsigned int OSArray::getCapacityIncrement() const { return capacityIncrement; }
 170 unsigned int OSArray::setCapacityIncrement(unsigned int increment)
 171 {
 172     capacityIncrement = (increment)? increment : 16;
 173
 174     return capacityIncrement;
 175 }
 176
 177 unsigned int OSArray::ensureCapacity(unsigned int newCapacity)
 178 {
 179     const OSMetaClassBase **newArray;
 180     int oldSize, newSize;
 181
 182     if (newCapacity <= capacity)
 183         return capacity;
 184
 185     // round up
 186     newCapacity = (((newCapacity - 1) / capacityIncrement) + 1)
 187                 * capacityIncrement;
 188     newSize = sizeof(const OSMetaClassBase *) * newCapacity;
 189
 190     newArray = (const OSMetaClassBase **) kalloc(newSize);
 191     if (newArray) {
 192         oldSize = sizeof(const OSMetaClassBase *) * capacity;
 193
 194         ACCUMSIZE(newSize - oldSize);
 195
 196         bcopy(array, newArray, oldSize);
 197         bzero(&newArray[capacity], newSize - oldSize);
 198         kfree((vm_offset_t)array, oldSize);
 199         array = newArray;
 200         capacity = newCapacity;
 201     }
 202
 203     return capacity;
 204 }
 205
 206 void OSArray::flushCollection()
 207 {
 208     unsigned int i;
 209
 210     haveUpdated();
 211     for (i = 0; i < count; i++)
 212         array[i]->taggedRelease(OSTypeID(OSCollection));
 213     count = 0;
 214 }
 215
 216 bool OSArray::setObject(const OSMetaClassBase *anObject)
 217 {
 218     return setObject(count, anObject);
 219 }
 220
 221 bool OSArray::setObject(unsigned int index, const OSMetaClassBase *anObject)
 222 {
 223     unsigned int i;
 224     unsigned int newCount = count + 1;
 225
 226     if ((index > count) || !anObject)
 227         return false;
 228
 229     // do we need more space?
 230     if (newCount > capacity && newCount > ensureCapacity(newCount))
 231         return false;
 232
 233     haveUpdated();
 234     if (index != count) {
 235         for (i = count; i > index; i--)
 236             array[i] = array[i-1];
 237     }
 238     array[index] = anObject;
 239     anObject->taggedRetain(OSTypeID(OSCollection));
 240     count++;
 241
 242     return true;
 243 }
 244
 245 bool OSArray::merge(const OSArray * otherArray)
 246 {
 247     unsigned int otherCount = otherArray->getCount();
 248     unsigned int newCount = count + otherCount;
 249
 250     if (!otherCount)
 251         return true;
 252
 253     // do we need more space?
 254     if (newCount > capacity && newCount > ensureCapacity(newCount))
 255         return false;
 256
 257     haveUpdated();
 258     for (unsigned int i = 0; i < otherCount; i++) {
 259         const OSMetaClassBase *newObject = otherArray->getObject(i);
 260
 261         array[count++] = newObject;
 262         newObject->taggedRetain(OSTypeID(OSCollection));
 263     }
 264
 265     return true;
 266 }
 267
 268 void OSArray::
 269 replaceObject(unsigned int index, const OSMetaClassBase *anObject)
 270 {
 271     const OSMetaClassBase *oldObject;
 272
 273     if ((index >= count) || !anObject)
 274         return;
 275
 276     haveUpdated();
 277     oldObject = array[index];
 278     array[index] = anObject;
 279     anObject->taggedRetain(OSTypeID(OSCollection));
 280
 281     oldObject->taggedRelease(OSTypeID(OSCollection));
 282 }
 283
 284 void OSArray::removeObject(unsigned int index)
 285 {
 286     unsigned int i;
 287     const OSMetaClassBase *oldObject;
 288
 289     if (index >= count)
 290         return;
 291
 292     haveUpdated();
 293     oldObject = array[index];
 294
 295     count--;
 296     for (i = index; i < count; i++)
 297         array[i] = array[i+1];
 298
 299     oldObject->taggedRelease(OSTypeID(OSCollection));
 300 }
 301
 302 bool OSArray::isEqualTo(const OSArray *anArray) const
 303 {
 304     unsigned int i;
 305
 306     if ( this == anArray )
 307         return true;
 308
 309     if ( count != anArray->getCount() )
 310         return false;
 311
 312     for ( i = 0; i < count; i++ ) {
 313         if ( !array[i]->isEqualTo(anArray->getObject(i)) )
 314             return false;
 315     }
 316
 317     return true;
 318 }
 319
 320 bool OSArray::isEqualTo(const OSMetaClassBase *anObject) const
 321 {
 322     OSArray *otherArray;
 323
 324     otherArray = OSDynamicCast(OSArray, anObject);
 325     if ( otherArray )
 326         return isEqualTo(otherArray);
 327     else
 328         return false;
 329 }
 330
 331 OSObject *OSArray::getObject(unsigned int index) const
 332 {
 333     if (index >= count)
 334         return 0;
 335     else
 336         return (OSObject *) array[index];
 337 }
 338
 339 OSObject *OSArray::getLastObject() const
 340 {
 341     if (count == 0)
 342         return 0;
 343     else
 344         return (OSObject *) array[count - 1];
 345 }
 346
 347 unsigned int OSArray::getNextIndexOfObject(const OSMetaClassBase * anObject,
 348                                             unsigned int index) const
 349 {
 350     while ((index < count) && (array[index] != anObject))
 351         index++;
 352     if (index >= count)
 353         index = (unsigned int)-1;
 354     return index;
 355 }
 356
 357 unsigned int OSArray::iteratorSize() const
 358 {
 359     return sizeof(unsigned int);
 360 }
 361
 362 bool OSArray::initIterator(void *inIterator) const
 363 {
 364     unsigned int *iteratorP = (unsigned int *) inIterator;
 365
 366     *iteratorP = 0;
 367     return true;
 368 }
 369
 370 bool OSArray::getNextObjectForIterator(void *inIterator, OSObject **ret) const
 371 {
 372     unsigned int *iteratorP = (unsigned int *) inIterator;
 373     unsigned int index = (*iteratorP)++;
 374
 375     if (index < count) {
 376         *ret = (OSObject *) array[index];
 377         return true;
 378     }
 379     else {
 380         *ret = 0;
 381         return false;
 382     }
 383 }
 384
 385 bool OSArray::serialize(OSSerialize *s) const
 386 {
 387     if (s->previouslySerialized(this)) return true;
 388
 389     if (!s->addXMLStartTag(this, "array")) return false;
 390
 391     for (unsigned i = 0; i < count; i++) {
 392         if (!array[i]->serialize(s)) return false;
 393     }
 394
 395     return s->addXMLEndTag("array");
 396 }