[apple/xnu.git] / libkern / c++ / OSOrderedSet.cpp

/*
 * Copyright (c) 2000 Apple Computer, Inc. All rights reserved.
 *
 * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
 * 
 * This file contains Original Code and/or Modifications of Original Code
 * as defined in and that are subject to the Apple Public Source License
 * Version 2.0 (the 'License'). You may not use this file except in
 * compliance with the License. The rights granted to you under the License
 * may not be used to create, or enable the creation or redistribution of,
 * unlawful or unlicensed copies of an Apple operating system, or to
 * circumvent, violate, or enable the circumvention or violation of, any
 * terms of an Apple operating system software license agreement.
 * 
 * Please obtain a copy of the License at
 * http://www.opensource.apple.com/apsl/ and read it before using this file.
 * 
 * The Original Code and all software distributed under the License are
 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
 * Please see the License for the specific language governing rights and
 * limitations under the License.
 * 
 * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
 */

#include <libkern/c++/OSDictionary.h>
#include <libkern/c++/OSOrderedSet.h>
#include <libkern/c++/OSLib.h>

#define super OSCollection

OSDefineMetaClassAndStructors(OSOrderedSet, OSCollection)
OSMetaClassDefineReservedUnused(OSOrderedSet, 0);
OSMetaClassDefineReservedUnused(OSOrderedSet, 1);
OSMetaClassDefineReservedUnused(OSOrderedSet, 2);
OSMetaClassDefineReservedUnused(OSOrderedSet, 3);
OSMetaClassDefineReservedUnused(OSOrderedSet, 4);
OSMetaClassDefineReservedUnused(OSOrderedSet, 5);
OSMetaClassDefineReservedUnused(OSOrderedSet, 6);
OSMetaClassDefineReservedUnused(OSOrderedSet, 7);


struct _Element {
    const OSMetaClassBase *		obj;
//    unsigned int	pri;
};

#define EXT_CAST(obj) \
    reinterpret_cast<OSObject *>(const_cast<OSMetaClassBase *>(obj))

bool OSOrderedSet::
initWithCapacity(unsigned int inCapacity,
                 OSOrderFunction inOrdering, void *inOrderingRef)
{
    unsigned int size;

    if (!super::init())
        return false;

    if (inCapacity > (UINT_MAX / sizeof(_Element)))
        return false;

    size = sizeof(_Element) * inCapacity;
    array = (_Element *) kalloc_container(size);
    if (!array)
        return false;

    count = 0;
    capacity = inCapacity;
    capacityIncrement = (inCapacity)? inCapacity : 16;
    ordering = inOrdering;
    orderingRef = inOrderingRef;

    bzero(array, size);
    OSCONTAINER_ACCUMSIZE(size);

    return true;	
}

OSOrderedSet * OSOrderedSet::
withCapacity(unsigned int capacity,
             OSOrderFunction ordering, void * orderingRef)
{
    OSOrderedSet *me = new OSOrderedSet;

    if (me && !me->initWithCapacity(capacity, ordering, orderingRef)) {
        me->release();
	me = 0;
    }

    return me;
}

void OSOrderedSet::free()
{
    (void) super::setOptions(0, kImmutable);
    flushCollection();

    if (array) {
        kfree(array, sizeof(_Element) * capacity);
        OSCONTAINER_ACCUMSIZE( -(sizeof(_Element) * capacity) );
    }

    super::free();
}

unsigned int OSOrderedSet::getCount() const { return count; }
unsigned int OSOrderedSet::getCapacity() const { return capacity; }
unsigned int OSOrderedSet::getCapacityIncrement() const
	{ return capacityIncrement; }
unsigned int OSOrderedSet::setCapacityIncrement(unsigned int increment)
{
    capacityIncrement = (increment)? increment : 16;
    return capacityIncrement;
}

unsigned int OSOrderedSet::ensureCapacity(unsigned int newCapacity)
{
    _Element *newArray;
    unsigned int finalCapacity, oldSize, newSize;

    if (newCapacity <= capacity)
        return capacity;

    // round up
    finalCapacity = (((newCapacity - 1) / capacityIncrement) + 1)
                * capacityIncrement;
    if ((finalCapacity < newCapacity) ||
        (finalCapacity > (UINT_MAX / sizeof(_Element)))) {
        return capacity;
    }
    newSize = sizeof(_Element) * finalCapacity;

    newArray = (_Element *) kalloc_container(newSize);
    if (newArray) {
        oldSize = sizeof(_Element) * capacity;

        OSCONTAINER_ACCUMSIZE(((size_t)newSize) - ((size_t)oldSize));

        bcopy(array, newArray, oldSize);
        bzero(&newArray[capacity], newSize - oldSize);
        kfree(array, oldSize);
        array = newArray;
        capacity = finalCapacity;
    }

    return capacity;
}

