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