Return to OSOrderedSet.cpp CVS log

Up to [Apple XNU] / XNU / libkern / c++

Annotation of XNU/libkern/c++/OSOrderedSet.cpp, revision 1.1

1.1     ! root        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: 
        !            30: #ifdef DEBUG
        !            31: extern "C" {
        !            32:     extern int debug_container_malloc_size;
        !            33: };
        !            34: #define ACCUMSIZE(s) do { debug_container_malloc_size += (s); } while(0)
        !            35: #else
        !            36: #define ACCUMSIZE(s)
        !            37: #endif
        !            38: 
        !            39: struct _Element {
        !            40:     OSObject *         obj;
        !            41: //    unsigned int     pri;
        !            42: };
        !            43: 
        !            44: 
        !            45: bool OSOrderedSet::initWithCapacity(unsigned int inCapacity,
        !            46:                                 OSOrderFunction ordering, void * orderingRef)
        !            47: {
        !            48:     int size;
        !            49: 
        !            50:     if (!super::init())
        !            51:         return false;
        !            52: 
        !            53:     size = sizeof(_Element) * inCapacity;
        !            54:     array = (_Element *) kalloc(size);
        !            55:     if (!array)
        !            56:         return false;
        !            57: 
        !            58:     count = 0;
        !            59:     capacity = inCapacity;
        !            60:     capacityIncrement = capacity;
        !            61:     this->ordering = ordering;
        !            62:     this->orderingRef = orderingRef;
        !            63: 
        !            64:     bzero(array, size);
        !            65:     ACCUMSIZE(size);
        !            66: 
        !            67:     return this;       
        !            68: }
        !            69: 
        !            70: OSOrderedSet * OSOrderedSet::withCapacity(unsigned int capacity,
        !            71:                                 OSOrderFunction ordering, void * orderingRef)
        !            72: {
        !            73:     OSOrderedSet *me = new OSOrderedSet;
        !            74: 
        !            75:     if (me && !me->initWithCapacity(capacity, ordering, orderingRef)) {
        !            76:         me->free();
        !            77:        me = 0;
        !            78:     }
        !            79: 
        !            80:     return me;
        !            81: }
        !            82: 
        !            83: void OSOrderedSet::free()
        !            84: {
        !            85:     flushCollection();
        !            86: 
        !            87:     if (array) {
        !            88:         kfree((vm_offset_t)array, sizeof(_Element) * capacity);
        !            89:         ACCUMSIZE( -(sizeof(_Element) * capacity) );
        !            90:     }
        !            91: 
        !            92:     super::free();
        !            93: }
        !            94: 
        !            95: unsigned int OSOrderedSet::getCount() const { return count; }
        !            96: unsigned int OSOrderedSet::getCapacity() const { return capacity; }
        !            97: unsigned int OSOrderedSet::getCapacityIncrement() const
        !            98:        { return capacityIncrement; }
        !            99: unsigned int OSOrderedSet::setCapacityIncrement(unsigned int increment)
        !           100: {
        !           101:     return capacityIncrement = increment;
        !           102: }
        !           103: 
        !           104: unsigned int OSOrderedSet::ensureCapacity(unsigned int newCapacity)
        !           105: {
        !           106:     _Element *newArray;
        !           107:     int oldSize, newSize;
        !           108: 
        !           109:     if (!capacityIncrement || newCapacity <= capacity)
        !           110:         return capacity;
        !           111: 
        !           112:     // round up
        !           113:     newCapacity = (((newCapacity - 1) / capacityIncrement) + 1)
        !           114:                 * capacityIncrement;
        !           115:     newSize = sizeof(_Element) * newCapacity;
        !           116: 
        !           117:     newArray = (_Element *) kalloc(newSize);
        !           118:     if (newArray) {
        !           119:         oldSize = sizeof(_Element) * capacity;
        !           120: 
        !           121:         ACCUMSIZE(newSize - oldSize);
        !           122: 
        !           123:         bcopy(array, newArray, oldSize);
        !           124:         bzero(&newArray[capacity], newSize - oldSize);
        !           125:         kfree((vm_offset_t)array, oldSize);
        !           126:         array = newArray;
        !           127:         capacity = newCapacity;
        !           128:     }
        !           129: 
        !           130:     return capacity;
        !           131: }
        !           132: 
        !           133: void OSOrderedSet::flushCollection()
        !           134: {
        !           135:     unsigned int i;
        !           136: 
        !           137:     haveUpdated();
        !           138: 
        !           139:     for (i = 0; i < count; i++)
        !           140:         array[i].obj->release();
        !           141: 
        !           142:     count = 0;
        !           143: }
        !           144: 
        !           145: /* internal */
        !           146: bool OSOrderedSet::setObject(unsigned int index, OSObject *anObject)
        !           147: {
        !           148:     unsigned int i;
        !           149:     unsigned int newCount = count + 1;
        !           150: 
        !           151:     if ((index > count) || !anObject)
        !           152:         return false;
        !           153: 
        !           154:     if (containsObject(anObject))
        !           155:         return false;
        !           156: 
        !           157:     // do we need more space?
        !           158:     if (newCount > capacity && newCount > ensureCapacity(newCount))
        !           159:         return false;
        !           160: 
        !           161:     haveUpdated();
        !           162:     if (index != count) {
        !           163:         for (i = count; i > index; i--)
        !           164:             array[i] = array[i-1];
        !           165:     }
        !           166:     array[index].obj = anObject;
        !           167: //    array[index].pri = pri;
        !           168:     anObject->retain();
        !           169:     count++;
        !           170: 
        !           171:     return true;
        !           172: }
        !           173: 
        !           174: 
        !           175: bool OSOrderedSet::setFirstObject(OSObject *anObject)
        !           176: {
        !           177:     return( setObject(0, anObject));
        !           178: }
        !           179: 
        !           180: bool OSOrderedSet::setLastObject(OSObject *anObject)
        !           181: {
        !           182:     return( setObject( count, anObject));
        !           183: }
        !           184: 
        !           185: 
        !           186: #define ORDER(obj1,obj2) \
        !           187:     (ordering ? ((*ordering)( obj1, obj2, orderingRef)) : 0)
        !           188: 
        !           189: bool OSOrderedSet::setObject(OSObject *anObject )
        !           190: {
        !           191:     unsigned int i;
        !           192: 
        !           193:     // queue it behind those with same priority
        !           194:     for( i = 0;
        !           195:        (i < count) && (ORDER(array[i].obj, anObject) >= 0);
        !           196:        i++ ) {}
        !           197: 
        !           198:     return( setObject(i, anObject));
        !           199: }
        !           200: 
        !           201: void OSOrderedSet::removeObject(OSObject *anObject)
        !           202: {
        !           203:     bool               deleted = false;
        !           204:     unsigned int       i;
        !           205: 
        !           206:     for (i = 0; i < count; i++) {
        !           207: 
        !           208:         if( deleted)
        !           209:             array[i-1] = array[i];
        !           210:         else if( (array[i].obj == anObject)) {
        !           211:             array[i].obj->release();
        !           212:             deleted = true;
        !           213:         }
        !           214:     }
        !           215: 
        !           216:     if( deleted) {
        !           217:         count--;
        !           218:         haveUpdated();
        !           219:     }
        !           220: }
        !           221: 
        !           222: bool OSOrderedSet::containsObject(const OSObject *anObject) const
        !           223: {
        !           224:     return anObject && member(anObject);
        !           225: }
        !           226: 
        !           227: bool OSOrderedSet::member(const OSObject *anObject) const
        !           228: {
        !           229:     unsigned int i;
        !           230: 
        !           231:     for( i = 0;
        !           232:        (i < count) && (array[i].obj != anObject);
        !           233:        i++ ) {}
        !           234: 
        !           235:     return( i < count);
        !           236: }
        !           237: 
        !           238: /* internal */
        !           239: OSObject *OSOrderedSet::getObject( unsigned int index ) const
        !           240: {
        !           241:     if (index >= count)
        !           242:         return 0;
        !           243: 
        !           244: //    if( pri)
        !           245: //     *pri = array[index].pri;
        !           246: 
        !           247:     return( array[index].obj );
        !           248: }
        !           249: 
        !           250: OSObject *OSOrderedSet::getFirstObject() const
        !           251: {
        !           252:     if( count)
        !           253:         return( array[0].obj );
        !           254:     else
        !           255:        return( 0 );
        !           256: }
        !           257: 
        !           258: OSObject *OSOrderedSet::getLastObject() const
        !           259: {
        !           260:     if( count)
        !           261:         return( array[count-1].obj );
        !           262:     else
        !           263:        return( 0 );
        !           264: }
        !           265: 
        !           266: SInt32 OSOrderedSet::orderObject( OSObject * anObject )
        !           267: {
        !           268:     return( ORDER( anObject, 0 ));
        !           269: }
        !           270: 
        !           271: void *OSOrderedSet::getOrderingRef()
        !           272: {
        !           273:     return orderingRef;
        !           274: }
        !           275: 
        !           276: bool OSOrderedSet::isEqualTo(OSOrderedSet *anOrderedSet) const
        !           277: {
        !           278:     unsigned int i;
        !           279:     
        !           280:     if ( this == anOrderedSet )
        !           281:         return true;
        !           282: 
        !           283:     if ( count != anOrderedSet->getCount() )
        !           284:         return false;
        !           285: 
        !           286:     for ( i = 0; i < count; i++ ) {
        !           287:         if ( !array[i].obj->isEqualTo(anOrderedSet->getObject(i)) )
        !           288:             return false;
        !           289:     }
        !           290: 
        !           291:     return true;
        !           292: }
        !           293: 
        !           294: bool OSOrderedSet::isEqualTo(const OSObject *anObject) const
        !           295: {
        !           296:     OSOrderedSet *oSet;
        !           297: 
        !           298:     oSet = OSDynamicCast(OSOrderedSet, (OSObject *)anObject);
        !           299:     if ( oSet )
        !           300:         return isEqualTo(oSet);
        !           301:     else
        !           302:         return false;
        !           303: }
        !           304: 
        !           305: unsigned int OSOrderedSet::iteratorSize() const
        !           306: {
        !           307:     return( sizeof(unsigned int));
        !           308: }
        !           309: 
        !           310: bool OSOrderedSet::initIterator(void *inIterator) const
        !           311: {
        !           312:     unsigned int *iteratorP = (unsigned int *) inIterator;
        !           313: 
        !           314:     *iteratorP = 0;
        !           315:     return true;
        !           316: }
        !           317: 
        !           318: bool OSOrderedSet::getNextObjectForIterator(void *inIterator, OSObject **ret) const
        !           319: {
        !           320:     unsigned int *iteratorP = (unsigned int *) inIterator;
        !           321:     unsigned int index = (*iteratorP)++;
        !           322: 
        !           323:     if (index < count)
        !           324:         *ret = array[index].obj;
        !           325:     else
        !           326:         *ret = 0;
        !           327: 
        !           328:     return (*ret != 0);
        !           329: }
        !           330: 

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.