void OSOrderedSet::flushCollection()
{
    unsigned int i;

    haveUpdated();

    for (i = 0; i < count; i++)
        array[i].obj->taggedRelease(OSTypeID(OSCollection));

    count = 0;
}

/* internal */
bool OSOrderedSet::setObject(unsigned int index, const OSMetaClassBase *anObject)
{
    unsigned int i;
    unsigned int newCount = count + 1;

    if ((index > count) || !anObject)
        return false;

    if (containsObject(anObject))
        return false;

    // do we need more space?
    if (newCount > capacity && newCount > ensureCapacity(newCount))
        return false;

    haveUpdated();
    if (index != count) {
        for (i = count; i > index; i--)
            array[i] = array[i-1];
    }
    array[index].obj = anObject;
//    array[index].pri = pri;
    anObject->taggedRetain(OSTypeID(OSCollection));
    count++;

    return true;
}


bool OSOrderedSet::setFirstObject(const OSMetaClassBase *anObject)
{
    return( setObject(0, anObject));
}

bool OSOrderedSet::setLastObject(const OSMetaClassBase *anObject)
{
    return( setObject( count, anObject));
}


#define ORDER(obj1,obj2) \
    (ordering ? ((*ordering)( (const OSObject *) obj1, (const OSObject *) obj2, orderingRef)) : 0)

bool OSOrderedSet::setObject(const OSMetaClassBase *anObject )
{
    unsigned int i;

    // queue it behind those with same priority
    for( i = 0;
	(i < count) && (ORDER(array[i].obj, anObject) >= 0);
	i++ ) {}

    return( setObject(i, anObject));
}

void OSOrderedSet::removeObject(const OSMetaClassBase *anObject)
{
    bool		deleted = false;
    unsigned int 	i;

    for (i = 0; i < count; i++) {

        if (deleted)
            array[i-1] = array[i];
        else if (array[i].obj == anObject) {
            deleted = true;
	    haveUpdated();	// Pity we can't flush the log
            array[i].obj->taggedRelease(OSTypeID(OSCollection));
        }
    }

    if (deleted)
	count--;
}

bool OSOrderedSet::containsObject(const OSMetaClassBase *anObject) const
{
    return anObject && member(anObject);
}

bool OSOrderedSet::member(const OSMetaClassBase *anObject) const
{
    unsigned int i;

    for( i = 0;
	(i < count) && (array[i].obj != anObject);
	i++ ) {}

    return( i < count);
}

/* internal */
OSObject *OSOrderedSet::getObject( unsigned int index ) const
{
    if (index >= count)
        return 0;

//    if( pri)
//	*pri = array[index].pri;

    return( const_cast<OSObject *>((const OSObject *) array[index].obj) );
}

OSObject *OSOrderedSet::getFirstObject() const
{
    if( count)
        return( const_cast<OSObject *>((const OSObject *) array[0].obj) );
    else
	return( 0 );
}

OSObject *OSOrderedSet::getLastObject() const
{
    if( count)
        return( const_cast<OSObject *>((const OSObject *) array[count-1].obj) );
    else
	return( 0 );
}

SInt32 OSOrderedSet::orderObject( const OSMetaClassBase * anObject )
{
    return( ORDER( anObject, 0 ));
}

void *OSOrderedSet::getOrderingRef()
{
    return orderingRef;
}

bool OSOrderedSet::isEqualTo(const OSOrderedSet *anOrderedSet) const
{
    unsigned int i;
    
    if ( this == anOrderedSet )
        return true;

    if ( count != anOrderedSet->getCount() )
        return false;

    for ( i = 0; i < count; i++ ) {
        if ( !array[i].obj->isEqualTo(anOrderedSet->getObject(i)) )
            return false;
    }

    return true;
}

bool OSOrderedSet::isEqualTo(const OSMetaClassBase *anObject) const
{
    OSOrderedSet *oSet;

    oSet = OSDynamicCast(OSOrderedSet, anObject);
    if ( oSet )
        return isEqualTo(oSet);
    else
        return false;
}

unsigned int OSOrderedSet::iteratorSize() const
{
    return( sizeof(unsigned int));
}

bool OSOrderedSet::initIterator(void *inIterator) const
{
    unsigned int *iteratorP = (unsigned int *) inIterator;

    *iteratorP = 0;
    return true;
}

bool OSOrderedSet::
getNextObjectForIterator(void *inIterator, OSObject **ret) const
{
    unsigned int *iteratorP = (unsigned int *) inIterator;
    unsigned int index = (*iteratorP)++;

    if (index < count)
        *ret = const_cast<OSObject *>((const OSObject *) array[index].obj);
    else
        *ret = 0;

    return (*ret != 0);
}


unsigned OSOrderedSet::setOptions(unsigned options, unsigned mask, void *)
{
    unsigned old = super::setOptions(options, mask);
    if ((old ^ options) & mask) {

	// Value changed need to recurse over all of the child collections
	for ( unsigned i = 0; i < count; i++ ) {
	    OSCollection *coll = OSDynamicCast(OSCollection, array[i].obj);
	    if (coll)
		coll->setOptions(options, mask);
	}
    }

    return old;
}

OSCollection * OSOrderedSet::copyCollection(OSDictionary *cycleDict)
{
    bool allocDict = !cycleDict;
    OSCollection *ret = 0;
    OSOrderedSet *newSet = 0;

    if (allocDict) {
	cycleDict = OSDictionary::withCapacity(16);
	if (!cycleDict)
	    return 0;
    }

    do {
	// Check for a cycle
	ret = super::copyCollection(cycleDict);
	if (ret)
	    continue;
	
	// Duplicate the set with no contents
	newSet = OSOrderedSet::withCapacity(capacity, ordering, orderingRef);
	if (!newSet)
	    continue;

	// Insert object into cycle Dictionary
	cycleDict->setObject((const OSSymbol *) this, newSet);

	newSet->capacityIncrement = capacityIncrement;

	// Now copy over the contents to the new duplicate
	for (unsigned int i = 0; i < count; i++) {
	    OSObject *obj = EXT_CAST(array[i].obj);
	    OSCollection *coll = OSDynamicCast(OSCollection, obj);
	    if (coll) {
		OSCollection *newColl = coll->copyCollection(cycleDict);
		if (newColl) {
		    obj = newColl;	// Rely on cycleDict ref for a bit
		    newColl->release();
		}
		else
		    goto abortCopy;
	    };
	    newSet->setLastObject(obj);
	};

	ret = newSet;
	newSet = 0;

    } while (false);

abortCopy:
    if (newSet)
	newSet->release();

    if (allocDict)
	cycleDict->release();

    return ret;
}
Commit	Line	Data
1c79356b A	1	/*
	2	* Copyright (c) 2000 Apple Computer, Inc. All rights reserved.
	3	*
2d21ac55	4	* @APPLE_OSREFERENCE_LICENSE_HEADER_START@
1c79356b	5	*
2d21ac55 A	6	* This file contains Original Code and/or Modifications of Original Code
	7	* as defined in and that are subject to the Apple Public Source License
	8	* Version 2.0 (the 'License'). You may not use this file except in
	9	* compliance with the License. The rights granted to you under the License
	10	* may not be used to create, or enable the creation or redistribution of,
	11	* unlawful or unlicensed copies of an Apple operating system, or to
	12	* circumvent, violate, or enable the circumvention or violation of, any
	13	* terms of an Apple operating system software license agreement.
8f6c56a5	14	*
2d21ac55 A	15	* Please obtain a copy of the License at
	16	* http://www.opensource.apple.com/apsl/ and read it before using this file.
	17	*
	18	* The Original Code and all software distributed under the License are
	19	* distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
8f6c56a5 A	20	* EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
8f6c56a5 A	21	* INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
2d21ac55 A	22	* FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
	23	* Please see the License for the specific language governing rights and
	24	* limitations under the License.
8f6c56a5	25	*
2d21ac55	26	* @APPLE_OSREFERENCE_LICENSE_HEADER_END@
1c79356b A	27	*/
1c79356b A	28
91447636	29	#include <libkern/c++/OSDictionary.h>
1c79356b A	30	#include <libkern/c++/OSOrderedSet.h>
	31	#include <libkern/c++/OSLib.h>
	32
	33	#define super OSCollection
	34
	35	OSDefineMetaClassAndStructors(OSOrderedSet, OSCollection)
	36	OSMetaClassDefineReservedUnused(OSOrderedSet, 0);
	37	OSMetaClassDefineReservedUnused(OSOrderedSet, 1);
	38	OSMetaClassDefineReservedUnused(OSOrderedSet, 2);
	39	OSMetaClassDefineReservedUnused(OSOrderedSet, 3);
	40	OSMetaClassDefineReservedUnused(OSOrderedSet, 4);
	41	OSMetaClassDefineReservedUnused(OSOrderedSet, 5);
	42	OSMetaClassDefineReservedUnused(OSOrderedSet, 6);
	43	OSMetaClassDefineReservedUnused(OSOrderedSet, 7);
	44
1c79356b A	45
	46	struct _Element {
	47	const OSMetaClassBase * obj;
	48	// unsigned int pri;
	49	};
	50
91447636 A	51	#define EXT_CAST(obj) \
91447636 A	52	reinterpret_cast<OSObject >(const_cast<OSMetaClassBase >(obj))
1c79356b A	53
	54	bool OSOrderedSet::
	55	initWithCapacity(unsigned int inCapacity,
	56	OSOrderFunction inOrdering, void *inOrderingRef)
	57	{
fe8ab488	58	unsigned int size;
1c79356b A	59
	60	if (!super::init())
	61	return false;
	62
fe8ab488 A	63	if (inCapacity > (UINT_MAX / sizeof(_Element)))
	64	return false;
	65
1c79356b	66	size = sizeof(_Element) * inCapacity;
3e170ce0	67	array = (_Element *) kalloc_container(size);
1c79356b A	68	if (!array)
	69	return false;
	70
	71	count = 0;
	72	capacity = inCapacity;
	73	capacityIncrement = (inCapacity)? inCapacity : 16;
	74	ordering = inOrdering;
	75	orderingRef = inOrderingRef;
	76
	77	bzero(array, size);
3e170ce0	78	OSCONTAINER_ACCUMSIZE(size);
1c79356b	79
3e170ce0	80	return true;
1c79356b A	81	}
	82
	83	OSOrderedSet * OSOrderedSet::
	84	withCapacity(unsigned int capacity,
	85	OSOrderFunction ordering, void * orderingRef)
	86	{
	87	OSOrderedSet *me = new OSOrderedSet;
	88
	89	if (me && !me->initWithCapacity(capacity, ordering, orderingRef)) {
55e303ae	90	me->release();
1c79356b A	91	me = 0;
	92	}
	93
	94	return me;
	95	}
	96
	97	void OSOrderedSet::free()
	98	{
91447636	99	(void) super::setOptions(0, kImmutable);
1c79356b A	100	flushCollection();
	101
	102	if (array) {
0c530ab8	103	kfree(array, sizeof(_Element) * capacity);
3e170ce0	104	OSCONTAINER_ACCUMSIZE( -(sizeof(_Element) * capacity) );
1c79356b A	105	}
	106
	107	super::free();
	108	}
	109
	110	unsigned int OSOrderedSet::getCount() const { return count; }
	111	unsigned int OSOrderedSet::getCapacity() const { return capacity; }
	112	unsigned int OSOrderedSet::getCapacityIncrement() const
	113	{ return capacityIncrement; }
	114	unsigned int OSOrderedSet::setCapacityIncrement(unsigned int increment)
	115	{
	116	capacityIncrement = (increment)? increment : 16;
	117	return capacityIncrement;
	118	}
	119
	120	unsigned int OSOrderedSet::ensureCapacity(unsigned int newCapacity)
	121	{
	122	_Element *newArray;
fe8ab488	123	unsigned int finalCapacity, oldSize, newSize;
1c79356b A	124
	125	if (newCapacity <= capacity)
	126	return capacity;
	127
	128	// round up
fe8ab488	129	finalCapacity = (((newCapacity - 1) / capacityIncrement) + 1)
1c79356b	130	* capacityIncrement;
fe8ab488 A	131	if ((finalCapacity < newCapacity) \|\|
	132	(finalCapacity > (UINT_MAX / sizeof(_Element)))) {
	133	return capacity;
	134	}
	135	newSize = sizeof(_Element) * finalCapacity;
1c79356b	136
3e170ce0	137	newArray = (_Element *) kalloc_container(newSize);
1c79356b A	138	if (newArray) {
	139	oldSize = sizeof(_Element) * capacity;
	140
3e170ce0	141	OSCONTAINER_ACCUMSIZE(((size_t)newSize) - ((size_t)oldSize));
1c79356b A	142
	143	bcopy(array, newArray, oldSize);
	144	bzero(&newArray[capacity], newSize - oldSize);
0c530ab8	145	kfree(array, oldSize);
1c79356b	146	array = newArray;
fe8ab488	147	capacity = finalCapacity;
1c79356b A	148	}
	149
	150	return capacity;
	151	}
	152
	153	void OSOrderedSet::flushCollection()
	154	{
	155	unsigned int i;
	156
	157	haveUpdated();
	158
	159	for (i = 0; i < count; i++)
9bccf70c	160	array[i].obj->taggedRelease(OSTypeID(OSCollection));
1c79356b A	161
	162	count = 0;
	163	}
	164
	165	/* internal */
	166	bool OSOrderedSet::setObject(unsigned int index, const OSMetaClassBase *anObject)
	167	{
	168	unsigned int i;
	169	unsigned int newCount = count + 1;
	170
	171	if ((index > count) \|\| !anObject)
	172	return false;
	173
	174	if (containsObject(anObject))
	175	return false;
	176
	177	// do we need more space?
	178	if (newCount > capacity && newCount > ensureCapacity(newCount))
	179	return false;
	180
	181	haveUpdated();
	182	if (index != count) {
	183	for (i = count; i > index; i--)
	184	array[i] = array[i-1];
	185	}
	186	array[index].obj = anObject;
	187	// array[index].pri = pri;
9bccf70c	188	anObject->taggedRetain(OSTypeID(OSCollection));
1c79356b A	189	count++;
	190
	191	return true;
	192	}
	193
	194
	195	bool OSOrderedSet::setFirstObject(const OSMetaClassBase *anObject)
	196	{
	197	return( setObject(0, anObject));
	198	}
	199
	200	bool OSOrderedSet::setLastObject(const OSMetaClassBase *anObject)
	201	{
	202	return( setObject( count, anObject));
	203	}
	204
	205
	206	#define ORDER(obj1,obj2) \
b0d623f7	207	(ordering ? ((ordering)( (const OSObject ) obj1, (const OSObject *) obj2, orderingRef)) : 0)
1c79356b A	208
	209	bool OSOrderedSet::setObject(const OSMetaClassBase *anObject )
	210	{
	211	unsigned int i;
	212
	213	// queue it behind those with same priority
	214	for( i = 0;
	215	(i < count) && (ORDER(array[i].obj, anObject) >= 0);
	216	i++ ) {}
	217
	218	return( setObject(i, anObject));
	219	}
	220
	221	void OSOrderedSet::removeObject(const OSMetaClassBase *anObject)
	222	{
	223	bool deleted = false;
	224	unsigned int i;
	225
	226	for (i = 0; i < count; i++) {
	227
6d2010ae	228	if (deleted)
1c79356b	229	array[i-1] = array[i];
6d2010ae	230	else if (array[i].obj == anObject) {
1c79356b	231	deleted = true;
91447636 A	232	haveUpdated(); // Pity we can't flush the log
91447636 A	233	array[i].obj->taggedRelease(OSTypeID(OSCollection));
1c79356b A	234	}
	235	}
	236
91447636 A	237	if (deleted)
91447636 A	238	count--;
1c79356b A	239	}
	240
	241	bool OSOrderedSet::containsObject(const OSMetaClassBase *anObject) const
	242	{
	243	return anObject && member(anObject);
	244	}
	245
	246	bool OSOrderedSet::member(const OSMetaClassBase *anObject) const
	247	{
	248	unsigned int i;
	249
	250	for( i = 0;
	251	(i < count) && (array[i].obj != anObject);
	252	i++ ) {}
	253
	254	return( i < count);
	255	}
	256
	257	/* internal */
	258	OSObject *OSOrderedSet::getObject( unsigned int index ) const
	259	{
	260	if (index >= count)
	261	return 0;
	262
	263	// if( pri)
	264	// *pri = array[index].pri;
	265
b0d623f7	266	return( const_cast<OSObject >((const OSObject ) array[index].obj) );
1c79356b A	267	}
	268
	269	OSObject *OSOrderedSet::getFirstObject() const
	270	{
	271	if( count)
b0d623f7	272	return( const_cast<OSObject >((const OSObject ) array[0].obj) );
1c79356b A	273	else
	274	return( 0 );
	275	}
	276
	277	OSObject *OSOrderedSet::getLastObject() const
	278	{
	279	if( count)
b0d623f7	280	return( const_cast<OSObject >((const OSObject ) array[count-1].obj) );
1c79356b A	281	else
	282	return( 0 );
	283	}
	284
	285	SInt32 OSOrderedSet::orderObject( const OSMetaClassBase * anObject )
	286	{
	287	return( ORDER( anObject, 0 ));
	288	}
	289
	290	void *OSOrderedSet::getOrderingRef()
	291	{
	292	return orderingRef;
	293	}
	294
	295	bool OSOrderedSet::isEqualTo(const OSOrderedSet *anOrderedSet) const
	296	{
	297	unsigned int i;
	298
	299	if ( this == anOrderedSet )
	300	return true;
	301
	302	if ( count != anOrderedSet->getCount() )
	303	return false;
	304
	305	for ( i = 0; i < count; i++ ) {
	306	if ( !array[i].obj->isEqualTo(anOrderedSet->getObject(i)) )
	307	return false;
	308	}
	309
	310	return true;
	311	}
	312
	313	bool OSOrderedSet::isEqualTo(const OSMetaClassBase *anObject) const
	314	{
	315	OSOrderedSet *oSet;
	316
	317	oSet = OSDynamicCast(OSOrderedSet, anObject);
	318	if ( oSet )
	319	return isEqualTo(oSet);
	320	else
	321	return false;
	322	}
	323
	324	unsigned int OSOrderedSet::iteratorSize() const
	325	{
	326	return( sizeof(unsigned int));
	327	}
	328
	329	bool OSOrderedSet::initIterator(void *inIterator) const
	330	{
	331	unsigned int iteratorP = (unsigned int ) inIterator;
	332
	333	*iteratorP = 0;
	334	return true;
	335	}
	336
	337	bool OSOrderedSet::
	338	getNextObjectForIterator(void inIterator, OSObject *ret) const
	339	{
	340	unsigned int iteratorP = (unsigned int ) inIterator;
	341	unsigned int index = (*iteratorP)++;
	342
	343	if (index < count)
b0d623f7	344	ret = const_cast<OSObject >((const OSObject *) array[index].obj);
1c79356b A	345	else
	346	*ret = 0;
	347
	348	return (*ret != 0);
	349	}
	350
91447636 A	351
	352	unsigned OSOrderedSet::setOptions(unsigned options, unsigned mask, void *)
	353	{
	354	unsigned old = super::setOptions(options, mask);
	355	if ((old ^ options) & mask) {
	356
	357	// Value changed need to recurse over all of the child collections
	358	for ( unsigned i = 0; i < count; i++ ) {
	359	OSCollection *coll = OSDynamicCast(OSCollection, array[i].obj);
	360	if (coll)
	361	coll->setOptions(options, mask);
	362	}
	363	}
	364
	365	return old;
	366	}
	367
	368	OSCollection * OSOrderedSet::copyCollection(OSDictionary *cycleDict)
	369	{
	370	bool allocDict = !cycleDict;
	371	OSCollection *ret = 0;
	372	OSOrderedSet *newSet = 0;
	373
	374	if (allocDict) {
	375	cycleDict = OSDictionary::withCapacity(16);
	376	if (!cycleDict)
	377	return 0;
	378	}
	379
	380	do {
	381	// Check for a cycle
	382	ret = super::copyCollection(cycleDict);
	383	if (ret)
	384	continue;
	385
	386	// Duplicate the set with no contents
	387	newSet = OSOrderedSet::withCapacity(capacity, ordering, orderingRef);
	388	if (!newSet)
	389	continue;
	390
	391	// Insert object into cycle Dictionary
	392	cycleDict->setObject((const OSSymbol *) this, newSet);
	393
	394	newSet->capacityIncrement = capacityIncrement;
	395
	396	// Now copy over the contents to the new duplicate
	397	for (unsigned int i = 0; i < count; i++) {
	398	OSObject *obj = EXT_CAST(array[i].obj);
	399	OSCollection *coll = OSDynamicCast(OSCollection, obj);
	400	if (coll) {
	401	OSCollection *newColl = coll->copyCollection(cycleDict);
	402	if (newColl) {
	403	obj = newColl; // Rely on cycleDict ref for a bit
	404	newColl->release();
	405	}
	406	else
	407	goto abortCopy;
	408	};
	409	newSet->setLastObject(obj);
	410	};
	411
	412	ret = newSet;
	413	newSet = 0;
	414
415	} while (false);
416
417	abortCopy:
418	if (newSet)
419	newSet->release();
420
421	if (allocDict)
422	cycleDict->release();
423
424	return ret;
425	}